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


-- | Immutable disk-based B* trees
--   
--   Immutable disk-based B* trees
@package b-tree
@version 0.1.3

module BTree.BinaryList

-- | A file containing a finite list of binary encoded items
data BinaryList a

-- | Encode the items of the given producer
toBinaryList :: forall m a r. (MonadMask m, MonadIO m, Binary a) => FilePath -> Producer a m r -> m (BinaryList a, r)

-- | Open a <a>BinaryList</a> file.
--   
--   TODO: Sanity checking at open time.
open :: FilePath -> BinaryList a

-- | Stream the items out of a <tt>BinaryList</tt>
stream :: forall m a. (Binary a, MonadMask m, MonadIO m) => BinaryList a -> ExceptT String m (Producer a m (Either String ()))
length :: (MonadMask m, MonadIO m) => BinaryList a -> ExceptT String m Word64

-- | Get the path to the <tt>BinaryList</tt> file
filePath :: BinaryList a -> FilePath
instance GHC.Show.Show BTree.BinaryList.Header
instance GHC.Show.Show (BTree.BinaryList.BinaryList a)
instance Data.Binary.Class.Binary BTree.BinaryList.Header


-- | This package provides immutable B* trees targetting large data sets
--   requiring secondary storage.
module BTree

-- | A tree leaf (e.g. key/value pair)
data BLeaf k e
BLeaf :: !k -> !e -> BLeaf k e

-- | The number of entries in a B-tree
type Size = Word64

-- | The maximum number of children of a B-tree inner node
type Order = Word64

-- | Build a B-tree into the given file.
--   
--   As the name suggests, this requires that the <tt>Producer</tt> emits
--   leaves in ascending key order.
fromOrderedToFile :: (MonadMask m, MonadIO m, Binary e, Binary k) => Order -> Size -> FilePath -> Producer (BLeaf k e) m r -> m ()

-- | Build a B-tree into <tt>ByteString</tt>
--   
--   As the name suggests, this requires that the <tt>Producer</tt> emits
--   leaves in ascending key order.
--   
--   This is primarily used for testing. In particular, note that this is a
--   bad idea for large trees as the entire contents of the tree will need
--   to be kept in memory until all leaves have been added so that the
--   header can be prepended.
fromOrderedToByteString :: (Monad m, Binary e, Binary k) => Order -> Size -> Producer (BLeaf k e) m r -> m ByteString

-- | Build a B-tree into the given file.
--   
--   This does not assume that the leaves are produced in order. Instead,
--   the sorting is handled internally through a simple merge sort. Chunks
--   of leaves are collected, sorted in memory, and then written to
--   intermediate trees. At the end these trees are then merged.
fromUnorderedToFile :: forall m e k r. (MonadMask m, MonadIO m, Binary (BLeaf k e), Binary k, Binary e, Ord k) => FilePath -> Int -> Order -> FilePath -> Producer (BLeaf k e) m r -> ExceptT String m ()

-- | A read-only B-tree for lookups
data LookupTree k e

-- | Open a B-tree file.
open :: FilePath -> IO (Either String (LookupTree k e))

-- | Read a B-tree from a <tt>ByteString</tt> produced by <a>Builder</a>
fromByteString :: ByteString -> Either String (LookupTree k e)

-- | Lookup a key in a B-tree.
lookup :: (Binary k, Binary e, Ord k) => LookupTree k e -> k -> Maybe e

-- | How many keys are in a <a>LookupTree</a>.
size :: LookupTree k e -> Size

-- | Merge several <tt>LookupTrees</tt>
--   
--   This is a convenience function for merging several trees already on
--   disk. For a more flexible interface, see <a>mergeLeaves</a>.
mergeTrees :: (MonadMask m, MonadIO m, Functor m, Binary k, Binary e, Ord k) => (e -> e -> m e) -> Order -> FilePath -> [LookupTree k e] -> m ()

-- | Merge trees' leaves taking ordered leaves from a set of producers.
--   
--   Each producer must be annotated with the number of leaves it is
--   expected to produce. The size of the resulting tree will be at most
--   the sum of these sizes.
mergeLeaves :: (MonadMask m, MonadIO m, Functor m, Binary k, Binary e, Ord k) => (e -> e -> m e) -> Order -> FilePath -> [(Size, Producer (BLeaf k e) m ())] -> m ()

-- | Get a sized <a>Producer</a> suitable for <a>mergeLeaves</a> from a
--   <a>LookupTree</a>
sizedProducerForTree :: (Monad m, Binary k, Binary e) => LookupTree k e -> (Size, Producer (BLeaf k e) m ())

-- | Iterate over the leaves of the given tree in ascending key order.
walkLeaves :: (Binary k, Binary v, Monad m) => LookupTree k v -> Producer (BLeaf k v) m (ByteString, Maybe String)