Data.BTree.Impure.NonEmpty

Non empty wrapper around the impure Tree.

Structures

data NonEmptyTree key val where

A non-empty variant of Tree.

Constructors

NonEmptyTree :: {..} -> NonEmptyTree key val

Fields

• treeHeight :: Height height

  A term-level witness for the type-level height index.

• treeRootId :: NodeId height key val

  An empty tree is represented by Nothing. Otherwise it's Just a NodeId pointer the root.

Instances

(Show key, Show val) => Show (NonEmptyTree key val)

Methods

showsPrec :: Int -> NonEmptyTree key val -> ShowS

show :: NonEmptyTree key val -> String

showList :: [NonEmptyTree key val] -> ShowS

Binary (NonEmptyTree key val)

Methods

put :: NonEmptyTree key val -> Put

get :: Get (NonEmptyTree key val)

putList :: [NonEmptyTree key val] -> Put

(Value k, Value v) => Value (NonEmptyTree k v)

Methods

fixedSize :: Proxy * (NonEmptyTree k v) -> Maybe Int

data Node height key val where

A node in a B+-tree.

Nodes are parameterized over the key and value types and are additionally indexed by their height. All paths from the root to the leaves have the same length. The height is the number of edges from the root to the leaves, i.e. leaves are at height zero and index nodes increase the height.

Sub-trees are represented by a NodeId that are used to resolve the actual storage location of the sub-tree node.

Constructors

Idx :: {..} -> Node (S height) key val

Fields

• idxChildren :: Index key (NodeId height key val)

Leaf :: {..} -> Node Z key val

Fields

• leafItems :: LeafItems key val

Instances

(Eq key, Eq val) => Eq (Node height key val)

Methods

(==) :: Node height key val -> Node height key val -> Bool

(/=) :: Node height key val -> Node height key val -> Bool

(Show key, Show val) => Show (Node height key val)

Methods

showsPrec :: Int -> Node height key val -> ShowS

show :: Node height key val -> String

showList :: [Node height key val] -> ShowS

Conversions

fromTree :: Tree key val -> Maybe (NonEmptyTree key val)

Convert a Tree into a NonEmptyTree.

toTree :: NonEmptyTree key val -> Tree key val

Convert a NonEmptyTree into a Tree.

nonEmptyToList :: (AllocReaderM m, Key k, Value v) => NonEmptyTree k v -> m (NonEmpty (k, v))

Convert a non-empty tree to a list of key-value pairs.

Construction

fromNonEmptyList :: (AllocM m, Key k, Value v) => NonEmpty (k, v) -> m (NonEmptyTree k v)

Create a NonEmptyTree from a NonEmpty list.

Inserting

insertNonEmptyTree :: (AllocM m, Key k, Value v) => k -> v -> NonEmptyTree k v -> m (NonEmptyTree k v)

Insert an item into a NonEmptyTree

insertNonEmptyTreeMany :: (AllocM m, Key k, Value v) => Map k v -> NonEmptyTree k v -> m (NonEmptyTree k v)

Bulk insert a bunch of key-value pairs into a NonEmptyTree.