-- File created: 2008-11-13 21:13:55

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies
           , FlexibleContexts, Rank2Types #-}

module Data.ListTrie.Base
   ( Trie(..)
   , null, size, size', member, notMember, lookup, lookupWithDefault
   , isSubmapOfBy, isProperSubmapOfBy
   , empty, singleton
   , insert, insert', insertWith, insertWith'
   , delete, adjust, adjust', updateLookup, alter, alter'
   , unionWith, unionWithKey, unionWith', unionWithKey'
   , unionsWith, unionsWithKey, unionsWith', unionsWithKey'
   , differenceWith, differenceWithKey
   , intersectionWith,  intersectionWithKey
   , intersectionWith', intersectionWithKey'
   , filterWithKey, partitionWithKey
   , split, splitLookup
   , mapKeysWith, mapInKeysWith, mapInKeysWith'
   , foldrWithKey,  foldrAscWithKey,  foldrDescWithKey
   , foldlWithKey,  foldlAscWithKey,  foldlDescWithKey
   , foldlWithKey', foldlAscWithKey', foldlDescWithKey'
   , toList, toAscList, toDescList
   , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey'
   , findMin, findMax, deleteMin, deleteMax, minView, maxView
   , findPredecessor, findSuccessor
   , lookupPrefix, addPrefix, deletePrefix, deleteSuffixes
   , splitPrefix, children, children1
   , showTrieWith
   ) where

