Data.CritBit.Map.Lazy

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.

Types

class Eq k => CritBitKey k where

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.

Methods

byteCount :: k -> Int

Return the number of bytes used by this key.

For reasonable performance, implementations must be inlined and O(1).

getByte :: k -> Int -> Word16

Return the byte at the given offset (counted in bytes) of this key, bitwise-ORed with 256. If the offset is past the end of the key, return zero.

For reasonable performance, implementations must be inlined and O(1).

Instances

CritBitKey ByteString

CritBitKey Text

data CritBit k v

A crit-bit tree.

Instances

(Eq k, Eq v) => Eq (CritBit k v)

(Show k, Show v) => Show (CritBit k v)

(NFData k, NFData v) => NFData (CritBit k v)

Operators

Query

null :: CritBit k v -> Bool

O(1). Is the map empty?

 null (empty)           == True
 null (singleton 1 'a') == False

size :: CritBit k v -> Int

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

member :: CritBitKey k => k -> CritBit k v -> Bool

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.

notMember :: 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.

lookup :: CritBitKey k => k -> CritBit k v -> Maybe v

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

findWithDefault

Arguments

:: CritBitKey k

=> v

Default value to return if lookup fails.

-> k

-> CritBit k v

-> 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

lookupGT :: CritBitKey k => k -> CritBit k v -> Maybe (k, 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

Construction

empty :: CritBit k v

O(1). The empty map.

 empty      == fromList []
 size empty == 0

singleton :: k -> v -> CritBit k v

O(1). A map with a single element.

 singleton "a" 1        == fromList [("a", 1)]

Insertion

insert :: CritBitKey k => k -> v -> CritBit 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

Deletion

delete :: CritBitKey k => k -> 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

Combination

Union

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

Difference

Intersection

Traversal

Map

Folds

foldl :: (a -> v -> a) -> a -> CritBit k v -> a

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

foldr :: (v -> a -> 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

foldlWithKey :: (a -> k -> v -> 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)"

foldrWithKey :: (k -> v -> a -> 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)"

Strict folds

foldl' :: (a -> v -> 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.

foldr' :: (v -> a -> 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.

foldlWithKey' :: (a -> k -> v -> 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.

foldrWithKey' :: (k -> v -> a -> 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.

Conversion

keys :: CritBit k v -> [k]

O(n). Return all keys of the map in ascending order.

 keys (fromList [("b",5), ("a",3)]) == ["a","b"]
 keys empty == []

Lists

toList :: CritBit k v -> [(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 == []

fromList :: CritBitKey k => [(k, v)] -> CritBit 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)]

Ordered lists

Filter

Submap