-- File created: 2008-11-08 15:52:33

{-# LANGUAGE CPP, MultiParamTypeClasses, FlexibleInstances
           , FlexibleContexts, UndecidableInstances #-}

#include "exports.h"

-- | The base implementation of a trie representing a set of lists, generalized
-- over any type of map from key values to tries.
--
-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers
-- to the number of keys in the set and @m@ to their maximum length. @s@ refers
-- to the length of a key given to the function, not any property of the set.
--
-- In addition, the trie's branching factor plays a part in almost every
-- operation, but the complexity depends on the underlying 'Map'. Thus, for
-- instance, 'member' is actually @O(m f(b))@ where @f(b)@ is the complexity of
-- a lookup operation on the 'Map' used. This complexity depends on the
-- underlying operation, which is not part of the specification of the visible
-- function. Thus it could change whilst affecting the complexity only for
-- certain Map types: hence this \"b factor\" is not shown explicitly.
--
-- Disclaimer: the complexities have not been proven.
module Data.ListTrie.Set (SET_EXPORTS) where

import Control.Arrow  ((***))
import Control.Monad  (liftM2)
import Data.Binary    (Binary,get,put)
import Data.Function  (on)
import qualified Data.List.NonEmpty as NE
import Data.Semigroup (Semigroup(..), stimesIdempotent)
import Prelude hiding (filter, foldl, foldl', foldr, map, null)
import qualified Prelude

#if __GLASGOW_HASKELL__
import Text.Read (readPrec, lexP, parens, prec, Lexeme(Ident))
#endif

import qualified Data.ListTrie.Base     as Base
import qualified Data.ListTrie.Base.Map as Map
import Data.ListTrie.Base.Classes (Identity(..), Unwrappable(..))
import Data.ListTrie.Base.Map     (Map, OrdMap)
import Data.ListTrie.Util         ((.:), (.:.), both)

#include "docs.h"

-- Invariant: any (Tr False _) has a True descendant.
--
-- We need this 'bool' and Base stuff in order to satisfy the Base.Trie type
-- class.
data TrieSetBase map a bool = Tr !bool !(CMap map a bool)
type CMap map a bool = map a (TrieSetBase map a bool)

-- That makes TrieSet a newtype, which means some unfortunate wrapping and
-- unwrapping in the function definitions below.
--
-- | The data structure itself: a set of keys of type @[a]@ implemented as a
-- trie, using @map@ to map keys of type @a@ to sub-tries.
--
-- Regarding the instances:
--
-- - The @CMap@ type is internal, ignore it. For 'Eq' and 'Ord' an 'Eq'
--   instance is required: what this means is that @map a v@ is expected to be
--   an instance of 'Eq', given 'Eq'@ v@.
--
-- - The 'Eq' constraint for the 'Ord' instance is misleading: it is needed
--   only because 'Eq' is a superclass of 'Ord'.
--
-- - The 'Monoid' instance defines 'mappend' as 'union' and 'mempty' as
--   'empty'.
newtype TrieSet map a = TS { forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS :: TrieSetBase map a Bool }

inTS :: (TrieSetBase map a Bool -> TrieSetBase nap b Bool)
     -> (TrieSet map a -> TrieSet nap b)
inTS :: forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS TrieSetBase map a Bool -> TrieSetBase nap b Bool
f = TrieSetBase nap b Bool -> TrieSet nap b
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase nap b Bool -> TrieSet nap b)
-> (TrieSet map a -> TrieSetBase nap b Bool)
-> TrieSet map a
-> TrieSet nap b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> TrieSetBase nap b Bool
f (TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSetBase nap b Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

instance Map map k => Base.Trie TrieSetBase Identity map k where
   mkTrie :: forall a.
Identity a -> CMap TrieSetBase map k a -> TrieSetBase map k a
mkTrie = a -> CMap map k a -> TrieSetBase map k a
forall (map :: * -> * -> *) a bool.
bool -> CMap map a bool -> TrieSetBase map a bool
Tr (a -> CMap map k a -> TrieSetBase map k a)
-> (Identity a -> a)
-> Identity a
-> CMap map k a
-> TrieSetBase map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Identity a -> a
forall a. Identity a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap
   tParts :: forall a.
TrieSetBase map k a -> (Identity a, CMap TrieSetBase map k a)
tParts (Tr a
b CMap map k a
m) = (a -> Identity a
forall a. a -> Identity a
Id a
b,CMap map k a
m)

-- CMap contains TrieSetBase, not TrieSet, hence we must supply these instances
-- for TrieSetBase first
instance Eq (CMap map a Bool) => Eq (TrieSetBase map a Bool) where
   Tr Bool
b1 CMap map a Bool
m1 == :: TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool
== Tr Bool
b2 CMap map a Bool
m2 = Bool
b1 Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bool
b2 Bool -> Bool -> Bool
&& CMap map a Bool
m1 CMap map a Bool -> CMap map a Bool -> Bool
forall a. Eq a => a -> a -> Bool
== CMap map a Bool
m2

instance (Eq (CMap map a Bool), OrdMap map a, Ord a)
      => Ord (TrieSetBase map a Bool)
 where
   compare :: TrieSetBase map a Bool -> TrieSetBase map a Bool -> Ordering
compare = [([a], Bool)] -> [([a], Bool)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([([a], Bool)] -> [([a], Bool)] -> Ordering)
-> (TrieSetBase map a Bool -> [([a], Bool)])
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSetBase map a Bool -> [([a], Bool)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
Base.toAscList

instance Eq (CMap map a Bool) => Eq (TrieSet map a) where
   == :: TrieSet map a -> TrieSet map a -> Bool
(==) = TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool
forall a. Eq a => a -> a -> Bool
(==) (TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- The CMap constraint is needed only because Eq is a superclass of Ord....
-- sigh
instance (Eq (CMap map a Bool), OrdMap map a, Ord a) => Ord (TrieSet map a)
 where
   compare :: TrieSet map a -> TrieSet map a -> Ordering
compare = TrieSetBase map a Bool -> TrieSetBase map a Bool -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (TrieSetBase map a Bool -> TrieSetBase map a Bool -> Ordering)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

instance Map map a => Semigroup (TrieSet map a) where
   <> :: TrieSet map a -> TrieSet map a -> TrieSet map a
(<>) = TrieSet map a -> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> TrieSet map a
union
   sconcat :: NonEmpty (TrieSet map a) -> TrieSet map a
sconcat = [TrieSet map a] -> TrieSet map a
forall (map :: * -> * -> *) a.
Map map a =>
[TrieSet map a] -> TrieSet map a
unions ([TrieSet map a] -> TrieSet map a)
-> (NonEmpty (TrieSet map a) -> [TrieSet map a])
-> NonEmpty (TrieSet map a)
-> TrieSet map a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty (TrieSet map a) -> [TrieSet map a]
forall a. NonEmpty a -> [a]
NE.toList
   stimes :: forall b. Integral b => b -> TrieSet map a -> TrieSet map a
stimes = b -> TrieSet map a -> TrieSet map a
forall b a. Integral b => b -> a -> a
stimesIdempotent

instance Map map a => Monoid (TrieSet map a) where
   mempty :: TrieSet map a
mempty  = TrieSet map a
forall (map :: * -> * -> *) a. Map map a => TrieSet map a
empty
   mappend :: TrieSet map a -> TrieSet map a -> TrieSet map a
mappend = TrieSet map a -> TrieSet map a -> TrieSet map a
forall a. Semigroup a => a -> a -> a
(<>)
   mconcat :: [TrieSet map a] -> TrieSet map a
mconcat = [TrieSet map a] -> TrieSet map a
forall (map :: * -> * -> *) a.
Map map a =>
[TrieSet map a] -> TrieSet map a
unions

instance (Map map a, Show a) => Show (TrieSet map a) where
   showsPrec :: Int -> TrieSet map a -> ShowS
showsPrec Int
p TrieSet map a
s = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[a]] -> ShowS
forall a. Show a => a -> ShowS
shows (TrieSet map a -> [[a]]
forall (map :: * -> * -> *) a. Map map a => TrieSet map a -> [[a]]
toList TrieSet map a
s)

instance (Map map a, Read a) => Read (TrieSet map a) where
#if __GLASGOW_HASKELL__
   readPrec :: ReadPrec (TrieSet map a)
readPrec = ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a))
-> ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a))
-> ReadPrec (TrieSet map a) -> ReadPrec (TrieSet map a)
forall a b. (a -> b) -> a -> b
$ do
      Ident String
