Data.BTree.Primitives.Index

Documentation

data Index key node

The Index encodes the internal structure of an index node.

The index is abstracted over the type node of sub-trees. The keys and nodes are stored in separate Vectors and the keys are sorted in strictly increasing order. There should always be one more sub-tree than there are keys. Hence structurally the smallest Index has one sub-tree and no keys, but a valid B+-tree index node will have at least two sub-trees and one key.

Constructors

Index !(Vector key) !(Vector node)

Instances

Functor (Index key)

Methods

fmap :: (a -> b) -> Index key a -> Index key b

(<$) :: a -> Index key b -> Index key a

Foldable (Index key)

Methods

fold :: Monoid m => Index key m -> m

foldMap :: Monoid m => (a -> m) -> Index key a -> m

foldr :: (a -> b -> b) -> b -> Index key a -> b

foldr' :: (a -> b -> b) -> b -> Index key a -> b

foldl :: (b -> a -> b) -> b -> Index key a -> b

foldl' :: (b -> a -> b) -> b -> Index key a -> b

foldr1 :: (a -> a -> a) -> Index key a -> a

foldl1 :: (a -> a -> a) -> Index key a -> a

toList :: Index key a -> [a]

null :: Index key a -> Bool

length :: Index key a -> Int

elem :: Eq a => a -> Index key a -> Bool

maximum :: Ord a => Index key a -> a

minimum :: Ord a => Index key a -> a

sum :: Num a => Index key a -> a

product :: Num a => Index key a -> a

Traversable (Index key)

Methods

traverse :: Applicative f => (a -> f b) -> Index key a -> f (Index key b)

sequenceA :: Applicative f => Index key (f a) -> f (Index key a)

mapM :: Monad m => (a -> m b) -> Index key a -> m (Index key b)

sequence :: Monad m => Index key (m a) -> m (Index key a)

(Eq node, Eq key) => Eq (Index key node)

Methods

(==) :: Index key node -> Index key node -> Bool

(/=) :: Index key node -> Index key node -> Bool

(Show node, Show key) => Show (Index key node)

Methods

showsPrec :: Int -> Index key node -> ShowS

show :: Index key node -> String

showList :: [Index key node] -> ShowS

(Binary k, Binary n) => Binary (Index k n)

Methods

put :: Index k n -> Put

get :: Get (Index k n)

putList :: [Index k n] -> Put

indexNumKeys :: Index key val -> Int

Return the number of keys in this Index.

indexNumVals :: Index key val -> Int

Return the number of values stored in this Index.

validIndex :: Ord key => Index key node -> Bool

Validate the key/node count invariant of an Index.

validIndexSize :: Ord key => Int -> Int -> Index key node -> Bool

Validate the size of an Index.

splitIndexAt :: Int -> Index key val -> (Index key val, key, Index key val)

Split an index node.

This function splits an index node into two new nodes at the given key position numLeftKeys and returns the resulting indices and the key separating them. Eventually this should take the binary size of serialized keys and sub-tree pointers into account. See also splitLeaf in Data.BTree.Primitives.Leaf.

extendedIndex :: Int -> (Index k b -> a) -> Index k b -> Index k a

Split an index many times.

This function splits an Index node into smaller pieces. Each resulting sub-Index has between maxIdxKeys/2 and maxIdxKeys inclusive values and is additionally applied to the function f.

This is the dual of a monadic bind and is also known as the extended function of extendable functors. See Data.Functor.Extend in the "semigroupoids" package.

bindIndex (extendedIndex n id idx) id == idx

extendIndexPred :: (a -> Bool) -> (Index k b -> a) -> Index k b -> Maybe (Index k a)

mergeIndex :: Index key val -> key -> Index key val -> Index key val

Merge two indices.

Merge two indices leftIndex, rightIndex given a discriminating key middleKey, i.e. such that '∀ (k,v) ∈ leftIndex. k < middleKey' and '∀ (k,v) ∈ rightIndex. middleKey <= k'.

mergeIndex is a partial inverse of splitIndex, i.e. prop> splitIndex is == (left,mid,right) => mergeIndex left mid right == is

indexFromList :: [key] -> [val] -> Index key val

Create an index from key-value lists.

The internal invariants of the Index data structure apply. That means there is one more value than there are keys and keys are ordered in strictly increasing order.

singletonIndex :: val -> Index key val

Create an index with a single value.

fromSingletonIndex :: Index key val -> Maybe val

Test if the index consists of a single value.

Returns the element if the index is a singleton. Otherwise fails.

fromSingletonIndex (singletonIndex val) == Just val

bindIndex :: Index k a -> (a -> Index k b) -> Index k b

Bind an index

bindIndex idx singletonIndex == idx

bindIndexM :: (Functor m, Monad m) => Index k a -> (a -> m (Index k b)) -> m (Index k b)

data IndexCtx key val

Representation of one-hole contexts of Index.

Just one val removes. All keys are present.

V.length leftVals  == V.length lefyKeys

V.length rightVals == V.length rightKeys

Constructors

IndexCtx

Fields

• indexCtxLeftKeys :: !(Vector key)
• indexCtxRightKeys :: !(Vector key)
• indexCtxLeftVals :: !(Vector val)
• indexCtxRightVals :: !(Vector val)

Instances

Functor (IndexCtx key)

Methods

fmap :: (a -> b) -> IndexCtx key a -> IndexCtx key b

(<$) :: a -> IndexCtx key b -> IndexCtx key a

Foldable (IndexCtx key)

Methods

fold :: Monoid m => IndexCtx key m -> m

foldMap :: Monoid m => (a -> m) -> IndexCtx key a -> m

foldr :: (a -> b -> b) -> b -> IndexCtx key a -> b

foldr' :: (a -> b -> b) -> b -> IndexCtx key a -> b

foldl :: (b -> a -> b) -> b -> IndexCtx key a -> b

foldl' :: (b -> a -> b) -> b -> IndexCtx key a -> b

foldr1 :: (a -> a -> a) -> IndexCtx key a -> a

foldl1 :: (a -> a -> a) -> IndexCtx key a -> a

toList :: IndexCtx key a -> [a]

null :: IndexCtx key a -> Bool

length :: IndexCtx key a -> Int

elem :: Eq a => a -> IndexCtx key a -> Bool

maximum :: Ord a => IndexCtx key a -> a

minimum :: Ord a => IndexCtx key a -> a

sum :: Num a => IndexCtx key a -> a

product :: Num a => IndexCtx key a -> a

Traversable (IndexCtx key)

Methods

traverse :: Applicative f => (a -> f b) -> IndexCtx key a -> f (IndexCtx key b)

sequenceA :: Applicative f => IndexCtx key (f a) -> f (IndexCtx key a)

mapM :: Monad m => (a -> m b) -> IndexCtx key a -> m (IndexCtx key b)

sequence :: Monad m => IndexCtx key (m a) -> m (IndexCtx key a)

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

Methods

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

show :: IndexCtx key val -> String

showList :: [IndexCtx key val] -> ShowS

putVal :: IndexCtx key val -> val -> Index key val

putIdx :: IndexCtx key val -> Index key val -> Index key val

valView :: Ord key => key -> Index key val -> (IndexCtx key val, val)

valViewMin :: Index key val -> (IndexCtx key val, val)

valViewMax :: Index key val -> (IndexCtx key val, val)

distribute :: Ord k => Map k v -> Index k node -> Index k (Map k v, node)

Distribute a map of key-value pairs over an index.

leftView :: IndexCtx key val -> Maybe (IndexCtx key val, val, key)

rightView :: IndexCtx key val -> Maybe (key, val, IndexCtx key val)