-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | B+-tree implementation in Haskell.
--   
--   This package provides two B+-tree implementations. The first one is a
--   pure B+-tree of a specific order, while the second one is an impure
--   one backed by a page allocator.
--   
--   For more information on how to use this package, visit
--   <a>https://github.com/haskell-haskey/haskey-btree</a>
@package haskey-btree
@version 0.3.0.0


-- | Setup of an impure B+-tree
module Data.BTree.Impure.Internal.Setup
minFanout :: Int
minLeafItems :: Int
minIdxKeys :: Int


-- | A collection of exceptions that can be raised in the pure algorithms
--   in <a>Data.BTree.Primitives</a>, <a>Data.BTree.Impure</a> and
--   <a>Data.BTree.Pure</a>.
module Data.BTree.Primitives.Exception

-- | Throw an exception. Exceptions may be thrown from purely functional
--   code, but may only be caught within the <a>IO</a> monad.
throw :: Exception e => e -> a

-- | An exception raised when the pure modification algorithms are called
--   using invalid state.
--   
--   This exception is only raised when a the library contains a bug.
--   
--   The first argument is a function name indicating the location of the
--   error. The second argument is the description of the error.
data TreeAlgorithmError
TreeAlgorithmError :: String -> String -> TreeAlgorithmError

-- | An exception thrown when the keys inserted in the database are larger
--   than <a>maxKeySize</a>.
--   
--   Note that this exception can be thrown long after the key violating
--   the maximum key size was inserted. It is only detected when the tree
--   modification algorithms try to split the node containing that key.
--   
--   Increase the page size to fix this problem.
data KeyTooLargeError
KeyTooLargeError :: KeyTooLargeError
instance GHC.Show.Show Data.BTree.Primitives.Exception.KeyTooLargeError
instance GHC.Exception.Exception Data.BTree.Primitives.Exception.KeyTooLargeError
instance GHC.Show.Show Data.BTree.Primitives.Exception.TreeAlgorithmError
instance GHC.Exception.Exception Data.BTree.Primitives.Exception.TreeAlgorithmError