"fromList" <- ReadPrec Lexeme
lexP
      ([[a]] -> TrieSet map a)
-> ReadPrec [[a]] -> ReadPrec (TrieSet map a)
forall a b. (a -> b) -> ReadPrec a -> ReadPrec b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [[a]] -> TrieSet map a
forall (map :: * -> * -> *) a. Map map a => [[a]] -> TrieSet map a
fromList ReadPrec [[a]]
forall a. Read a => ReadPrec a
readPrec
#else
   readsPrec p = readParen (p > 10) $ \r -> do
      ("fromList", list) <- lex r
      (xs, rest) <- readsPrec (p+1) list
      [(fromList xs, rest)]
#endif

instance (Map map k, Binary k, Binary a) => Binary (TrieSetBase map k a) where
   put :: TrieSetBase map k a -> Put
put (Tr a
v CMap map k a
m) = a -> Put
forall t. Binary t => t -> Put
put a
v Put -> Put -> Put
forall a b. PutM a -> PutM b -> PutM b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ([(k, TrieSetBase map k a)] -> Put
forall t. Binary t => t -> Put
put ([(k, TrieSetBase map k a)] -> Put)
-> (CMap map k a -> [(k, TrieSetBase map k a)])
-> CMap map k a
-> Put
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap map k a -> [(k, TrieSetBase map k a)]
forall a. map k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
Map.serializeToList (CMap map k a -> Put) -> CMap map k a -> Put
forall a b. (a -> b) -> a -> b
$ CMap map k a
m)
   get :: Get (TrieSetBase map k a)
