--------------------------------------------------------------------------------
-- |
-- Module      :  HGeometry.Trie.Binary
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- A Trie type
--
--------------------------------------------------------------------------------
module HGeometry.Trie.Binary
  ( TrieF(Node)
  , BinaryTrie
  , pattern Leaf, pattern LeftNode, pattern RightNode, pattern TwoNode
  , asBinaryTrie

  , AtMostTwoOriented(..)
  ) where


import qualified Data.Foldable as F
import           Data.Functor.Classes
import           HGeometry.Sequence.KV
import           HGeometry.Trie.Type

--------------------------------------------------------------------------------

-- | At most two elements. A one element can either be left or right
data AtMostTwoOriented a = Zero | OneLeft !a | OneRight !a | Two !a !a
  deriving (Int -> AtMostTwoOriented a -> ShowS
[AtMostTwoOriented a] -> ShowS
AtMostTwoOriented a -> String
(Int -> AtMostTwoOriented a -> ShowS)
-> (AtMostTwoOriented a -> String)
-> ([AtMostTwoOriented a] -> ShowS)
-> Show (AtMostTwoOriented a)
forall a. Show a => Int -> AtMostTwoOriented a -> ShowS
forall a. Show a => [AtMostTwoOriented a] -> ShowS
forall a. Show a => AtMostTwoOriented a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> AtMostTwoOriented a -> ShowS
showsPrec :: Int -> AtMostTwoOriented a -> ShowS
$cshow :: forall a. Show a => AtMostTwoOriented a -> String
show :: AtMostTwoOriented a -> String
$cshowList :: forall a. Show a => [AtMostTwoOriented a] -> ShowS
showList :: [AtMostTwoOriented a] -> ShowS
Show,ReadPrec [AtMostTwoOriented a]
ReadPrec (AtMostTwoOriented a)
Int -> ReadS (AtMostTwoOriented a)
ReadS [AtMostTwoOriented a]
(Int -> ReadS (AtMostTwoOriented a))
-> ReadS [AtMostTwoOriented a]
-> ReadPrec (AtMostTwoOriented a)
-> ReadPrec [AtMostTwoOriented a]
-> Read (AtMostTwoOriented a)
forall a. Read a => ReadPrec [AtMostTwoOriented a]
forall a. Read a => ReadPrec (AtMostTwoOriented a)
forall a. Read a => Int -> ReadS (AtMostTwoOriented a)
forall a. Read a => ReadS [AtMostTwoOriented a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
$creadsPrec :: forall a. Read a => Int -> ReadS (AtMostTwoOriented a)
readsPrec :: Int -> ReadS (AtMostTwoOriented a)
$creadList :: forall a. Read a => ReadS [AtMostTwoOriented a]
readList :: ReadS [AtMostTwoOriented a]
$creadPrec :: forall a. Read a => ReadPrec (AtMostTwoOriented a)
readPrec :: ReadPrec (AtMostTwoOriented a)
$creadListPrec :: forall a. Read a => ReadPrec [AtMostTwoOriented a]
readListPrec :: ReadPrec [AtMostTwoOriented a]
Read,AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
(AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> (AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> Eq (AtMostTwoOriented a)
forall a.
Eq a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a.
Eq a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
== :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
$c/= :: forall a.
Eq a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
/= :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
Eq,Eq (AtMostTwoOriented a)
Eq (AtMostTwoOriented a) =>
(AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering)
-> (AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> (AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> (AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> (AtMostTwoOriented a -> AtMostTwoOriented a -> Bool)
-> (AtMostTwoOriented a
    -> AtMostTwoOriented a -> AtMostTwoOriented a)
-> (AtMostTwoOriented a
    -> AtMostTwoOriented a -> AtMostTwoOriented a)
-> Ord (AtMostTwoOriented a)
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering
AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (AtMostTwoOriented a)
forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering
forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
$ccompare :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering
compare :: AtMostTwoOriented a -> AtMostTwoOriented a -> Ordering
$c< :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
< :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
$c<= :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
<= :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
$c> :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
> :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
$c>= :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
>= :: AtMostTwoOriented a -> AtMostTwoOriented a -> Bool
$cmax :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
max :: AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
$cmin :: forall a.
Ord a =>
AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
min :: AtMostTwoOriented a -> AtMostTwoOriented a -> AtMostTwoOriented a
Ord,(forall a b.
 (a -> b) -> AtMostTwoOriented a -> AtMostTwoOriented b)
-> (forall a b. a -> AtMostTwoOriented b -> AtMostTwoOriented a)
-> Functor AtMostTwoOriented
forall a b. a -> AtMostTwoOriented b -> AtMostTwoOriented a
forall a b. (a -> b) -> AtMostTwoOriented a -> AtMostTwoOriented b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> AtMostTwoOriented a -> AtMostTwoOriented b
fmap :: forall a b. (a -> b) -> AtMostTwoOriented a -> AtMostTwoOriented b
$c<$ :: forall a b. a -> AtMostTwoOriented b -> AtMostTwoOriented a
<$ :: forall a b. a -> AtMostTwoOriented b -> AtMostTwoOriented a
Functor,(forall m. Monoid m => AtMostTwoOriented m -> m)
-> (forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m)
-> (forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m)
-> (forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b)
-> (forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b)
-> (forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b)
-> (forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b)
-> (forall a. (a -> a -> a) -> AtMostTwoOriented a -> a)
-> (forall a. (a -> a -> a) -> AtMostTwoOriented a -> a)
-> (forall a. AtMostTwoOriented a -> [a])
-> (forall a. AtMostTwoOriented a -> Bool)
-> (forall a. AtMostTwoOriented a -> Int)
-> (forall a. Eq a => a -> AtMostTwoOriented a -> Bool)
-> (forall a. Ord a => AtMostTwoOriented a -> a)
-> (forall a. Ord a => AtMostTwoOriented a -> a)
-> (forall a. Num a => AtMostTwoOriented a -> a)
-> (forall a. Num a => AtMostTwoOriented a -> a)
-> Foldable AtMostTwoOriented
forall a. Eq a => a -> AtMostTwoOriented a -> Bool
forall a. Num a => AtMostTwoOriented a -> a
forall a. Ord a => AtMostTwoOriented a -> a
forall m. Monoid m => AtMostTwoOriented m -> m
forall a. AtMostTwoOriented a -> Bool
forall a. AtMostTwoOriented a -> Int
forall a. AtMostTwoOriented a -> [a]
forall a. (a -> a -> a) -> AtMostTwoOriented a -> a
forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m
forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b
forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => AtMostTwoOriented m -> m
fold :: forall m. Monoid m => AtMostTwoOriented m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> AtMostTwoOriented a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b
foldr :: forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> AtMostTwoOriented a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b
foldl :: forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> AtMostTwoOriented a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> AtMostTwoOriented a -> a
foldr1 :: forall a. (a -> a -> a) -> AtMostTwoOriented a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> AtMostTwoOriented a -> a
foldl1 :: forall a. (a -> a -> a) -> AtMostTwoOriented a -> a
$ctoList :: forall a. AtMostTwoOriented a -> [a]
toList :: forall a. AtMostTwoOriented a -> [a]
$cnull :: forall a. AtMostTwoOriented a -> Bool
null :: forall a. AtMostTwoOriented a -> Bool
$clength :: forall a. AtMostTwoOriented a -> Int
length :: forall a. AtMostTwoOriented a -> Int
$celem :: forall a. Eq a => a -> AtMostTwoOriented a -> Bool
elem :: forall a. Eq a => a -> AtMostTwoOriented a -> Bool
$cmaximum :: forall a. Ord a => AtMostTwoOriented a -> a
maximum :: forall a. Ord a => AtMostTwoOriented a -> a
$cminimum :: forall a. Ord a => AtMostTwoOriented a -> a
minimum :: forall a. Ord a => AtMostTwoOriented a -> a
$csum :: forall a. Num a => AtMostTwoOriented a -> a
sum :: forall a. Num a => AtMostTwoOriented a -> a
$cproduct :: forall a. Num a => AtMostTwoOriented a -> a
product :: forall a. Num a => AtMostTwoOriented a -> a
Foldable,Functor AtMostTwoOriented
Foldable AtMostTwoOriented
(Functor AtMostTwoOriented, Foldable AtMostTwoOriented) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> AtMostTwoOriented a -> f (AtMostTwoOriented b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    AtMostTwoOriented (f a) -> f (AtMostTwoOriented a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> AtMostTwoOriented a -> m (AtMostTwoOriented b))
-> (forall (m :: * -> *) a.
    Monad m =>
    AtMostTwoOriented (m a) -> m (AtMostTwoOriented a))
-> Traversable AtMostTwoOriented
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
AtMostTwoOriented (m a) -> m (AtMostTwoOriented a)
forall (f :: * -> *) a.
Applicative f =>
AtMostTwoOriented (f a) -> f (AtMostTwoOriented a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> AtMostTwoOriented a -> m (AtMostTwoOriented b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> AtMostTwoOriented a -> f (AtMostTwoOriented b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> AtMostTwoOriented a -> f (AtMostTwoOriented b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> AtMostTwoOriented a -> f (AtMostTwoOriented b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
AtMostTwoOriented (f a) -> f (AtMostTwoOriented a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
AtMostTwoOriented (f a) -> f (AtMostTwoOriented a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> AtMostTwoOriented a -> m (AtMostTwoOriented b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> AtMostTwoOriented a -> m (AtMostTwoOriented b)
$csequence :: forall (m :: * -> *) a.
Monad m =>
AtMostTwoOriented (m a) -> m (AtMostTwoOriented a)
sequence :: forall (m :: * -> *) a.
Monad m =>
AtMostTwoOriented (m a) -> m (AtMostTwoOriented a)
Traversable)

instance Show1 AtMostTwoOriented where
  liftShowsPrec :: forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> AtMostTwoOriented a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
_ Int
d = \case
    AtMostTwoOriented a
Zero ->
      \String
s -> String
s String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"Zero"
    OneLeft a
x ->
      (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith Int -> a -> ShowS
sp String
"OneLeft" Int
d a
x
    OneRight a
x ->
      (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith Int -> a -> ShowS
sp String
"OneRight" Int
d a
x
    Two a
x a
y ->
      (Int -> a -> ShowS)
-> (Int -> a -> ShowS) -> String -> Int -> a -> a -> ShowS
forall a b.
(Int -> a -> ShowS)
-> (Int -> b -> ShowS) -> String -> Int -> a -> b -> ShowS
showsBinaryWith Int -> a -> ShowS
sp Int -> a -> ShowS
sp String
"Two" Int
d a
x a
y

instance Eq1   AtMostTwoOriented where
  liftEq :: forall a b.
(a -> b -> Bool)
-> AtMostTwoOriented a -> AtMostTwoOriented b -> Bool
liftEq a -> b -> Bool
_ AtMostTwoOriented a
Zero         AtMostTwoOriented b
Zero          = Bool
True
  liftEq a -> b -> Bool
f (OneLeft a
x)  (OneLeft b
x')  = a -> b -> Bool
f a
x b
x'
  liftEq a -> b -> Bool
f (OneRight a
x) (OneRight b
x') = a -> b -> Bool
f a
x b
x'
  liftEq a -> b -> Bool
f (Two a
x a
y)    (Two b
x' b
y')   = a -> b -> Bool
f a
x b
x' Bool -> Bool -> Bool
&& a -> b -> Bool
f a
y b
y'
  liftEq a -> b -> Bool
_ AtMostTwoOriented a
_         AtMostTwoOriented b
_                = Bool
False

instance Ord1  AtMostTwoOriented where
  liftCompare :: forall a b.
(a -> b -> Ordering)
-> AtMostTwoOriented a -> AtMostTwoOriented b -> Ordering
liftCompare a -> b -> Ordering
_ AtMostTwoOriented a
Zero          AtMostTwoOriented b
Zero         = Ordering
EQ
  liftCompare a -> b -> Ordering
_ AtMostTwoOriented a
Zero          AtMostTwoOriented b
_            = Ordering
LT

  liftCompare a -> b -> Ordering
_ (OneLeft a
_)   AtMostTwoOriented b
Zero         = Ordering
GT
  liftCompare a -> b -> Ordering
f (OneLeft a
x)   (OneLeft b
x') = a -> b -> Ordering
f a
x b
x'
  liftCompare a -> b -> Ordering
_ (OneLeft a
_)   (OneRight b
_) = Ordering
LT
  liftCompare a -> b -> Ordering
_ (OneLeft a
_)   (Two b
_ b
_)    = Ordering
LT

  liftCompare a -> b -> Ordering
_ (OneRight a
_) AtMostTwoOriented b
Zero          = Ordering
GT
  liftCompare a -> b -> Ordering
_ (OneRight a
_) (OneLeft b
_)   = Ordering
GT
  liftCompare a -> b -> Ordering
f (OneRight a
x) (OneRight b
x') = a -> b -> Ordering
f a
x b
x'
  liftCompare a -> b -> Ordering
_ (OneRight a
_) (Two b
_ b
_)     = Ordering
LT

  liftCompare a -> b -> Ordering
f (Two a
x a
y)    (Two b
x' b
y')   = a -> b -> Ordering
f a
x b
x' Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> a -> b -> Ordering
f a
y b
y'
  liftCompare a -> b -> Ordering
_ AtMostTwoOriented a
_            AtMostTwoOriented b
_             = Ordering
GT


--------------------------------------------------------------------------------

-- | A binary Trie type
type BinaryTrie e v = TrieF (KV AtMostTwoOriented) e v

-- | Pattern match on a leaf node
pattern Leaf   :: v -> BinaryTrie e v
pattern $bLeaf :: forall v e. v -> BinaryTrie e v
$mLeaf :: forall {r} {v} {e}. BinaryTrie e v -> (v -> r) -> ((# #) -> r) -> r
Leaf v = Node v (KV Zero)

-- | Pattern match on a node with one child, namely on the left
pattern LeftNode     :: v -> (e, BinaryTrie e v) -> BinaryTrie e v
pattern $bLeftNode :: forall v e. v -> (e, BinaryTrie e v) -> BinaryTrie e v
$mLeftNode :: forall {r} {v} {e}.
BinaryTrie e v
-> (v -> (e, BinaryTrie e v) -> r) -> ((# #) -> r) -> r
LeftNode v x = Node v (KV (OneLeft x))

-- | Pattern match on a node with one child, namely on the left
pattern RightNode     :: v -> (e, BinaryTrie e v) -> BinaryTrie e v
pattern $bRightNode :: forall v e. v -> (e, BinaryTrie e v) -> BinaryTrie e v
$mRightNode :: forall {r} {v} {e}.
BinaryTrie e v
-> (v -> (e, BinaryTrie e v) -> r) -> ((# #) -> r) -> r
RightNode v x = Node v (KV (OneRight x))


-- | Pattern match on a node with two children
pattern TwoNode      :: v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v
pattern $bTwoNode :: forall v e.
v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v
$mTwoNode :: forall {r} {v} {e}.
BinaryTrie e v
-> (v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> r)
-> ((# #) -> r)
-> r
TwoNode v l r = Node v (KV (Two l r))

{-# COMPLETE Leaf, LeftNode, RightNode, TwoNode #-}

--------------------------------------------------------------------------------

-- | Trie to convert the trie into a binary trie. If we only have one element,
-- we alwasy produce a left node.
asBinaryTrie              :: Traversable f => TrieF (KV f) e v -> Maybe (BinaryTrie e v)
asBinaryTrie :: forall (f :: * -> *) e v.
Traversable f =>
TrieF (KV f) e v -> Maybe (BinaryTrie e v)
asBinaryTrie (Node v
x KV f e (TrieF (KV f) e v)
chs) = (TrieF (KV f) e v -> Maybe (BinaryTrie e v))
-> KV f e (TrieF (KV f) e v) -> Maybe (KV f e (BinaryTrie e v))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> KV f e a -> f (KV f e b)
traverse TrieF (KV f) e v -> Maybe (BinaryTrie e v)
forall (f :: * -> *) e v.
Traversable f =>
TrieF (KV f) e v -> Maybe (BinaryTrie e v)
asBinaryTrie KV f e (TrieF (KV f) e v)
chs Maybe (KV f e (BinaryTrie e v))
-> (KV f e (BinaryTrie e v) -> Maybe (BinaryTrie e v))
-> Maybe (BinaryTrie e v)
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \KV f e (BinaryTrie e v)
res -> case f (e, BinaryTrie e v) -> [(e, BinaryTrie e v)]
forall a. f a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (KV f e (BinaryTrie e v) -> f (e, BinaryTrie e v)
forall (f :: * -> *) k v. Foldable f => KV f k v -> f (k, v)
assocs KV f e (BinaryTrie e v)
res) of
                              []    -> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BinaryTrie e v -> Maybe (BinaryTrie e v))
-> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a b. (a -> b) -> a -> b
$ v -> BinaryTrie e v
forall v e. v -> BinaryTrie e v
Leaf v
x
                              [(e, BinaryTrie e v)
c]   -> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BinaryTrie e v -> Maybe (BinaryTrie e v))
-> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a b. (a -> b) -> a -> b
$ v -> (e, BinaryTrie e v) -> BinaryTrie e v
forall v e. v -> (e, BinaryTrie e v) -> BinaryTrie e v
LeftNode v
x (e, BinaryTrie e v)
c
                              [(e, BinaryTrie e v)
l,(e, BinaryTrie e v)
r] -> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BinaryTrie e v -> Maybe (BinaryTrie e v))
-> BinaryTrie e v -> Maybe (BinaryTrie e v)
forall a b. (a -> b) -> a -> b
$ v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v
forall v e.
v -> (e, BinaryTrie e v) -> (e, BinaryTrie e v) -> BinaryTrie e v
TwoNode v
x (e, BinaryTrie e v)
l (e, BinaryTrie e v)
r
                              [(e, BinaryTrie e v)]
_     -> Maybe (BinaryTrie e v)
forall a. Maybe a
Nothing