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


-- | Trees whose branches are resistant to change
--   
@package stable-tree
@version 0.5.0


-- | Tools for working with StableTree keys.
module Data.StableTree.Key

-- | A wrapper for keys; this has an ephemeral <tt>t</tt> that will be
--   either <a>Terminal</a> or <a>Nonterminal</a> depending on the result
--   of <tt>byte k</tt>.
data Key t k

-- | A sum type to contain either a <a>Terminal</a> or a <a>Nonterminal</a>
--   <a>Key</a>
data SomeKey k
SomeKey_T :: (Key Terminal k) -> SomeKey k
SomeKey_N :: (Key Nonterminal k) -> SomeKey k

-- | Used to indicate that a <a>Key</a> is terminal
data Terminal

-- | Used to indicate that a <a>Key</a> is not terminal
data Nonterminal

-- | Do the magic of wrapping up a key into a <a>SomeKey</a>
wrap :: Serialize k => k -> SomeKey k

-- | Extract the original key from a wrapped one
unwrap :: SomeKey k -> k
instance Eq k => Eq (Key t k)
instance Ord k => Ord (Key t k)
instance Show k => Show (Key t k)
instance Eq k => Eq (SomeKey k)
instance Ord k => Ord (SomeKey k)
instance Show k => Show (SomeKey k)


-- | Definitions of primitive types used in different modules of
--   stable-tree
module Data.StableTree.Types

-- | Alias to indicate how deep a branch in a tree is. Bottoms have depth 0
type Depth = Int

-- | Alias that indicates the total number of values underneath a tree
type ValueCount = Int


-- | This is the implementation of tree fragments, which are stand-alone
--   chunks of data representing each branch within a <a>Tree</a>. This
--   module is also used by the Tree code for generating each branch's
--   <a>ObjectID</a>.
module Data.StableTree.Fragment

-- | A <a>Fragment</a> is a user-visible part of a tree, i.e. a single node
--   in the tree that can actually be manipulated by a user. This is useful
--   when doing the work of persisting trees.
data Fragment k v
FragmentBranch :: Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: Map k v -> Fragment k v
fragmentMap :: Fragment k v -> Map k v
instance (Eq k, Eq v) => Eq (Fragment k v)
instance (Ord k, Ord v) => Ord (Fragment k v)
instance (Show k, Show v) => Show (Fragment k v)
instance (Ord k, Serialize k, Serialize v) => Serialize (Fragment k v)


-- | This is the core implementation of the stable tree. The primary
--   functions exported by this module are <a>nextBottom</a> and
--   <a>nextBranch</a>, which gather values or lower-level <a>Tree</a>s
--   into <a>Tree</a>s of the next level.
--   
--   This module is fairly esoteric. <a>Data.StableTree</a> or
--   <a>Data.StableTree.IO</a> are probably what you actually want to be
--   using.
module Data.StableTree.Tree

-- | <tt>StableTree</tt> is the user-visible type that wraps the actual
--   <a>Tree</a> implementation. All the public functions operate on this
--   type.
data StableTree k v
StableTree_I :: (Tree Incomplete k v) -> StableTree k v
StableTree_C :: (Tree Complete k v) -> StableTree k v

-- | The actual Rose Tree structure. StableTree is built on one main idea:
--   every <a>Key</a> is either <a>Terminal</a> or <a>Nonterminal</a>. A
--   complete <a>Tree</a> is one whose final element's Key is terminal, and
--   the rest of the Keys are not (exept for two freebies at the beginning
--   to guarantee convergence). A complete tree always has complete
--   children.
--   
--   If we don't have enough data to generate a complete tree (i.e. we ran
--   out of elements before hitting a terminal key), then an
--   <a>Incomplete</a> tree is generated. Incomplete trees are always
--   contained by other incomplete trees, and a tree built from only the
--   complete chlidren of an incomplete tree would never itself be
--   complete.
--   
--   It is easiest to understand how this structure promotes stability by
--   looking at how trees typically work. The easiest tree to understand is
--   a simple, well balanced, binary tree. In that case, we would have a
--   structure like this:
--   
--   <pre>
--         |D|
--     |B|     |F|
--   |A| |C| |E| |G|
--   </pre>
--   
--   Now, suppose that we want to delete the data stored in <tt>|A|</tt>.
--   Then, we'll get a new structure that shares nothing in common with the
--   original one:
--   
--   <pre>
--         |E|
--     |C|     |G|
--   |B| |D| |F|
--   </pre>
--   
--   The entire tree had to be re-written. This structure is clearly
--   unstable under mutation. Making the tree wider doesn't help much if
--   the tree's size is changing. Simple updates to existing keys are
--   handled well by branches with many children, but deleting from or
--   adding to the beginning of the tree will always cause every single
--   branch to change, which is what this structure is trying to avoid.
--   
--   Instead, the stable tree branches have variable child counts. A branch
--   is considered full when its highest key is "terminal", which is
--   determined by hashing the key and looking at some bits of the hash.
--   I've found that a target branch size of 16 children works fairly well,
--   so we check to see if the hash has its least-significant four bits
--   set; if that's the case, the key is terminal. A branch gets two free
--   children (meaning it doesn't care about whether the keys are temrinal
--   or not), and then a run of nonterminal keys, and a final, terminal
--   key. Under this scheme, inserting a new entry into a branch will
--   probably mean inserting a nonterminal key, and it will probably be
--   inserted into the run of nonterminal children. If that's the case, no
--   neighbors will be affected, and only the parents will have to change
--   to point to the new branch. Stability is acheived!
data Tree c k v

