-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | More general IntMap replacement. -- -- A version of IntMap that uses the Enum typeclass instead of Int. This -- is very nearly a direct copy of the IntMap package by Daan Leijen and -- Andriy Palamarchuk. The only change is coercing the package to accept -- anything with the Enum class constraint instead of forcing Int's. @package EnumMap @version 0.0.2 -- | An efficient implementation of maps from integer keys to values. -- -- Since many function names (but not the type name) clash with -- Prelude names, this module is usually imported -- qualified, e.g. -- -- 
--   import Data.EnumMap (EnumMap)
--   import qualified Data.EnumMap k as EnumMap
--
-- -- The implementation is based on big-endian patricia trees. This -- data structure performs especially well on binary operations like -- union and intersection. However, my benchmarks show that -- it is also (much) faster on insertions and deletions when compared to -- a generic size-balanced map implementation (see Data.Map). -- -- -- -- Operation comments contain the operation time complexity in the Big-O -- notation http://en.wikipedia.org/wiki/Big_O_notation. Many -- operations have a worst-case complexity of O(min(n,W)). This -- means that the operation can become linear in the number of elements -- with a maximum of W -- the number of bits in an Int (32 -- or 64). module Data.EnumMap -- | A map of integers to values a. data EnumMap k a type Key_ = Int -- | O(min(n,W)). Find the value at a key. Calls error when -- the element can not be found. -- -- 
--   fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
--   fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: (Show k, Enum k) => EnumMap k a -> k -> a -- | Same as difference. (\\) :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(1). Is the map empty? -- -- 
--   Data.EnumMap.null (empty)           == True
--   Data.EnumMap.null (singleton 1 'a') == False
--
null :: EnumMap k a -> Bool -- | O(n). Number of elements in the map. -- -- 
--   size empty                                   == 0
--   size (singleton 1 'a')                       == 1
--   size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: EnumMap k a -> Int -- | O(min(n,W)). Is the key a member of the map? -- -- 
--   member 5 (fromList [(5,'a'), (3,'b')]) == True
--   member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: Enum k => k -> EnumMap k a -> Bool -- | O(log n). Is the key not a member of the map? -- -- 
--   notMember 5 (fromList [(5,'a'), (3,'b')]) == False
--   notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: Enum k => k -> EnumMap k a -> Bool -- | O(min(n,W)). Lookup the value at a key in the map. See also -- Data.Map.lookup. lookup :: Enum k => k -> EnumMap k a -> Maybe a -- | O(min(n,W)). The expression (findWithDefault def k -- map) returns the value at key k or returns def -- when the key is not an element of the map. -- -- 
--   findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: Enum k => a -> k -> EnumMap k a -> a -- | O(1). The empty map. -- -- 
--   empty      == fromList []
--   size empty == 0
--
empty :: EnumMap k a -- | O(1). A map of one element. -- -- 
--   singleton 1 'a'        == fromList [(1, 'a')]
--   size (singleton 1 'a') == 1
--
singleton :: Enum k => k -> a -> EnumMap k a -- | O(min(n,W)). Insert a new key/value pair in the map. If the key -- is already present in the map, the associated value is replaced with -- the supplied value, i.e. insert is equivalent to -- insertWith const. -- -- 
--   insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
--   insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
--   insert 5 'x' empty                         == singleton 5 'x'
--
insert :: Enum k => k -> a -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). Insert with a combining function. -- insertWith f key value mp will insert the pair (key, -- value) into mp if key does not exist in the map. If the key -- does exist, the function will insert f new_value old_value. -- -- 
--   insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
--   insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
--
insertWith :: Enum k => (a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). Insert with a combining function. -- insertWithKey f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert f key new_value -- old_value. -- -- 
--   let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
--   insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
--
insertWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). 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 = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
--   insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
--   insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
--
-- -- This is how to define insertLookup using -- insertLookupWithKey: -- -- 
--   let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
--   insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
--   insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
--
insertLookupWithKey :: Enum k => (k -> a -> a -> a) -> k -> a -> EnumMap k a -> (Maybe a, EnumMap k a) -- | O(min(n,W)). 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 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   delete 5 empty                         == empty
--
delete :: Enum k => k -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). Adjust a value at a specific key. When the key is -- not a member of the map, the original map is returned. -- -- 
--   adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   adjust ("new " ++) 7 empty                         == empty
--
adjust :: Enum k => (a -> a) -> k -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). Adjust a value at a specific key. When the key is -- not a member of the map, the original map is returned. -- -- 
--   let f key x = (show key) ++ ":new " ++ x
--   adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   adjustWithKey f 7 empty                         == empty
--
adjustWithKey :: Enum k => (k -> a -> a) -> k -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). 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 == "a" then Just "new a" else Nothing
--   update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
update :: Enum k => (a -> Maybe a) -> k -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). The expression (update 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 == "a" then Just ((show k) ++ ":new a") else Nothing
--   updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateWithKey :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> EnumMap k a -- | O(min(n,W)). Lookup and update. The function returns original -- value, if it is updated. This is different behavior than -- Data.Map.updateLookupWithKey. Returns the original key value -- if the map entry is deleted. -- -- 
--   let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
--   updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--
updateLookupWithKey :: Enum k => (k -> a -> Maybe a) -> k -> EnumMap k a -> (Maybe a, EnumMap k a) -- | O(log n). 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 an EnumMap. -- In short : lookup k (alter f k m) = f (lookup -- k m). alter :: (Maybe a -> Maybe a) -> Int -> EnumMap k a -> EnumMap k a -- | O(n+m). The (left-biased) union of two maps. It prefers the -- first map when duplicate keys are encountered, i.e. (union -- == unionWith const). -- -- 
--   union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: Enum k => EnumMap k a -> EnumMap k a -> EnumMap k a -- | O(n+m). The union with a combining function. -- -- 
--   unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: Enum k => (a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k a -- | O(n+m). The union with a combining function. -- -- 
--   let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
--   unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--
unionWithKey :: Enum k => (k -> a -> a -> a) -> EnumMap k a -> EnumMap k a -> EnumMap k a -- | The union of a list of maps. -- -- 
--   unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--       == fromList [(3, "b"), (5, "a"), (7, "C")]
--   unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
--       == fromList [(3, "B3"), (5, "A3"), (7, "C")]
--
unions :: Enum k => [EnumMap k a] -> EnumMap k a -- | The union of a list of maps, with a combining operation. -- -- 
--   unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--       == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--
unionsWith :: Enum k => (a -> a -> a) -> [EnumMap k a] -> EnumMap k a -- | O(n+m). Difference between two maps (based on keys). -- -- 
--   difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(n+m). Difference with a combining function. -- -- 
--   let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
--   differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
--       == singleton 3 "b:B"
--
differenceWith :: Enum k => (a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap k a -- | 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 al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
--   differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
--       == singleton 3 "3:b|B"
--
differenceWithKey :: Enum k => (k -> a -> b -> Maybe a) -> EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(n+m). The (left-biased) intersection of two maps (based on -- keys). -- -- 
--   intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: Enum k => EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(n+m). The intersection with a combining function. -- -- 
--   intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: Enum k => (a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(n+m). The intersection with a combining function. -- -- 
--   let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
--   intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
--
intersectionWithKey :: Enum k => (k -> a -> b -> a) -> EnumMap k a -> EnumMap k b -> EnumMap k a -- | O(n). Map a function over all values in the map. -- -- 
--   map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: Enum k => (a -> b) -> EnumMap k a -> EnumMap k b -- | O(n). Map a function over all values in the map. -- -- 
--   let f key x = (show key) ++ ":" ++ x
--   mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: Enum k => (k -> a -> b) -> EnumMap k a -> EnumMap k b -- | O(n). The function mapAccum threads an -- accumulating argument through the map in ascending order of keys. -- -- 
--   let f a b = (a ++ b, b ++ "X")
--   mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--
mapAccum :: Enum k => (a -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c) -- | 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) ++ "-" ++ b, b ++ "X")
--   mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
--
mapAccumWithKey :: Enum k => (a -> k -> b -> (a, c)) -> a -> EnumMap k b -> (a, EnumMap k c) -- | O(n). Fold the values in the map, such that fold f z -- == foldr f z . elems. For example, -- -- 
--   elems map = fold (:) [] map
--
-- -- 
--   let f a len = len + (length a)
--   fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
fold :: Enum k => (a -> b -> b) -> b -> EnumMap k a -> b -- | O(n). Fold the keys and values in the map, such that -- foldWithKey f z == foldr (uncurry f) z . -- toAscList. For example, -- -- 
--   keys map = foldWithKey (\k x ks -> k:ks) [] map
--
-- -- 
--   let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
--
foldWithKey :: Enum k => (k -> a -> b -> b) -> b -> EnumMap k a -> b -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- -- 
--   elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
--   elems empty == []
--
elems :: Enum k => EnumMap k a -> [a] -- | O(n). Return all keys of the map in ascending order. -- -- 
--   keys (fromList [(5,"a"), (3,"b")]) == [3,5]
--   keys empty == []
--
keys :: Enum k => EnumMap k a -> [k] -- | O(n*min(n,W)). The set of all keys of the map. -- -- 
--   keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5]
--   keysSet empty == Data.IntSet.empty
--
keysSet :: Enum k => EnumMap k a -> IntSet -- | O(n). Return all key/value pairs in the map in ascending key -- order. -- -- 
--   assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--   assocs empty == []
--
assocs :: Enum k => EnumMap k a -> [(k, a)] -- | O(n). Convert the map to a list of key/value pairs. -- -- 
--   toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
--   toList empty == []
--
toList :: Enum k => EnumMap k a -> [(k, a)] -- | O(n*min(n,W)). Create a map from a list of key/value pairs. -- -- 
--   fromList [] == empty
--   fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
--   fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
--
fromList :: Enum k => [(k, a)] -> EnumMap k a -- | O(n*min(n,W)). Create a map from a list of key/value pairs with -- a combining function. See also fromAscListWith. -- -- 
--   fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
--   fromListWith (++) [] == empty
--
fromListWith :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k a -- | O(n*min(n,W)). Build a map from a list of key/value pairs with -- a combining function. See also fromAscListWithKey'. -- -- 
--   fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
--   fromListWith (++) [] == empty
--
fromListWithKey :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k a -- | 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 :: (Num k, Ord k, Enum k) => EnumMap k a -> [(k, a)] -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order. -- -- 
--   fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
--   fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
--
fromAscList :: Enum k => [(k, a)] -> EnumMap k a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order, with a combining function on equal -- keys. -- -- 
--   fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWith :: Enum k => (a -> a -> a) -> [(k, a)] -> EnumMap k a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order, with a combining function on equal -- keys. -- -- 
--   fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWithKey :: Enum k => (k -> a -> a -> a) -> [(k, a)] -> EnumMap k a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order and all distinct. -- -- 
--   fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
--
fromDistinctAscList :: Enum k => [(k, a)] -> EnumMap k a -- | O(n). Filter all values that satisfy some predicate. -- -- 
--   filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
--   filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
--
filter :: Enum k => (a -> Bool) -> EnumMap k a -> EnumMap k a -- | O(n). Filter all keys/values that satisfy some predicate. -- -- 
--   filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: Enum k => (k -> a -> Bool) -> EnumMap k a -> EnumMap k a -- | O(n). Partition the map according to some predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. -- -- 
--   partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
--   partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--
partition :: Enum k => (a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a) -- | O(n). Partition the map according to some 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 > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
--   partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--
partitionWithKey :: Enum k => (k -> a -> Bool) -> EnumMap k a -> (EnumMap k a, EnumMap k a) -- | O(n). Map values and collect the Just results. -- -- 
--   let f x = if x == "a" then Just "new a" else Nothing
--   mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: Enum k => (a -> Maybe b) -> EnumMap k a -> EnumMap k b -- | O(n). Map keys/values and collect the Just results. -- -- 
--   let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
--   mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: Enum k => (k -> a -> Maybe b) -> EnumMap k a -> EnumMap k b -- | O(n). Map values and separate the Left and Right -- results. -- -- 
--   let f a = if a < "c" then Left a else Right a
--   mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
--   
--   mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--
mapEither :: Enum k => (a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap k c) -- | O(n). Map keys/values and separate the Left and -- Right results. -- -- 
--   let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
--   mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
--   
--   mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
--
mapEitherWithKey :: Enum k => (k -> a -> Either b c) -> EnumMap k a -> (EnumMap k b, EnumMap k c) -- | O(log n). The expression (split k map) is a -- pair (map1,map2) where all keys in map1 are lower -- than k and all keys in map2 larger than k. -- Any key equal to k is found in neither map1 nor -- map2. -- -- 
--   split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
--   split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
--   split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
--   split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
--   split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
--
split :: Enum k => k -> EnumMap k a -> (EnumMap k a, EnumMap k a) -- | O(log n). Performs a split but also returns whether the -- pivot key was found in the original map. -- -- 
--   splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
--   splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
--   splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
--   splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
--   splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
--
splitLookup :: Enum k => k -> EnumMap k a -> (EnumMap k a, Maybe a, EnumMap k a) -- | O(n+m). Is this a submap? Defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Eq a, Enum k) => EnumMap k a -> EnumMap k a -> Bool -- | O(n+m). The expression (isSubmapOfBy f m1 m2) -- returns True if 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: -- -- 
--   isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--   isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--   isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
--
-- -- But the following are all False: -- -- 
--   isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)])
--   isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--   isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
--
isSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap k b -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- Defined as (isProperSubmapOf = isProperSubmapOfBy -- (==)). isProperSubmapOf :: (Enum k, Eq a) => EnumMap k a -> EnumMap k a -> 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 [(1,1)]) (fromList [(1,1),(2,2)])
--   isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
--
-- -- But the following are all False: -- -- 
--   isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
--   isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
--   isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
--
isProperSubmapOfBy :: Enum k => (a -> b -> Bool) -> EnumMap k a -> EnumMap k b -> Bool -- | O(log n). Retrieves the maximal key of the map, and the map -- stripped of that element, or Nothing if passed an empty map. maxView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a) -- | O(log n). Retrieves the minimal key of the map, and the map -- stripped of that element, or Nothing if passed an empty map. minView :: Enum k => EnumMap k a -> Maybe (a, EnumMap k a) -- | O(log n). The minimal key of the map. findMin :: Enum k => EnumMap k a -> a -- | O(log n). The maximal key of the map. findMax :: Enum k => EnumMap k a -> a -- | O(log n). Delete the minimal key. deleteMin :: Enum k => EnumMap k a -> EnumMap k a -- | O(log n). Delete the maximal key. deleteMax :: Enum k => EnumMap k a -> EnumMap k a -- | O(log n). Delete and find the minimal element. deleteFindMin :: Enum k => EnumMap k a -> (a, EnumMap k a) -- | O(log n). Delete and find the maximal element. deleteFindMax :: Enum k => EnumMap k a -> (a, EnumMap k a) -- | O(log n). Update the value at the minimal key. -- -- 
--   updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
--   updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateMin :: Enum k => (a -> a) -> EnumMap k a -> EnumMap k a -- | O(log n). Update the value at the maximal key. -- -- 
--   updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
--   updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--
updateMax :: Enum k => (a -> a) -> EnumMap k a -> EnumMap k a -- | O(log n). Update the value at the minimal key. -- -- 
--   updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
--   updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateMinWithKey :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap k a -- | O(log n). Update the value at the maximal key. -- -- 
--   updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
--   updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--
updateMaxWithKey :: Enum k => (k -> a -> a) -> EnumMap k a -> EnumMap k a -- | O(log n). 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 [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
--   minViewWithKey empty == Nothing
--
minViewWithKey :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap k a) -- | O(log n). 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 [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
--   maxViewWithKey empty == Nothing
--
maxViewWithKey :: Enum k => EnumMap k a -> Maybe ((k, a), EnumMap k a) -- | O(n). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. showTree :: Show a => EnumMap k a -> String -- | O(n). The expression (showTreeWith hang wide -- map) shows the tree that implements the map. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. showTreeWith :: Show a => Bool -> Bool -> EnumMap k a -> String instance Typeable1 (EnumMap k) instance (Read e, Read k, Enum k) => Read (EnumMap k e) instance (Show a, Show k, Enum k) => Show (EnumMap k a) instance Enum k => Functor (EnumMap k) instance (Ord k, Ord a, Enum k) => Ord (EnumMap k a) instance Eq a => Eq (EnumMap k a) instance (Data a, Data k, Enum k) => Data (EnumMap k a) instance Foldable (EnumMap k) instance Enum k => Monoid (EnumMap k a)