get = (a -> CMap map k a -> TrieSetBase map k a)
-> Get a -> Get (CMap map k a) -> Get (TrieSetBase map k a)
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 a -> CMap map k a -> TrieSetBase map k a
forall (map :: * -> * -> *) a bool.
bool -> CMap map a bool -> TrieSetBase map a bool
Tr Get a
forall t. Binary t => Get t
get (Get [(k, TrieSetBase map k a)]
forall t. Binary t => Get t
get Get [(k, TrieSetBase map k a)]
-> ([(k, TrieSetBase map k a)] -> Get (CMap map k a))
-> Get (CMap map k a)
forall a b. Get a -> (a -> Get b) -> Get b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= CMap map k a -> Get (CMap map k a)
forall a. a -> Get a
forall (m :: * -> *) a. Monad m => a -> m a
return (CMap map k a -> Get (CMap map k a))
-> ([(k, TrieSetBase map k a)] -> CMap map k a)
-> [(k, TrieSetBase map k a)]
-> Get (CMap map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, TrieSetBase map k a)] -> CMap map k a
forall a. [(k, a)] -> map k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
Map.deserializeFromList)

instance (Map map a, Binary a) => Binary (TrieSet map a) where
   put :: TrieSet map a -> Put
put = TrieSetBase map a Bool -> Put
forall t. Binary t => t -> Put
put (TrieSetBase map a Bool -> Put)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> Put
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS
   get :: Get (TrieSet map a)
