Data.StableTree.Build

This is the core implementation of the stable tree. The primary functions exported by this module are nextBottom and nextBranch, which gather values or lower-level Trees into Trees of the next level.

This module is fairly esoteric. Data.StableTree is probably what you actually want to be using.

Documentation

fromMap :: (Ord k, StableKey k) => Map k v -> StableTree k v

Convert a simple key/value map into a StableTree

empty :: (Ord k, StableKey k) => StableTree k v

Create a new empty StableTree

append :: (Ord k, StableKey k) => StableTree k v -> StableTree k v -> StableTree k v

Smash two StableTree instances into a single one

concat :: (Ord k, StableKey k) => [StableTree k v] -> StableTree k v

Smash a whole bunch of StableTree instances into a single one

consume :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> StableTree k v

Helper function to convert a complete bunch of Tree instances (of the same depth) into a single StableTree.

consumeMap :: (Ord k, StableKey k) => Map k v -> ([Tree Z Complete k v], Maybe (Tree Z Incomplete k v))

Convert a single key/value map into Tree bottom (zero-depth) instances. The resulting list of Tree instances will never be overlapping, and will be sorted such that each Tree's highest key is lower than the next Tree's lowest key. This is not guaranteed by types because i don't think that can be done in Haskell.

consumeBranches :: (Ord k, StableKey k) => Map k (Tree d Complete k v) -> Maybe (k, Tree d Incomplete k v) -> ([Tree (S d) Complete k v], Maybe (Tree (S d) Incomplete k v))

Given a mapping from each Tree's first key to that Tree, (and a final incomplete Tree if desired), this will build the next level of Tree instances. As with consumeMap, the resulting list of Tree instances will be non-overlapping and ordered such that each Tree's highest key is smaller than the next Tree's lowest key.

consumeBranches' :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> ([Tree (S d) Complete k v], Maybe (Tree (S d) Incomplete k v))

Given a simple listing of complete Trees and maybe an incomplete one, this will build the next level ot Trees. This just builds a map and calls the previous consumeBranches function, but it's a convenient function to have.

nextBottom :: (Ord k, StableKey k) => Map k v -> Either (Tree Z Incomplete k v) (Tree Z Complete k v, Map k v)

Wrap up some of a k/v map into a Tree. A Right result gives a complete tree and the map updated to not have the key/values that went into that tree. A Left result gives an incomplete tree that contains everything that the given map contained.

data NextBranch d k v

Result of the nextBranch function; values are described below.

Constructors

Empty

Final (Tree (S d) Incomplete k v)

More (Tree (S d) Complete k v) (Map k (Tree d Complete k v))

nextBranch :: (Ord k, StableKey k) => Map k (Tree d Complete k v) -> Maybe (k, Tree d Incomplete k v) -> NextBranch d k v

Generate a parent for a k/Tree map. An Empty result means that the function was called with an empty Map and Nothing for an incomplete. A Final result means that an incomplete Tree was build and there is no more work to be done. A More result means that a complete Tree was built, and there is (possibly) more work to do.

merge :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> ([Tree d Complete k v], Maybe (Tree d Incomplete k v))

Tree mutation functions (insert, delete) will generally wind up with a bunch of Trees that come before the key that was to be changed, and then the result of updating the relevant Tree, and then a bunch of Trees (and maybe an incomplete Tree) that come after it. Merge can splice this result back into a correctly ordered, non-overlapping list of complete Trees and maybe a final incomplete one.