module Data.BTree.Primitives.Height
data Nat
Z :: Nat
S :: Nat -> Nat
newtype Height (h :: Nat)
Height :: Word8 -> Height
[fromHeight] :: Height -> Word8
zeroHeight :: Height  'Z
incrHeight :: Height h -> Height ( 'S h)
decrHeight :: Height ( 'S h) -> Height h
data UHeight (height :: Nat) :: *
[UZero] :: UHeight  'Z
[USucc] :: Height height -> UHeight ( 'S height)
viewHeight :: Height height -> UHeight height
instance GHC.Classes.Ord (Data.BTree.Primitives.Height.Height h)
instance GHC.Classes.Eq (Data.BTree.Primitives.Height.Height h)
instance Data.Binary.Class.Binary (Data.BTree.Primitives.Height.Height h)
instance GHC.Show.Show (Data.BTree.Primitives.Height.Height h)

module Data.BTree.Primitives.Value
class (Binary v, Show v, Typeable v) => Value v

-- | <a>Just</a> with the size in bytes if <tt>v</tt> is a fixed sized
--   value, <a>Nothing</a> if <tt>v</tt> is variable sized.
fixedSize :: Value v => Proxy v -> Maybe Int
instance Data.BTree.Primitives.Value.Value ()
instance Data.BTree.Primitives.Value.Value GHC.Types.Bool
instance Data.BTree.Primitives.Value.Value GHC.Types.Char
instance Data.BTree.Primitives.Value.Value GHC.Types.Double
instance Data.BTree.Primitives.Value.Value GHC.Types.Float
instance Data.BTree.Primitives.Value.Value GHC.Int.Int8
instance Data.BTree.Primitives.Value.Value GHC.Int.Int16
instance Data.BTree.Primitives.Value.Value GHC.Int.Int32
instance Data.BTree.Primitives.Value.Value GHC.Int.Int64
instance Data.BTree.Primitives.Value.Value GHC.Word.Word8
instance Data.BTree.Primitives.Value.Value GHC.Word.Word16
instance Data.BTree.Primitives.Value.Value GHC.Word.Word32
instance Data.BTree.Primitives.Value.Value GHC.Word.Word64
instance Data.BTree.Primitives.Value.Value Data.ByteString.Internal.ByteString
instance Data.BTree.Primitives.Value.Value GHC.Integer.Type.Integer
instance Data.BTree.Primitives.Value.Value Data.Text.Internal.Text
instance (Data.BTree.Primitives.Value.Value k1, Data.BTree.Primitives.Value.Value k2) => Data.BTree.Primitives.Value.Value (k1, k2)
instance Data.BTree.Primitives.Value.Value v => Data.BTree.Primitives.Value.Value [v]

module Data.BTree.Primitives.Key
class (Ord k, Value k) => Key k

-- | Given two keys <tt>a</tt>, <tt>b</tt> such that 'a &lt; b' compute two
--   new keys <tt>a2</tt>, <tt>b2</tt> such that 'a &lt;= a2 &lt; b2 &lt;=
--   b'. Obviously this always holds for 'a2 == a' and 'b2 = b' but for
--   <a>ByteString</a>s we can potentially find smaller <tt>a2</tt> and
--   <tt>b2</tt>. If <tt>a</tt> equals <tt>b</tt>, the behaviour is
--   undefined.
narrow :: Key k => k -> k -> (k, k)
instance Data.BTree.Primitives.Key.Key ()
instance Data.BTree.Primitives.Key.Key GHC.Types.Bool
instance Data.BTree.Primitives.Key.Key GHC.Types.Double
instance Data.BTree.Primitives.Key.Key GHC.Types.Float
instance Data.BTree.Primitives.Key.Key GHC.Int.Int8
instance Data.BTree.Primitives.Key.Key GHC.Int.Int16
instance Data.BTree.Primitives.Key.Key GHC.Int.Int32
instance Data.BTree.Primitives.Key.Key GHC.Int.Int64
instance Data.BTree.Primitives.Key.Key GHC.Integer.Type.Integer
instance Data.BTree.Primitives.Key.Key Data.Text.Internal.Text
instance Data.BTree.Primitives.Key.Key GHC.Word.Word8
instance Data.BTree.Primitives.Key.Key GHC.Word.Word16
instance Data.BTree.Primitives.Key.Key GHC.Word.Word32
instance Data.BTree.Primitives.Key.Key GHC.Word.Word64
instance Data.BTree.Primitives.Key.Key Data.ByteString.Internal.ByteString
instance (Data.BTree.Primitives.Key.Key a, Data.BTree.Primitives.Key.Key b) => Data.BTree.Primitives.Key.Key (a, b)

module Data.BTree.Primitives.Ids

-- | Reference to a stored page.
newtype PageId
PageId :: Word64 -> PageId
[fromPageId] :: PageId -> Word64

-- | Reference to a stored overflow page.
--   
--   An overflow id is the combination of the transaction id that generated
--   it, and a counter.
type OverflowId = (TxId, Word32)

-- | Type used to indicate the size of storage pools.
newtype PageCount
PageCount :: Word64 -> PageCount
[fromPageCount] :: PageCount -> Word64

-- | Type used to indicate the size of a single physical page in bytes.
newtype PageSize
PageSize :: Word32 -> PageSize
[fromPageSize] :: PageSize -> Word32

-- | Reference to a stored <tt>Node</tt>.
--   
--   <a>NodeId</a> has phantom type arguments for the parameters of
--   <tt>Node</tt> to be able to enforce consistency. In a setting with a
--   single storage pool this <tt>Id</tt> will essentially be a
--   <a>PageId</a> with just the extra typing. In a multi storage pool
--   setting <a>NodeId</a>s will additionally have to be resolved to
--   <a>PageId</a>s by the node allocator.
newtype NodeId (height :: Nat) key val
NodeId :: Word64 -> NodeId key val
[fromNodeId] :: NodeId key val -> Word64

-- | Convert a <a>NodeId</a> to a <a>PageId</a>
nodeIdToPageId :: NodeId height key val -> PageId

-- | Convert a <a>PageId</a> to a <a>NodeId</a>
pageIdToNodeId :: PageId -> NodeId height key val

-- | Transaction ids that are used as revision numbers.
newtype TxId
TxId :: Word64 -> TxId
[fromTxId] :: TxId -> Word64
instance Data.BTree.Primitives.Key.Key Data.BTree.Primitives.Ids.TxId
instance Data.BTree.Primitives.Value.Value Data.BTree.Primitives.Ids.TxId
instance Data.Hashable.Class.Hashable Data.BTree.Primitives.Ids.TxId
instance GHC.Num.Num Data.BTree.Primitives.Ids.TxId
instance Data.Binary.Class.Binary Data.BTree.Primitives.Ids.TxId
instance GHC.Classes.Ord Data.BTree.Primitives.Ids.TxId
instance GHC.Classes.Eq Data.BTree.Primitives.Ids.TxId
instance GHC.Num.Num (Data.BTree.Primitives.Ids.NodeId height key val)
instance Data.Binary.Class.Binary (Data.BTree.Primitives.Ids.NodeId height key val)
instance GHC.Classes.Ord (Data.BTree.Primitives.Ids.NodeId height key val)
instance GHC.Classes.Eq (Data.BTree.Primitives.Ids.NodeId height key val)
instance GHC.Real.Integral Data.BTree.Primitives.Ids.PageSize
instance GHC.Real.Real Data.BTree.Primitives.Ids.PageSize
instance GHC.Enum.Enum Data.BTree.Primitives.Ids.PageSize
instance GHC.Num.Num Data.BTree.Primitives.Ids.PageSize
instance Data.Binary.Class.Binary Data.BTree.Primitives.Ids.PageSize
instance GHC.Show.Show Data.BTree.Primitives.Ids.PageSize
instance GHC.Classes.Ord Data.BTree.Primitives.Ids.PageSize
instance GHC.Classes.Eq Data.BTree.Primitives.Ids.PageSize
instance GHC.Enum.Enum Data.BTree.Primitives.Ids.PageCount
instance GHC.Num.Num Data.BTree.Primitives.Ids.PageCount
instance Data.Binary.Class.Binary Data.BTree.Primitives.Ids.PageCount
instance GHC.Classes.Ord Data.BTree.Primitives.Ids.PageCount
instance GHC.Classes.Eq Data.BTree.Primitives.Ids.PageCount
instance Data.BTree.Primitives.Key.Key Data.BTree.Primitives.Ids.PageId
instance Data.BTree.Primitives.Value.Value Data.BTree.Primitives.Ids.PageId
instance GHC.Num.Num Data.BTree.Primitives.Ids.PageId
instance Data.Binary.Class.Binary Data.BTree.Primitives.Ids.PageId
instance GHC.Classes.Ord Data.BTree.Primitives.Ids.PageId
instance GHC.Classes.Eq Data.BTree.Primitives.Ids.PageId
instance GHC.Show.Show Data.BTree.Primitives.Ids.TxId
instance GHC.Show.Show (Data.BTree.Primitives.Ids.NodeId height key val)
instance GHC.Show.Show Data.BTree.Primitives.Ids.PageCount
instance GHC.Show.Show Data.BTree.Primitives.Ids.PageId


-- | This module contains structures relating the the setup of a pure
--   B+-tree.
module Data.BTree.Pure.Setup

-- | Setup of a pure B+-tree.
data TreeSetup
TreeSetup :: Int -> Int -> Int -> Int -> Int -> Int -> TreeSetup
[minFanout] :: TreeSetup -> Int
[maxFanout] :: TreeSetup -> Int
[minIdxKeys] :: TreeSetup -> Int
[maxIdxKeys] :: TreeSetup -> Int
[minLeafItems] :: TreeSetup -> Int
[maxLeafItems] :: TreeSetup -> Int

-- | Setup of a 2-3 tree.
twoThreeSetup :: TreeSetup

-- | Setup of a B+-tree with a certain minimum degree, as defined in CLRS.
--   
--   To get for example a 2-3-4 tree, use
--   
--   <pre>
--   &gt;&gt;&gt; setupWithMinimumDegreeOf 2
--   </pre>
setupWithMinimumDegreeOf :: Int -> TreeSetup
instance GHC.Show.Show Data.BTree.Pure.Setup.TreeSetup

module Data.BTree.Primitives.Index

-- | The <a>Index</a> encodes the internal structure of an index node.
--   
--   The index is abstracted over the type <tt>node</tt> of sub-trees. The
--   keys and nodes are stored in separate <a>Vector</a>s 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
--   <a>Index</a> has one sub-tree and no keys, but a valid B+-tree index
--   node will have at least two sub-trees and one key.
data Index key node
Index :: !(Vector key) -> !(Vector node) -> Index key node

-- | Return the number of keys in this <a>Index</a>.
indexNumKeys :: Index key val -> Int

-- | Return the number of values stored in this <a>Index</a>.
indexNumVals :: Index key val -> Int

-- | Validate the key/node count invariant of an <a>Index</a>.
validIndex :: Ord key => Index key node -> Bool

-- | Validate the size of an <a>Index</a>.
validIndexSize :: Ord key => Int -> Int -> Index key node -> Bool

-- | Split an index node.
--   
--   This function splits an index node into two new nodes at the given key
--   position <tt>numLeftKeys</tt> 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
--   <tt>splitLeaf</tt> in <a>Data.BTree.Primitives.Leaf</a>.
splitIndexAt :: Int -> Index key val -> (Index key val, key, Index key val)

-- | Split an index many times.
--   
--   This function splits an <a>Index</a> node into smaller pieces. Each
--   resulting sub-<a>Index</a> has between <tt>maxIdxKeys/2</tt> and
--   <tt>maxIdxKeys</tt> inclusive values and is additionally applied to
--   the function <tt>f</tt>.
--   
--   This is the dual of a monadic bind and is also known as the
--   <tt>extended</tt> function of extendable functors. See
--   <a>Data.Functor.Extend</a> in the "semigroupoids" package.
--   
--   <pre>
--   bindIndex (extendedIndex n id idx) id == idx
--   </pre>
extendedIndex :: Int -> (Index k b -> a) -> Index k b -> Index k a
extendIndexPred :: (a -> Bool) -> (Index k b -> a) -> Index k b -> Maybe (Index k a)

-- | Merge two indices.
--   
--   Merge two indices <tt>leftIndex</tt>, <tt>rightIndex</tt> given a
--   discriminating key <tt>middleKey</tt>, i.e. such that '∀ (k,v) ∈
--   leftIndex. k &lt; middleKey' and '∀ (k,v) ∈ rightIndex. middleKey
--   &lt;= k'.
--   
--   <a>mergeIndex</a> is a partial inverse of splitIndex, i.e. prop&gt;
--   splitIndex is == (left,mid,right) =&gt; mergeIndex left mid right ==
--   is
mergeIndex :: Index key val -> key -> Index key val -> Index key val

-- | Create an index from key-value lists.
--   
--   The internal invariants of the <a>Index</a> data structure apply. That
--   means there is one more value than there are keys and keys are ordered
--   in strictly increasing order.
indexFromList :: [key] -> [val] -> Index key val

-- | Create an index with a single value.
singletonIndex :: val -> Index key val

-- | Test if the index consists of a single value.
--   
--   Returns the element if the index is a singleton. Otherwise fails.
--   
--   <pre>
--   fromSingletonIndex (singletonIndex val) == Just val
--   </pre>
fromSingletonIndex :: Index key val -> Maybe val

-- | Bind an index
--   
--   <pre>
--   bindIndex idx singletonIndex == idx
--   </pre>
bindIndex :: Index k a -> (a -> Index k b) -> Index k b
bindIndexM :: (Functor m, Monad m) => Index k a -> (a -> m (Index k b)) -> m (Index k b)

-- | Representation of one-hole contexts of <a>Index</a>.
--   
--   Just one val removes. All keys are present.
--   
--   <pre>
--   V.length leftVals  == V.length lefyKeys
--   </pre>
--   
--   <pre>
--   V.length rightVals == V.length rightKeys
--   </pre>
data IndexCtx key val
IndexCtx :: !(Vector key) -> !(Vector key) -> !(Vector val) -> !(Vector val) -> IndexCtx key val
[indexCtxLeftKeys] :: IndexCtx key val -> !(Vector key)
[indexCtxRightKeys] :: IndexCtx key val -> !(Vector key)
[indexCtxLeftVals] :: IndexCtx key val -> !(Vector val)
[indexCtxRightVals] :: IndexCtx key val -> !(Vector val)
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 a map of key-value pairs over an index.
distribute :: Ord k => Map k v -> Index k node -> Index k (Map k v, node)
leftView :: IndexCtx key val -> Maybe (IndexCtx key val, val, key)
rightView :: IndexCtx key val -> Maybe (key, val, IndexCtx key val)
instance Data.Traversable.Traversable (Data.BTree.Primitives.Index.IndexCtx key)
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Primitives.Index.IndexCtx key val)
instance Data.Foldable.Foldable (Data.BTree.Primitives.Index.IndexCtx key)
instance GHC.Base.Functor (Data.BTree.Primitives.Index.IndexCtx key)
instance Data.Traversable.Traversable (Data.BTree.Primitives.Index.Index key)
instance (GHC.Show.Show key, GHC.Show.Show node) => GHC.Show.Show (Data.BTree.Primitives.Index.Index key node)
instance Data.Foldable.Foldable (Data.BTree.Primitives.Index.Index key)
instance GHC.Base.Functor (Data.BTree.Primitives.Index.Index key)
instance (GHC.Classes.Eq key, GHC.Classes.Eq node) => GHC.Classes.Eq (Data.BTree.Primitives.Index.Index key node)
instance (Data.Binary.Class.Binary k, Data.Binary.Class.Binary n) => Data.Binary.Class.Binary (Data.BTree.Primitives.Index.Index k n)

module Data.BTree.Primitives.Leaf

-- | Split a leaf many times until the predicate is satisfied.
--   
--   This function ensures that the for each returned leaf, the predicate
--   is satisfied, or returns <a>Nothing</a> when it can't be satisfied.
splitLeafManyPred :: (Key key) => (a -> Bool) -> (Map key val -> a) -> Map key val -> Maybe (Index key a)

-- | Split a leaf many times.
--   
--   This function ensures that the for each returned leaf, the amount of
--   items <a>maxLeafItems (and</a>= minLeafItems, except when the original
--   leaf had less than minLeafItems items.
splitLeafMany :: Key key => Int -> (Map key val -> a) -> Map key val -> Index key a


-- | A pure in-memory B+-tree implementation.
module Data.BTree.Pure

-- | A pure B+-tree.
--   
--   This is a simple wrapper around a root <a>Node</a>. An empty tree is
--   represented by <a>Nothing</a>. Otherwise it's <a>Just</a> the root.
--   The height is existentially quantified.
data Tree key val
[Tree] :: !TreeSetup -> Maybe (Node height key val) -> Tree key val

-- | 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.
data Node (height :: Nat) key val
[Idx] :: {idxChildren :: Index key (Node height key val)} -> Node ( 'S height) key val
[Leaf] :: {leafItems :: Map key val} -> Node  'Z key val

-- | The empty tree.
empty :: TreeSetup -> Tree key val

-- | Construct a tree containg one element.
singleton :: Key k => TreeSetup -> k -> v -> Tree k v

-- | <i>O(n*log n)</i>. Construct a B-tree from a list of key/value pairs.
--   
--   If the list contains duplicate keys, the last pair for a duplicate key
--   is kept.
fromList :: Key k => TreeSetup -> [(k, v)] -> Tree k v

-- | Insert a key-value pair into a tree.
--   
--   When inserting a new entry, the leaf it is inserted to and the index
--   nodes on the path to the leaf potentially need to be split. Instead of
--   returning the outcome, 1 node or 2 nodes (with a discriminating key),
--   we return an <a>Index</a> of these nodes.
--   
--   If the key already existed in the tree, it is overwritten.
insert :: Key k => k -> v -> Tree k v -> Tree k v

-- | Insert a bunch of key-value pairs simultaneously.
insertMany :: Key k => Map k v -> Tree k v -> Tree k v

-- | Delete a key-value pair from the tree.
delete :: Key k => k -> Tree k v -> Tree k v

-- | Lookup a value in the tree.
lookup :: Key k => k -> Tree k v -> Maybe v

-- | Lookup a value in the tree, or return a default.
findWithDefault :: Key k => v -> k -> Tree k v -> v

-- | Check whether a key is present in the tree.
member :: Key k => k -> Tree k v -> Bool

-- | Check whether a key is not present in the tree.
notMember :: Key k => k -> Tree k v -> Bool

-- | Check whether the tree is empty.
null :: Tree k v -> Bool

-- | The size of a tree.
size :: Tree k v -> Int

-- | <i>O(n)</i>. Fold key/value pairs in the B-tree.
foldrWithKey :: forall k v w. (k -> v -> w -> w) -> w -> Tree k v -> w

-- | <i>O(n)</i>. Convert the B-tree to a sorted list of key/value pairs.
toList :: Tree k v -> [(k, v)]
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Pure.Node height key val)
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Pure.Tree key val)
instance Data.Foldable.Foldable (Data.BTree.Pure.Tree key)
instance Data.Foldable.Foldable (Data.BTree.Pure.Node height key)


-- | Primitive data structures and algorithms needed for both the pure
--   (<a>Data.BTree.Pure</a>) and impure (<a>Data.BTree.Impure</a>) B+-tree
--   implementation.
module Data.BTree.Primitives


-- | Basic structures of an impure B+-tree.
module Data.BTree.Impure.Internal.Structures

-- | A B+-tree.
--   
--   This is a simple wrapper around a root <a>Node</a>. The type-level
--   height is existentially quantified, but a term-level witness is
--   stores.
data Tree key val
[Tree] :: {treeHeight :: Height height  A term-level witness for the type-level height index., treeRootId :: Maybe (NodeId height key val)  An empty tree is represented by 'Nothing'. Otherwise it's 'Just' a 'NodeId' pointer the root.} -> Tree key val

-- | 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 <a>NodeId</a> that are used to resolve
--   the actual storage location of the sub-tree node.
data Node height key val
[Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
[Leaf] :: {leafItems :: LeafItems key val} -> Node  'Z key val
type LeafItems k v = Map k (LeafValue v)
data LeafValue v
RawValue :: v -> LeafValue v
OverflowValue :: OverflowId -> LeafValue v

-- | Encode a <a>Leaf</a> <a>Node</a>.
putLeafNode :: (Binary key, Binary val) => Node  'Z key val -> Put

-- | Decode a <a>Leaf</a> <a>Node</a>.
getLeafNode :: (Ord key, Binary key, Binary val) => Height  'Z -> Get (Node  'Z key val)

-- | Encode an <a>Idx</a> <a>Node</a>.
putIndexNode :: (Binary key, Binary val) => Node ( 'S n) key val -> Put

-- | Decode an <a>Idx</a> <a>Node</a>.
getIndexNode :: (Binary key, Binary val) => Height ( 'S n) -> Get (Node ( 'S n) key val)

-- | Cast a node to a different type.
--   
--   Essentially this is just a drop-in replacement for <a>cast</a>.
castNode :: forall n key1 val1 height1 key2 val2 height2. (Typeable key1, Typeable val1, Typeable key2, Typeable val2) => Height height1 -> Height height2 -> n height1 key1 val1 -> Maybe (n height2 key2 val2)

-- | Cast a node to one of the available types.
castNode' :: forall n h k v. (Typeable k, Typeable v) => Height h -> n h k v -> Either (n  'Z k v) (n ( 'S h) k v)

-- | Cast a value to a different type.
--   
--   Essentially this is just a drop-in replacement for <a>cast</a>.
castValue :: (Typeable v1, Typeable v2) => v1 -> Maybe v2
instance GHC.Show.Show v => GHC.Show.Show (Data.BTree.Impure.Internal.Structures.LeafValue v)
instance GHC.Classes.Eq v => GHC.Classes.Eq (Data.BTree.Impure.Internal.Structures.LeafValue v)
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Impure.Internal.Structures.Node height key val)
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Impure.Internal.Structures.Tree key val)
instance (GHC.Classes.Eq key, GHC.Classes.Eq val) => GHC.Classes.Eq (Data.BTree.Impure.Internal.Structures.Node height key val)
instance Data.Binary.Class.Binary v => Data.Binary.Class.Binary (Data.BTree.Impure.Internal.Structures.LeafValue v)
instance (Data.BTree.Primitives.Value.Value k, Data.BTree.Primitives.Value.Value v) => Data.BTree.Primitives.Value.Value (Data.BTree.Impure.Internal.Structures.Tree k v)
instance Data.Binary.Class.Binary (Data.BTree.Impure.Internal.Structures.Tree key val)


-- | A page allocator manages all physical pages.
module Data.BTree.Alloc.Class

-- | A page allocator that can read physical pages.
class (Applicative m, Monad m) => AllocReaderM m

-- | Read a page and return the actual node.
readNode :: (AllocReaderM m, Key key, Value val) => Height height -> NodeId height key val -> m (Node height key val)

-- | Read an overflow page.
readOverflow :: (AllocReaderM m, (Value val)) => OverflowId -> m val

-- | A page allocator that can write physical pages.
class AllocReaderM m => AllocM m

-- | A function that calculates the hypothetical size of a node, if it were
--   to be written to a page (regardless of the maximum page size).
nodePageSize :: (AllocM m, Key key, Value val) => m (Height height -> Node height key val -> PageSize)

-- | The maximum page size the allocator can handle.
maxPageSize :: AllocM m => m PageSize

-- | The maximum key size
maxKeySize :: AllocM m => m Word64

-- | The maximum value size
maxValueSize :: AllocM m => m Word64

-- | Allocate a new page for a node, and write the node to the page.
allocNode :: (AllocM m, Key key, Value val) => Height height -> Node height key val -> m (NodeId height key val)

-- | Free the page belonging to the node.
freeNode :: AllocM m => Height height -> NodeId height key val -> m ()

-- | Allocate a new overflow page, and write the value to the page.
allocOverflow :: (AllocM m, (Value val)) => val -> m OverflowId

-- | Free an overflow page.
freeOverflow :: AllocM m => OverflowId -> m ()

-- | Force delete overflow data from disk.
deleteOverflowData :: AllocM m => OverflowId -> m ()


-- | Functions related to overflow pages.
module Data.BTree.Impure.Internal.Overflow
toLeafValue :: (AllocM m, Value v) => v -> m (LeafValue v)
fromLeafValue :: (AllocReaderM m, Value v) => LeafValue v -> m v
toLeafItems :: (AllocM m, Value v) => Map k v -> m (LeafItems k v)
fromLeafItems :: (AllocReaderM m, Value v) => LeafItems k v -> m (Map k v)


-- | Algorithms related to looking up key-value pairs in an impure B+-tree.
module Data.BTree.Impure.Internal.Lookup
lookupRec :: forall m height key val. (AllocReaderM m, Key key, Value val) => key -> Height height -> NodeId height key val -> m (Maybe val)

-- | Lookup a value in an impure B+-tree.
lookup :: forall m key val. (AllocReaderM m, Key key, Value val) => key -> Tree key val -> m (Maybe val)

-- | The minimal key of the map, returns <a>Nothing</a> if the map is
--   empty.
lookupMin :: (AllocReaderM m, Key key, Value val) => Tree key val -> m (Maybe (key, val))

-- | The maximal key of the map, returns <a>Nothing</a> if the map is
--   empty.
lookupMax :: (AllocReaderM m, Key key, Value val) => Tree key val -> m (Maybe (key, val))


-- | Algorithms related to inserting key-value pairs in an impure B+-tree.
module Data.BTree.Impure.Internal.Insert

-- | Split an index node.
--   
--   This function is partial. It fails when the original index cannot be
--   split, because it does not contain enough elements (underflow).
splitIndex :: (AllocM m, Key key, Value val) => Height ( 'S height) -> Index key (NodeId height key val) -> m (Index key (Node ( 'S height) key val))