import Control.Arrow       ((***), first)
import qualified Data.DList as DL
import Data.DList          (DList)
import Data.Foldable       (foldr, foldl')
import Data.List           (partition)
import Data.Maybe          (fromJust)
import Prelude hiding      (lookup, filter, foldr, null)
import qualified Prelude

import qualified Data.ListTrie.Base.Map.Internal as Map
import Data.ListTrie.Base.Classes
   ( Boolable(..)
   , Unwrappable(..)
   , Unionable(..), Differentiable(..), Intersectable(..)
   , Alt(..)
   , fmap', (<$!>)
   )
import Data.ListTrie.Base.Map (Map, OrdMap)
import Data.ListTrie.Util     ((.:), both)

class (Map map k, Functor st, Unwrappable st)
   => Trie trie st map k | trie -> st where

   mkTrie :: st a -> CMap trie map k a -> trie map k a
   tParts :: trie map k a -> (st a, CMap trie map k a)

type CMap trie map k v = map k (trie map k v)

hasValue, noValue :: Boolable b => b -> Bool
hasValue :: forall b. Boolable b => b -> Bool
hasValue = b -> Bool
forall b. Boolable b => b -> Bool
toBool
noValue :: forall b. Boolable b => b -> Bool
noValue  = Bool -> Bool
not (Bool -> Bool) -> (b -> Bool) -> b -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Bool
forall b. Boolable b => b -> Bool
hasValue

tVal :: Trie trie st map k => trie map k a -> st a
tVal :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal = (st a, CMap trie map k a) -> st a
forall a b. (a, b) -> a
fst ((st a, CMap trie map k a) -> st a)
-> (trie map k a -> (st a, CMap trie map k a))
-> trie map k a
-> st a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts

tMap :: Trie trie st map k => trie map k a -> CMap trie map k a
tMap :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap = (st a, CMap trie map k a) -> CMap trie map k a
forall a b. (a, b) -> b
snd ((st a, CMap trie map k a) -> CMap trie map k a)
-> (trie map k a -> (st a, CMap trie map k a))
-> trie map k a
-> CMap trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts

mapVal :: Trie trie st map k => (forall x y. (x -> y) -> x -> y)
                             -> trie map k a
                             -> (st a -> st a)
                             -> trie map k a
mapVal :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> trie map k a -> (st a -> st a) -> trie map k a
mapVal forall x y. (x -> y) -> x -> y
($$) trie map k a
tr st a -> st a
f = (st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie (st a -> CMap trie map k a -> trie map k a)
-> st a -> CMap trie map k a -> trie map k a
forall x y. (x -> y) -> x -> y
$$ (st a -> st a
f (st a -> st a) -> (trie map k a -> st a) -> trie map k a -> st a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal (trie map k a -> st a) -> trie map k a -> st a
forall a b. (a -> b) -> a -> b
$ trie map k a
tr)) (trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr)

mapMap :: (Trie trie st map k1, Trie trie st map k2)
       => (forall x y. (x -> y) -> x -> y)
       -> trie map k1 a
       -> (CMap trie map k1 a -> CMap trie map k2 a)
       -> trie map k2 a
mapMap :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k1 k2 a.
(Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
mapMap forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr CMap trie map k1 a -> CMap trie map k2 a
f = (st a -> CMap trie map k2 a -> trie map k2 a
forall a. st a -> CMap trie map k2 a -> trie map k2 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie (st a -> CMap trie map k2 a -> trie map k2 a)
-> st a -> CMap trie map k2 a -> trie map k2 a
forall x y. (x -> y) -> x -> y
$$ trie map k1 a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k1 a
tr) (CMap trie map k1 a -> CMap trie map k2 a
f (CMap trie map k1 a -> CMap trie map k2 a)
-> (trie map k1 a -> CMap trie map k1 a)
-> trie map k1 a
-> CMap trie map k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k1 a -> CMap trie map k1 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap (trie map k1 a -> CMap trie map k2 a)
-> trie map k1 a -> CMap trie map k2 a
forall a b. (a -> b) -> a -> b
$ trie map k1 a
tr)

onVals :: Trie trie st map k => (forall x y. (x -> y) -> x -> y)
                             -> (st a -> st b -> st c)
                             -> trie map k a
                             -> trie map k b
                             -> st c
onVals :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals forall x y. (x -> y) -> x -> y
($$) st a -> st b -> st c
f trie map k a
a trie map k b
b = st a -> st b -> st c
f (st a -> st b -> st c) -> st a -> st b -> st c
forall x y. (x -> y) -> x -> y
$$ trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
a (st b -> st c) -> st b -> st c
forall x y. (x -> y) -> x -> y
$$ trie map k b -> st b
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k b
b

onMaps :: Trie trie st map k => (forall x y. (x -> y) -> x -> y)
                             -> (  CMap trie map k a
                                -> CMap trie map k b
                                -> CMap trie map k c
                                )
                             -> trie map k a
                             -> trie map k b
                             -> CMap trie map k c
onMaps :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps forall x y. (x -> y) -> x -> y
($$) CMap trie map k a -> CMap trie map k b -> CMap trie map k c
f trie map k a
a trie map k b
b = CMap trie map k a -> CMap trie map k b -> CMap trie map k c
f (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> CMap trie map k a -> CMap trie map k b -> CMap trie map k c
forall x y. (x -> y) -> x -> y
$$ trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
a (CMap trie map k b -> CMap trie map k c)
-> CMap trie map k b -> CMap trie map k c
forall x y. (x -> y) -> x -> y
$$ trie map k b -> CMap trie map k b
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k b
b

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

-- * Construction

-- O(1)
empty :: (Alt st a, Trie trie st map k) => trie map k a
empty :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty = st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty CMap trie map k a
forall a. map k a
forall (m :: * -> * -> *) k a. Map m k => m k a
Map.empty

-- O(s)
singleton :: (Alt st a, Trie trie st map k) => [k] -> a -> trie map k a
singleton :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a
singleton [k]
xs a
v = [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
addPrefix [k]
xs (trie map k a -> trie map k a) -> trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$ st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie (a -> st a
forall a. a -> st a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
v) CMap trie map k a
forall a. map k a
forall (m :: * -> * -> *) k a. Map m k => m k a
Map.empty

-- O(min(m,s))
insert :: (Alt st a, Trie trie st map k)
       => [k] -> a -> trie map k a -> trie map k a
insert :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a -> trie map k a
insert = (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith a -> a -> a
forall a b. a -> b -> a
const

-- O(min(m,s))
insert' :: (Alt st a, Boolable (st a), Trie trie st map k)
        => [k] -> a -> trie map k a -> trie map k a
insert' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> a -> trie map k a -> trie map k a
insert' = (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith' a -> a -> a
forall a b. a -> b -> a
const

-- O(min(m,s))
insertWith :: (Alt st a, Trie trie st map k)
           => (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith = (forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
genericInsertWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) (a -> a) -> st a -> st a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
(<$>)

-- O(min(m,s))
insertWith' :: (Alt st a, Boolable (st a), Trie trie st map k)
            => (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith' = (a -> (trie map k a -> trie map k a) -> trie map k a -> trie map k a
forall a b. a -> b -> b
seq (a
 -> (trie map k a -> trie map k a) -> trie map k a -> trie map k a)
-> (a -> trie map k a -> trie map k a)
-> a
-> trie map k a
-> trie map k a
forall a b. (a -> a -> b) -> (a -> a) -> a -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*>) ((a -> trie map k a -> trie map k a)
 -> a -> trie map k a -> trie map k a)
-> ((a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
genericInsertWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) (a -> a) -> st a -> st a
forall (f :: * -> *) a b.
(Boolable (f a), Unwrappable f, Alt f b) =>
(a -> b) -> f a -> f b
(<$!>)

genericInsertWith :: (Alt st a, Trie trie st map k)
                  => (forall x y. (x -> y) -> x -> y)
                  -> ((a -> a) -> st a -> st a)
                  -> (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
genericInsertWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a -> a)
-> [k]
-> a
-> trie map k a
-> trie map k a
genericInsertWith forall x y. (x -> y) -> x -> y
($$) (a -> a) -> st a -> st a
(<$$>) a -> a -> a
f = [k] -> a -> trie map k a -> trie map k a
forall {trie :: (* -> * -> *) -> * -> * -> *} {map :: * -> * -> *}
       {k1}.
Trie trie st map k1 =>
[k1] -> a -> trie map k1 a -> trie map k1 a
go
 where
   go :: [k1] -> a -> trie map k1 a -> trie map k1 a
go []     a
new trie map k1 a
tr =
      (forall x y. (x -> y) -> x -> y)
-> trie map k1 a -> (st a -> st a) -> trie map k1 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> trie map k a -> (st a -> st a) -> trie map k a
mapVal (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr ((st a -> st a) -> trie map k1 a)
-> (st a -> st a) -> trie map k1 a
forall a b. (a -> b) -> a -> b
$ \st a
old -> (a -> a -> a
f a
new (a -> a) -> st a -> st a
<$$> st a
old) st a -> st a -> st a
forall (a :: * -> *) x. Alt a x => a x -> a x -> a x
<|> a -> st a
forall a. a -> st a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
new

   go (k1
x:[k1]
xs) a
val trie map k1 a
tr = (forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k1 a)
-> trie map k1 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k1 k2 a.
(Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
mapMap (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr ((CMap trie map k1 a -> CMap trie map k1 a) -> trie map k1 a)
-> (CMap trie map k1 a -> CMap trie map k1 a) -> trie map k1 a
forall a b. (a -> b) -> a -> b
$ \CMap trie map k1 a
m ->
      (trie map k1 a -> trie map k1 a -> trie map k1 a)
-> k1 -> trie map k1 a -> CMap trie map k1 a -> CMap trie map k1 a
forall a. (a -> a -> a) -> k1 -> a -> map k1 a -> map k1 a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> k -> a -> m k a -> m k a
Map.insertWith (\trie map k1 a
_ trie map k1 a
old -> [k1] -> a -> trie map k1 a -> trie map k1 a
go [k1]
xs a
val trie map k1 a
old) k1
x ([k1] -> a -> trie map k1 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a
singleton [k1]
xs a
val) CMap trie map k1 a
m

-- O(min(m,s))
delete :: (Alt st a, Boolable (st a), Trie trie st map k)
       => [k] -> trie map k a -> trie map k a
delete :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
delete = (st a -> st a) -> [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(st a -> st a) -> [k] -> trie map k a -> trie map k a
alter (st a -> st a -> st a
forall a b. a -> b -> a
const st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty)

-- O(min(m,s))
adjust :: Trie trie st map k
       => (a -> a) -> [k] -> trie map k a -> trie map k a
adjust :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(a -> a) -> [k] -> trie map k a -> trie map k a
adjust = (forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a)
-> [k]
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a)
-> [k]
-> trie map k a
-> trie map k a
genericAdjust (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) (a -> a) -> st a -> st a
forall a b. (a -> b) -> st a -> st b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- O(min(m,s))
adjust' :: (Alt st a, Boolable (st a), Trie trie st map k)
        => (a -> a) -> [k] -> trie map k a -> trie map k a
adjust' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a) -> [k] -> trie map k a -> trie map k a
adjust' = (forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a)
-> [k]
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a)
-> [k]
-> trie map k a
-> trie map k a
genericAdjust (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) (a -> a) -> st a -> st a
forall (f :: * -> *) a b.
(Boolable (f a), Unwrappable f, Alt f b) =>
(a -> b) -> f a -> f b
fmap'

genericAdjust :: Trie trie st map k
              => (forall x y. (x -> y) -> x -> y)
              -> ((a -> a) -> st a -> st a)
              -> (a -> a) -> [k] -> trie map k a -> trie map k a
genericAdjust :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a) -> st a -> st a)
-> (a -> a)
-> [k]
-> trie map k a
-> trie map k a
genericAdjust forall x y. (x -> y) -> x -> y
($$) (a -> a) -> st a -> st a
(<$$>) a -> a
f = [k] -> trie map k a -> trie map k a
forall {trie :: (* -> * -> *) -> * -> * -> *} {map :: * -> * -> *}
       {k1}.
Trie trie st map k1 =>
[k1] -> trie map k1 a -> trie map k1 a
go
 where
   go :: [k1] -> trie map k1 a -> trie map k1 a
go []     trie map k1 a
tr = (forall x y. (x -> y) -> x -> y)
-> trie map k1 a -> (st a -> st a) -> trie map k1 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> trie map k a -> (st a -> st a) -> trie map k a
mapVal (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr (a -> a
f (a -> a) -> st a -> st a
<$$>)
   go (k1
x:[k1]
xs) trie map k1 a
tr = (forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k1 a)
-> trie map k1 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k1 k2 a.
(Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
mapMap (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr ((trie map k1 a -> trie map k1 a)
-> k1 -> CMap trie map k1 a -> CMap trie map k1 a
forall a. (a -> a) -> k1 -> map k1 a -> map k1 a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a) -> k -> m k a -> m k a
Map.adjust ([k1] -> trie map k1 a -> trie map k1 a
go [k1]
xs) k1
x)

-- O(min(m,s))
updateLookup :: (Alt st a, Boolable (st a), Trie trie st map k)
             => (a -> st a) -> [k] -> trie map k a -> (st a, trie map k a)
updateLookup :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> st a) -> [k] -> trie map k a -> (st a, trie map k a)
updateLookup a -> st a
f = [k] -> trie map k a -> (st a, trie map k a)
forall {trie :: (* -> * -> *) -> * -> * -> *} {map :: * -> * -> *}
       {k}.
Trie trie st map k =>
[k] -> trie map k a -> (st a, trie map k a)
go
 where
   go :: [k] -> trie map k a -> (st a, trie map k a)
go [] trie map k a
tr =
      let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
          v' :: st a
v'    = if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue st a
v then a -> st a
f (st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap st a
v) else st a
v
       in (st a
v, st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v' CMap trie map k a
m)

   go (k
x:[k]
xs) trie map k a
orig =
      let m :: CMap trie map k a
m   = trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
orig
       in case k -> CMap trie map k a -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x CMap trie map k a
m of
               Maybe (trie map k a)
Nothing -> (st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty, trie map k a
orig)
               Just trie map k a
tr ->
                  let (st a
ret, trie map k a
upd) = [k] -> trie map k a -> (st a, trie map k a)
go [k]
xs trie map k a
tr
                   in ( st a
ret
                      , st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie (trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
orig) (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$ if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
upd
                                                then k -> CMap trie map k a -> CMap trie map k a
forall a. k -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> m k a
Map.delete             k
x CMap trie map k a
m
                                                else (trie map k a -> trie map k a)
-> k -> CMap trie map k a -> CMap trie map k a
forall a. (a -> a) -> k -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a) -> k -> m k a -> m k a
Map.adjust (trie map k a -> trie map k a -> trie map k a
forall a b. a -> b -> a
const trie map k a
upd) k
x CMap trie map k a
m
                      )

-- O(min(m,s))
--
-- Lazy in exactly one case: the key is the prefix of another key in the trie.
-- Otherwise we have to test whether the function removed a key or not, lest
-- the trie fall into an invalid state.
alter :: (Alt st a, Boolable (st a), Trie trie st map k)
      => (st a -> st a) -> [k] -> trie map k a -> trie map k a
alter :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(st a -> st a) -> [k] -> trie map k a -> trie map k a
alter = (forall x y. (x -> y) -> x -> y)
-> (st a -> trie map k a -> trie map k a)
-> (st a -> st a)
-> [k]
-> trie map k a
-> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> trie map k a -> trie map k a)
-> (st a -> st a)
-> [k]
-> trie map k a
-> trie map k a
genericAlter (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) ((trie map k a -> st a -> trie map k a)
-> st a -> trie map k a -> trie map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip trie map k a -> st a -> trie map k a
forall a b. a -> b -> a
const)

-- O(min(m,s))
alter' :: (Alt st a, Boolable (st a), Trie trie st map k)
       => (st a -> st a) -> [k] -> trie map k a -> trie map k a
alter' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(st a -> st a) -> [k] -> trie map k a -> trie map k a
alter' = (forall x y. (x -> y) -> x -> y)
-> (st a -> trie map k a -> trie map k a)
-> (st a -> st a)
-> [k]
-> trie map k a
-> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> trie map k a -> trie map k a)
-> (st a -> st a)
-> [k]
-> trie map k a
-> trie map k a
genericAlter (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) st a -> trie map k a -> trie map k a
forall a b. a -> b -> b
seq

genericAlter :: (Alt st a, Boolable (st a), Trie trie st map k)
             => (forall x y. (x -> y) -> x -> y)
             -> (st a -> trie map k a -> trie map k a)
             -> (st a -> st a) -> [k] -> trie map k a -> trie map k a
genericAlter :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> trie map k a -> trie map k a)
-> (st a -> st a)
-> [k]
-> trie map k a
-> trie map k a
genericAlter forall x y. (x -> y) -> x -> y
($$) st a -> trie map k a -> trie map k a
seeq st a -> st a
f = [k] -> trie map k a -> trie map k a
go
 where
   go :: [k] -> trie map k a -> trie map k a
go []     trie map k a
tr =
      let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
          v' :: st a
v'    = st a -> st a
f st a
v
       in st a
v' st a -> trie map k a -> trie map k a
`seeq` st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v' CMap trie map k a
m

   go (k
x:[k]
xs) trie map k a
tr = (forall x y. (x -> y) -> x -> y)
-> trie map k a
-> (CMap trie map k a -> CMap trie map k a)
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k1 k2 a.
(Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
mapMap (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k a
tr ((CMap trie map k a -> CMap trie map k a) -> trie map k a)
-> (CMap trie map k a -> CMap trie map k a) -> trie map k a
forall a b. (a -> b) -> a -> b
$ \CMap trie map k a
m ->
      (Maybe (trie map k a) -> Maybe (trie map k a))
-> k -> CMap trie map k a -> CMap trie map k a
forall a. (Maybe a -> Maybe a) -> k -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(Maybe a -> Maybe a) -> k -> m k a -> m k a
Map.alter (\Maybe (trie map k a)
mold -> case Maybe (trie map k a)
mold of
                               Maybe (trie map k a)
Nothing ->
                                  let v :: st a
v = st a -> st a
f st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty
                                   in if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue st a
v
                                         then trie map k a -> Maybe (trie map k a)
forall a. a -> Maybe a
Just ([k] -> a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a
singleton [k]
xs (st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap st a
v))
                                         else Maybe (trie map k a)
forall a. Maybe a
Nothing
                               Just trie map k a
old ->
                                  let new :: trie map k a
new = [k] -> trie map k a -> trie map k a
go [k]
xs trie map k a
old
                                   in if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
new then Maybe (trie map k a)
forall a. Maybe a
Nothing else trie map k a -> Maybe (trie map k a)
forall a. a -> Maybe a
Just trie map k a
new)
                 k
x CMap trie map k a
m

-- * Querying

-- O(1)
--
-- Test the strict field last for maximal laziness
null :: (Boolable (st a), Trie trie st map k) => trie map k a -> Bool
null :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr = map k (trie map k a) -> Bool
forall a. map k a -> Bool
forall (m :: * -> * -> *) k a. Map m k => m k a -> Bool
Map.null (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr) Bool -> Bool -> Bool
&& (st a -> Bool
forall b. Boolable b => b -> Bool
noValue(st a -> Bool) -> (trie map k a -> st a) -> trie map k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal (trie map k a -> Bool) -> trie map k a -> Bool
forall a b. (a -> b) -> a -> b
$ trie map k a
tr)

-- O(n m)
size :: (Boolable (st a), Trie trie st map k, Num n) => trie map k a -> n
size :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
size  trie map k a
tr = (trie map k a -> n -> n) -> n -> map k (trie map k a) -> n
forall a b. (a -> b -> b) -> b -> map k a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr  (n -> n -> n
forall a. Num a => a -> a -> a
(+) (n -> n -> n) -> (trie map k a -> n) -> trie map k a -> n -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
size)  (if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue (trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
tr) then n
1 else n
0) (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr)

-- O(n m)
size' :: (Boolable (st a), Trie trie st map k, Num n) => trie map k a -> n
size' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
size' trie map k a
tr = (n -> trie map k a -> n) -> n -> map k (trie map k a) -> n
forall b a. (b -> a -> b) -> b -> map k a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((trie map k a -> n -> n) -> n -> trie map k a -> n
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((trie map k a -> n -> n) -> n -> trie map k a -> n)
-> (trie map k a -> n -> n) -> n -> trie map k a -> n
forall a b. (a -> b) -> a -> b
$ n -> n -> n
forall a. Num a => a -> a -> a
(+) (n -> n -> n) -> (trie map k a -> n) -> trie map k a -> n -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
size')
                  (if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue (trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
tr) then n
1 else n
0)
                  (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr)

-- O(min(m,s))
member :: (Alt st a, Boolable (st a), Trie trie st map k)
       => [k] -> trie map k a -> Bool
member :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
member = st a -> Bool
forall b. Boolable b => b -> Bool
hasValue (st a -> Bool)
-> ([k] -> trie map k a -> st a) -> [k] -> trie map k a -> Bool
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [k] -> trie map k a -> st a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> st a
lookup

-- O(min(m,s))
notMember :: (Alt st a, Boolable (st a), Trie trie st map k)
          => [k] -> trie map k a -> Bool
notMember :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
notMember = Bool -> Bool
not (Bool -> Bool)
-> ([k] -> trie map k a -> Bool) -> [k] -> trie map k a -> Bool
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [k] -> trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
member

-- O(min(m,s))
lookup :: (Alt st a, Trie trie st map k) => [k] -> trie map k a -> st a
lookup :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> st a
lookup []     trie map k a
tr = trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
tr
lookup (k
x:[k]
xs) trie map k a
tr = st a -> (trie map k a -> st a) -> Maybe (trie map k a) -> st a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty ([k] -> trie map k a -> st a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> st a
lookup [k]
xs) (k -> map k (trie map k a) -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr))

-- O(min(m,s))
lookupWithDefault :: (Alt st a, Trie trie st map k)
                  => a -> [k] -> trie map k a -> a
lookupWithDefault :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
a -> [k] -> trie map k a -> a
lookupWithDefault a
def [k]
k trie map k a
tr = st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap (st a -> a) -> st a -> a
forall a b. (a -> b) -> a -> b
$ [k] -> trie map k a -> st a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> st a
lookup [k]
k trie map k a
tr st a -> st a -> st a
forall (a :: * -> *) x. Alt a x => a x -> a x -> a x
<|> a -> st a
forall a. a -> st a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
def

-- O(min(n1 m1,n2 m2))
isSubmapOfBy :: (Boolable (st a), Boolable (st b), Trie trie st map k)
             => (a -> b -> Bool)
             -> trie map k a
             -> trie map k b
             -> Bool
isSubmapOfBy :: forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Boolable (st b), Trie trie st map k) =>
(a -> b -> Bool) -> trie map k a -> trie map k b -> Bool
isSubmapOfBy a -> b -> Bool
f = trie map k a -> trie map k b -> Bool
forall {trie :: (* -> * -> *) -> * -> * -> *} {w :: * -> *}
       {m :: * -> * -> *} {k} {trie :: (* -> * -> *) -> * -> * -> *}
       {w :: * -> *}.
(Trie trie w m k, Trie trie w m k, Boolable (w b),
 Boolable (w a)) =>
trie m k a -> trie m k b -> Bool
go
 where
   go :: trie m k a -> trie m k b -> Bool
go trie m k a
tr1 trie m k b
tr2 =
      let (w a
v1,CMap trie m k a
m1) = trie m k a -> (w a, CMap trie m k a)
forall a. trie m k a -> (w a, CMap trie m k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie m k a
tr1
          (w b
v2,CMap trie m k b
m2) = trie m k b -> (w b, CMap trie m k b)
forall a. trie m k a -> (w a, CMap trie m k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie m k b
tr2
          hv1 :: Bool
hv1     = w a -> Bool
forall b. Boolable b => b -> Bool
hasValue w a
v1
          hv2 :: Bool
hv2     = w b -> Bool
forall b. Boolable b => b -> Bool
hasValue w b
v2
       in [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ Bool -> Bool
not (Bool
hv1 Bool -> Bool -> Bool
&& Bool -> Bool
not Bool
hv2)
              , (Bool -> Bool
not Bool
hv1 Bool -> Bool -> Bool
&& Bool -> Bool
not Bool
hv2) Bool -> Bool -> Bool
|| a -> b -> Bool
f (w a -> a
forall a. w a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap w a
v1) (w b -> b
forall a. w a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap w b
v2)
              , (trie m k a -> trie m k b -> Bool)
-> CMap trie m k a -> CMap trie m k b -> Bool
forall a b. (a -> b -> Bool) -> m k a -> m k b -> Bool
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b -> Bool) -> m k a -> m k b -> Bool
Map.isSubmapOfBy trie m k a -> trie m k b -> Bool
go CMap trie m k a
m1 CMap trie m k b
m2
              ]

-- O(min(n1 m1,n2 m2))
isProperSubmapOfBy :: (Boolable (st a), Boolable (st b), Trie trie st map k)
                   => (a -> b -> Bool)
                   -> trie map k a
                   -> trie map k b
                   -> Bool
isProperSubmapOfBy :: forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Boolable (st b), Trie trie st map k) =>
(a -> b -> Bool) -> trie map k a -> trie map k b -> Bool
isProperSubmapOfBy a -> b -> Bool
f = Bool -> trie map k a -> trie map k b -> Bool
forall {trie :: (* -> * -> *) -> * -> * -> *} {w :: * -> *}
       {m :: * -> * -> *} {k} {trie :: (* -> * -> *) -> * -> * -> *}
       {w :: * -> *}.
(Trie trie w m k, Trie trie w m k, Boolable (w a),
 Boolable (w b)) =>
Bool -> trie m k a -> trie m k b -> Bool
go Bool
False
 where
   go :: Bool -> trie m k a -> trie m k b -> Bool
go Bool
proper trie m k a
tr1 trie m k b
tr2 =
      let (w a
v1,CMap trie m k a
m1) = trie m k a -> (w a, CMap trie m k a)
forall a. trie m k a -> (w a, CMap trie m k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie m k a
tr1
          (w b
v2,CMap trie m k b
m2) = trie m k b -> (w b, CMap trie m k b)
forall a. trie m k a -> (w a, CMap trie m k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie m k b
tr2
          hv1 :: Bool
hv1     = w a -> Bool
forall b. Boolable b => b -> Bool
hasValue w a
v1
          hv2 :: Bool
hv2     = w b -> Bool
forall b. Boolable b => b -> Bool
hasValue w b
v2
          -- This seems suboptimal but I can't think of anything better
          proper' :: Bool
proper' = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
or [ Bool
proper
                       , w a -> Bool
forall b. Boolable b => b -> Bool
noValue w a
v1 Bool -> Bool -> Bool
&& w b -> Bool
forall b. Boolable b => b -> Bool
hasValue w b
v2
                       , Bool -> Bool
not (CMap trie m k b -> Bool
forall a. m k a -> Bool
forall (m :: * -> * -> *) k a. Map m k => m k a -> Bool
Map.null (CMap trie m k b -> Bool) -> CMap trie m k b -> Bool
forall a b. (a -> b) -> a -> b
$ CMap trie m k b -> CMap trie m k a -> CMap trie m k b
forall (m :: * -> * -> *) k a b. Map m k => m k a -> m k b -> m k a
Map.difference CMap trie m k b
m2 CMap trie m k a
m1)
                       ]
       in [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and [ Bool -> Bool
not (Bool
hv1 Bool -> Bool -> Bool
&& Bool -> Bool
not Bool
hv2)
              , (Bool -> Bool
not Bool
hv1 Bool -> Bool -> Bool
&& Bool -> Bool
not Bool
hv2) Bool -> Bool -> Bool
|| a -> b -> Bool
f (w a -> a
forall a. w a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap w a
v1) (w b -> b
forall a. w a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap w b
v2)
              , if CMap trie m k a -> Bool
forall a. m k a -> Bool
forall (m :: * -> * -> *) k a. Map m k => m k a -> Bool
Map.null CMap trie m k a
m1
                   then Bool
proper'
                   else (trie m k a -> trie m k b -> Bool)
-> CMap trie m k a -> CMap trie m k b -> Bool
forall a b. (a -> b -> Bool) -> m k a -> m k b -> Bool
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b -> Bool) -> m k a -> m k b -> Bool
Map.isSubmapOfBy (Bool -> trie m k a -> trie m k b -> Bool
go Bool
proper') CMap trie m k a
m1 CMap trie m k b
m2
              ]


-- * Combination

-- O(min(n1 m1,n2 m2))
unionWith :: (Unionable st a, Trie trie st map k)
          => (a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith a -> a -> a
f = (forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> trie map k a
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) ((a -> a -> a) -> st a -> st a -> st a
forall (v :: * -> *) a.
Unionable v a =>
(a -> a -> a) -> v a -> v a -> v a
unionVals a -> a -> a
f) ((trie map k a -> st a -> trie map k a)
-> st a -> trie map k a -> trie map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip trie map k a -> st a -> trie map k a
forall a b. a -> b -> a
const)

-- O(min(n1 m1,n2 m2))
unionWith' :: (Unionable st a, Trie trie st map k)
          => (a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith' a -> a -> a
f = (forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> trie map k a
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((a -> a -> a) -> st a -> st a -> st a
forall (v :: * -> *) a.
Unionable v a =>
(a -> a -> a) -> v a -> v a -> v a
unionVals' a -> a -> a
f) st a -> trie map k a -> trie map k a
forall a b. a -> b -> b
seq

genericUnionWith :: Trie trie st map k
                 => (forall x y. (x -> y) -> x -> y)
                 -> (st a -> st a -> st a)
                 -> (st a -> trie map k a -> trie map k a)
                 -> trie map k a
                 -> trie map k a
                 -> trie map k a
genericUnionWith :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWith forall x y. (x -> y) -> x -> y
($$) st a -> st a -> st a
valUnion st a -> trie map k a -> trie map k a
seeq = trie map k a -> trie map k a -> trie map k a
go
 where
   go :: trie map k a -> trie map k a -> trie map k a
go trie map k a
tr1 trie map k a
tr2 =
      let v :: st a
v = (forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a) -> trie map k a -> trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) st a -> st a -> st a
valUnion trie map k a
tr1 trie map k a
tr2
       in st a
v st a -> trie map k a -> trie map k a
`seeq` (st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$ (forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k a -> CMap trie map k a)
-> trie map k a
-> trie map k a
-> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((trie map k a -> trie map k a -> trie map k a)
-> CMap trie map k a -> CMap trie map k a -> CMap trie map k a
forall a. (a -> a -> a) -> map k a -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> m k a -> m k a -> m k a
Map.unionWith trie map k a -> trie map k a -> trie map k a
go) trie map k a
tr1 trie map k a
tr2)

-- O(min(n1 m1,n2 m2))
unionWithKey :: (Unionable st a, Trie trie st map k) => ([k] -> a -> a -> a)
                                                     -> trie map k a
                                                     -> trie map k a
                                                     -> trie map k a
unionWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
unionWithKey = (forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a) -> st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> ([k] -> a -> a -> a)
-> trie map k a
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a) -> st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> ([k] -> a -> a -> a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWithKey (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) (a -> a -> a) -> st a -> st a -> st a
forall (v :: * -> *) a.
Unionable v a =>
(a -> a -> a) -> v a -> v a -> v a
unionVals ((trie map k a -> st a -> trie map k a)
-> st a -> trie map k a -> trie map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip trie map k a -> st a -> trie map k a
forall a b. a -> b -> a
const)

-- O(min(n1 m1,n2 m2))
unionWithKey' :: (Unionable st a, Trie trie st map k) => ([k] -> a -> a -> a)
                                                      -> trie map k a
                                                      -> trie map k a
                                                      -> trie map k a
unionWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
unionWithKey' = (forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a) -> st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> ([k] -> a -> a -> a)
-> trie map k a
-> trie map k a
-> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a) -> st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> ([k] -> a -> a -> a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWithKey (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) (a -> a -> a) -> st a -> st a -> st a
forall (v :: * -> *) a.
Unionable v a =>
(a -> a -> a) -> v a -> v a -> v a
unionVals' st a -> trie map k a -> trie map k a
forall a b. a -> b -> b
seq

genericUnionWithKey :: Trie trie st map k
                    => (forall x y. (x -> y) -> x -> y)
                    -> ((a -> a -> a) -> st a -> st a -> st a)
                    -> (st a -> trie map k a -> trie map k a)
                    -> ([k] -> a -> a -> a)
                    -> trie map k a
                    -> trie map k a
                    -> trie map k a
genericUnionWithKey :: forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a) -> st a -> st a -> st a)
-> (st a -> trie map k a -> trie map k a)
-> ([k] -> a -> a -> a)
-> trie map k a
-> trie map k a
-> trie map k a
genericUnionWithKey forall x y. (x -> y) -> x -> y
($$) (a -> a -> a) -> st a -> st a -> st a
valUnion st a -> trie map k a -> trie map k a
seeq [k] -> a -> a -> a
f = DList k -> trie map k a -> trie map k a -> trie map k a
go DList k
forall a. DList a
DL.empty
 where
   go :: DList k -> trie map k a -> trie map k a -> trie map k a
go DList k
k trie map k a
tr1 trie map k a
tr2 =
      let v :: st a
v = (forall x y. (x -> y) -> x -> y)
-> (st a -> st a -> st a) -> trie map k a -> trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((a -> a -> a) -> st a -> st a -> st a
valUnion ([k] -> a -> a -> a
f ([k] -> a -> a -> a) -> [k] -> a -> a -> a
forall a b. (a -> b) -> a -> b
$ DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
k)) trie map k a
tr1 trie map k a
tr2
       in st a
v st a -> trie map k a -> trie map k a
`seeq` (st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$
                       (forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k a -> CMap trie map k a)
-> trie map k a
-> trie map k a
-> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((k -> trie map k a -> trie map k a -> trie map k a)
-> CMap trie map k a -> CMap trie map k a -> CMap trie map k a
forall a. (k -> a -> a -> a) -> map k a -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(k -> a -> a -> a) -> m k a -> m k a -> m k a
Map.unionWithKey ((k -> trie map k a -> trie map k a -> trie map k a)
 -> CMap trie map k a -> CMap trie map k a -> CMap trie map k a)
-> (k -> trie map k a -> trie map k a -> trie map k a)
-> CMap trie map k a
-> CMap trie map k a
-> CMap trie map k a
forall a b. (a -> b) -> a -> b
$ DList k -> trie map k a -> trie map k a -> trie map k a
go (DList k -> trie map k a -> trie map k a -> trie map k a)
-> (k -> DList k)
-> k
-> trie map k a
-> trie map k a
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (DList k
k DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc`))
                              trie map k a
tr1 trie map k a
tr2)

-- O(sum(n))
unionsWith :: (Alt st a, Unionable st a, Trie trie st map k)
           => (a -> a -> a) -> [trie map k a] -> trie map k a
unionsWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> [trie map k a] -> trie map k a
unionsWith a -> a -> a
f = (trie map k a -> trie map k a -> trie map k a)
-> trie map k a -> [trie map k a] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith a -> a -> a
f) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(sum(n))
unionsWith' :: (Alt st a, Unionable st a, Trie trie st map k)
            => (a -> a -> a) -> [trie map k a] -> trie map k a
unionsWith' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> [trie map k a] -> trie map k a
unionsWith' a -> a -> a
f = (trie map k a -> trie map k a -> trie map k a)
-> trie map k a -> [trie map k a] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith' a -> a -> a
f) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(sum(n))
unionsWithKey :: (Alt st a, Unionable st a, Trie trie st map k)
              => ([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
unionsWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
unionsWithKey [k] -> a -> a -> a
j = (trie map k a -> trie map k a -> trie map k a)
-> trie map k a -> [trie map k a] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
unionWithKey [k] -> a -> a -> a
j) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(sum(n))
unionsWithKey' :: (Alt st a, Unionable st a, Trie trie st map k)
               => ([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
unionsWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
unionsWithKey' [k] -> a -> a -> a
j = (trie map k a -> trie map k a -> trie map k a)
-> trie map k a -> [trie map k a] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
unionWithKey' [k] -> a -> a -> a
j) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(min(n1 m1,n2 m2))
differenceWith :: (Boolable (st a), Differentiable st a b, Trie trie st map k)
               => (a -> b -> Maybe a)
               -> trie map k a
               -> trie map k b
               -> trie map k a
differenceWith :: forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Differentiable st a b, Trie trie st map k) =>
(a -> b -> Maybe a) -> trie map k a -> trie map k b -> trie map k a
differenceWith a -> b -> Maybe a
f = trie map k a -> trie map k b -> trie map k a
forall {st :: * -> *} {trie :: (* -> * -> *) -> * -> * -> *}
       {map :: * -> * -> *} {k}.
(Boolable (st a), Trie trie st map k, Differentiable st a b) =>
trie map k a -> trie map k b -> trie map k a
go
 where
   go :: trie map k a -> trie map k b -> trie map k a
go trie map k a
tr1 trie map k b
tr2 =
      let v :: st a
v = (forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st a) -> trie map k a -> trie map k b -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((a -> b -> Maybe a) -> st a -> st b -> st a
forall (v :: * -> *) a b.
Differentiable v a b =>
(a -> b -> Maybe a) -> v a -> v b -> v a
differenceVals a -> b -> Maybe a
f) trie map k a
tr1 trie map k b
tr2

          -- This would be lazy only in the case where the differing keys were at
          -- []. (And even then most operations on the trie would force the
          -- value.) For consistency with other keys and Patricia, just seq it for
          -- that case as well.
       in st a
v st a -> trie map k a -> trie map k a
forall a b. a -> b -> b
`seq` st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$ (forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k a)
-> trie map k a
-> trie map k b
-> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((trie map k a -> trie map k b -> Maybe (trie map k a))
-> CMap trie map k a -> CMap trie map k b -> CMap trie map k a
forall a b. (a -> b -> Maybe a) -> map k a -> map k b -> map k a
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b -> Maybe a) -> m k a -> m k b -> m k a
Map.differenceWith trie map k a -> trie map k b -> Maybe (trie map k a)
g) trie map k a
tr1 trie map k b
tr2

   g :: trie map k a -> trie map k b -> Maybe (trie map k a)
g trie map k a
t1 trie map k b
t2 = let t' :: trie map k a
t' = trie map k a -> trie map k b -> trie map k a
go trie map k a
t1 trie map k b
t2
              in if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
t' then Maybe (trie map k a)
forall a. Maybe a
Nothing else trie map k a -> Maybe (trie map k a)
forall a. a -> Maybe a
Just trie map k a
t'

-- O(min(n1 m1,n2 m2))
differenceWithKey :: ( Boolable (st a), Differentiable st a b
                     , Trie trie st map k
                     )
                  => ([k] -> a -> b -> Maybe a)
                  -> trie map k a
                  -> trie map k b
                  -> trie map k a
differenceWithKey :: forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Differentiable st a b, Trie trie st map k) =>
([k] -> a -> b -> Maybe a)
-> trie map k a -> trie map k b -> trie map k a
differenceWithKey [k] -> a -> b -> Maybe a
f = DList k -> trie map k a -> trie map k b -> trie map k a
forall {st :: * -> *} {trie :: (* -> * -> *) -> * -> * -> *}
       {map :: * -> * -> *}.
(Boolable (st a), Trie trie st map k, Differentiable st a b) =>
DList k -> trie map k a -> trie map k b -> trie map k a
go DList k
forall a. DList a
DL.empty
 where
   go :: DList k -> trie map k a -> trie map k b -> trie map k a
go DList k
k trie map k a
tr1 trie map k b
tr2 =
      let v :: st a
v = (forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st a) -> trie map k a -> trie map k b -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((a -> b -> Maybe a) -> st a -> st b -> st a
forall (v :: * -> *) a b.
Differentiable v a b =>
(a -> b -> Maybe a) -> v a -> v b -> v a
differenceVals ([k] -> a -> b -> Maybe a
f ([k] -> a -> b -> Maybe a) -> [k] -> a -> b -> Maybe a
forall a b. (a -> b) -> a -> b
$ DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
k)) trie map k a
tr1 trie map k b
tr2

          -- see comment in differenceWith for seq explanation
       in st a
v st a -> trie map k a -> trie map k a
forall a b. a -> b -> b
`seq` st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$
                     (forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k a)
-> trie map k a
-> trie map k b
-> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((k -> trie map k a -> trie map k b -> Maybe (trie map k a))
-> CMap trie map k a -> CMap trie map k b -> CMap trie map k a
forall a b.
(k -> a -> b -> Maybe a) -> map k a -> map k b -> map k a
forall (m :: * -> * -> *) k a b.
Map m k =>
(k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a
Map.differenceWithKey (DList k
-> k -> trie map k a -> trie map k b -> Maybe (trie map k a)
g DList k
k)) trie map k a
tr1 trie map k b
tr2

   g :: DList k
-> k -> trie map k a -> trie map k b -> Maybe (trie map k a)
g DList k
k k
x trie map k a
t1 trie map k b
t2 = let t' :: trie map k a
t' = DList k -> trie map k a -> trie map k b -> trie map k a
go (DList k
k DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc` k
x) trie map k a
t1 trie map k b
t2
                  in if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
t' then Maybe (trie map k a)
forall a. Maybe a
Nothing else trie map k a -> Maybe (trie map k a)
forall a. a -> Maybe a
Just trie map k a
t'

-- O(min(n1 m1,n2 m2))
intersectionWith :: ( Boolable (st c), Intersectable st a b c
                    , Trie trie st map k
                    )
                 => (a -> b -> c)
                 -> trie map k a
                 -> trie map k b
                 -> trie map k c
intersectionWith :: forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
(a -> b -> c) -> trie map k a -> trie map k b -> trie map k c
intersectionWith a -> b -> c
f = (forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> trie map k a
-> trie map k b
-> trie map k c
forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) ((a -> b -> c) -> st a -> st b -> st c
forall (v :: * -> *) a b c.
Intersectable v a b c =>
(a -> b -> c) -> v a -> v b -> v c
intersectionVals a -> b -> c
f) ((trie map k c -> st c -> trie map k c)
-> st c -> trie map k c -> trie map k c
forall a b c. (a -> b -> c) -> b -> a -> c
flip trie map k c -> st c -> trie map k c
forall a b. a -> b -> a
const)

-- O(min(n1 m1,n2 m2))
intersectionWith' :: ( Boolable (st c), Intersectable st a b c
                     , Trie trie st map k
                     )
                  => (a -> b -> c)
                  -> trie map k a
                  -> trie map k b
                  -> trie map k c
intersectionWith' :: forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
(a -> b -> c) -> trie map k a -> trie map k b -> trie map k c
intersectionWith' a -> b -> c
f = (forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> trie map k a
-> trie map k b
-> trie map k c
forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) ((a -> b -> c) -> st a -> st b -> st c
forall (v :: * -> *) a b c.
Intersectable v a b c =>
(a -> b -> c) -> v a -> v b -> v c
intersectionVals' a -> b -> c
f) st c -> trie map k c -> trie map k c
forall a b. a -> b -> b
seq

genericIntersectionWith :: (Boolable (st c), Trie trie st map k)
                        => (forall x y. (x -> y) -> x -> y)
                        -> (st a -> st b -> st c)
                        -> (st c -> trie map k c -> trie map k c)
                        -> trie map k a
                        -> trie map k b
                        -> trie map k c
genericIntersectionWith :: forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWith forall x y. (x -> y) -> x -> y
($$) st a -> st b -> st c
valIntersection st c -> trie map k c -> trie map k c
seeq = trie map k a -> trie map k b -> trie map k c
go
 where
   go :: trie map k a -> trie map k b -> trie map k c
go trie map k a
tr1 trie map k b
tr2 =
      (st c -> trie map k c -> trie map k c)
-> st c -> map k (trie map k c) -> trie map k c
forall {map :: * -> * -> *} {k} {st :: * -> *} {a}
       {trie :: (* -> * -> *) -> * -> * -> *} {t}.
(Boolable (st a), Trie trie st map k) =>
(st a -> trie map k a -> t) -> st a -> map k (trie map k a) -> t
tr st c -> trie map k c -> trie map k c
seeq
         ((forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) st a -> st b -> st c
valIntersection trie map k a
tr1 trie map k b
tr2)
         ((forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> map k (trie map k c))
-> trie map k a
-> trie map k b
-> map k (trie map k c)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((trie map k c -> Bool)
-> map k (trie map k c) -> map k (trie map k c)
forall a. (a -> Bool) -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> Bool) -> m k a -> m k a
Map.filter (Bool -> Bool
not(Bool -> Bool) -> (trie map k c -> Bool) -> trie map k c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.trie map k c -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null) (map k (trie map k c) -> map k (trie map k c))
-> (CMap trie map k a -> CMap trie map k b -> map k (trie map k c))
-> CMap trie map k a
-> CMap trie map k b
-> map k (trie map k c)
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (trie map k a -> trie map k b -> trie map k c)
-> CMap trie map k a -> CMap trie map k b -> map k (trie map k c)
forall a b c. (a -> b -> c) -> map k a -> map k b -> map k c
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> b -> c) -> m k a -> m k b -> m k c
Map.intersectionWith trie map k a -> trie map k b -> trie map k c
go)
                 trie map k a
tr1 trie map k b
tr2)

   tr :: (st a -> trie map k a -> t) -> st a -> map k (trie map k a) -> t
tr st a -> trie map k a -> t
seeq' st a
v map k (trie map k a)
m =
      st a
v st a -> trie map k a -> t
`seeq'` (st a -> map k (trie map k a) -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (map k (trie map k a) -> trie map k a)
-> map k (trie map k a) -> trie map k a
forall a b. (a -> b) -> a -> b
$
                    case map k (trie map k a) -> Maybe (k, trie map k a)
forall a. map k a -> Maybe (k, a)
forall (m :: * -> * -> *) k a. Map m k => m k a -> Maybe (k, a)
Map.singletonView map k (trie map k a)
m of
                         Just (k
_, trie map k a
child) | trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
child -> trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
child
                         Maybe (k, trie map k a)
_                            -> map k (trie map k a)
m)

-- O(min(n1 m1,n2 m2))
intersectionWithKey :: ( Boolable (st c), Intersectable st a b c
                       , Trie trie st map k
                       )
                    => ([k] -> a -> b -> c)
                    -> trie map k a
                    -> trie map k b
                    -> trie map k c
intersectionWithKey :: forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
([k] -> a -> b -> c)
-> trie map k a -> trie map k b -> trie map k c
intersectionWithKey =
   (forall x y. (x -> y) -> x -> y)
-> ((a -> b -> c) -> st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> ([k] -> a -> b -> c)
-> trie map k a
-> trie map k b
-> trie map k c
forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> b -> c) -> st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> ([k] -> a -> b -> c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWithKey (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) (a -> b -> c) -> st a -> st b -> st c
forall (v :: * -> *) a b c.
Intersectable v a b c =>
(a -> b -> c) -> v a -> v b -> v c
intersectionVals ((trie map k c -> st c -> trie map k c)
-> st c -> trie map k c -> trie map k c
forall a b c. (a -> b -> c) -> b -> a -> c
flip trie map k c -> st c -> trie map k c
forall a b. a -> b -> a
const)

-- O(min(n1 m1,n2 m2))
intersectionWithKey' :: ( Boolable (st c), Intersectable st a b c
                        , Trie trie st map k
                        )
                     => ([k] -> a -> b -> c)
                     -> trie map k a
                     -> trie map k b
                     -> trie map k c
intersectionWithKey' :: forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
([k] -> a -> b -> c)
-> trie map k a -> trie map k b -> trie map k c
intersectionWithKey' = (forall x y. (x -> y) -> x -> y)
-> ((a -> b -> c) -> st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> ([k] -> a -> b -> c)
-> trie map k a
-> trie map k b
-> trie map k c
forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> b -> c) -> st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> ([k] -> a -> b -> c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWithKey (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) (a -> b -> c) -> st a -> st b -> st c
forall (v :: * -> *) a b c.
Intersectable v a b c =>
(a -> b -> c) -> v a -> v b -> v c
intersectionVals' st c -> trie map k c -> trie map k c
forall a b. a -> b -> b
seq

genericIntersectionWithKey :: (Boolable (st c), Trie trie st map k)
                           => (forall x y. (x -> y) -> x -> y)
                           -> ((a -> b -> c) -> st a -> st b -> st c)
                           -> (st c -> trie map k c -> trie map k c)
                           -> ([k] -> a -> b -> c)
                           -> trie map k a
                           -> trie map k b
                           -> trie map k c
genericIntersectionWithKey :: forall (st :: * -> *) c (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k a b.
(Boolable (st c), Trie trie st map k) =>
(forall x y. (x -> y) -> x -> y)
-> ((a -> b -> c) -> st a -> st b -> st c)
-> (st c -> trie map k c -> trie map k c)
-> ([k] -> a -> b -> c)
-> trie map k a
-> trie map k b
-> trie map k c
genericIntersectionWithKey forall x y. (x -> y) -> x -> y
($$) (a -> b -> c) -> st a -> st b -> st c
valIntersection st c -> trie map k c -> trie map k c
seeq [k] -> a -> b -> c
f = DList k -> trie map k a -> trie map k b -> trie map k c
go DList k
forall a. DList a
DL.empty
 where
   go :: DList k -> trie map k a -> trie map k b -> trie map k c
go DList k
k trie map k a
tr1 trie map k b
tr2 =
      st c -> map k (trie map k c) -> trie map k c
tr
         ((forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (st a -> st b -> st c) -> trie map k a -> trie map k b -> st c
onVals (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((a -> b -> c) -> st a -> st b -> st c
valIntersection ([k] -> a -> b -> c
f ([k] -> a -> b -> c) -> [k] -> a -> b -> c
forall a b. (a -> b) -> a -> b
$ DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
k)) trie map k a
tr1 trie map k b
tr2)
         ((forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> map k (trie map k c))
-> trie map k a
-> trie map k b
-> map k (trie map k c)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a b c.
Trie trie st map k =>
(forall x y. (x -> y) -> x -> y)
-> (CMap trie map k a -> CMap trie map k b -> CMap trie map k c)
-> trie map k a
-> trie map k b
-> CMap trie map k c
onMaps (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) ((trie map k c -> Bool)
-> map k (trie map k c) -> map k (trie map k c)
forall a. (a -> Bool) -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> Bool) -> m k a -> m k a
Map.filter (Bool -> Bool
not(Bool -> Bool) -> (trie map k c -> Bool) -> trie map k c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.trie map k c -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null) (map k (trie map k c) -> map k (trie map k c))
-> (CMap trie map k a -> CMap trie map k b -> map k (trie map k c))
-> CMap trie map k a
-> CMap trie map k b
-> map k (trie map k c)
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.:
                          (k -> trie map k a -> trie map k b -> trie map k c)
-> CMap trie map k a -> CMap trie map k b -> map k (trie map k c)
forall a b c. (k -> a -> b -> c) -> map k a -> map k b -> map k c
forall (m :: * -> * -> *) k a b c.
Map m k =>
(k -> a -> b -> c) -> m k a -> m k b -> m k c
Map.intersectionWithKey (DList k -> trie map k a -> trie map k b -> trie map k c
go (DList k -> trie map k a -> trie map k b -> trie map k c)
-> (k -> DList k)
-> k
-> trie map k a
-> trie map k b
-> trie map k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (DList k
k DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc`)))
                 trie map k a
tr1 trie map k b
tr2)

   tr :: st c -> map k (trie map k c) -> trie map k c
tr st c
v map k (trie map k c)
m =
      st c
v st c -> trie map k c -> trie map k c
`seeq` (st c -> map k (trie map k c) -> trie map k c
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st c
v (map k (trie map k c) -> trie map k c)
-> map k (trie map k c) -> trie map k c
forall a b. (a -> b) -> a -> b
$
                   case map k (trie map k c) -> Maybe (k, trie map k c)
forall a. map k a -> Maybe (k, a)
forall (m :: * -> * -> *) k a. Map m k => m k a -> Maybe (k, a)
Map.singletonView map k (trie map k c)
m of
                        Just (k
_, trie map k c
child) | trie map k c -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k c
child -> trie map k c -> map k (trie map k c)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k c
child
                        Maybe (k, trie map k c)
_                            -> map k (trie map k c)
m)

-- * Filtering

-- O(n m)
filterWithKey :: (Alt st a, Boolable (st a), Trie trie st map k)
              => ([k] -> a -> Bool) -> trie map k a -> trie map k a
filterWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> Bool) -> trie map k a -> trie map k a
filterWithKey [k] -> a -> Bool
p = [([k], a)] -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
fromList ([([k], a)] -> trie map k a)
-> (trie map k a -> [([k], a)]) -> trie map k a -> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (([k], a) -> Bool) -> [([k], a)] -> [([k], a)]
forall a. (a -> Bool) -> [a] -> [a]
Prelude.filter (([k] -> a -> Bool) -> ([k], a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> Bool
p) ([([k], a)] -> [([k], a)])
-> (trie map k a -> [([k], a)]) -> trie map k a -> [([k], a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- O(n m)
partitionWithKey :: (Alt st a, Boolable (st a), Trie trie st map k)
                 => ([k] -> a -> Bool)
                 -> trie map k a
                 -> (trie map k a, trie map k a)
partitionWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> Bool) -> trie map k a -> (trie map k a, trie map k a)
partitionWithKey [k] -> a -> Bool
p = ([([k], a)] -> trie map k a)
-> ([([k], a)], [([k], a)]) -> (trie map k a, trie map k a)
forall a b. (a -> b) -> (a, a) -> (b, b)
both [([k], a)] -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
fromList (([([k], a)], [([k], a)]) -> (trie map k a, trie map k a))
-> (trie map k a -> ([([k], a)], [([k], a)]))
-> trie map k a
-> (trie map k a, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (([k], a) -> Bool) -> [([k], a)] -> ([([k], a)], [([k], a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (([k] -> a -> Bool) -> ([k], a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> Bool
p) ([([k], a)] -> ([([k], a)], [([k], a)]))
-> (trie map k a -> [([k], a)])
-> trie map k a
-> ([([k], a)], [([k], a)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- * Mapping

-- O(n m)
mapKeysWith :: (Boolable (st a), Trie trie st map k1, Trie trie st map k2)
            => ([([k2],a)] -> trie map k2 a)
            -> ([k1] -> [k2])
            -> trie map k1 a
            -> trie map k2 a
mapKeysWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Boolable (st a), Trie trie st map k1, Trie trie st map k2) =>
([([k2], a)] -> trie map k2 a)
-> ([k1] -> [k2]) -> trie map k1 a -> trie map k2 a
mapKeysWith [([k2], a)] -> trie map k2 a
fromlist [k1] -> [k2]
f = [([k2], a)] -> trie map k2 a
fromlist ([([k2], a)] -> trie map k2 a)
-> (trie map k1 a -> [([k2], a)]) -> trie map k1 a -> trie map k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (([k1], a) -> ([k2], a)) -> [([k1], a)] -> [([k2], a)]
forall a b. (a -> b) -> [a] -> [b]
map (([k1] -> [k2]) -> ([k1], a) -> ([k2], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first [k1] -> [k2]
f) ([([k1], a)] -> [([k2], a)])
-> (trie map k1 a -> [([k1], a)]) -> trie map k1 a -> [([k2], a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k1 a -> [([k1], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- O(n m)
mapInKeysWith :: (Unionable st a, Trie trie st map k1, Trie trie st map k2)
              => (a -> a -> a)
              -> (k1 -> k2)
              -> trie map k1 a
              -> trie map k2 a
mapInKeysWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(a -> a -> a) -> (k1 -> k2) -> trie map k1 a -> trie map k2 a
mapInKeysWith = (forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a)
    -> trie map k2 a -> trie map k2 a -> trie map k2 a)
-> (a -> a -> a)
-> (k1 -> k2)
-> trie map k1 a
-> trie map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2 f.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> (f -> trie map k2 a -> trie map k2 a -> trie map k2 a)
-> f
-> (k1 -> k2)
-> trie map k1 a
-> trie map k2 a
genericMapInKeysWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($) (a -> a -> a) -> trie map k2 a -> trie map k2 a -> trie map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith

-- O(n m)
mapInKeysWith' :: (Unionable st a, Trie trie st map k1, Trie trie st map k2)
               => (a -> a -> a)
               -> (k1 -> k2)
               -> trie map k1 a
               -> trie map k2 a
mapInKeysWith' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(a -> a -> a) -> (k1 -> k2) -> trie map k1 a -> trie map k2 a
mapInKeysWith' = (forall x y. (x -> y) -> x -> y)
-> ((a -> a -> a)
    -> trie map k2 a -> trie map k2 a -> trie map k2 a)
-> (a -> a -> a)
-> (k1 -> k2)
-> trie map k1 a
-> trie map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2 f.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> (f -> trie map k2 a -> trie map k2 a -> trie map k2 a)
-> f
-> (k1 -> k2)
-> trie map k1 a
-> trie map k2 a
genericMapInKeysWith (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
forall a b. (a -> b) -> a -> b
($!) (a -> a -> a) -> trie map k2 a -> trie map k2 a -> trie map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
unionWith'

genericMapInKeysWith :: ( Unionable st a
                        , Trie trie st map k1, Trie trie st map k2
                        )
                     => (forall x y. (x -> y) -> x -> y)
                     -> (f -> trie map k2 a -> trie map k2 a -> trie map k2 a)
                     -> f
                     -> (k1 -> k2)
                     -> trie map k1 a
                     -> trie map k2 a
genericMapInKeysWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2 f.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> (f -> trie map k2 a -> trie map k2 a -> trie map k2 a)
-> f
-> (k1 -> k2)
-> trie map k1 a
-> trie map k2 a
genericMapInKeysWith forall x y. (x -> y) -> x -> y
($$) f -> trie map k2 a -> trie map k2 a -> trie map k2 a
unionW f
j k1 -> k2
f = trie map k1 a -> trie map k2 a
go
 where
   go :: trie map k1 a -> trie map k2 a
go trie map k1 a
tr = (forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k1 k2 a.
(Trie trie st map k1, Trie trie st map k2) =>
(forall x y. (x -> y) -> x -> y)
-> trie map k1 a
-> (CMap trie map k1 a -> CMap trie map k2 a)
-> trie map k2 a
mapMap (x -> y) -> x -> y
forall x y. (x -> y) -> x -> y
($$) trie map k1 a
tr ((CMap trie map k1 a -> CMap trie map k2 a) -> trie map k2 a)
-> (CMap trie map k1 a -> CMap trie map k2 a) -> trie map k2 a
forall a b. (a -> b) -> a -> b
$
              (trie map k2 a -> trie map k2 a -> trie map k2 a)
-> [(k2, trie map k2 a)] -> CMap trie map k2 a
forall a. (a -> a -> a) -> [(k2, a)] -> map k2 a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> [(k, a)] -> m k a
Map.fromListKVWith (f -> trie map k2 a -> trie map k2 a -> trie map k2 a
unionW f
j) ([(k2, trie map k2 a)] -> CMap trie map k2 a)
-> (CMap trie map k1 a -> [(k2, trie map k2 a)])
-> CMap trie map k1 a
-> CMap trie map k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1, trie map k1 a) -> (k2, trie map k2 a))
-> [(k1, trie map k1 a)] -> [(k2, trie map k2 a)]
forall a b. (a -> b) -> [a] -> [b]
map (k1 -> k2
f (k1 -> k2)
-> (trie map k1 a -> trie map k2 a)
-> (k1, trie map k1 a)
-> (k2, trie map k2 a)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** trie map k1 a -> trie map k2 a
go) ([(k1, trie map k1 a)] -> [(k2, trie map k2 a)])
-> (CMap trie map k1 a -> [(k1, trie map k1 a)])
-> CMap trie map k1 a
-> [(k2, trie map k2 a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k1 a -> [(k1, trie map k1 a)]
forall a. map k1 a -> [(k1, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
Map.toListKV

-- * Folding

-- O(n m)
foldrWithKey :: (Boolable (st a), Trie trie st map k)
             => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrWithKey [k] -> a -> b -> b
f b
x = (([k], a) -> b -> b) -> b -> [([k], a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- O(n m)
foldrAscWithKey :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrAscWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrAscWithKey [k] -> a -> b -> b
f b
x = (([k], a) -> b -> b) -> b -> [([k], a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toAscList

-- O(n m)
foldrDescWithKey :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                 => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrDescWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldrDescWithKey [k] -> a -> b -> b
f b
x = (([k], a) -> b -> b) -> b -> [([k], a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toDescList

-- O(n m)
foldlWithKey :: (Boolable (st a), Trie trie st map k)
             => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlWithKey [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- O(n m)
foldlAscWithKey :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlAscWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlAscWithKey [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toAscList

-- O(n m)
foldlDescWithKey :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                 => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlDescWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlDescWithKey [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toDescList

-- O(n m)
foldlWithKey' :: (Boolable (st a), Trie trie st map k)
              => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlWithKey' [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList

-- O(n m)
foldlAscWithKey' :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                 => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlAscWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlAscWithKey' [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toAscList

-- O(n m)
foldlDescWithKey' :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                  => ([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlDescWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
foldlDescWithKey' [k] -> a -> b -> b
f b
x = (b -> ([k], a) -> b) -> b -> [([k], a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> b -> b) -> b -> ([k], a) -> b)
-> (([k], a) -> b -> b) -> b -> ([k], a) -> b
forall a b. (a -> b) -> a -> b
$ ([k] -> a -> b -> b) -> ([k], a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> b -> b
f) b
x ([([k], a)] -> b)
-> (trie map k a -> [([k], a)]) -> trie map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toDescList

-- * Conversion between lists

-- O(n m)
toList :: (Boolable (st a), Trie trie st map k) => trie map k a -> [([k],a)]
toList :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
toList = (CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
genericToList CMap trie map k a -> [(k, trie map k a)]
forall a. map k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
Map.toListKV ([k], a) -> DList ([k], a) -> DList ([k], a)
forall a. a -> DList a -> DList a
DL.cons

-- O(n m)
toAscList :: (Boolable (st a), Trie trie st map k, OrdMap map k)
          => trie map k a -> [([k],a)]
toAscList :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toAscList = (CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
genericToList CMap trie map k a -> [(k, trie map k a)]
forall a. map k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
Map.toAscList ([k], a) -> DList ([k], a) -> DList ([k], a)
forall a. a -> DList a -> DList a
DL.cons

-- O(n m)
toDescList :: (Boolable (st a), Trie trie st map k, OrdMap map k)
           => trie map k a -> [([k],a)]
toDescList :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
toDescList = (CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
genericToList ([(k, trie map k a)] -> [(k, trie map k a)]
forall a. [a] -> [a]
reverse ([(k, trie map k a)] -> [(k, trie map k a)])
-> (CMap trie map k a -> [(k, trie map k a)])
-> CMap trie map k a
-> [(k, trie map k a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> [(k, trie map k a)]
forall a. map k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
Map.toAscList) ((DList ([k], a) -> ([k], a) -> DList ([k], a))
-> ([k], a) -> DList ([k], a) -> DList ([k], a)
forall a b c. (a -> b -> c) -> b -> a -> c
flip DList ([k], a) -> ([k], a) -> DList ([k], a)
forall a. DList a -> a -> DList a
DL.snoc)

genericToList :: (Boolable (st a), Trie trie st map k)
              => (CMap trie map k a -> [(k, trie map k a)])
              -> (([k],a) -> DList ([k],a) -> DList ([k],a))
              -> trie map k a
              -> [([k],a)]
genericToList :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(CMap trie map k a -> [(k, trie map k a)])
-> (([k], a) -> DList ([k], a) -> DList ([k], a))
-> trie map k a
-> [([k], a)]
genericToList CMap trie map k a -> [(k, trie map k a)]
tolist ([k], a) -> DList ([k], a) -> DList ([k], a)
add = DList ([k], a) -> [([k], a)]
forall a. DList a -> [a]
DL.toList (DList ([k], a) -> [([k], a)])
-> (trie map k a -> DList ([k], a)) -> trie map k a -> [([k], a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DList k -> trie map k a -> DList ([k], a)
go DList k
forall a. DList a
DL.empty
 where
   go :: DList k -> trie map k a -> DList ([k], a)
go DList k
xs trie map k a
tr =
      let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
          xs' :: DList ([k], a)
xs'   =
             [DList ([k], a)] -> DList ([k], a)
forall a. [DList a] -> DList a
DL.concat ([DList ([k], a)] -> DList ([k], a))
-> (CMap trie map k a -> [DList ([k], a)])
-> CMap trie map k a
-> DList ([k], a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             ((k, trie map k a) -> DList ([k], a))
-> [(k, trie map k a)] -> [DList ([k], a)]
forall a b. (a -> b) -> [a] -> [b]
map (\(k
x,trie map k a
t) -> DList k -> trie map k a -> DList ([k], a)
go (DList k
xs DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc` k
x) trie map k a
t) ([(k, trie map k a)] -> [DList ([k], a)])
-> (CMap trie map k a -> [(k, trie map k a)])
-> CMap trie map k a
-> [DList ([k], a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             CMap trie map k a -> [(k, trie map k a)]
tolist (CMap trie map k a -> DList ([k], a))
-> CMap trie map k a -> DList ([k], a)
forall a b. (a -> b) -> a -> b
$ CMap trie map k a
m
       in if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue st a
v
             then ([k], a) -> DList ([k], a) -> DList ([k], a)
add (DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
xs, st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap st a
v) DList ([k], a)
xs'
             else                              DList ([k], a)
xs'

-- O(n m)
fromList :: (Alt st a, Trie trie st map k) => [([k],a)] -> trie map k a
fromList :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
fromList = (a -> a -> a) -> [([k], a)] -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [([k], a)] -> trie map k a
fromListWith a -> a -> a
forall a b. a -> b -> a
const

-- O(n m)
fromListWith :: (Alt st a, Trie trie st map k)
             => (a -> a -> a) -> [([k],a)] -> trie map k a
fromListWith :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [([k], a)] -> trie map k a
fromListWith a -> a -> a
f = (trie map k a -> ([k], a) -> trie map k a)
-> trie map k a -> [([k], a)] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((([k], a) -> trie map k a -> trie map k a)
-> trie map k a -> ([k], a) -> trie map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> trie map k a -> trie map k a)
 -> trie map k a -> ([k], a) -> trie map k a)
-> (([k] -> a -> trie map k a -> trie map k a)
    -> ([k], a) -> trie map k a -> trie map k a)
-> ([k] -> a -> trie map k a -> trie map k a)
-> trie map k a
-> ([k], a)
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([k] -> a -> trie map k a -> trie map k a)
-> ([k], a) -> trie map k a -> trie map k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (([k] -> a -> trie map k a -> trie map k a)
 -> trie map k a -> ([k], a) -> trie map k a)
-> ([k] -> a -> trie map k a -> trie map k a)
-> trie map k a
-> ([k], a)
-> trie map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith a -> a -> a
f) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(n m)
fromListWith' :: (Alt st a, Boolable (st a), Trie trie st map k)
              => (a -> a -> a) -> [([k],a)] -> trie map k a
fromListWith' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [([k], a)] -> trie map k a
fromListWith' a -> a -> a
f = (trie map k a -> ([k], a) -> trie map k a)
-> trie map k a -> [([k], a)] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((([k], a) -> trie map k a -> trie map k a)
-> trie map k a -> ([k], a) -> trie map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((([k], a) -> trie map k a -> trie map k a)
 -> trie map k a -> ([k], a) -> trie map k a)
-> (([k] -> a -> trie map k a -> trie map k a)
    -> ([k], a) -> trie map k a -> trie map k a)
-> ([k] -> a -> trie map k a -> trie map k a)
-> trie map k a
-> ([k], a)
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([k] -> a -> trie map k a -> trie map k a)
-> ([k], a) -> trie map k a -> trie map k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (([k] -> a -> trie map k a -> trie map k a)
 -> trie map k a -> ([k], a) -> trie map k a)
-> ([k] -> a -> trie map k a -> trie map k a)
-> trie map k a
-> ([k], a)
-> trie map k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith' a -> a -> a
f) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(n m)
fromListWithKey :: (Alt st a, Trie trie st map k)
                => ([k] -> a -> a -> a) -> [([k],a)] -> trie map k a
fromListWithKey :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [([k], a)] -> trie map k a
fromListWithKey [k] -> a -> a -> a
f = (trie map k a -> ([k], a) -> trie map k a)
-> trie map k a -> [([k], a)] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\trie map k a
tr ([k]
k,a
v) -> (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith ([k] -> a -> a -> a
f [k]
k) [k]
k a
v trie map k a
tr) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- O(n m)
fromListWithKey' :: (Alt st a, Boolable (st a), Trie trie st map k)
                 => ([k] -> a -> a -> a) -> [([k],a)] -> trie map k a
fromListWithKey' :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> a -> a) -> [([k], a)] -> trie map k a
fromListWithKey' [k] -> a -> a -> a
f = (trie map k a -> ([k], a) -> trie map k a)
-> trie map k a -> [([k], a)] -> trie map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\trie map k a
tr ([k]
k,a
v) -> (a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
insertWith' ([k] -> a -> a -> a
f [k]
k) [k]
k a
v trie map k a
tr) trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty

-- * Min/max

-- O(m)
minView :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
        => trie map k a -> (Maybe ([k], a), trie map k a)
minView :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
minView = (trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (Maybe ([k], a), trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (Maybe ([k], a), trie map k a)
minMaxView (st a -> Bool
forall b. Boolable b => b -> Bool
hasValue (st a -> Bool) -> (trie map k a -> st a) -> trie map k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal) ((Maybe (k, trie map k a), CMap trie map k a)
-> Maybe (k, trie map k a)
forall a b. (a, b) -> a
fst ((Maybe (k, trie map k a), CMap trie map k a)
 -> Maybe (k, trie map k a))
-> (CMap trie map k a
    -> (Maybe (k, trie map k a), CMap trie map k a))
-> CMap trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> (Maybe (k, trie map k a), CMap trie map k a)
forall a. map k a -> (Maybe (k, a), map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
Map.minViewWithKey)

-- O(m)
maxView :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
        => trie map k a -> (Maybe ([k], a), trie map k a)
maxView :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
maxView = (trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (Maybe ([k], a), trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (Maybe ([k], a), trie map k a)
minMaxView (CMap trie map k a -> Bool
forall a. map k a -> Bool
forall (m :: * -> * -> *) k a. Map m k => m k a -> Bool
Map.null (CMap trie map k a -> Bool)
-> (trie map k a -> CMap trie map k a) -> trie map k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap) ((Maybe (k, trie map k a), CMap trie map k a)
-> Maybe (k, trie map k a)
forall a b. (a, b) -> a
fst ((Maybe (k, trie map k a), CMap trie map k a)
 -> Maybe (k, trie map k a))
-> (CMap trie map k a
    -> (Maybe (k, trie map k a), CMap trie map k a))
-> CMap trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> (Maybe (k, trie map k a), CMap trie map k a)
forall a. map k a -> (Maybe (k, a), map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
Map.maxViewWithKey)

minMaxView :: (Alt st a, Boolable (st a), Trie trie st map k)
           => (trie map k a -> Bool)
           -> (CMap trie map k a -> Maybe (k, trie map k a))
           -> trie map k a
           -> (Maybe ([k], a), trie map k a)
minMaxView :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (Maybe ([k], a), trie map k a)
minMaxView trie map k a -> Bool
_        CMap trie map k a -> Maybe (k, trie map k a)
_       trie map k a
tr_ | trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr_ = (Maybe ([k], a)
forall a. Maybe a
Nothing, trie map k a
tr_)
minMaxView trie map k a -> Bool
isWanted CMap trie map k a -> Maybe (k, trie map k a)
mapView trie map k a
tr_ = (([k], a) -> Maybe ([k], a))
-> (([k], a), trie map k a) -> (Maybe ([k], a), trie map k a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first ([k], a) -> Maybe ([k], a)
forall a. a -> Maybe a
Just (trie map k a -> (([k], a), trie map k a)
go trie map k a
tr_)
 where
   go :: trie map k a -> (([k], a), trie map k a)
go trie map k a
tr =
      let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
       in if trie map k a -> Bool
isWanted trie map k a
tr
             then (([], st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap st a
v), st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty CMap trie map k a
m)
             else let (k
k,      trie map k a
tr')  = Maybe (k, trie map k a) -> (k, trie map k a)
forall a. HasCallStack => Maybe a -> a
fromJust (CMap trie map k a -> Maybe (k, trie map k a)
mapView CMap trie map k a
m)
                      (([k], a)
minMax, trie map k a
tr'') = trie map k a -> (([k], a), trie map k a)
go trie map k a
tr'
                   in ( ([k] -> [k]) -> ([k], a) -> ([k], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:) ([k], a)
minMax
                      , st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (CMap trie map k a -> trie map k a)
-> CMap trie map k a -> trie map k a
forall a b. (a -> b) -> a -> b
$ if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr''
                                      then k -> CMap trie map k a -> CMap trie map k a
forall a. k -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> m k a
Map.delete              k
k CMap trie map k a
m
                                      else (trie map k a -> trie map k a)
-> k -> CMap trie map k a -> CMap trie map k a
forall a. (a -> a) -> k -> map k a -> map k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a) -> k -> m k a -> m k a
Map.adjust (trie map k a -> trie map k a -> trie map k a
forall a b. a -> b -> a
const trie map k a
tr'') k
k CMap trie map k a
m
                      )

-- O(m)
findMin :: (Boolable (st a), Trie trie st map k, OrdMap map k)
        => trie map k a -> Maybe ([k], a)
findMin :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
findMin = (trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> Maybe ([k], a)
findMinMax (st a -> Bool
forall b. Boolable b => b -> Bool
hasValue (st a -> Bool) -> (trie map k a -> st a) -> trie map k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal) ((Maybe (k, trie map k a), CMap trie map k a)
-> Maybe (k, trie map k a)
forall a b. (a, b) -> a
fst ((Maybe (k, trie map k a), CMap trie map k a)
 -> Maybe (k, trie map k a))
-> (CMap trie map k a
    -> (Maybe (k, trie map k a), CMap trie map k a))
-> CMap trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> (Maybe (k, trie map k a), CMap trie map k a)
forall a. map k a -> (Maybe (k, a), map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
Map.minViewWithKey)

-- O(m)
findMax :: (Boolable (st a), Trie trie st map k, OrdMap map k)
        => trie map k a -> Maybe ([k], a)
findMax :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
findMax = (trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> Maybe ([k], a)
findMinMax (CMap trie map k a -> Bool
forall a. map k a -> Bool
forall (m :: * -> * -> *) k a. Map m k => m k a -> Bool
Map.null (CMap trie map k a -> Bool)
-> (trie map k a -> CMap trie map k a) -> trie map k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap) ((Maybe (k, trie map k a), CMap trie map k a)
-> Maybe (k, trie map k a)
forall a b. (a, b) -> a
fst ((Maybe (k, trie map k a), CMap trie map k a)
 -> Maybe (k, trie map k a))
-> (CMap trie map k a
    -> (Maybe (k, trie map k a), CMap trie map k a))
-> CMap trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> (Maybe (k, trie map k a), CMap trie map k a)
forall a. map k a -> (Maybe (k, a), map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
Map.maxViewWithKey)

findMinMax :: (Boolable (st a), Trie trie st map k)
           => (trie map k a -> Bool)
           -> (CMap trie map k a -> Maybe (k, trie map k a))
           -> trie map k a
           -> Maybe ([k], a)
findMinMax :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
(trie map k a -> Bool)
-> (CMap trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> Maybe ([k], a)
findMinMax trie map k a -> Bool
_        CMap trie map k a -> Maybe (k, trie map k a)
_       trie map k a
tr_ | trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr_ = Maybe ([k], a)
forall a. Maybe a
Nothing
findMinMax trie map k a -> Bool
isWanted CMap trie map k a -> Maybe (k, trie map k a)
mapView trie map k a
tr_ = ([k], a) -> Maybe ([k], a)
forall a. a -> Maybe a
Just (DList k -> trie map k a -> ([k], a)
go DList k
forall a. DList a
DL.empty trie map k a
tr_)
 where
   go :: DList k -> trie map k a -> ([k], a)
go DList k
xs trie map k a
tr =
      if trie map k a -> Bool
isWanted trie map k a
tr
         then (DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
xs, st a -> a
forall a. st a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap (trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
tr))
         else let (k
k, trie map k a
tr') = Maybe (k, trie map k a) -> (k, trie map k a)
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe (k, trie map k a) -> (k, trie map k a))
-> (trie map k a -> Maybe (k, trie map k a))
-> trie map k a
-> (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap trie map k a -> Maybe (k, trie map k a)
mapView (CMap trie map k a -> Maybe (k, trie map k a))
-> (trie map k a -> CMap trie map k a)
-> trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap (trie map k a -> (k, trie map k a))
-> trie map k a -> (k, trie map k a)
forall a b. (a -> b) -> a -> b
$ trie map k a
tr
               in DList k -> trie map k a -> ([k], a)
go (DList k
xs DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc` k
k) trie map k a
tr'

-- O(m)
deleteMin :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
          => trie map k a -> trie map k a
deleteMin :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> trie map k a
deleteMin = (Maybe ([k], a), trie map k a) -> trie map k a
forall a b. (a, b) -> b
snd ((Maybe ([k], a), trie map k a) -> trie map k a)
-> (trie map k a -> (Maybe ([k], a), trie map k a))
-> trie map k a
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> (Maybe ([k], a), trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
minView

-- O(m)
deleteMax :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
          => trie map k a -> trie map k a
deleteMax :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> trie map k a
deleteMax = (Maybe ([k], a), trie map k a) -> trie map k a
forall a b. (a, b) -> b
snd ((Maybe ([k], a), trie map k a) -> trie map k a)
-> (trie map k a -> (Maybe ([k], a), trie map k a))
-> trie map k a
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> (Maybe ([k], a), trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
maxView

-- O(min(m,s))
split :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
      => [k] -> trie map k a -> (trie map k a, trie map k a)
split :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, trie map k a)
split [k]
xs trie map k a
tr = let (trie map k a
l,st a
_,trie map k a
g) = [k] -> trie map k a -> (trie map k a, st a, trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, st a, trie map k a)
splitLookup [k]
xs trie map k a
tr in (trie map k a
l,trie map k a
g)

-- O(min(m,s))
splitLookup :: (Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k)
            => [k]
            -> trie map k a
            -> (trie map k a, st a, trie map k a)
splitLookup :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, st a, trie map k a)
splitLookup []     trie map k a
tr = (trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty, trie map k a -> st a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> st a
tVal trie map k a
tr, st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty (trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr))
splitLookup (k
x:[k]
xs) trie map k a
tr =
   let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
       (CMap trie map k a
ml, Maybe (trie map k a)
subTr, CMap trie map k a
mg) = k
-> CMap trie map k a
-> (CMap trie map k a, Maybe (trie map k a), CMap trie map k a)
forall a. k -> map k a -> (map k a, Maybe a, map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> (m k a, Maybe a, m k a)
Map.splitLookup k
x CMap trie map k a
m
    in case Maybe (trie map k a)
subTr of
            Maybe (trie map k a)
Nothing  -> (st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v CMap trie map k a
ml, st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty, st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty CMap trie map k a
mg)
            Just trie map k a
tr' ->
               let (trie map k a
tl, st a
v', trie map k a
tg) = [k] -> trie map k a -> (trie map k a, st a, trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, st a, trie map k a)
splitLookup [k]
xs trie map k a
tr'
                   ml' :: CMap trie map k a
ml' = if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tl then CMap trie map k a
ml else k -> trie map k a -> CMap trie map k a -> CMap trie map k a
forall a. k -> a -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a -> m k a
Map.insert k
x trie map k a
tl CMap trie map k a
ml
                   mg' :: CMap trie map k a
mg' = if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tg then CMap trie map k a
mg else k -> trie map k a -> CMap trie map k a -> CMap trie map k a
forall a. k -> a -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a -> m k a
Map.insert k
x trie map k a
tg CMap trie map k a
mg
                in (st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v CMap trie map k a
ml', st a
v', st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty CMap trie map k a
mg')

-- O(m)
findPredecessor :: (Boolable (st a), Trie trie st map k, OrdMap map k)
                => [k] -> trie map k a -> Maybe ([k], a)
findPredecessor :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
findPredecessor [k]
_   trie map k a
tr | trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr = Maybe ([k], a)
forall a. Maybe a
Nothing
findPredecessor [k]
xs_ trie map k a
tr_          = [k] -> trie map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
go [k]
xs_ trie map k a
tr_
 where
   go :: [a] -> trie map a a -> Maybe ([a], a)
go [] trie map a a
_ = Maybe ([a], a)
forall a. Maybe a
Nothing

   -- We need to try the trie at x and then the trie at the predecessor of x:
   -- e.g. if looking for "foo", we need to try any 'f' branch to see if it has
   -- "fob" first, before grabbing the next-best option of the maximum of the
   -- 'b' branch, say "bar".
   --
   -- If there's no branch less than 'f' we try the current position as a last
   -- resort.
   go (a
x:[a]
xs) trie map a a
tr =
      let (w a
v,CMap trie map a a
m) = trie map a a -> (w a, CMap trie map a a)
forall a. trie map a a -> (w a, CMap trie map a a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map a a
tr
          predecessor :: Maybe (a, trie map a a)
predecessor = a -> CMap trie map a a -> Maybe (a, trie map a a)
forall a. a -> map a a -> Maybe (a, a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> Maybe (k, a)
Map.findPredecessor a
x CMap trie map a a
m
       in (([a], a) -> ([a], a)) -> Maybe ([a], a) -> Maybe ([a], a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([a] -> [a]) -> ([a], a) -> ([a], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) (a -> CMap trie map a a -> Maybe (trie map a a)
forall a. a -> map a a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup a
x CMap trie map a a
m Maybe (trie map a a)
-> (trie map a a -> Maybe ([a], a)) -> Maybe ([a], a)
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [a] -> trie map a a -> Maybe ([a], a)
go [a]
xs)
          Maybe ([a], a) -> Maybe ([a], a) -> Maybe ([a], a)
forall (a :: * -> *) x. Alt a x => a x -> a x -> a x
<|>
          case Maybe (a, trie map a a)
predecessor of
               Maybe (a, trie map a a)
Nothing         ->
                  if w a -> Bool
forall b. Boolable b => b -> Bool
hasValue w a
v
                     then ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just ([], w a -> a
forall a. w a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap w a
v)
                     else Maybe ([a], a)
forall a. Maybe a
Nothing
               Just (a
best,trie map a a
btr) -> (([a], a) -> ([a], a)) -> Maybe ([a], a) -> Maybe ([a], a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([a] -> [a]) -> ([a], a) -> ([a], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (a
besta -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) (trie map a a -> Maybe ([a], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
findMax trie map a a
btr)

-- O(m)
findSuccessor :: forall trie map st k a .
                 (Boolable (st a), Trie trie st map k, OrdMap map k)
              => [k] -> trie map k a -> Maybe ([k], a)
findSuccessor :: forall (trie :: (* -> * -> *) -> * -> * -> *) (map :: * -> * -> *)
       (st :: * -> *) k a.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
findSuccessor [k]
_   trie map k a
tr | trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr = Maybe ([k], a)
forall a. Maybe a
Nothing
findSuccessor [k]
xs_ trie map k a
tr_          = [k] -> trie map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
go [k]
xs_ trie map k a
tr_
 where
   go :: (Boolable (st a), Trie trie st map k, OrdMap map k)
      => [k] -> trie map k a -> Maybe ([k], a)
   go :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
go [] trie map k a
tr = do (k
k,trie map k a
t) <- (Maybe (k, trie map k a), map k (trie map k a))
-> Maybe (k, trie map k a)
forall a b. (a, b) -> a
fst ((Maybe (k, trie map k a), map k (trie map k a))
 -> Maybe (k, trie map k a))
-> (trie map k a
    -> (Maybe (k, trie map k a), map k (trie map k a)))
-> trie map k a
-> Maybe (k, trie map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. map k (trie map k a)
-> (Maybe (k, trie map k a), map k (trie map k a))
forall a. map k a -> (Maybe (k, a), map k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
Map.minViewWithKey (map k (trie map k a)
 -> (Maybe (k, trie map k a), map k (trie map k a)))
-> (trie map k a -> map k (trie map k a))
-> trie map k a
-> (Maybe (k, trie map k a), map k (trie map k a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap (trie map k a -> Maybe (k, trie map k a))
-> trie map k a -> Maybe (k, trie map k a)
forall a b. (a -> b) -> a -> b
$ trie map k a
tr
                 (([k], a) -> ([k], a)) -> Maybe ([k], a) -> Maybe ([k], a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([k] -> [k]) -> ([k], a) -> ([k], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:)) (trie map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
findMin trie map k a
t)

   go (k
x:[k]
xs) trie map k a
tr =
      let m :: map k (trie map k a)
m = trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr
          successor :: Maybe (k, trie map k a)
successor = k -> map k (trie map k a) -> Maybe (k, trie map k a)
forall a. k -> map k a -> Maybe (k, a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> Maybe (k, a)
Map.findSuccessor k
x map k (trie map k a)
m
       in (([k], a) -> ([k], a)) -> Maybe ([k], a) -> Maybe ([k], a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([k] -> [k]) -> ([k], a) -> ([k], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k
xk -> [k] -> [k]
forall a. a -> [a] -> [a]
:)) (k -> map k (trie map k a) -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x map k (trie map k a)
m Maybe (trie map k a)
-> (trie map k a -> Maybe ([k], a)) -> Maybe ([k], a)
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= [k] -> trie map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
go [k]
xs)
          Maybe ([k], a) -> Maybe ([k], a) -> Maybe ([k], a)
forall (a :: * -> *) x. Alt a x => a x -> a x -> a x
<|>
          (Maybe (k, trie map k a)
successor Maybe (k, trie map k a)
-> ((k, trie map k a) -> Maybe ([k], a)) -> Maybe ([k], a)
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \(k
best,trie map k a
btr) -> (([k], a) -> ([k], a)) -> Maybe ([k], a) -> Maybe ([k], a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([k] -> [k]) -> ([k], a) -> ([k], a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k
bestk -> [k] -> [k]
forall a. a -> [a] -> [a]
:)) (trie map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
findMin trie map k a
btr))

-- * Trie-only operations

-- O(s)
lookupPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)
             => [k] -> trie map k a -> trie map k a
lookupPrefix :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
lookupPrefix []     trie map k a
tr = trie map k a
tr
lookupPrefix (k
x:[k]
xs) trie map k a
tr =
   case k -> map k (trie map k a) -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr) of
        Maybe (trie map k a)
Nothing  -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty
        Just trie map k a
tr' -> let tr'' :: trie map k a
tr'' = [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
lookupPrefix [k]
xs trie map k a
tr'
                     in if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr''
                           then trie map k a
tr''
                           else st a -> map k (trie map k a) -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty (k -> trie map k a -> map k (trie map k a)
forall a. k -> a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a
Map.singleton k
x trie map k a
tr'')

-- O(s)
addPrefix :: (Alt st a, Trie trie st map k)
          => [k] -> trie map k a -> trie map k a
addPrefix :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
addPrefix []     = trie map k a -> trie map k a
forall a. a -> a
id
addPrefix (k
x:[k]
xs) = st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty (CMap trie map k a -> trie map k a)
-> (trie map k a -> CMap trie map k a)
-> trie map k a
-> trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> trie map k a -> CMap trie map k a
forall a. k -> a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a
Map.singleton k
x (trie map k a -> CMap trie map k a)
-> (trie map k a -> trie map k a)
-> trie map k a
-> CMap trie map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
addPrefix [k]
xs

-- O(s)
deletePrefix :: (Alt st a, Trie trie st map k)
             => [k] -> trie map k a -> trie map k a
deletePrefix :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
deletePrefix []     trie map k a
tr = trie map k a
tr
deletePrefix (k
x:[k]
xs) trie map k a
tr =
   case k -> map k (trie map k a) -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr) of
        Maybe (trie map k a)
Nothing  -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty
        Just trie map k a
tr' -> [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
deletePrefix [k]
xs trie map k a
tr'

-- O(s)
deleteSuffixes :: (Alt st a, Boolable (st a), Trie trie st map k)
               => [k] -> trie map k a -> trie map k a
deleteSuffixes :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
deleteSuffixes []     trie map k a
_  = trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
empty
deleteSuffixes (k
x:[k]
xs) trie map k a
tr =
   let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
    in case k -> CMap trie map k a -> Maybe (trie map k a)
forall a. k -> map k a -> Maybe a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> Maybe a
Map.lookup k
x CMap trie map k a
m of
            Maybe (trie map k a)
Nothing  -> trie map k a
tr
            Just trie map k a
tr' -> let tr'' :: trie map k a
tr'' = [k] -> trie map k a -> trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
deleteSuffixes [k]
xs trie map k a
tr'
                         in if trie map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
null trie map k a
tr''
                               then st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (k -> CMap trie map k a -> CMap trie map k a
forall a. k -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> m k a -> m k a
Map.delete k
x      CMap trie map k a
m)
                               else st a -> CMap trie map k a -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
v (k -> trie map k a -> CMap trie map k a -> CMap trie map k a
forall a. k -> a -> map k a -> map k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a -> m k a
Map.insert k
x trie map k a
tr'' CMap trie map k a
m)

-- O(m)
splitPrefix :: forall trie map st k a .
               (Alt st a, Trie trie st map k)
            => trie map k a -> ([k], st a, trie map k a)
splitPrefix :: forall (trie :: (* -> * -> *) -> * -> * -> *) (map :: * -> * -> *)
       (st :: * -> *) k a.
(Alt st a, Trie trie st map k) =>
trie map k a -> ([k], st a, trie map k a)
splitPrefix = DList k -> trie map k a -> ([k], st a, trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
DList k -> trie map k a -> ([k], st a, trie map k a)
go DList k
forall a. DList a
DL.empty
 where
   go :: (Alt st a, Trie trie st map k)
      => DL.DList k -> trie map k a -> ([k], st a, trie map k a)
   go :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
DList k -> trie map k a -> ([k], st a, trie map k a)
go DList k
xs trie map k a
tr =
      case map k (trie map k a) -> Maybe (k, trie map k a)
forall a. map k a -> Maybe (k, a)
forall (m :: * -> * -> *) k a. Map m k => m k a -> Maybe (k, a)
Map.singletonView (trie map k a -> map k (trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap trie map k a
tr) of
           Just (k
x,trie map k a
tr') -> DList k -> trie map k a -> ([k], st a, trie map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
DList k -> trie map k a -> ([k], st a, trie map k a)
go (DList k
xs DList k -> k -> DList k
forall a. DList a -> a -> DList a
`DL.snoc` k
x) trie map k a
tr'
           Maybe (k, trie map k a)
Nothing      -> let (st a
v,map k (trie map k a)
m) = trie map k a -> (st a, map k (trie map k a))
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
                            in (DList k -> [k]
forall a. DList a -> [a]
DL.toList DList k
xs, st a
v, st a -> map k (trie map k a) -> trie map k a
forall a. st a -> CMap trie map k a -> trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
st a -> CMap trie map k a -> trie map k a
mkTrie st a
forall (a :: * -> *) x. Alt a x => a x
altEmpty map k (trie map k a)
m)

-- O(m)
children :: (Boolable (st a), Trie trie st map k)
         => trie map k a -> CMap trie map k a
children :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> CMap trie map k a
children trie map k a
tr = let (st a
v,CMap trie map k a
m) = trie map k a -> (st a, CMap trie map k a)
forall a. trie map k a -> (st a, CMap trie map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie map k a
tr
               in if st a -> Bool
forall b. Boolable b => b -> Bool
hasValue st a
v
                     then CMap trie map k a
m
                     else case CMap trie map k a -> Maybe (k, trie map k a)
forall a. map k a -> Maybe (k, a)
forall (m :: * -> * -> *) k a. Map m k => m k a -> Maybe (k, a)
Map.singletonView CMap trie map k a
m of
                               Just (k
_, trie map k a
tr') -> trie map k a -> CMap trie map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> CMap trie map k a
children trie map k a
tr'
                               Maybe (k, trie map k a)
Nothing       -> CMap trie map k a
m

-- O(1)
children1 :: (Alt st a, Trie trie st map k)
          => trie map k a -> CMap trie map k a
children1 :: forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a -> CMap trie map k a
children1 = trie map k a -> CMap trie map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> CMap trie map k a
tMap

-- * Visualization

-- O(n m)
showTrieWith :: (Show k, Trie trie st map k)
             => (st a -> ShowS) -> trie map k a -> ShowS
showTrieWith :: forall k (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) a.
(Show k, Trie trie st map k) =>
(st a -> ShowS) -> trie map k a -> ShowS
showTrieWith = Int -> (st a -> ShowS) -> trie map k a -> ShowS
forall {trie :: (* -> * -> *) -> * -> * -> *} {st :: * -> *}
       {m :: * -> * -> *} {a} {a}.
(Trie trie st m a, Show a) =>
Int -> (st a -> ShowS) -> trie m a a -> ShowS
go Int
0
 where
   go :: Int -> (st a -> ShowS) -> trie m a a -> ShowS
go Int
indent st a -> ShowS
f trie m a a
tr =
      let (st a
v,CMap trie m a a
m) = trie m a a -> (st a, CMap trie m a a)
forall a. trie m a a -> (st a, CMap trie m a a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
trie map k a -> (st a, CMap trie map k a)
tParts trie m a a
tr
          sv :: ShowS
sv    = st a -> ShowS
f st a
v
          lv :: Int
lv    = [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (ShowS
sv [])
       in ShowS
sv ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((ShowS -> ShowS -> ShowS) -> ShowS -> [ShowS] -> ShowS
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ShowS
forall a. a -> a
id ([ShowS] -> ShowS)
-> ([Bool -> ShowS] -> [ShowS]) -> [Bool -> ShowS] -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> (Bool -> ShowS) -> ShowS)
-> [Bool] -> [Bool -> ShowS] -> [ShowS]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (((Bool -> ShowS) -> Bool -> ShowS)
-> Bool -> (Bool -> ShowS) -> ShowS
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Bool -> ShowS) -> Bool -> ShowS
forall a b. (a -> b) -> a -> b
($)) (Bool
False Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
: Bool -> [Bool]
forall a. a -> [a]
repeat Bool
True) ([Bool -> ShowS] -> ShowS) -> [Bool -> ShowS] -> ShowS
forall a b. (a -> b) -> a -> b
$
              ((a, trie m a a) -> Bool -> ShowS)
-> [(a, trie m a a)] -> [Bool -> ShowS]
forall a b. (a -> b) -> [a] -> [b]
map (\(a
k,trie m a a
t) -> \Bool
b -> let sk :: ShowS
sk = a -> ShowS
forall a. Show a => a -> ShowS
shows a
k
                                       lk :: Int
lk = [Char] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (ShowS
sk [])
                                       i :: Int
i  = Int
indent Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lv Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
                                    in (if Bool
b
                                           then Char -> ShowS
showChar Char
'\n'
                                              ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (Int -> Char -> [Char]
forall a. Int -> a -> [a]
replicate Int
i Char
' ')
                                           else ShowS
forall a. a -> a
id)
                                     ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"-> "
                                     ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
sk ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
                                     ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> (st a -> ShowS) -> trie m a a -> ShowS
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
lk Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
4) st a -> ShowS
f trie m a a
t)
                  (CMap trie m a a -> [(a, trie m a a)]
forall a. m a a -> [(a, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
Map.toListKV CMap trie m a a
m))