| Copyright | Jeremy Groven |
|---|---|
| License | BSD3 |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.StableTree.Properties
Description
Various functions for getting interested data about StableTrees and
Trees.
- getKey :: Tree d c k v -> Maybe k
- completeKey :: Tree d Complete k v -> k
- size :: StableTree k v -> ValueCount
- lookup :: Ord k => k -> StableTree k v -> Maybe v
- keys :: Ord k => StableTree k v -> [k]
- elems :: Ord k => StableTree k v -> [v]
- assocs :: Ord k => StableTree k v -> [(k, v)]
- treeContents :: Ord k => Tree d c k v -> Map k v
- toMap :: Ord k => StableTree k v -> Map k v
- stableChildren :: Ord k => StableTree k v -> Either (Map k v) (Map k (ValueCount, StableTree k v))
- bottomChildren :: Ord k => Tree Z c k v -> Map k v
- branchChildren :: Ord k => Tree (S d) c k v -> (Map k (ValueCount, Tree d Complete k v), Maybe (k, ValueCount, Tree d Incomplete k v))
- selectNode :: Ord k => k -> Tree (S d) c k v -> Either ([Tree d Complete k v], Tree d Incomplete k v) ([Tree d Complete k v], Tree d Complete k v, [Tree d Complete k v], Maybe (Tree d Incomplete k v))
Documentation
getKey :: Tree d c k v -> Maybe k Source
Get the key of the first entry in this branch. If the branch is empty, returns Nothing.
completeKey :: Tree d Complete k v -> k Source
Get the key of the first entry in this complete branch. This function is total.
size :: StableTree k v -> ValueCount Source
Get the total number of k/v pairs in the tree
lookup :: Ord k => k -> StableTree k v -> Maybe v Source
Get the value associated with the given key, or Nothing if there is no value for the key.
keys :: Ord k => StableTree k v -> [k] Source
Get the keys in the map
elems :: Ord k => StableTree k v -> [v] Source
Get the elements stored in the map
assocs :: Ord k => StableTree k v -> [(k, v)] Source
Get the key/value pairs in the map
treeContents :: Ord k => Tree d c k v -> Map k v Source
Convert an entire Tree into a k/v map.
toMap :: Ord k => StableTree k v -> Map k v Source
Convert a StableTree into a normal key/value Map
stableChildren :: Ord k => StableTree k v -> Either (Map k v) (Map k (ValueCount, StableTree k v)) Source
Either get the StableTree "children" of a StableTree, or get the
key/value map if the tree is already a bottom.
bottomChildren :: Ord k => Tree Z c k v -> Map k v Source
Non-recursive function to simply get the immediate children of the given branch. This will either give the keyvalue map of a Bottom, or the keytree map of a non-bottom branch.
branchChildren :: Ord k => Tree (S d) c k v -> (Map k (ValueCount, Tree d Complete k v), Maybe (k, ValueCount, Tree d Incomplete k v)) Source
Get the Trees stored under the given Tree. The Tree type prevents this
function from being called on bottom Trees.
selectNode :: Ord k => k -> Tree (S d) c k v -> Either ([Tree d Complete k v], Tree d Incomplete k v) ([Tree d Complete k v], Tree d Complete k v, [Tree d Complete k v], Maybe (Tree d Incomplete k v)) Source
Choose the child node most likely to hold the given key. If this returns
Left, then the chosen node is the Incomplete node. In the Right case, the
sole Complete node is the best node. The Complete nodes in the first slot of
the quad are the nodes that came before the chosen node, while the nodes in
the third slot are the nodes that came after. This is useful for changing a
specific node, and then patching things back together with the
merge function.