-- | Split a leaf node.
--   
--   This function is partial. It fails when the original leaf cannot be
--   split, because it does not contain enough elements (underflow).
splitLeaf :: (AllocM m, Key key, Value val) => LeafItems key val -> m (Index key (Node  'Z key val))
insertRec :: forall m height key val. (AllocM m, Key key, Value val) => key -> val -> Height height -> NodeId height key val -> m (Index key (NodeId height key val))
insertRecMany :: forall m height key val. (AllocM m, Key key, Value val) => Height height -> Map key val -> NodeId height key val -> m (Index key (NodeId height key val))

-- | Insert a key-value pair in an impure B+-tree.
--   
--   You are responsible to make sure the key is smaller than
--   <a>maxKeySize</a>, otherwise a <a>KeyTooLargeError</a> can (but not
--   always will) be thrown.
insert :: (AllocM m, Key key, Value val) => key -> val -> Tree key val -> m (Tree key val)

-- | Bulk insert a bunch of key-value pairs in an impure B+-tree.
--   
--   You are responsible to make sure all keys is smaller than
--   <a>maxKeySize</a>, otherwise a <a>KeyTooLargeError</a> can (but not
--   always will) be thrown.
insertMany :: (AllocM m, Key key, Value val) => Map key val -> Tree key val -> m (Tree key val)

-- | Fix up the root node of a tree.
--   
--   Fix up the root node of a tree, where all other nodes are valid, but
--   the root node may contain more items than allowed. Do this by
--   repeatedly splitting up the root node.
fixUp :: (AllocM m, Key key, Value val) => Height height -> Index key (NodeId height key val) -> m (Tree key val)


-- | Algorithms related to folding over an impure B+-tree.
module Data.BTree.Impure.Internal.Fold

-- | Perform a right-associative fold over the tree.
foldr :: (AllocReaderM m, Key k, Value a) => (a -> b -> b) -> b -> Tree k a -> m b

-- | Perform a right-associative fold over the tree key-value pairs.
foldrWithKey :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> b) -> b -> Tree k a -> m b

-- | Perform a monadic right-associative fold over the tree.
foldrM :: (AllocReaderM m, Key k, Value a) => (a -> b -> m b) -> b -> Tree k a -> m b

-- | Perform a monadic right-assiciative fold over the tree key-value
--   pairs.
foldrWithKeyM :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> m b) -> b -> Tree k a -> m b
foldrIdWithKeyM :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> m b) -> b -> Height h -> NodeId h k a -> m b
foldrNodeWithKeyM :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> m b) -> b -> Height h -> Node h k a -> m b
foldrLeafItemsWithKeyM :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> m b) -> b -> Map k a -> m b

