Data.StableTree.Types

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 or Data.StableTree.IO are probably what you actually want to be using.

Documentation

class IsKey k where

Type class for anything that we can use as a key. The goal here is to wrap up a function that can generate a high-entropy eight-bit hash. Speed is somewhat important here, but since we only actually look at four bits of the hash, it really shouldn't be a problem to quickly generate sufficiently random data.

Implementors probably want to use hashSerialize, hashBinary, or hashByteString when writing their hash functions.

Methods

hash :: k -> Word8

Generate an 8-bit hash

Instances

IsKey Char

IsKey Double

IsKey Float

IsKey Int

IsKey Int8

IsKey Int16

IsKey Int32

IsKey Int64

IsKey Integer

IsKey Word

IsKey Word8

IsKey Word16

IsKey Word32

IsKey Word64

IsKey ByteString

IsKey ByteString

data Tree c k v where

The actual Rose Tree structure. StableTree is built on one main idea: every Key is either Terminal or Nonterminal. A complete Tree is one whose final element's Key is terminal, and the rest of the Keys are not (exept for two freebies at the beginning to guarantee convergence). A complete tree always has complete children.

If we don't have enough data to generate a complete tree (i.e. we ran out of elements before hitting a terminal key), then an Incomplete tree is generated. Incomplete trees are always contained by other incomplete trees, and a tree built from only the complete chlidren of an incomplete tree would never itself be complete.

It is easiest to understand how this structure promotes stability by looking at how trees typically work. The easiest tree to understand is a simple, well balanced, binary tree. In that case, we would have a structure like this:

       |D|
   |B|     |F|
 |A| |C| |E| |G|

Now, suppose that we want to delete the data stored in |A|. Then, we'll get a new structure that shares nothing in common with the original one:

       |E|
   |C|     |G|
 |B| |D| |F|

The entire tree had to be re-written. This structure is clearly unstable under mutation. Making the tree wider doesn't help much if the tree's size is changing. Simple updates to existing keys are handled well by branches with many children, but deleting from or adding to the beginning of the tree will always cause every single branch to change, which is what this structure is trying to avoid.

Instead, the stable tree branches have variable child counts. A branch is considered full when its highest key is terminal, which is determined by hashing the key and looking at some bits of the hash. I've found that a target branch size of 16 children works fairly well, so we check to see if the hash has its least-significant four bits set; if that's the case, the key is terminal. A branch gets two free children (meaning it doesn't care about whether the keys are temrinal or not), and then a run of nonterminal keys, and a final, terminal key. Under this scheme, inserting a new entry into a branch will probably mean inserting a nonterminal key, and it will probably be inserted into the run of nonterminal children. If that's the case, no neighbors will be affected, and only the parents will have to change to point to the new branch. Stability is acheived!

Constructors

Bottom :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Complete k v

Branch :: Depth -> (SomeKey k, ValueCount, Tree Complete k v) -> (SomeKey k, ValueCount, Tree Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree Complete k v) -> (Key Terminal k, ValueCount, Tree Complete k v) -> Tree Complete k v

IBottom0 :: Maybe (SomeKey k, v) -> Tree Incomplete k v

IBottom1 :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Incomplete k v

IBranch0 :: Depth -> (SomeKey k, ValueCount, Tree Incomplete k v) -> Tree Incomplete k v

IBranch1 :: Depth -> (SomeKey k, ValueCount, Tree Complete k v) -> Maybe (SomeKey k, ValueCount, Tree Incomplete k v) -> Tree Incomplete k v

IBranch2 :: Depth -> (SomeKey k, ValueCount, Tree Complete k v) -> (SomeKey k, ValueCount, Tree Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree Complete k v) -> Maybe (SomeKey k, ValueCount, Tree Incomplete k v) -> Tree Incomplete k v

Instances

(Ord k, Show k, Show v) => Show (Tree c k v)

data Complete

Used to indicate that a Tree is complete

data Incomplete

Used to indicate that a Tree is not complete

type Depth = Int

Alias to indicate how deep a branch in a tree is. Bottoms have depth 0

type ValueCount = Int

Alias that indicates the total number of values underneath a tree

nextBottom :: (Ord k, IsKey k) => Map k v -> Either (Tree Incomplete k v) (Tree 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.

nextBranch :: (Ord k, IsKey k) => Map k (Tree Complete k v) -> Maybe (k, Tree Incomplete k v) -> Either (Tree Incomplete k v) (Tree Complete k v, Map k (Tree Complete k v))

Generate a parent for a k/Tree map. A Right result gives a complete tree and the map updated to not have the key/trees that went into that tree. A Left result gives an incomplete tree that contains everything that the given map contained.

getKey :: Tree c k v -> Maybe k

Get the key of the first entry in this branch. If the branch is empty, returns Nothing.

completeKey :: Tree Complete k v -> k

Get the key of the fist entry in this complete branch. This function is total.

treeContents :: Ord k => Tree c k v -> Map k v

Convert an entire Tree into a k/v map.

branchContents :: Ord k => Tree c k v -> Either (Map k (ValueCount, Tree Complete k v), Maybe (k, ValueCount, Tree Incomplete k v)) (Map k v)

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.

getDepth :: Tree c k v -> Depth

Get the number of levels of branches that live below this one

getValueCount :: Tree c k v -> ValueCount

Get the number of actual values that live below this branch