-- | Used to indicate that a <a>Tree</a> is complete
data Complete

-- | Used to indicate that a <a>Tree</a> is not complete
data Incomplete

-- | Wrap up some of a k/v map into a <a>Tree</a>. A <a>Right</a> result
--   gives a complete tree and the map updated to not have the key/values
--   that went into that tree. A <a>Left</a> result gives an incomplete
--   tree that contains everything that the given map contained.
nextBottom :: (Ord k, Serialize k, Serialize v) => Map k v -> Either (Tree Incomplete k v) (Tree Complete k v, Map k v)

-- | Generate a parent for a k/Tree map. A <a>Right</a> result gives a
--   complete tree and the map updated to not have the key/trees that went
--   into that tree. A <a>Left</a> result gives an incomplete tree that
--   contains everything that the given map contained.
nextBranch :: (Ord k, Serialize k, Serialize v) => Map k (Tree Complete k v) -> Maybe (k, Tree Incomplete k v) -> Either (Tree Incomplete k v) (Tree Complete k v, Map k (Tree Complete k v))

-- | Get the key of the first entry in this branch. If the branch is empty,
--   returns Nothing.
getKey :: Tree c k v -> Maybe k

-- | Get the key of the fist entry in this complete branch. This function
--   is total.
completeKey :: Tree Complete k v -> k

-- | Convert an entire Tree into a k/v map.
treeContents :: Ord k => Tree c k v -> Map k v

-- | Non-recursive function to simply get the immediate children of the
--   given branch. This will either give the key<i>value map of a Bottom,
--   or the key</i>tree map of a non-bottom branch.
branchContents :: Ord k => Tree c k v -> Either (Map k (ValueCount, Tree Complete k v), Maybe (k, ValueCount, Tree Incomplete k v)) (Map k v)

-- | Get the ObjectID of a tree node
getObjectID :: Tree c k v -> ObjectID

-- | Get the number of levels of branches that live below this one
getDepth :: Tree c k v -> Depth

-- | Get the number of actual values that live below this branch
getValueCount :: Tree c k v -> ValueCount
instance (Ord k, Show k, Show v) => Show (StableTree k v)
instance (Ord k, Show k, Show v) => Show (Tree c k v)
instance Eq (Tree c k v)


-- | Functions for converting between Tree and Fragment types
module Data.StableTree.Conversion
toFragments :: Ord k => Tree c k v -> [(ObjectID, Fragment k v)]
fromFragments :: (Ord k, Serialize k, Serialize v) => Map ObjectID (Fragment k v) -> Fragment k v -> Either Text (Either (Tree Incomplete k v) (Tree Complete k v))


-- | Logic for dealing with the actual persistence of Stable Trees. The key
--   exports here are <a>Error</a>, <tt>Store</tt>, <a>load</a>, and
--   <a>store</a>. A user needs to implement the <tt>loadTree</tt>,
--   <tt>loadValue</tt>, <tt>storeTree</tt> and <tt>storeValue</tt> parts
--   of <tt>Store</tt>, and make an appropriate Error type to report
--   storage errors, and then the <a>load</a> and <a>store</a> functions
--   can just do their thing. If necessary, a user can also implement
--   <a>Serialize</a> for custom data types.
module Data.StableTree.Persist

