Safe Haskell	None
Language	Haskell2010

Data.BTree.Impure.NonEmpty

Contents

Structures
Conversions
Construction
Inserting

Description

Non empty wrapper around the impure Tree.

Synopsis

Structures

data NonEmptyTree key val where Source #

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) Source #
Methods showsPrec :: Int -> NonEmptyTree key val -> ShowS # show :: NonEmptyTree key val -> String # showList :: [NonEmptyTree key val] -> ShowS #
Binary (NonEmptyTree key val) Source #
Methods put :: NonEmptyTree key val -> Put # get :: Get (NonEmptyTree key val) # putList :: [NonEmptyTree key val] -> Put #
(Value k, Value v) => Value (NonEmptyTree k v) Source #
Methods fixedSize :: Proxy * (NonEmptyTree k v) -> Maybe Int Source #

data Node height key val where Source #

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

Convert a Tree into a NonEmptyTree.

toTree :: NonEmptyTree key val -> Tree key val Source #

Convert a NonEmptyTree into a Tree.

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

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

Create a NonEmptyTree from a NonEmpty list.

Inserting

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

Insert an item into a NonEmptyTree

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

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