-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Crit-bit maps and sets
--
-- Whee.
@package critbit
@version 0.0.0.0
-- | 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(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(log n). 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(log n). 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(log n). 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(log n). 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(log n). 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(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(log n). 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(log n). 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
union :: CritBitKey k => CritBit k 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). 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 keys of the map in ascending order.
--
--
-- keys (fromList [("b",5), ("a",3)]) == ["a","b"]
-- keys empty == []
--
keys :: CritBit k v -> [k]
-- | 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(n*log n). 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