Portability | GHC |
---|---|

Stability | experimental |

Maintainer | bos@serpentine.com |

Safe Haskell | None |

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 2*n*-1 internal nodes and leaves.

- class Eq k => CritBitKey k where
- data CritBit k v
- null :: CritBit k v -> Bool
- size :: CritBit k v -> Int
- member :: CritBitKey k => k -> CritBit k v -> Bool
- notMember :: CritBitKey k => k -> CritBit k v -> Bool
- lookup :: CritBitKey k => k -> CritBit k v -> Maybe v
- findWithDefault :: CritBitKey k => v -> k -> CritBit k v -> v
- lookupGT :: CritBitKey k => k -> CritBit k v -> Maybe (k, v)
- empty :: CritBit k v
- singleton :: k -> v -> CritBit k v
- insert :: CritBitKey k => k -> v -> CritBit k v -> CritBit k v
- 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
- foldl :: (a -> v -> a) -> a -> CritBit k v -> a
- foldr :: (v -> a -> a) -> a -> CritBit k v -> a
- foldlWithKey :: (a -> k -> v -> a) -> a -> CritBit k v -> a
- foldrWithKey :: (k -> v -> a -> a) -> a -> CritBit k v -> a
- foldl' :: (a -> v -> a) -> a -> CritBit k v -> a
- foldr' :: (v -> a -> a) -> a -> CritBit k v -> a
- foldlWithKey' :: (a -> k -> v -> a) -> a -> CritBit k v -> a
- foldrWithKey' :: (k -> v -> a -> a) -> a -> CritBit k v -> a
- keys :: CritBit k v -> [k]
- toList :: CritBit k v -> [(k, v)]
- fromList :: CritBitKey k => [(k, v)] -> CritBit k v

# Types

class Eq k => CritBitKey k whereSource

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.

Return the number of bytes used by this key.

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

getByte :: k -> Int -> Word16Source

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)*.

A crit-bit tree.

# Operators

# Query

null :: CritBit k v -> BoolSource

*O(1)*. Is the map empty?

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

size :: CritBit k v -> IntSource

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

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

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

*O(log n)*. Lookup the value at a key in the map.

The function will return the corresponding value as `(`

,
or `Just`

value)`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

:: 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)Source

*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

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

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

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

*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

## Difference

## Intersection

# Traversal

## Map

# Folds

foldlWithKey :: (a -> k -> v -> a) -> a -> CritBit k v -> aSource

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

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

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

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

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

*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]Source

*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)]Source

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

*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)]