-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Crit-bit maps and sets
--
-- This package implements crit-bit trees, a key-value container type for
-- storing keys that can be treated as bitstrings (e.g. ByteString
-- and Text).
--
-- Compared to the data structures from the containers and
-- unordered-containers packages, you will find that sometimes the
-- functions implemented in this package are faster, sometimes slower.
--
-- In many cases, a CritBit tree provides performance close to
-- that of a HashMap, while providing ordered storage and
-- traversal like a Map.
@package critbit
@version 0.2.0.0
-- | A set type that uses crit-bit trees internally.
--
-- For every n key-value pairs stored, a crit-bit tree uses
-- n-1 internal nodes, for a total of 2n-1 internal nodes
-- and leaves.
module Data.CritBit.Set
-- | A set based on crit-bit trees.
data Set a
-- | Same as difference.
(\\) :: CritBitKey a => Set a -> Set a -> Set a
-- | O(1). Is the set empty?
--
--
-- null (empty) == True
-- null (singleton "a") == False
--
null :: Set a -> Bool
-- | O(n). The number of elements in the set.
--
--
-- size empty == 0
-- size (singleton "a") == 1
-- size (fromList ["a", "c", "b"]) == 3
--
size :: Set a -> Int
-- | O(k). Is the element in the set?
--
--
-- member "a" (fromList ["a", "b"]) == True
-- member "c" (fromList ["a", "b"]) == False
--
--
-- See also notMember.
member :: CritBitKey a => a -> Set a -> Bool
-- | O(k). Is the element not in the set?
--
--
-- notMember "a" (fromList ["a", "b"]) == False
-- notMember "c" (fromList ["a", "b"]) == True
--
--
-- See also member.
notMember :: CritBitKey a => a -> Set a -> Bool
-- | O(k). Find largest element smaller than the given one.
--
--
-- lookupLT "b" (fromList ["a", "b"]) == Just "a"
-- lookupLT "aa" (fromList ["a", "b"]) == Just "a"
-- lookupLT "a" (fromList ["a", "b"]) == Nothing
--
lookupLT :: CritBitKey a => a -> Set a -> Maybe a
-- | O(k). Find smallest element greater than the given one.
--
--
-- lookupGT "b" (fromList ["a", "b"]) == Nothing
-- lookupGT "aa" (fromList ["a", "b"]) == Just "b"
-- lookupGT "a" (fromList ["a", "b"]) == Just "b"
--
lookupGT :: CritBitKey a => a -> Set a -> Maybe a
-- | O(k). Find largest element smaller than or equal to the given
-- one.
--
--
-- lookupGE "b" (fromList ["a", "b"]) == Just "b"
-- lookupGE "aa" (fromList ["a", "b"]) == Just "b"
-- lookupGE "a" (fromList ["a", "b"]) == Just "a"
-- lookupGE "" (fromList ["a", "b"]) == Nothing
--
lookupLE :: CritBitKey a => a -> Set a -> Maybe a
-- | O(k). Find smallest element greater than or equal to the given
-- one.
--
--
-- lookupGE "aa" (fromList ["a", "b"]) == Just "b"
-- lookupGE "b" (fromList ["a", "b"]) == Just "b"
-- lookupGE "bb" (fromList ["a", "b"]) == Nothing
--
lookupGE :: CritBitKey a => a -> Set a -> Maybe a
-- | O(n+m). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: CritBitKey a => Set a -> Set a -> Bool
-- | O(n+m). Is this a proper subset (ie. a subset but not equal)?
-- (s1 isSubsetOf s2) tells whether s1 is a
-- proper subset of s2.
isProperSubsetOf :: CritBitKey a => Set a -> Set a -> Bool
-- | O(1). The empty set.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: Set a
-- | O(1). A set with a single element.
--
--
-- singleton "a" == fromList ["a"]
--
singleton :: a -> Set a
-- | O(k). Insert an element in a set. If the set already contains
-- an element equal to the given value, it is replaced with the new
-- value.
insert :: CritBitKey a => a -> Set a -> Set a
-- | O(k). Delete an element from a set.
delete :: CritBitKey a => a -> Set a -> Set a
-- | O(k). The union of two sets, preferring the first set when
-- equal elements are encountered.
union :: CritBitKey a => Set a -> Set a -> Set a
-- | The union of a list of sets: (unions == foldl
-- union empty).
unions :: CritBitKey a => [Set a] -> Set a
-- | O(k). The difference of two sets.
difference :: CritBitKey a => Set a -> Set a -> Set a
-- | O(k). The intersection of two sets. Elements of the result come
-- from the first set.
intersection :: CritBitKey a => Set a -> Set a -> Set a
-- | O(n). Filter all elements that satisfy the predicate.
--
--
-- filter (> "a") (fromList ["a", "b"]) == fromList [("3","b")]
-- filter (> "x") (fromList ["a", "b"]) == empty
-- filter (< "a") (fromList ["a", "b"]) == empty
--
filter :: (a -> Bool) -> Set a -> Set a
-- | O(n). Partition the set into two sets, one with all elements
-- that satisfy the predicate and one with all elements that don't
-- satisfy the predicate. See also split.
partition :: CritBitKey a => (a -> Bool) -> Set a -> (Set a, Set a)
-- | O(k). The expression (split x set) is a pair
-- (set1,set2) where set1 comprises the elements of
-- set less than x and set2 comprises the
-- elements of set greater than x.
--
--
-- split "a" (fromList ["b", "d"]) == (empty, fromList ["b", "d")])
-- split "b" (fromList ["b", "d"]) == (empty, singleton "d")
-- split "c" (fromList ["b", "d"]) == (singleton "b", singleton "d")
-- split "d" (fromList ["b", "d"]) == (singleton "b", empty)
-- split "e" (fromList ["b", "d"]) == (fromList ["b", "d"], empty)
--
split :: CritBitKey a => a -> Set a -> (Set a, Set a)
-- | O(k). Performs a split but also returns whether the
-- pivot element was found in the original set.
--
--
-- splitMember "a" (fromList ["b", "d"]) == (empty, False, fromList ["b", "d"])
-- splitMember "b" (fromList ["b", "d"]) == (empty, True, singleton "d")
-- splitMember "c" (fromList ["b", "d"]) == (singleton "b", False, singleton "d")
-- splitMember "d" (fromList ["b", "d"]) == (singleton "b", True, empty)
-- splitMember "e" (fromList ["b", "d"]) == (fromList ["b", "d"], False, empty)
--
splitMember :: CritBitKey a => a -> Set a -> (Set a, Bool, Set a)
-- | O(k). map f s is the set obtained by applying
-- f to each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: CritBitKey a2 => (a1 -> a2) -> Set a1 -> Set a2
-- | O(n). The mapMonotonic f s == map f s,
-- but works only when f is monotonic. The precondition is
-- not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: CritBitKey a2 => (a1 -> a2) -> Set a1 -> Set a2
-- | O(n). Fold the elements in the set using the given
-- right-associative binary operator, such that foldr f z ==
-- foldr f z . toAscList.
--
-- For example,
--
--
-- toAscList set = foldr (:) [] set
--
foldr :: (a -> b -> b) -> b -> Set a -> b
-- | O(n). Fold the elements in the set using the given
-- left-associative binary operator, such that foldl f z ==
-- foldl f z . toAscList.
--
-- For example,
--
--
-- toDescList set = foldl (flip (:)) [] set
--
foldl :: (a -> b -> a) -> a -> Set b -> a
-- | O(n). A strict version of foldr. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Set a -> b
-- | O(n). A strict version of foldl. Each application of the
-- operator is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> Set b -> a
-- | O(k'). The minimal element of a set.
findMin :: Set a -> a
-- | O(k). The maximal element of a set.
findMax :: Set a -> a
-- | O(k'). Delete the minimal element. Returns an empty set if the
-- set is empty.
deleteMin :: Set a -> Set a
-- | O(k). Delete the maximal element. Returns an empty set if the
-- set is empty.
deleteMax :: Set a -> Set a
-- | O(k'). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: Set a -> (a, Set a)
-- | O(k). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: Set a -> (a, Set a)
-- | O(k). Retrieves the maximal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
maxView :: Set a -> Maybe (a, Set a)
-- | O(k'). Retrieves the minimal key of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
minView :: Set a -> Maybe (a, Set a)
-- | O(n). An alias of toList.
--
-- Returns the elements of a set in ascending order.
elems :: Set a -> [a]
-- | O(n). Convert the set to a list of values. The list returned
-- will be sorted in lexicographically ascending order.
--
--
-- toList (fromList ["b", "a"]) == ["a", "b"]
-- toList empty == []
--
toList :: Set a -> [a]
-- | O(k). Build a set from a list of values.
--
--
-- fromList [] == empty
-- fromList ["a", "b", "a"] == fromList ["a", "b"]
--
fromList :: CritBitKey a => [a] -> Set a
-- | O(n). Convert the set to an ascending list of elements.
toAscList :: Set a -> [a]
-- | O(n). Convert the set to a descending list of elements.
toDescList :: Set a -> [a]
-- | O(n). Build a set from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
fromAscList :: CritBitKey a => [a] -> Set a
-- | O(n). Build a set from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
fromDistinctAscList :: CritBitKey a => [a] -> Set a
instance Foldable Set
instance CritBitKey k => Monoid (Set k)
instance Show a => Show (Set a)
-- | A crit-bit tree that does not evaluate its values by default.
--
-- For every n key-value pairs stored, a crit-bit tree uses
-- n-1 internal nodes, for a total of 2n-1 internal nodes
-- and leaves.
module Data.CritBit.Map.Lazy
-- | A type that can be used as a key in a crit-bit tree.
--
-- We use 9 bits to represent 8-bit bytes so that we can distinguish
-- between an interior byte that is zero (which must have the 9th bit
-- set) and a byte past the end of the input (which must not have
-- the 9th bit set).
--
-- Without this trick, the critical bit calculations would fail on zero
-- bytes within a string, and our tree would be unable to handle
-- arbitrary binary data.
class Eq k => CritBitKey k
byteCount :: CritBitKey k => k -> Int
getByte :: CritBitKey k => k -> Int -> Word16
-- | A crit-bit tree.
data CritBit k v
-- | O(k). Find the value at a key. Calls error when the
-- element can not be found.
--
--
-- fromList [("a",5), ("b",3)] ! "c" Error: element not in the map
-- fromList [("a",5), ("b",3)] ! "a" == 5
--
(!) :: CritBitKey k => CritBit k v -> k -> v
-- | Same as difference.
(\\) :: CritBitKey k => CritBit k v -> CritBit k w -> CritBit k v
-- | O(1). Is the map empty?
--
--
-- null (empty) == True
-- null (singleton 1 'a') == False
--
null :: CritBit k v -> Bool
-- | O(n). The number of elements in the map.
--
--
-- size empty == 0
-- size (singleton "a" 1) == 1
-- size (fromList [("a",1), ("c",2), ("b",3)]) == 3
--
size :: CritBit k v -> Int
-- | O(k). Is the key a member of the map?
--
--
-- member "a" (fromList [("a",5), ("b",3)]) == True
-- member "c" (fromList [("a",5), ("b",3)]) == False
--
--
-- See also notMember.
member :: CritBitKey k => k -> CritBit k v -> Bool
-- | O(k). Is the key not a member of the map?
--
--
-- notMember "a" (fromList [("a",5), ("b",3)]) == False
-- notMember "c" (fromList [("a",5), ("b",3)]) == True
--
--
-- See also member.
notMember :: CritBitKey k => k -> CritBit k v -> Bool
-- | O(k). Lookup the value at a key in the map.
--
-- The function will return the corresponding value as (Just
-- value), or Nothing if the key isn't in the map.
--
-- An example of using lookup:
--
--
-- {-# LANGUAGE OverloadedStrings #-}
-- import Data.Text
-- import Prelude hiding (lookup)
-- import Data.CritBit.Map.Lazy
--
-- employeeDept, deptCountry, countryCurrency :: CritBit Text Text
-- employeeDept = fromList [("John","Sales"), ("Bob","IT")]
-- deptCountry = fromList [("IT","USA"), ("Sales","France")]
-- countryCurrency = fromList [("USA", "Dollar"), ("France", "Euro")]
--
-- employeeCurrency :: Text -> Maybe Text
-- employeeCurrency name = do
-- dept <- lookup name employeeDept
-- country <- lookup dept deptCountry
-- lookup country countryCurrency
--
-- main = do
-- putStrLn $ "John's currency: " ++ show (employeeCurrency "John")
-- putStrLn $ "Pete's currency: " ++ show (employeeCurrency "Pete")
--
--
-- The output of this program:
--
--
-- John's currency: Just "Euro"
-- Pete's currency: Nothing
--
lookup :: CritBitKey k => k -> CritBit k v -> Maybe v
-- | O(k). Returns the value associated with the given key, or the
-- given default value if the key is not in the map.
--
--
-- findWithDefault 1 "x" (fromList [("a",5), ("b",3)]) == 1
-- findWithDefault 1 "a" (fromList [("a",5), ("b",3)]) == 5
--
findWithDefault :: CritBitKey k => v -> k -> CritBit k v -> v
-- | O(k). Find smallest key greater than the given one and return
-- the corresponding (key, value) pair.
--
--
-- lookupGT "aa" (fromList [("a",3), ("b",5)]) == Just ("b",5)
-- lookupGT "b" (fromList [("a",3), ("b",5)]) == Nothing
--
lookupGT :: CritBitKey k => k -> CritBit k v -> Maybe (k, v)
-- | O(k). Find smallest key greater than or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- lookupGE "aa" (fromList [("a",3), ("b",5)]) == Just("b",5)
-- lookupGE "b" (fromList [("a",3), ("b",5)]) == Just("b",5)
-- lookupGE "bb" (fromList [("a",3), ("b",5)]) == Nothing
--
lookupGE :: CritBitKey k => k -> CritBit k v -> Maybe (k, v)
-- | O(k). Find largest key smaller than the given one and return
-- the corresponding (key, value) pair.
--
--
-- lookupLT "aa" (fromList [("a",3), ("b",5)]) == Just ("a",3)
-- lookupLT "a" (fromList [("a",3), ("b",5)]) == Nothing
--
lookupLT :: CritBitKey k => k -> CritBit k v -> Maybe (k, v)
-- | O(k). Find largest key smaller than or equal to the given one
-- and return the corresponding (key, value) pair.
--
--
-- lookupGE "bb" (fromList [("aa",3), ("b",5)]) == Just("b",5)
-- lookupGE "aa" (fromList [("aa",3), ("b",5)]) == Just("aa",5)
-- lookupGE "a" (fromList [("aa",3), ("b",5)]) == Nothing
--
lookupLE :: CritBitKey k => k -> CritBit k v -> Maybe (k, v)
-- | O(1). The empty map.
--
--
-- empty == fromList []
-- size empty == 0
--
empty :: CritBit k v
-- | O(1). A map with a single element.
--
--
-- singleton "a" 1 == fromList [("a",1)]
--
singleton :: k -> v -> CritBit k v
-- | O(k). Insert a new key and value in the map. If the key is
-- already present in the map, the associated value is replaced with the
-- supplied value. insert is equivalent to insertWith
-- const.
--
--
-- insert "b" 7 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",7)]
-- insert "x" 7 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3), ("x",7)]
-- insert "x" 5 empty == singleton "x" 5
--
insert :: CritBitKey k => k -> v -> CritBit k v -> CritBit k v
-- | O(k). Insert with a function, combining new value and old
-- value. insertWith f key value cb will insert the pair
-- (key, value) into cb if key does not exist in the map. If the
-- key does exist, the function will insert the pair (key, f
-- new_value old_value).
--
--
-- insertWith (+) "a" 1 (fromList [("a",5), ("b",3)]) == fromList [("a",6), ("b",3)]
-- insertWith (+) "c" 7 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3), ("c",7)]
-- insertWith (+) "x" 5 empty == singleton "x" 5
--
insertWith :: CritBitKey k => (v -> v -> v) -> k -> v -> CritBit k v -> CritBit k v
-- | O(k). Insert with a function, combining key, new value and old
-- value. insertWithKey f key value cb will insert the
-- pair (key, value) into cb if key does not exist in the map. If the key
-- does exist, the function will insert the pair (key,f key new_value
-- old_value). Note that the key passed to f is the same key passed
-- to insertWithKey.
--
--
-- let f key new_value old_value = byteCount key + new_value + old_value
-- insertWithKey f "a" 1 (fromList [("a",5), ("b",3)]) == fromList [("a",7), ("b",3)]
-- insertWithKey f "c" 1 (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3), ("c",1)]
-- insertWithKey f "a" 1 empty == singleton "a" 1
--
insertWithKey :: CritBitKey k => (k -> v -> v -> v) -> k -> v -> CritBit k v -> CritBit k v
-- | O(k). Combines insert operation with old value retrieval. The
-- expression (insertLookupWithKey f k x map) is a pair
-- where the first element is equal to (lookup k map) and
-- the second element equal to (insertWithKey f k x map).
--
--
-- let f key new_value old_value = length key + old_value + new_value
-- insertLookupWithKey f "a" 2 (fromList [("a",5), ("b",3)]) == (Just 5, fromList [("a",8), ("b",3)])
-- insertLookupWithKey f "c" 2 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [("a",5), ("b",3), ("c",2)])
-- insertLookupWithKey f "a" 2 empty == (Nothing, singleton "a" 2)
--
--
-- This is how to define insertLookup using
-- insertLookupWithKey:
--
--
-- let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
-- insertLookup "a" 1 (fromList [("a",5), ("b",3)]) == (Just 5, fromList [("a",1), ("b",3)])
-- insertLookup "c" 1 (fromList [("a",5), ("b",3)]) == (Nothing, fromList [("a",5), ("b",3), ("c",1)])
--
insertLookupWithKey :: CritBitKey k => (k -> v -> v -> v) -> k -> v -> CritBit k v -> (Maybe v, CritBit k v)
-- | O(k). Delete a key and its value from the map. When the key is
-- not a member of the map, the original map is returned.
--
--
-- delete "a" (fromList [("a",5), ("b",3)]) == singleton "b" 3
-- delete "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)]
-- delete "a" empty == empty
--
delete :: CritBitKey k => k -> CritBit k v -> CritBit k v
-- | O(k). Update a value at a specific key with the result of the
-- provided function. When the key is not a member of the map, the
-- original map is returned.
--
--
-- let f k x = x + 1
-- adjustWithKey f "a" (fromList [("b",3), ("a",5)]) == fromList [("a", 6), ("b",3)]
-- adjustWithKey f "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)]
-- adjustWithKey f "c" empty == empty
--
adjust :: CritBitKey k => (v -> v) -> k -> CritBit k v -> CritBit k v
-- | O(k). Adjust a value at a specific key. When the key is not a
-- member of the map, the original map is returned.
--
--
-- let f k x = x + fromEnum (k < "d")
-- adjustWithKey f "a" (fromList [("b",3), ("a",5)]) == fromList [("a", 6), ("b",3)]
-- adjustWithKey f "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)]
-- adjustWithKey f "c" empty == empty
--
adjustWithKey :: CritBitKey k => (k -> v -> v) -> k -> CritBit k v -> CritBit k v
-- | O(k). The expression (update f k map updates
-- the value x at k (if it is in the map). If (f
-- x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- y.
--
--
-- let f x = if x == 5 then Just 50 else Nothing
-- update f "a" (fromList [("b",3), ("a",5)]) == fromList [("a", 50), ("b",3)]
-- update f "c" (fromList [("b",3), ("a",5)]) == fromList [("a", 50), ("b",3)]
-- update f "b" (fromList [("b",3), ("a",5)]) == singleton "a" 5
--
update :: CritBitKey k => (v -> Maybe v) -> k -> CritBit k v -> CritBit k v
-- | O(log n). The expression (updateWithKey f k
-- map) updates the value x at k (if it is in the
-- map). If (f k x) is Nothing, the element is deleted.
-- If it is (Just y), the key k is bound to the
-- new value y.
--
--
-- let f k x = if x == 5 then Just (x + fromEnum (k < "d")) else Nothing
-- updateWithKey f "a" (fromList [("b",3), ("a",5)]) == fromList [("a", 6), ("b",3)]
-- updateWithKey f "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)]
-- updateWithKey f "b" (fromList [("a",5), ("b",3)]) == singleton "a" 5
--
updateWithKey :: CritBitKey k => (k -> v -> Maybe v) -> k -> CritBit k v -> CritBit k v
-- | O(k). Lookup and update; see also updateWithKey. This
-- function returns the changed value if it is updated, or the original
-- value if the entry is deleted.
--
--
-- let f k x = if x == 5 then Just (x + fromEnum (k < "d")) else Nothing
-- updateLookupWithKey f "a" (fromList [("b",3), ("a",5)]) == (Just 6, fromList [("a", 6), ("b",3)])
-- updateLookupWithKey f "c" (fromList [("a",5), ("b",3)]) == (Nothing, fromList [("a",5), ("b",3)])
-- updateLookupWithKey f "b" (fromList [("a",5), ("b",3)]) == (Just 3, singleton "a" 5)
--
updateLookupWithKey :: CritBitKey k => (k -> v -> Maybe v) -> k -> CritBit k v -> (Maybe v, CritBit k v)
-- | O(k). The expression (alter f k map) alters the
-- value x at k, or absence thereof. alter can
-- be used to insert, delete, or update a value in a CritBit. In
-- short : lookup k (alter f k m) = f (lookup k
-- m).
--
--
-- let f _ = Nothing
-- alter f "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3)]
-- alter f "a" (fromList [("a",5), ("b",3)]) == fromList [("b",3)]
--
-- let f _ = Just 1
-- alter f "c" (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",3), ("c",1)]
-- alter f "a" (fromList [(5,"a"), (3,"b")]) == fromList [("a",1), ("b",3)]
--
alter :: CritBitKey k => (Maybe v -> Maybe v) -> k -> CritBit k v -> CritBit k v
-- | O(n+m). The expression (union t1 t2) takes the
-- left-biased union of t1 and t2.
--
-- It prefers t1 when duplicate keys are encountered, i.e.
-- (union == unionWith const).
--
--
-- union (fromList [("a", 5), ("b", 3)]) (fromList [("a", 4), ("c", 7)]) == fromList [("a", 5), ("b", "3"), ("c", 7)]
--
union :: CritBitKey k => CritBit k v -> CritBit k v -> CritBit k v
-- | Union with a combining function.
--
--
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 5), ("b", 7)]
-- unionWith (+) l r == fromList [("A",5),("a",5),("b",10)]
--
unionWith :: CritBitKey k => (v -> v -> v) -> CritBit k v -> CritBit k v -> CritBit k v
-- | Union with a combining function.
--
--
-- let f key new_value old_value = byteCount key + new_value + old_value
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 5), ("C", 7)]
-- unionWithKey f l r == fromList [("A",5),("C",7),("a",5),("b",3)]
--
unionWithKey :: CritBitKey k => (k -> v -> v -> v) -> CritBit k v -> CritBit k v -> CritBit k v
-- | The union of a list of maps: (unions == foldl
-- union empty).
--
--
-- unions [(fromList [("a", 5), ("b", 3)]), (fromList [("a", 6), ("c", 7)]), (fromList [("a", 9), ("b", 5)])]
-- == fromList [("a", 5), ("b", 4), (c, 7)]
-- unions [(fromList [("a", 9), ("b", 8)]), (fromList [("ab", 5), ("c",7)]), (fromList [("a", 5), ("b", 3)])]
-- == fromList [("a", 9), ("ab", 5), ("b", 8), ("c", 7)]
--
unions :: CritBitKey k => [CritBit k v] -> CritBit k v
-- | The union of a list of maps, with a combining operation:
-- (unionsWith f == foldl (unionWith f)
-- empty).
--
--
-- unionsWith (+) [(fromList [("a",5), ("b", 3)]), (fromList [("a", 3), ("c", 7)]), (fromList [("a", 5), ("b", 5)])]
-- == fromList [("a", 12), ("b", 8), ("c")]
--
unionsWith :: CritBitKey k => (v -> v -> v) -> [CritBit k v] -> CritBit k v
unionL :: CritBitKey k => CritBit k v -> CritBit k v -> CritBit k v
unionR :: CritBitKey k => CritBit k v -> CritBit k v -> CritBit k v
-- | O(n+m). Difference of two maps. | Return data in the first map
-- not existing in the second map.
--
--
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 2), ("b", 7)]
-- difference l r == fromList [("a", 5)]
--
difference :: CritBitKey k => CritBit k v -> CritBit k w -> CritBit k v
-- | O(n+m). Difference with a combining function. | When two equal
-- keys are encountered, the combining function is applied | to the
-- values of theese keys. If it returns Nothing, the element is |
-- discarded (proper set difference). If it returns (Just
-- y), | the element is updated with a new value y.
--
--
-- let f av bv = if av == 3 then Just (av + bv) else Nothing
-- let l = fromList [(pack "a", 5), (pack "b", 3), (pack "c", 8)]
-- let r = fromList [(pack "a", 2), (pack "b", 7), (pack "d", 8)]
-- differenceWith f l r == fromList [(pack "b", 10), (pack "c", 8)]
--
differenceWith :: CritBitKey k => (v -> w -> Maybe v) -> CritBit k v -> CritBit k w -> CritBit k v
-- | O(n+m). Difference with a combining function. | When two equal
-- keys are encountered, the combining function is applied | to the key
-- and both values. If it returns Nothing, the element is |
-- discarded (proper set difference). If it returns (Just
-- y), | the element is updated with a new value y.
--
--
-- let f k av bv = if k == "b" then Just (length k + av + bv) else Nothing
-- let l = fromList [("a", 5), ("b", 3), ("c", 8)]
-- let r = fromList [("a", 2), ("b", 7), ("d", 8)]
-- differenceWithKey f l r == fromList [("b", 11), ("c", 8)]
--
differenceWithKey :: CritBitKey k => (k -> v -> w -> Maybe v) -> CritBit k v -> CritBit k w -> CritBit k v
-- | O(n+m). Intersection of two maps. | Return data in the first
-- map for the keys existing in both maps.
--
--
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 2), ("b", 7)]
-- intersection l r == fromList [("b", 3)]
--
intersection :: CritBitKey k => CritBit k v -> CritBit k w -> CritBit k v
-- | O(n+m). Intersection with a combining function.
--
--
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 2), ("b", 7)]
-- intersectionWith (+) l r == fromList [("b", 10)]
--
intersectionWith :: CritBitKey k => (v -> w -> x) -> CritBit k v -> CritBit k w -> CritBit k x
-- | O(n+m). Intersection with a combining function.
--
--
-- let f key new_value old_value = length key + new_value + old_value
-- let l = fromList [("a", 5), ("b", 3)]
-- let r = fromList [("A", 2), ("b", 7)]
-- intersectionWithKey f l r == fromList [("b", 11)]
--
intersectionWithKey :: CritBitKey k => (k -> v -> w -> x) -> CritBit k v -> CritBit k w -> CritBit k x
-- | O(n). Apply a function to all values.
--
--
-- map show (fromList [("b",5), ("a",3)]) == fromList [("b","5"), ("a","3")]
--
map :: CritBitKey k => (v -> w) -> CritBit k v -> CritBit k w
-- | O(n). Apply a function to all values.
--
--
-- let f key x = show key ++ ":" ++ show x
-- mapWithKey f (fromList [("a",5), ("b",3)]) == fromList [("a","a:5"), ("b","b:3")]
--
mapWithKey :: (k -> v -> w) -> CritBit k v -> CritBit k w
-- | O(n). traverseWithKey f s == fromList
-- $ traverse ((k, v) -> (,) k $ f k v)
-- (toList m)
--
-- That is, behaves exactly like a regular traverse except that
-- the traversing function also has access to the key associated with a
-- value.
--
--
-- let f key value = show key ++ ":" ++ show value
-- traverseWithKey (\k v -> if odd v then Just (f k v) else Nothing) (fromList [("a",3), ("b",5)]) == Just (fromList [("a","a:3"), ("b","b:5")])
-- traverseWithKey (\k v -> if odd v then Just (f k v) else Nothing) (fromList [("c", 2)]) == Nothing
--
traverseWithKey :: (CritBitKey k, Applicative t) => (k -> v -> t w) -> CritBit k v -> t (CritBit k w)
-- | O(n). The function mapAccum threads an accumulating
-- argument through the map in ascending order of keys.
--
--
-- let f a b = (a ++ show b, show b ++ "X")
-- mapAccum f "Everything: " (fromList [("a",5), ("b",3)]) == ("Everything: 53", fromList [("a","5X"), ("b","3X")])
--
mapAccum :: CritBitKey k => (a -> v -> (a, w)) -> a -> CritBit k v -> (a, CritBit k w)
-- | O(n). The function mapAccumWithKey threads an
-- accumulating argument through the map in ascending order of keys.
--
--
-- let f a k b = (a ++ " " ++ show k ++ "-" ++ show b, show b ++ "X")
-- mapAccumWithKey f "Everything: " (fromList [("a",5), ("b",3)]) == ("Everything: a-5 b-3", fromList [("a","5X"), ("b","3X")])
--
mapAccumWithKey :: CritBitKey k => (a -> k -> v -> (a, w)) -> a -> CritBit k v -> (a, CritBit k w)
-- | O(n). The function mapAccumRWithKey threads an
-- accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: CritBitKey k => (a -> k -> v -> (a, w)) -> a -> CritBit k v -> (a, CritBit k w)
-- | O(k). mapKeys f applies the function f to the
-- keys of the map.
--
-- If f maps multiple keys to the same new key, the new key is
-- associated with the value of the greatest of the original keys.
--
--
-- let f = fromString . (++ "1") . show
-- mapKeys f (fromList [("a", 5), ("b", 3)]) == fromList ([("a1", 5), ("b1", 3)])
-- mapKeys (\ _ -> "a") (fromList [("a", 5), ("b", 3)]) == singleton "a" 3
--
mapKeys :: CritBitKey k2 => (k1 -> k2) -> CritBit k1 v -> CritBit k2 v
-- | O(k). mapKeysWith c f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using c.
--
--
-- mapKeysWith (+) (\ _ -> "a") (fromList [("b",1), ("a",2), ("d",3), ("c",4)]) == singleton "a" 10
--
mapKeysWith :: CritBitKey k2 => (v -> v -> v) -> (k1 -> k2) -> CritBit k1 v -> CritBit k2 v
-- | O(k). mapKeysMonotonic f s == mapKeys f
-- s, but works only when f is strictly monotonic. That is,
-- for any values x and y, if x <
-- y then f x < f y. The precondition is
-- not checked. Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has slightly better performance than
-- mapKeys.
--
--
-- mapKeysMonotonic (\ k -> succ k) (fromList [("a",5), ("b",3)]) == fromList [("b",5), ("c",3)]
--
mapKeysMonotonic :: CritBitKey k => (a -> k) -> CritBit a v -> CritBit k v
-- | O(n). Fold the values in the map using the given
-- left-associative function, such that foldl f z ==
-- foldl f z . elems.
--
-- Examples:
--
--
-- elems = reverse . foldl (flip (:)) []
--
--
--
-- foldl (+) 0 (fromList [("a",5), ("bbb",3)]) == 8
--
foldl :: (a -> v -> a) -> a -> CritBit k v -> a
-- | O(n). Fold the values in the map using the given
-- right-associative function, such that foldr f z ==
-- foldr f z . elems.
--
-- Example:
--
--
-- elems map = foldr (:) [] map
--
foldr :: (v -> a -> a) -> a -> CritBit k v -> a
-- | O(n). Fold the keys and values in the map using the given
-- left-associative function, such that foldlWithKey f z ==
-- foldl (\z' (kx, x) -> f z' kx x) z .
-- toAscList.
--
-- Examples:
--
--
-- keys = reverse . foldlWithKey (\ks k x -> k:ks) []
--
--
--
-- let f result k a = result ++ "(" ++ show k ++ ":" ++ a ++ ")"
-- foldlWithKey f "Map: " (fromList [("a",5), ("b",3)]) == "Map: (b:3)(a:5)"
--
foldlWithKey :: (a -> k -> v -> a) -> a -> CritBit k v -> a
-- | O(n). Fold the keys and values in the map using the given
-- right-associative function, such that foldrWithKey f z ==
-- foldr (uncurry f) z . toAscList.
--
-- Examples:
--
--
-- keys map = foldrWithKey (\k x ks -> k:ks) [] map
--
--
--
-- let f k a result = result ++ "(" ++ show k ++ ":" ++ a ++ ")"
-- foldrWithKey f "Map: " (fromList [("a",5), ("b",3)]) == "Map: (a:5)(b:3)"
--
foldrWithKey :: (k -> v -> a -> a) -> a -> CritBit k v -> a
-- | O(n). A strict version of foldl. Each application of the
-- function is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldl' :: (a -> v -> a) -> a -> CritBit k v -> a
-- | O(n). A strict version of foldr. Each application of the
-- function is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (v -> a -> a) -> a -> CritBit k v -> a
-- | O(n). A strict version of foldlWithKey. Each application
-- of the function is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldlWithKey' :: (a -> k -> v -> a) -> a -> CritBit k v -> a
-- | O(n). A strict version of foldrWithKey. Each application
-- of the function is evaluated before using the result in the next
-- application. This function is strict in the starting value.
foldrWithKey' :: (k -> v -> a -> a) -> a -> CritBit k v -> a
-- | O(n). Return all the elements of the map in ascending order of
-- their keys.
--
--
-- elems (fromList [("b",5), ("a",3)]) == [3,5]
-- elems empty == []
--
elems :: CritBit k v -> [v]
-- | O(n). Return all keys of the map in ascending order.
--
--
-- keys (fromList [("b",5), ("a",3)]) == ["a","b"]
-- keys empty == []
--
keys :: CritBit k v -> [k]
-- | O(n). An alias for toAscList. Return all key/value pairs
-- in the map in ascending order.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: CritBit k v -> [(k, v)]
-- | O(n). Return set of all keys of the map.
--
--
-- keysSet (fromList [("b",5), ("a",3)]) == Set.fromList ["a", "b"]
-- keysSet empty == []
--
keysSet :: CritBit k v -> Set k
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
--
--
-- fromSet (\k -> length k) (Data.IntSet.fromList ["a", "bb"]) == fromList [("a",1), ("bb",2)]
-- fromSet undefined Data.IntSet.empty == empty
--
fromSet :: (k -> v) -> Set k -> CritBit k v
-- | O(n). Convert the map to a list of key/value pairs. The list
-- returned will be sorted in lexicographically ascending order.
--
--
-- toList (fromList [("b",3), ("a",5)]) == [("a",5),("b",3)]
-- toList empty == []
--
toList :: CritBit k v -> [(k, v)]
-- | O(k). Build a map from a list of key/value pairs. If the list
-- contains more than one value for the same key, the last value for the
-- key is retained.
--
--
-- fromList [] == empty
-- fromList [("a",5), ("b",3), ("a",2)] == fromList [("a",2), ("b",3)]
--
fromList :: CritBitKey k => [(k, v)] -> CritBit k v
-- | O(k). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWith.
--
--
-- fromListWith (+) [("a",5), ("b",5), ("b",3), ("a",3), ("a",5)] ==
-- fromList [("a",13), ("b",8)]
-- fromListWith (+) [] == empty
--
fromListWith :: CritBitKey k => (v -> v -> v) -> [(k, v)] -> CritBit k v
-- | O(k). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWithKey.
--
--
-- let f key a1 a2 = byteCount key + a1 + a2
-- fromListWithKey f [("a",5), ("b",5), ("b",3), ("a",3), ("a",5)] ==
-- fromList [("a",16), ("b",10)]
-- fromListWithKey f [] == empty
--
fromListWithKey :: CritBitKey k => (k -> v -> v -> v) -> [(k, v)] -> CritBit k v
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in ascending order.
--
--
-- toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--
toAscList :: CritBit k v -> [(k, v)]
-- | O(n). Convert the map to a list of key/value pairs where the
-- keys are in descending order.
--
--
-- toDescList (fromList [(5,"a"), (3,"b")]) == [(5,"a"), (3,"b")]
--
toDescList :: CritBit k v -> [(k, v)]
-- | O(n). Build a tree from an ascending list in linear time.
-- The precondition (input list is ascending) is not checked.
--
--
-- fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
-- valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True
-- valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromAscList :: CritBitKey k => [(k, a)] -> CritBit k a
-- | O(n). Build a tree from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
-- valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
-- valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
--
fromAscListWith :: CritBitKey k => (a -> a -> a) -> [(k, a)] -> CritBit k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
--
--
-- let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
-- fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
-- valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
-- valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
--
fromAscListWithKey :: CritBitKey k => (k -> a -> a -> a) -> [(k, a)] -> CritBit k a
-- | O(n). Build a tree from an ascending list of distinct elements
-- in linear time. The precondition is not checked.
--
--
-- fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- valid (fromDistinctAscList [(3,"b"), (5,"a")]) == True
-- valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False
--
fromDistinctAscList :: CritBitKey k => [(k, a)] -> CritBit k a
-- | O(n). Filter all values that satisfy the predicate.
--
--
-- filter (> "a") (fromList [("5","a"), ("3","b")]) == fromList [("3","b")]
-- filter (> "x") (fromList [("5","a"), ("3","b")]) == empty
-- filter (< "a") (fromList [("5","a"), ("3","b")]) == empty
--
filter :: (v -> Bool) -> CritBit k v -> CritBit k v
-- | O(n). Filter all keys/values that satisfy the predicate.
--
--
-- filterWithKey (\k _ -> k > "4") (fromList [("5","a"), ("3","b")]) == fromList[("5","a")]
--
filterWithKey :: (k -> v -> Bool) -> CritBit k v -> CritBit k v
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also split.
--
--
-- partition (> 4) (fromList [("a",5), ("b",3)]) == (fromList [("a",5)], fromList [("b",3)])
-- partition (< 6) (fromList [("a",5), ("b",3)]) == (fromList [("a",5), ("b",3)], empty)
-- partition (> 6) (fromList [("a",5), ("b",3)]) == (empty, fromList [("a",5), ("b",3)])
--
partition :: CritBitKey k => (v -> Bool) -> CritBit k v -> (CritBit k v, CritBit k v)
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also split.
--
--
-- partitionWithKey (\ k _ -> k < "b") (fromList [("a",5), ("b",3)]) == (fromList [("a",5)], fromList [("b",3)])
-- partitionWithKey (\ k _ -> k < "c") (fromList [(5,"a"), (3,"b")]) == (fromList [("a",5), ("b",3)], empty)
-- partitionWithKey (\ k _ -> k > "c") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [("a",5), ("b",3)])
--
partitionWithKey :: CritBitKey k => (k -> v -> Bool) -> CritBit k v -> (CritBit k v, CritBit k v)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == 5 then Just 10 else Nothing
-- mapMaybe f (fromList [("a",5), ("b",3)]) == singleton "a" 10
--
mapMaybe :: (a -> Maybe b) -> CritBit k a -> CritBit k b
-- | O(n). Map keys/values and collect the Just results.
--
--
-- let f k v = if k == "a" then Just ("k,v: " ++ show k ++ "," ++ show v) else Nothing
-- mapMaybeWithKey f (fromList [("a",5), ("b",3)]) == singleton "a" "k,v: \"a\",3"
--
mapMaybeWithKey :: (k -> v -> Maybe v') -> CritBit k v -> CritBit k v'
-- | O(n). Map values and separate the Left and Right
-- results.
--
--
-- let f a = if a < 5 then Left a else Right a
-- mapEither f (fromList [("a",5), ("b",3), ("x",1), ("z",7)])
-- == (fromList [("b",3), ("x",1)], fromList [("a",5), ("z",7)])
--
-- mapEither (\ a -> Right a) (fromList [("a",5), ("b",3), ("x",1), ("z",7)])
-- == (empty, fromList [("a",5), ("b",3), ("x",1), ("z",7)])
--
mapEither :: (a -> Either b c) -> CritBit k a -> (CritBit k b, CritBit k c)
-- | O(n). Map keys/values and separate the Left and
-- Right results.
--
--
-- let f k a = if k < "c" then Left (k ++ k) else Right (a * 2)
-- mapEitherWithKey f (fromList [("a",5), ("b",3), ("x",1), ("z",7)])
-- == (fromList [("a","aa"), ("b","bb")], fromList [("x",2), ("z",14)])
--
-- mapEitherWithKey (\_ a -> Right a) (fromList [("a",5), ("b",3), ("x",1), ("z",7)])
-- == (empty, fromList [("x",1), ("b",3), ("a",5), ("z",7)])
--
mapEitherWithKey :: (k -> v -> Either v1 v2) -> CritBit k v -> (CritBit k v1, CritBit k v2)
-- | O(k). The expression (split k map) is a pair
-- (map1,map2) where the keys in map1 are smaller than
-- k and the keys in map2 larger than k. Any
-- key equal to k is found in neither map1 nor
-- map2.
--
--
-- split "a" (fromList [("b",1), ("d",2)]) == (empty, fromList [("b",1), ("d",2)])
-- split "b" (fromList [("b",1), ("d",2)]) == (empty, singleton "d" 2)
-- split "c" (fromList [("b",1), ("d",2)]) == (singleton "b" 1, singleton "d" 2)
-- split "d" (fromList [("b",1), ("d",2)]) == (singleton "b" 1, empty)
-- split "e" (fromList [("b",1), ("d",2)]) == (fromList [("b",1), ("d",2)], empty)
--
split :: CritBitKey k => k -> CritBit k v -> (CritBit k v, CritBit k v)
-- | O(k). The expression (splitLookup k map) splits
-- a map just like split but also returns lookup k
-- map.
--
--
-- splitLookup "a" (fromList [("b",1), ("d",2)]) == (empty, Nothing, fromList [("b",1), ("d",2)])
-- splitLookup "b" (fromList [("b",1), ("d",2)]) == (empty, Just 1, singleton "d" 2)
-- splitLookup "c" (fromList [("b",1), ("d",2)]) == (singleton "b" 1, Nothing, singleton "d" 2)
-- splitLookup "d" (fromList [("b",1), ("d",2)]) == (singleton "b" 1, Just 2, empty)
-- splitLookup "e" (fromList [("b",1), ("d",2)]) == (fromList [("b",1), ("d",2)], Nothing, empty)
--
splitLookup :: CritBitKey k => k -> CritBit k v -> (CritBit k v, Maybe v, CritBit k v)
-- | O(n+m). This function is defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: (CritBitKey k, Eq v) => CritBit k v -> CritBit k v -> Bool
-- | O(n+m). The expression (isSubmapOfBy f t1 t2)
-- returns True if all keys in t1 are in map t2,
-- and when f returns True when applied to their
-- respective values. For example, the following expressions are all
-- True:
--
--
-- isSubmapOfBy (==) (fromList [("a",1)]) (fromList [("a",1),("b",2)])
-- isSubmapOfBy (<=) (fromList [("a",1)]) (fromList [("a",1),("b",2)])
-- isSubmapOfBy (==) (fromList [("a",1),("b",2)]) (fromList [("a",1),("b",2)])
--
--
-- But the following are all False:
--
--
-- isSubmapOfBy (==) (fromList [("a",2)]) (fromList [("a",1),("b",2)])
-- isSubmapOfBy (<) (fromList [("a",1)]) (fromList [("a",1),("b",2)])
-- isSubmapOfBy (==) (fromList [("a",1),("b",2)]) (fromList [("a",1)])
--
isSubmapOfBy :: CritBitKey k => (a -> b -> Bool) -> CritBit k a -> CritBit k b -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- Defined as (isProperSubmapOf = isProperSubmapOfBy
-- (==)).
isProperSubmapOf :: (CritBitKey k, Eq v) => CritBit k v -> CritBit k v -> Bool
-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
-- The expression (isProperSubmapOfBy f m1 m2) returns
-- True when m1 and m2 are not equal, all keys
-- in m1 are in m2, and when f returns
-- True when applied to their respective values. For example, the
-- following expressions are all True:
--
--
-- isProperSubmapOfBy (==) (fromList [("a",1)]) (fromList [("a",1),("b",2)])
-- isProperSubmapOfBy (<=) (fromList [("a",0)]) (fromList [("a",1),("b",2)])
--
--
-- But the following are all False:
--
--
-- isProperSubmapOfBy (==) (fromList [("a",1),("b",2)]) (fromList [("a",1),("b",2)])
-- isProperSubmapOfBy (==) (fromList ["a",1),("b",2)]) (fromList [("a",1)])
-- isProperSubmapOfBy (<) (fromList [("a",1)]) (fromList [("a",1),("b",2)])
--
isProperSubmapOfBy :: CritBitKey k => (a -> b -> Bool) -> CritBit k a -> CritBit k b -> Bool
-- | O(minimum K). The minimal key of the map. Calls error if
-- the map is empty.
--
--
-- findMin (fromList [("b",3), ("a",5)]) == ("a",5)
-- findMin empty Error: empty map has no minimal element
--
findMin :: CritBit k v -> (k, v)
-- | O(k). The maximal key of the map. Calls error if the map
-- is empty.
--
--
-- findMax empty Error: empty map has no minimal element
--
findMax :: CritBit k v -> (k, v)
-- | O(k'). Delete the minimal key. Returns an empty map if the map
-- is empty.
--
--
-- deleteMin (fromList [("a",5), ("b",3), ("c",7)]) == fromList [("b",3), ("c",7)]
-- deleteMin empty == empty
--
deleteMin :: CritBit k v -> CritBit k v
-- | O(k). Delete the maximal key. Returns an empty map if the map
-- is empty.
--
--
-- deleteMin (fromList [("a",5), ("b",3), ("c",7)]) == fromList [("a",5), ("b","3")]
-- deleteMin empty == empty
--
deleteMax :: CritBit k v -> CritBit k v
-- | O(k'). Delete and find the minimal element.
--
--
-- deleteFindMin (fromList [("a",5), ("b",3), ("c",10)]) == (("a",5), fromList[("b",3), ("c",10)])
-- deleteFindMin Error: can not return the minimal element of an empty map
--
deleteFindMin :: CritBit k v -> ((k, v), CritBit k v)
-- | O(k). Delete and find the maximal element.
--
--
-- deleteFindMax (fromList [("a",5), ("b",3), ("c",10)]) == (("c",10), fromList[("a",5), ("b",3)])
-- deleteFindMax Error: can not return the maximal element of an empty map
--
deleteFindMax :: CritBit k v -> ((k, v), CritBit k v)
-- | O(k'). Update the value at the minimal key.
--
--
-- updateMin (\ a -> Just (a + 7)) (fromList [("a",5), ("b",3)]) == fromList [("a",12), ("b",3)]
-- updateMin (\ _ -> Nothing) (fromList [("a",5), ("b",3)]) == fromList [("b",3)]
--
updateMin :: (v -> Maybe v) -> CritBit k v -> CritBit k v
-- | O(k). Update the value at the maximal key.
--
--
-- updateMax (\ a -> Just (a + 7)) (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",10)]
-- updateMax (\ _ -> Nothing) (fromList [("a",5), ("b",3)]) == fromList [("a",5)]
--
updateMax :: (v -> Maybe v) -> CritBit k v -> CritBit k v
-- | O(k'). Update the value at the minimal key.
--
--
-- updateMinWithKey (\ k a -> Just (length k + a)) (fromList [("a",5), ("b",3)]) == fromList [("a",6), ("b",3)]
-- updateMinWithKey (\ _ _ -> Nothing) (fromList [("a",5), ("b",3)]) == fromList [("b",3)]
--
updateMinWithKey :: (k -> v -> Maybe v) -> CritBit k v -> CritBit k v
-- | O(k). Update the value at the maximal key.
--
--
-- updateMaxWithKey (\ k a -> Just (length k + a)) (fromList [("a",5), ("b",3)]) == fromList [("a",5), ("b",4)]
-- updateMaxWithKey (\ _ _ -> Nothing) (fromList [("a",5), ("b",3)]) == fromList [("a",5)]
--
updateMaxWithKey :: (k -> v -> Maybe v) -> CritBit k v -> CritBit k v
-- | O(k'). Retrieves the value associated with minimal key of the
-- map, and the map stripped of that element, or Nothing if passed
-- an empty map.
--
--
-- minView (fromList [("a",5), ("b",3)]) == Just (5, fromList [("b",3)])
-- minView empty == Nothing
--
minView :: CritBit k v -> Maybe (v, CritBit k v)
-- | O(k). Retrieves the value associated with maximal key of the
-- map, and the map stripped of that element, or Nothing if passed
-- an empty map.
--
--
-- maxView (fromList [("a",5), ("b",3)]) == Just (3, fromList [("a",5)])
-- maxView empty == Nothing
--
maxView :: CritBit k v -> Maybe (v, CritBit k v)
-- | O(k'). Retrieves the minimal (key,value) pair of the map, and
-- the map stripped of that element, or Nothing if passed an empty
-- map.
--
--
-- minViewWithKey (fromList [("a",5), ("b",3)]) == Just (("a",5), fromList [("b",3)])
-- minViewWithKey empty == Nothing
--
minViewWithKey :: CritBit k v -> Maybe ((k, v), CritBit k v)
-- | O(k). Retrieves the maximal (key,value) pair of the map, and
-- the map stripped of that element, or Nothing if passed an empty
-- map.
--
--
-- maxViewWithKey (fromList [("a",5), ("b",3)]) == Just (("b",3), fromList [("a",5)])
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: CritBit k v -> Maybe ((k, v), CritBit k v)