get = Get (TrieSetBase map a Bool)
forall t. Binary t => Get t
get Get (TrieSetBase map a Bool)
-> (TrieSetBase map a Bool -> Get (TrieSet map a))
-> Get (TrieSet map a)
forall a b. Get a -> (a -> Get b) -> Get b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= TrieSet map a -> Get (TrieSet map a)
forall a. a -> Get a
forall (m :: * -> *) a. Monad m => a -> m a
return (TrieSet map a -> Get (TrieSet map a))
-> (TrieSetBase map a Bool -> TrieSet map a)
-> TrieSetBase map a Bool
-> Get (TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS

-- * Construction

-- | @O(1)@. The empty set.
empty :: Map map a => TrieSet map a
empty :: forall (map :: * -> * -> *) a. Map map a => TrieSet map a
empty = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
Base.empty

-- | @O(s)@. The singleton set containing only the given key.
singleton :: Map map a => [a] -> TrieSet map a
singleton :: forall (map :: * -> * -> *) a. Map map a => [a] -> TrieSet map a
singleton [a]
k = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS(TrieSetBase map a Bool -> TrieSet map a)
-> TrieSetBase map a Bool -> TrieSet map a
forall a b. (a -> b) -> a -> b
$ [a] -> Bool -> TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a
Base.singleton [a]
k Bool
True

-- * Modification

-- | @O(min(m,s))@. Inserts the key into the set. If the key is already a
-- member of the set, the set is unchanged.
insert :: Map map a => [a] -> TrieSet map a -> TrieSet map a
insert :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
insert [a]
k = (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS((TrieSetBase map a Bool -> TrieSetBase map a Bool)
 -> TrieSet map a -> TrieSet map a)
-> (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
forall a b. (a -> b) -> a -> b
$ [a] -> Bool -> TrieSetBase map a Bool -> TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a -> trie map k a
Base.insert [a]
k Bool
True

-- | @O(min(m,s))@. Removes the key from the set. If the key is not a member of
-- the set, the set is unchanged.
delete :: Map map a => [a] -> TrieSet map a -> TrieSet map a
delete :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
delete = (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS ((TrieSetBase map a Bool -> TrieSetBase map a Bool)
 -> TrieSet map a -> TrieSet map a)
-> ([a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSet map a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.delete

-- * Querying

-- | @O(1)@. 'True' iff the set is empty.
null :: Map map a => TrieSet map a -> Bool
null :: forall (map :: * -> * -> *) a. Map map a => TrieSet map a -> Bool
null = TrieSetBase map a Bool -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
Base.null (TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. The number of keys in the set. The value is built up lazily,
-- allowing for delivery of partial results without traversing the whole set.
size :: (Map map a, Num n) => TrieSet map a -> n
size :: forall (map :: * -> * -> *) a n.
(Map map a, Num n) =>
TrieSet map a -> n
size = TrieSetBase map a Bool -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
Base.size (TrieSetBase map a Bool -> n)
-> (TrieSet map a -> TrieSetBase map a Bool) -> TrieSet map a -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. The number of keys in the set. The value is built strictly: no
-- value is returned until the set has been fully traversed.
size' :: (Map map a, Num n) => TrieSet map a -> n
size' :: forall (map :: * -> * -> *) a n.
(Map map a, Num n) =>
TrieSet map a -> n
size' = TrieSetBase map a Bool -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
Base.size' (TrieSetBase map a Bool -> n)
-> (TrieSet map a -> TrieSetBase map a Bool) -> TrieSet map a -> n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(m,s))@. 'True' iff the given key is contained within the set.
member :: Map map a => [a] -> TrieSet map a -> Bool
member :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> Bool
member = [a] -> TrieSetBase map a Bool -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
Base.member ([a] -> TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(m,s))@. 'False' iff the given key is contained within the set.
notMember :: Map map a => [a] -> TrieSet map a -> Bool
notMember :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> Bool
notMember = [a] -> TrieSetBase map a Bool -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
Base.notMember ([a] -> TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(n1 m1,n2 m2))@. 'True' iff the first set is a subset of the second,
-- i.e. all keys that are members of the first set are also members of the
-- second set.
isSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool
isSubsetOf :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> Bool
isSubsetOf = (Bool -> Bool -> Bool)
-> TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool
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
Base.isSubmapOfBy Bool -> Bool -> Bool
(&&) (TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(n1 m1,n2 m2))@. 'True' iff the first set is a proper subset of the
-- second, i.e. the first is a subset of the second, but the sets are not
-- equal.
isProperSubsetOf :: Map map a => TrieSet map a -> TrieSet map a -> Bool
isProperSubsetOf :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> Bool
isProperSubsetOf = (Bool -> Bool -> Bool)
-> TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool
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
Base.isProperSubmapOfBy Bool -> Bool -> Bool
(&&) (TrieSetBase map a Bool -> TrieSetBase map a Bool -> Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Combination

defaultUnion :: Bool -> Bool -> Bool
defaultUnion :: Bool -> Bool -> Bool
defaultUnion = String -> Bool -> Bool -> Bool
forall a. HasCallStack => String -> a
error String
"TrieSet.union :: internal error"

-- | @O(min(n1 m1,n2 m2))@. The union of the two sets: the set which contains
-- all keys that are members of either set.
--
-- The worst-case performance occurs when the two sets are identical.
union :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
union :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> TrieSet map a
union = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSetBase map a Bool
    -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (Bool -> Bool -> Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
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
Base.unionWith Bool -> Bool -> Bool
defaultUnion (TrieSetBase map a Bool -> TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> TrieSet map a
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(sum(n))@. The union of all the sets: the set which contains all keys
-- that are members of any of the sets.
--
-- The worst-case performance occurs when all the sets are identical.
unions :: Map map a => [TrieSet map a] -> TrieSet map a
unions :: forall (map :: * -> * -> *) a.
Map map a =>
[TrieSet map a] -> TrieSet map a
unions = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([TrieSet map a] -> TrieSetBase map a Bool)
-> [TrieSet map a]
-> TrieSet map a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bool -> Bool)
-> [TrieSetBase map a Bool] -> TrieSetBase map a Bool
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
Base.unionsWith Bool -> Bool -> Bool
defaultUnion ([TrieSetBase map a Bool] -> TrieSetBase map a Bool)
-> ([TrieSet map a] -> [TrieSetBase map a Bool])
-> [TrieSet map a]
-> TrieSetBase map a Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (TrieSet map a -> TrieSetBase map a Bool)
-> [TrieSet map a] -> [TrieSetBase map a Bool]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(n1 m1,n2 m2))@. The difference of the two sets: the set which
-- contains all keys that are members of the first set and not members of the
-- second set.
--
-- The worst-case performance occurs when the two sets are identical.
difference :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
difference :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> TrieSet map a
difference = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSetBase map a Bool
    -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (Bool -> Bool -> Maybe Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
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
Base.differenceWith
                      (String -> Bool -> Bool -> Maybe Bool
forall a. HasCallStack => String -> a
error String
"TrieSet.difference :: internal error")
                   (TrieSetBase map a Bool -> TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> TrieSet map a
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(n1 m1,n2 m2))@. The intersection of the two sets: the set which
-- contains all keys that are members of both sets.
--
-- The worst-case performance occurs when the two sets are identical.
intersection :: Map map a => TrieSet map a -> TrieSet map a -> TrieSet map a
intersection :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> TrieSet map a -> TrieSet map a
intersection = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSetBase map a Bool
    -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (Bool -> Bool -> Bool)
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
-> TrieSetBase map a Bool
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
Base.intersectionWith
                        (String -> Bool -> Bool -> Bool
forall a. HasCallStack => String -> a
error String
"TrieSet.intersection :: internal error")
                     (TrieSetBase map a Bool -> TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
-> TrieSet map a
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Filtering

-- | @O(n m)@. The set of those keys in the set for which the given predicate
-- returns 'True'.
filter :: Map map a => ([a] -> Bool) -> TrieSet map a -> TrieSet map a
filter :: forall (map :: * -> * -> *) a.
Map map a =>
([a] -> Bool) -> TrieSet map a -> TrieSet map a
filter [a] -> Bool
p = (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS ((TrieSetBase map a Bool -> TrieSetBase map a Bool)
 -> TrieSet map a -> TrieSet map a)
-> (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a
-> TrieSet map a
forall a b. (a -> b) -> a -> b
$ ([a] -> Bool -> Bool)
-> TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.filterWithKey (\[a]
k Bool
_ -> [a] -> Bool
p [a]
k)

-- | @O(n m)@. A pair of sets: the first element contains those keys for which
-- the given predicate returns 'True', and the second element contains those
-- for which it was 'False'.
partition :: Map map a
          => ([a] -> Bool) -> TrieSet map a -> (TrieSet map a, TrieSet map a)
partition :: forall (map :: * -> * -> *) a.
Map map a =>
([a] -> Bool) -> TrieSet map a -> (TrieSet map a, TrieSet map a)
partition [a] -> Bool
p = (TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
-> (TrieSet map a, TrieSet map a)
forall a b. (a -> b) -> (a, a) -> (b, b)
both TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS ((TrieSetBase map a Bool, TrieSetBase map a Bool)
 -> (TrieSet map a, TrieSet map a))
-> (TrieSet map a
    -> (TrieSetBase map a Bool, TrieSetBase map a Bool))
-> TrieSet map a
-> (TrieSet map a, TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> Bool -> Bool)
-> TrieSetBase map a Bool
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
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)
Base.partitionWithKey (\[a]
k Bool
_ -> [a] -> Bool
p [a]
k) (TrieSetBase map a Bool
 -> (TrieSetBase map a Bool, TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Mapping

-- | @O(n m)@. Apply the given function to all the keys in the set.
map :: (Map map a, Map map b) => ([a] -> [b]) -> TrieSet map a -> TrieSet map b
map :: forall (map :: * -> * -> *) a b.
(Map map a, Map map b) =>
([a] -> [b]) -> TrieSet map a -> TrieSet map b
map = (TrieSetBase map a Bool -> TrieSetBase map b Bool)
-> TrieSet map a -> TrieSet map b
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS ((TrieSetBase map a Bool -> TrieSetBase map b Bool)
 -> TrieSet map a -> TrieSet map b)
-> (([a] -> [b])
    -> TrieSetBase map a Bool -> TrieSetBase map b Bool)
-> ([a] -> [b])
-> TrieSet map a
-> TrieSet map b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([([b], Bool)] -> TrieSetBase map b Bool)
-> ([a] -> [b]) -> TrieSetBase map a Bool -> TrieSetBase map b Bool
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
Base.mapKeysWith [([b], Bool)] -> TrieSetBase map b Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
Base.fromList

-- | @O(n m)@. Apply the given function to the contents of all the keys in the
-- set.
mapIn :: (Map map a, Map map b) => (a -> b) -> TrieSet map a -> TrieSet map b
mapIn :: forall (map :: * -> * -> *) a b.
(Map map a, Map map b) =>
(a -> b) -> TrieSet map a -> TrieSet map b
mapIn = (TrieSetBase map a Bool -> TrieSetBase map b Bool)
-> TrieSet map a -> TrieSet map b
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS ((TrieSetBase map a Bool -> TrieSetBase map b Bool)
 -> TrieSet map a -> TrieSet map b)
-> ((a -> b) -> TrieSetBase map a Bool -> TrieSetBase map b Bool)
-> (a -> b)
-> TrieSet map a
-> TrieSet map b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bool -> Bool)
-> (a -> b) -> TrieSetBase map a Bool -> TrieSetBase map b Bool
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
Base.mapInKeysWith Bool -> Bool -> Bool
defaultUnion

-- * Folding

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toList' representation.
foldr :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldr :: forall (map :: * -> * -> *) a b.
Map map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldr [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldrWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toAscList' representation.
foldrAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldrAsc :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldrAsc [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldrAscWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toDescList' representation.
foldrDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldrDesc :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldrDesc [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldrDescWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl@ on the 'toList' representation.
foldl :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldl :: forall (map :: * -> * -> *) a b.
Map map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldl [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl@ on the 'toAscList' representation.
foldlAsc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldlAsc :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldlAsc [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlAscWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl@ on the 'toDescList' representation.
foldlDesc :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldlDesc :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldlDesc [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlDescWithKey (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toList' representation.
foldl' :: Map map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldl' :: forall (map :: * -> * -> *) a b.
Map map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldl' [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlWithKey' (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toAscList' representation.
foldlAsc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldlAsc' :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldlAsc' [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlAscWithKey' (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toDescList'
-- representation.
foldlDesc' :: OrdMap map a => ([a] -> b -> b) -> b -> TrieSet map a -> b
foldlDesc' :: forall (map :: * -> * -> *) a b.
OrdMap map a =>
([a] -> b -> b) -> b -> TrieSet map a -> b
foldlDesc' [a] -> b -> b
f = ([a] -> Bool -> b -> b) -> b -> TrieSetBase map a Bool -> b
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
Base.foldlDescWithKey' (\[a]
k Bool
_ -> [a] -> b -> b
f [a]
k) (b -> TrieSetBase map a Bool -> b)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> b
-> TrieSet map a
-> b
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Conversion between lists

-- | @O(n m)@. Converts the set to a list of the keys contained within, in
-- undefined order.
toList :: Map map a => TrieSet map a -> [[a]]
toList :: forall (map :: * -> * -> *) a. Map map a => TrieSet map a -> [[a]]
toList = (([a], Bool) -> [a]) -> [([a], Bool)] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst ([([a], Bool)] -> [[a]])
-> (TrieSet map a -> [([a], Bool)]) -> TrieSet map a -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> [([a], Bool)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
Base.toList (TrieSetBase map a Bool -> [([a], Bool)])
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> [([a], Bool)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Converts the set to a list of the keys contained within, in
-- ascending order.
toAscList :: OrdMap map a => TrieSet map a -> [[a]]
toAscList :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> [[a]]
toAscList = (([a], Bool) -> [a]) -> [([a], Bool)] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst ([([a], Bool)] -> [[a]])
-> (TrieSet map a -> [([a], Bool)]) -> TrieSet map a -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> [([a], Bool)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
Base.toAscList (TrieSetBase map a Bool -> [([a], Bool)])
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> [([a], Bool)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Converts the set to a list of the keys contained within, in
-- descending order.
toDescList :: OrdMap map a => TrieSet map a -> [[a]]
toDescList :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> [[a]]
toDescList = (([a], Bool) -> [a]) -> [([a], Bool)] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst ([([a], Bool)] -> [[a]])
-> (TrieSet map a -> [([a], Bool)]) -> TrieSet map a -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> [([a], Bool)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
Base.toDescList (TrieSetBase map a Bool -> [([a], Bool)])
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> [([a], Bool)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(n m)@. Creates a set from a list of keys.
fromList :: Map map a => [[a]] -> TrieSet map a
fromList :: forall (map :: * -> * -> *) a. Map map a => [[a]] -> TrieSet map a
fromList = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([[a]] -> TrieSetBase map a Bool) -> [[a]] -> TrieSet map a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [([a], Bool)] -> TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
Base.fromList ([([a], Bool)] -> TrieSetBase map a Bool)
-> ([[a]] -> [([a], Bool)]) -> [[a]] -> TrieSetBase map a Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> ([a], Bool)) -> [[a]] -> [([a], Bool)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (([a] -> Bool -> ([a], Bool)) -> Bool -> [a] -> ([a], Bool)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (,) Bool
True)

-- * Ordering ops

-- | @O(m)@. Removes and returns the minimal key in the set. If the set is
-- empty, 'Nothing' and the original set are returned.
minView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)
minView :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> (Maybe [a], TrieSet map a)
minView = ((([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> (TrieSetBase map a Bool -> TrieSet map a)
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
-> (Maybe [a], TrieSet map 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')
*** TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS) ((Maybe ([a], Bool), TrieSetBase map a Bool)
 -> (Maybe [a], TrieSet map a))
-> (TrieSet map a -> (Maybe ([a], Bool), TrieSetBase map a Bool))
-> TrieSet map a
-> (Maybe [a], TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
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)
Base.minView (TrieSetBase map a Bool
 -> (Maybe ([a], Bool), TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. Removes and returns the maximal key in the set. If the set is
-- empty, 'Nothing' and the original set are returned.
maxView :: OrdMap map a => TrieSet map a -> (Maybe [a], TrieSet map a)
maxView :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> (Maybe [a], TrieSet map a)
maxView = ((([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> (TrieSetBase map a Bool -> TrieSet map a)
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
-> (Maybe [a], TrieSet map 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')
*** TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS) ((Maybe ([a], Bool), TrieSetBase map a Bool)
 -> (Maybe [a], TrieSet map a))
-> (TrieSet map a -> (Maybe ([a], Bool), TrieSetBase map a Bool))
-> TrieSet map a
-> (Maybe [a], TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
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)
Base.maxView (TrieSetBase map a Bool
 -> (Maybe ([a], Bool), TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> (Maybe ([a], Bool), TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. Like 'fst' composed with 'minView'. 'Just' the minimal key in the
-- set, or 'Nothing' if the set is empty.
findMin :: OrdMap map a => TrieSet map a -> Maybe [a]
findMin :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> Maybe [a]
findMin = (([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> (TrieSet map a -> Maybe ([a], Bool))
-> TrieSet map a
-> Maybe [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> Maybe ([a], Bool)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
Base.findMin (TrieSetBase map a Bool -> Maybe ([a], Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> Maybe ([a], Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. Like 'fst' composed with 'maxView'. 'Just' the maximal key in the
-- set, or 'Nothing' if the set is empty.
findMax :: OrdMap map a => TrieSet map a -> Maybe [a]
findMax :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> Maybe [a]
findMax = (([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> (TrieSet map a -> Maybe ([a], Bool))
-> TrieSet map a
-> Maybe [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> Maybe ([a], Bool)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
Base.findMax (TrieSetBase map a Bool -> Maybe ([a], Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> Maybe ([a], Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. Like 'snd' composed with 'minView'. The set without its minimal
-- key, or the unchanged original set if it was empty.
deleteMin :: OrdMap map a => TrieSet map a -> TrieSet map a
deleteMin :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> TrieSet map a
deleteMin = (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.deleteMin

-- | @O(m)@. Like 'snd' composed with 'maxView'. The set without its maximal
-- key, or the unchanged original set if it was empty.
deleteMax :: OrdMap map a => TrieSet map a -> TrieSet map a
deleteMax :: forall (map :: * -> * -> *) a.
OrdMap map a =>
TrieSet map a -> TrieSet map a
deleteMax = (TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> TrieSet map a -> TrieSet map a
forall (map :: * -> * -> *) a (nap :: * -> * -> *) b.
(TrieSetBase map a Bool -> TrieSetBase nap b Bool)
-> TrieSet map a -> TrieSet nap b
inTS TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.deleteMax

-- | @O(min(m,s))@. Splits the set in two about the given key. The first
-- element of the resulting pair is a set containing the keys lesser than the
-- given key; the second contains those keys that are greater.
split :: OrdMap map a => [a] -> TrieSet map a -> (TrieSet map a, TrieSet map a)
split :: forall (map :: * -> * -> *) a.
OrdMap map a =>
[a] -> TrieSet map a -> (TrieSet map a, TrieSet map a)
split = (TrieSetBase map a Bool -> TrieSet map a)
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
-> (TrieSet map a, TrieSet map a)
forall a b. (a -> b) -> (a, a) -> (b, b)
both TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS ((TrieSetBase map a Bool, TrieSetBase map a Bool)
 -> (TrieSet map a, TrieSet map a))
-> ([a]
    -> TrieSet map a
    -> (TrieSetBase map a Bool, TrieSetBase map a Bool))
-> [a]
-> TrieSet map a
-> (TrieSet map a, TrieSet map a)
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a]
-> TrieSetBase map a Bool
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
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)
Base.split ([a]
 -> TrieSetBase map a Bool
 -> (TrieSetBase map a Bool, TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> (TrieSetBase map a Bool, TrieSetBase map a Bool)
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(min(m,s))@. Like 'split', but also returns whether the given key was a
-- member of the set or not.
splitMember :: OrdMap map a
            => [a] -> TrieSet map a -> (TrieSet map a, Bool, TrieSet map a)
splitMember :: forall (map :: * -> * -> *) a.
OrdMap map a =>
[a] -> TrieSet map a -> (TrieSet map a, Bool, TrieSet map a)
splitMember = (\(TrieSetBase map a Bool
l,Identity Bool
b,TrieSetBase map a Bool
g) -> (TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS TrieSetBase map a Bool
l,Identity Bool -> Bool
forall a. Identity a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap Identity Bool
b,TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS TrieSetBase map a Bool
g)) ((TrieSetBase map a Bool, Identity Bool, TrieSetBase map a Bool)
 -> (TrieSet map a, Bool, TrieSet map a))
-> ([a]
    -> TrieSet map a
    -> (TrieSetBase map a Bool, Identity Bool, TrieSetBase map a Bool))
-> [a]
-> TrieSet map a
-> (TrieSet map a, Bool, TrieSet map a)
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a]
-> TrieSetBase map a Bool
-> (TrieSetBase map a Bool, Identity Bool, TrieSetBase map a Bool)
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)
Base.splitLookup ([a]
 -> TrieSetBase map a Bool
 -> (TrieSetBase map a Bool, Identity Bool, TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> (TrieSetBase map a Bool, Identity Bool, TrieSetBase map a Bool)
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. 'Just' the key of the set which precedes the given key in order,
-- or 'Nothing' if the set is empty.
findPredecessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]
findPredecessor :: forall (map :: * -> * -> *) a.
OrdMap map a =>
[a] -> TrieSet map a -> Maybe [a]
findPredecessor = (([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> ([a] -> TrieSet map a -> Maybe ([a], Bool))
-> [a]
-> TrieSet map a
-> Maybe [a]
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> Maybe ([a], Bool)
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)
Base.findPredecessor ([a] -> TrieSetBase map a Bool -> Maybe ([a], Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> Maybe ([a], Bool)
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. 'Just' the key of the set which succeeds the given key in order,
-- or 'Nothing' if the set is empty.
findSuccessor :: OrdMap map a => [a] -> TrieSet map a -> Maybe [a]
findSuccessor :: forall (map :: * -> * -> *) a.
OrdMap map a =>
[a] -> TrieSet map a -> Maybe [a]
findSuccessor = (([a], Bool) -> [a]) -> Maybe ([a], Bool) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ([a], Bool) -> [a]
forall a b. (a, b) -> a
fst (Maybe ([a], Bool) -> Maybe [a])
-> ([a] -> TrieSet map a -> Maybe ([a], Bool))
-> [a]
-> TrieSet map a
-> Maybe [a]
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> Maybe ([a], Bool)
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)
Base.findSuccessor ([a] -> TrieSetBase map a Bool -> Maybe ([a], Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> Maybe ([a], Bool)
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Trie-only operations

-- | @O(s)@. The set which contains all keys of which the given key is a
-- prefix. For example:
--
-- > lookupPrefix "ab" (fromList ["a","ab","ac","abc"])
-- >    == fromList ["ab","abc"]
lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
lookupPrefix :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
lookupPrefix = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([a] -> TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.lookupPrefix ([a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSetBase map a Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(s)@. Prepends the given key to all the keys of the set. For example:
--
-- > addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"]
addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
addPrefix :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
addPrefix = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([a] -> TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.addPrefix ([a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSetBase map a Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(s)@. The set which contains all keys of which the given key is a
-- prefix, with the prefix removed from each key. If the given key is not a
-- prefix of any key in the set, an empty set is returned. For example:
--
-- > deletePrefix "a" (fromList ["a","ab","ac"]) == fromList ["","b","c"]
--
-- This function can be used, for instance, to reduce potentially expensive I/O
-- operations: if you need to check whether a string is a member of a set, but
-- you only have a prefix of it and retrieving the rest is an expensive
-- operation, calling 'deletePrefix' with what you have might allow you to
-- avoid the operation: if the resulting set is empty, the entire string cannot
-- be a member of the set.
deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a
deletePrefix :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
deletePrefix = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([a] -> TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.deletePrefix ([a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSetBase map a Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:
--
-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])
-- >    == fromList [("a",1),("ac",3),("b",4)]
deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a
deleteSuffixes :: forall (map :: * -> * -> *) a.
Map map a =>
[a] -> TrieSet map a -> TrieSet map a
deleteSuffixes = TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (TrieSetBase map a Bool -> TrieSet map a)
-> ([a] -> TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSet map a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: [a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool
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
Base.deleteSuffixes ([a] -> TrieSetBase map a Bool -> TrieSetBase map a Bool)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> [a]
-> TrieSet map a
-> TrieSetBase map a Bool
forall a b c d. (a -> b -> c) -> (d -> b) -> a -> d -> c
.:. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. A triple containing the longest common prefix of all keys in the
-- set, whether that prefix was a member of the set, and the set with that
-- prefix removed from all the keys as well as the set itself. Examples:
--
-- > splitPrefix (fromList ["a","b"]) == ("", False, fromList ["a","b"])
-- > splitPrefix (fromList ["a","ab","ac"]) == ("a", True, fromList ["b","c"])
splitPrefix :: Map map a => TrieSet map a -> ([a], Bool, TrieSet map a)
splitPrefix :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> ([a], Bool, TrieSet map a)
splitPrefix = (\([a]
k,Identity Bool
b,TrieSetBase map a Bool
t) -> ([a]
k,Identity Bool -> Bool
forall a. Identity a -> a
forall (w :: * -> *) a. Unwrappable w => w a -> a
unwrap Identity Bool
b,TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS TrieSetBase map a Bool
t)) (([a], Identity Bool, TrieSetBase map a Bool)
 -> ([a], Bool, TrieSet map a))
-> (TrieSet map a -> ([a], Identity Bool, TrieSetBase map a Bool))
-> TrieSet map a
-> ([a], Bool, TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool
-> ([a], Identity Bool, TrieSetBase map a Bool)
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)
Base.splitPrefix (TrieSetBase map a Bool
 -> ([a], Identity Bool, TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> ([a], Identity Bool, TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(m)@. The children of the longest common prefix in the trie as sets,
-- associated with their distinguishing key value. If the set contains less
-- than two keys, this function will return an empty map. Examples;
--
-- > children (fromList ["a","abc","abcd"])
-- >    == Map.fromList [('b',fromList ["c","cd"])]
-- > children (fromList ["b","c"])
-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]
children :: Map map a => TrieSet map a -> map a (TrieSet map a)
children :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> map a (TrieSet map a)
children = (TrieSetBase map a Bool -> TrieSet map a)
-> map a (TrieSetBase map a Bool) -> map a (TrieSet map a)
forall a b. (a -> b) -> map a a -> map a b
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b) -> m k a -> m k b
Map.map TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (map a (TrieSetBase map a Bool) -> map a (TrieSet map a))
-> (TrieSet map a -> map a (TrieSetBase map a Bool))
-> TrieSet map a
-> map a (TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> map a (TrieSetBase map a Bool)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> CMap trie map k a
Base.children (TrieSetBase map a Bool -> map a (TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> map a (TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- | @O(1)@. The children of the first element of the longest common prefix in
-- the trie as sets, associated with their distinguishing key value. If the set
-- contains less than two keys, this function will return an empty map.
--
-- If the longest common prefix of all keys in the trie is the empty list, this
-- function is equivalent to 'children'.
--
-- Examples:
--
-- > children1 (fromList ["abc","abcd"])
-- >    == Map.fromList [('a',fromList ["bc","bcd"])]
-- > children1 (fromList ["b","c"])
-- >    == Map.fromList [('b',fromList [""]),('c',fromList [""])]
children1 :: Map map a => TrieSet map a -> map a (TrieSet map a)
children1 :: forall (map :: * -> * -> *) a.
Map map a =>
TrieSet map a -> map a (TrieSet map a)
children1 = (TrieSetBase map a Bool -> TrieSet map a)
-> map a (TrieSetBase map a Bool) -> map a (TrieSet map a)
forall a b. (a -> b) -> map a a -> map a b
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b) -> m k a -> m k b
Map.map TrieSetBase map a Bool -> TrieSet map a
forall (map :: * -> * -> *) a.
TrieSetBase map a Bool -> TrieSet map a
TS (map a (TrieSetBase map a Bool) -> map a (TrieSet map a))
-> (TrieSet map a -> map a (TrieSetBase map a Bool))
-> TrieSet map a
-> map a (TrieSet map a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSetBase map a Bool -> map a (TrieSetBase map a Bool)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a -> CMap trie map k a
Base.children1 (TrieSetBase map a Bool -> map a (TrieSetBase map a Bool))
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> map a (TrieSetBase map a Bool)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS

-- * Visualization

-- | @O(n m)@. Displays the set's internal structure in an undefined way. That
-- is to say, no program should depend on the function's results.
showTrie :: (Show a, Map map a) => TrieSet map a -> ShowS
showTrie :: forall a (map :: * -> * -> *).
(Show a, Map map a) =>
TrieSet map a -> ShowS
showTrie = (Identity Bool -> ShowS) -> TrieSetBase map a Bool -> ShowS
forall k (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) a.
(Show k, Trie trie st map k) =>
(st a -> ShowS) -> trie map k a -> ShowS
Base.showTrieWith (\(Id Bool
b) -> Char -> ShowS
showChar (Char -> ShowS) -> Char -> ShowS
forall a b. (a -> b) -> a -> b
$ if Bool
b then Char
'X' else Char
' ')
         (TrieSetBase map a Bool -> ShowS)
-> (TrieSet map a -> TrieSetBase map a Bool)
-> TrieSet map a
-> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieSet map a -> TrieSetBase map a Bool
forall (map :: * -> * -> *) a.
TrieSet map a -> TrieSetBase map a Bool
unTS