-- | Map each value of the tree to a monoid, and combine the results.
foldMap :: (AllocReaderM m, Key k, Value a, Monoid c) => (a -> c) -> Tree k a -> m c

-- | Convert an impure B+-tree to a list of key-value pairs.
toList :: (AllocReaderM m, Key k, Value a) => Tree k a -> m [(k, a)]


-- | Algorithms related to deletion from an impure B+-tree.
module Data.BTree.Impure.Internal.Delete

-- | Check whether a node needs to be merged.
nodeNeedsMerge :: Node height key val -> Bool

-- | Merge two nodes.
mergeNodes :: (AllocM m, Key key, Value val) => Height height -> Node height key val -> key -> Node height key val -> m (Index key (Node height key val))
deleteRec :: forall height key val m. (AllocM m, Key key, Value val) => key -> Height height -> NodeId height key val -> m (Node height key val)

-- | Delete a node from the tree.
delete :: (AllocM m, Key key, Value val) => key -> Tree key val -> m (Tree key val)


-- | An impure B+-tree implementation.
--   
--   This module contains the implementation of a B+-tree that is backed by
--   a page allocator (see <a>Data.BTree.Alloc</a>).
module Data.BTree.Impure

-- | A B+-tree.
--   
--   This is a simple wrapper around a root <a>Node</a>. The type-level
--   height is existentially quantified, but a term-level witness is
--   stores.
data Tree key val
[Tree] :: {treeHeight :: Height height  A term-level witness for the type-level height index., treeRootId :: Maybe (NodeId height key val)  An empty tree is represented by 'Nothing'. Otherwise it's 'Just' a 'NodeId' pointer the root.} -> Tree key val

-- | 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 <a>NodeId</a> that are used to resolve
--   the actual storage location of the sub-tree node.
data Node height key val
[Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
[Leaf] :: {leafItems :: LeafItems key val} -> Node  'Z key val

-- | Create an empty tree.
empty :: Tree k v

-- | Create a tree from a list.
fromList :: (AllocM m, Key k, Value v) => [(k, v)] -> m (Tree k v)

-- | Create a tree from a map.
fromMap :: (AllocM m, Key k, Value v) => Map k v -> m (Tree k v)

-- | Insert a key-value pair in an impure B+-tree.
--   
--   You are responsible to make sure the key is smaller than
--   <a>maxKeySize</a>, otherwise a <a>KeyTooLargeError</a> can (but not
--   always will) be thrown.
insert :: (AllocM m, Key key, Value val) => key -> val -> Tree key val -> m (Tree key val)

-- | Bulk insert a bunch of key-value pairs in an impure B+-tree.
--   
--   You are responsible to make sure all keys is smaller than
--   <a>maxKeySize</a>, otherwise a <a>KeyTooLargeError</a> can (but not
--   always will) be thrown.
insertMany :: (AllocM m, Key key, Value val) => Map key val -> Tree key val -> m (Tree key val)

-- | Delete a node from the tree.
delete :: (AllocM m, Key key, Value val) => key -> Tree key val -> m (Tree key val)

-- | Lookup a value in an impure B+-tree.
lookup :: forall m key val. (AllocReaderM m, Key key, Value val) => key -> Tree key val -> m (Maybe val)

-- | The minimal key of the map, returns <a>Nothing</a> if the map is
--   empty.
lookupMin :: (AllocReaderM m, Key key, Value val) => Tree key val -> m (Maybe (key, val))

-- | The maximal key of the map, returns <a>Nothing</a> if the map is
--   empty.
lookupMax :: (AllocReaderM m, Key key, Value val) => Tree key val -> m (Maybe (key, val))

-- | Perform a right-associative fold over the tree.
foldr :: (AllocReaderM m, Key k, Value a) => (a -> b -> b) -> b -> Tree k a -> m b

-- | Perform a monadic right-associative fold over the tree.
foldrM :: (AllocReaderM m, Key k, Value a) => (a -> b -> m b) -> b -> Tree k a -> m b

-- | Perform a right-associative fold over the tree key-value pairs.
foldrWithKey :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> b) -> b -> Tree k a -> m b

-- | Perform a monadic right-assiciative fold over the tree key-value
--   pairs.
foldrWithKeyM :: (AllocReaderM m, Key k, Value a) => (k -> a -> b -> m b) -> b -> Tree k a -> m b

-- | Map each value of the tree to a monoid, and combine the results.
foldMap :: (AllocReaderM m, Key k, Value a, Monoid c) => (a -> c) -> Tree k a -> m c

-- | Convert an impure B+-tree to a list of key-value pairs.
toList :: (AllocReaderM m, Key k, Value a) => Tree k a -> m [(k, a)]


-- | Non empty wrapper around the impure <a>Tree</a>.
module Data.BTree.Impure.NonEmpty

-- | A non-empty variant of <a>Tree</a>.
data NonEmptyTree key val
[NonEmptyTree] :: {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.} -> NonEmptyTree key val

-- | 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 <a>NodeId</a> that are used to resolve
--   the actual storage location of the sub-tree node.
data Node height key val
[Idx] :: {idxChildren :: Index key (NodeId height key val)} -> Node ( 'S height) key val
[Leaf] :: {leafItems :: LeafItems key val} -> Node  'Z key val

-- | Convert a <a>Tree</a> into a <a>NonEmptyTree</a>.
fromTree :: Tree key val -> Maybe (NonEmptyTree key val)

-- | Convert a <a>NonEmptyTree</a> into a <a>Tree</a>.
toTree :: NonEmptyTree key val -> Tree key val

-- | Convert a non-empty tree to a list of key-value pairs.
toList :: (AllocReaderM m, Key k, Value v) => NonEmptyTree k v -> m (NonEmpty (k, v))

-- | Create a <a>NonEmptyTree</a> from a <a>NonEmpty</a> list.
fromList :: (AllocM m, Key k, Value v) => NonEmpty (k, v) -> m (NonEmptyTree k v)

-- | Insert an item into a <a>NonEmptyTree</a>
insert :: (AllocM m, Key k, Value v) => k -> v -> NonEmptyTree k v -> m (NonEmptyTree k v)

-- | Bulk insert a bunch of key-value pairs into a <a>NonEmptyTree</a>.
insertMany :: (AllocM m, Key k, Value v) => Map k v -> NonEmptyTree k v -> m (NonEmptyTree k v)
instance (GHC.Show.Show key, GHC.Show.Show val) => GHC.Show.Show (Data.BTree.Impure.NonEmpty.NonEmptyTree key val)
instance (Data.BTree.Primitives.Value.Value k, Data.BTree.Primitives.Value.Value v) => Data.BTree.Primitives.Value.Value (Data.BTree.Impure.NonEmpty.NonEmptyTree k v)
instance Data.Binary.Class.Binary (Data.BTree.Impure.NonEmpty.NonEmptyTree key val)


-- | An in memory allocator for debugging and testing purposes.
module Data.BTree.Alloc.Debug
data SomeNode
SomeNode :: (Height h) -> (Node h k v) -> SomeNode
getSomeNode :: SomeNode -> Node h k v
data SomeVal
SomeVal :: v -> SomeVal
getSomeVal :: SomeVal -> v
data Pages
Pages :: Map PageId SomeNode -> Map Word32 SomeVal -> Pages
[pagesNodes] :: Pages -> Map PageId SomeNode
[pagesOverflow] :: Pages -> Map Word32 SomeVal
emptyPages :: Pages
newtype DebugT m a
DebugT :: StateT Pages m a -> DebugT m a
[runDebugT] :: DebugT m a -> StateT Pages m a
runDebug :: Pages -> DebugT Identity a -> (a, Pages)
evalDebug :: Pages -> DebugT Identity a -> a
instance GHC.Base.Monad m => Control.Monad.State.Class.MonadState Data.BTree.Alloc.Debug.Pages (Data.BTree.Alloc.Debug.DebugT m)
instance Control.Monad.IO.Class.MonadIO m => Control.Monad.IO.Class.MonadIO (Data.BTree.Alloc.Debug.DebugT m)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.BTree.Alloc.Debug.DebugT m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Data.BTree.Alloc.Debug.DebugT m)
instance GHC.Base.Functor m => GHC.Base.Functor (Data.BTree.Alloc.Debug.DebugT m)
instance (GHC.Base.Functor m, GHC.Base.Monad m) => Data.BTree.Alloc.Class.AllocReaderM (Data.BTree.Alloc.Debug.DebugT m)
instance (GHC.Base.Functor m, GHC.Base.Monad m) => Data.BTree.Alloc.Class.AllocM (Data.BTree.Alloc.Debug.DebugT m)


-- | Page allocators that manage all physical pages.
module Data.BTree.Alloc