-- | Things go wrong with end-user storage, but things can also go wrong
--   with reconstructing tree values. Implement <a>stableTreeError</a> to
--   allow <a>load</a> and <a>store</a> to report their own errors.
class Error e
stableTreeError :: Error e => Text -> e
load :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (a -> ObjectID -> m (Either e (a, Fragment k v))) -> a -> ObjectID -> m (Either e (a, StableTree k v))
load' :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (ObjectID -> m (Either e (Fragment k v))) -> ObjectID -> m (Either e (StableTree k v))

-- | Record the tree into storage. This works like a fold, where the
--   function takes an accumulating state and each tree fragment to store,
--   while returning either an error message (which will abort the loop
--   immediately) or the next state for the accumulator.
--   
--   Any fragment referring to other fragments (<a>FragmentBranch</a>
--   fragments) will be given to the fold only after all their children
--   have been given to the fold. Exact ordering beyond that is not
--   guaranteed, but the current behaviour is post-order depth-first
--   traversal.
store :: (Monad m, Error e, Ord k) => (a -> ObjectID -> Fragment k v -> m (Either e a)) -> a -> StableTree k v -> m (Either e a)
store' :: (Monad m, Error e, Ord k) => (ObjectID -> Fragment k v -> m (Maybe e)) -> StableTree k v -> m (Either e ObjectID)


-- | A Rose Tree designed for maximal stability under mutation. The
--   StableTree structure is meant to be used in places where different
--   versions of a key/value map are kept, such as in a versioning file
--   system or a revision control system. As a tree's contents are mutated
--   (inserted, updated, deleted), it will tend to keep the vast majority
--   of its branches untouched, with generally just the immediate branch
--   and its immediate ancestor chain being modified. Put another way,
--   trees with similar contents will also share a majority of their
--   branches.
--   
--   This module exports the public interface for StableTree. Right now,
--   that's just a translation to the standard Data.Map and back. There's
--   nothing about StableTree that forbids direct manipulation, but I've
--   been playing with various implementations of this for way too long,
--   and I just want to start using the dang thing now.
module Data.StableTree

-- | <tt>StableTree</tt> is the user-visible type that wraps the actual
--   <a>Tree</a> implementation. All the public functions operate on this
--   type.
data StableTree k v
StableTree_I :: (Tree Incomplete k v) -> StableTree k v
StableTree_C :: (Tree Complete k v) -> StableTree k v

-- | Convert a <a>Map</a> into a <a>StableTree</a>.
fromMap :: (Ord k, Serialize k, Serialize v) => Map k v -> StableTree k v

-- | Convert a <a>StableTree</a> back into a <a>Map</a>
toMap :: Ord k => StableTree k v -> Map k v

-- | Things go wrong with end-user storage, but things can also go wrong
--   with reconstructing tree values. Implement <a>stableTreeError</a> to
--   allow <a>load</a> and <a>store</a> to report their own errors.
class Error e
stableTreeError :: Error e => Text -> e
load :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (a -> ObjectID -> m (Either e (a, Fragment k v))) -> a -> ObjectID -> m (Either e (a, StableTree k v))
load' :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (ObjectID -> m (Either e (Fragment k v))) -> ObjectID -> m (Either e (StableTree k v))

-- | Record the tree into storage. This works like a fold, where the
--   function takes an accumulating state and each tree fragment to store,
--   while returning either an error message (which will abort the loop
--   immediately) or the next state for the accumulator.
--   
--   Any fragment referring to other fragments (<a>FragmentBranch</a>
--   fragments) will be given to the fold only after all their children
--   have been given to the fold. Exact ordering beyond that is not
--   guaranteed, but the current behaviour is post-order depth-first
--   traversal.
store :: (Monad m, Error e, Ord k) => (a -> ObjectID -> Fragment k v -> m (Either e a)) -> a -> StableTree k v -> m (Either e a)
store' :: (Monad m, Error e, Ord k) => (ObjectID -> Fragment k v -> m (Maybe e)) -> StableTree k v -> m (Either e ObjectID)

-- | A <a>Fragment</a> is a user-visible part of a tree, i.e. a single node
--   in the tree that can actually be manipulated by a user. This is useful
--   when doing the work of persisting trees.
data Fragment k v
FragmentBranch :: Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: Map k v -> Fragment k v
fragmentMap :: Fragment k v -> Map k v