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


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


-- | Tools for working with StableTree keys. Just about anything can be a
--   key, so long as there's a sane way to implement IsKey and the standard
--   Ord class.
--   
--   Typical users don't need to worry about anything here other than
--   perhaps IsKey.
module Data.StableTree.Types.Key

-- | Type class for anything that we can use as a key. The goal here is to
--   wrap up a function that can generate a high-entropy eight-bit
--   <a>hash</a>. Speed is somewhat important here, but since we only
--   actually look at four bits of the hash, it really shouldn't be a
--   problem to quickly generate sufficiently random data.
--   
--   Implementors probably want to use <a>hashSerialize</a>,
--   <a>hashBinary</a>, or <a>hashByteString</a> when writing their
--   <a>hash</a> functions.
class IsKey k
hash :: IsKey k => k -> Word8

-- | 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>hash 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 :: IsKey k => k -> SomeKey k

-- | Extract the original key from a wrapped one
unwrap :: SomeKey k -> k

-- | Calculate a hash for an instance of <a>Serialize</a>
hashSerialize :: Serialize t => t -> Word8

-- | Calculate a hash for an instance of <a>Binary</a>
hashBinary :: Binary t => t -> Word8

-- | Calculate a hash for a <a>ByteString</a>
hashByteString :: ByteString -> Word8
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)
instance IsKey ByteString
instance IsKey ByteString
instance IsKey Word64
instance IsKey Word32
instance IsKey Word16
instance IsKey Word8
instance IsKey Word
instance IsKey Integer
instance IsKey Int64
instance IsKey Int32
instance IsKey Int16
instance IsKey Int8
instance IsKey Int
instance IsKey Float
instance IsKey Double
instance IsKey Char


-- | 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.Types

-- | Type class for anything that we can use as a key. The goal here is to
--   wrap up a function that can generate a high-entropy eight-bit
--   <a>hash</a>. Speed is somewhat important here, but since we only
--   actually look at four bits of the hash, it really shouldn't be a
--   problem to quickly generate sufficiently random data.
--   
--   Implementors probably want to use <a>hashSerialize</a>,
--   <a>hashBinary</a>, or <a>hashByteString</a> when writing their
--   <a>hash</a> functions.
class IsKey k
hash :: IsKey k => k -> Word8

-- | 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 <a>terminal</a>, 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
Bottom :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Complete k v
Branch :: Depth -> ValueCount -> (SomeKey k, Tree Complete k v) -> (SomeKey k, Tree Complete k v) -> Map (Key Nonterminal k) (Tree Complete k v) -> (Key Terminal k, Tree Complete k v) -> Tree Complete k v
IBottom0 :: Maybe (SomeKey k, v) -> Tree Incomplete k v
IBottom1 :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Incomplete k v
IBranch0 :: Depth -> ValueCount -> (SomeKey k, Tree Incomplete k v) -> Tree Incomplete k v
IBranch1 :: Depth -> ValueCount -> (SomeKey k, Tree Complete k v) -> Maybe (SomeKey k, Tree Incomplete k v) -> Tree Incomplete k v
IBranch2 :: Depth -> ValueCount -> (SomeKey k, Tree Complete k v) -> (SomeKey k, Tree Complete k v) -> Map (Key Nonterminal k) (Tree Complete k v) -> Maybe (SomeKey k, Tree Incomplete k v) -> Tree Incomplete 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

-- | 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

-- | 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, IsKey k) => 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, IsKey k) => 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 (Tree Complete k v), Maybe (k, Tree Incomplete k v)) (Map k v)

-- | 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 (Tree c k v)


-- | 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 opaque 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

-- | Type class for anything that we can use as a key. The goal here is to
--   wrap up a function that can generate a high-entropy eight-bit
--   <a>hash</a>. Speed is somewhat important here, but since we only
--   actually look at four bits of the hash, it really shouldn't be a
--   problem to quickly generate sufficiently random data.
--   
--   Implementors probably want to use <a>hashSerialize</a>,
--   <a>hashBinary</a>, or <a>hashByteString</a> when writing their
--   <a>hash</a> functions.
class IsKey k
hash :: IsKey k => k -> Word8

-- | Convert a <a>Map</a> into a <a>StableTree</a>.
fromMap :: (Ord k, IsKey k) => 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
instance (Ord k, Show k, Show v) => Show (StableTree k v)


-- | Logic for dealing with the actual persistence of Stable Trees. The key
--   exports here are <a>Error</a>, <a>Store</a>, <a>load</a>, and
--   <a>store</a>. A user needs to implement the <a>loadTree</a>,
--   <a>loadValue</a>, <a>storeTree</a> and <a>storeValue</a> parts of
--   <a>Store</a>, 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>Build</a>
--   for custom data types.
module Data.StableTree.Persist

-- | Write appropriate functions here to load and store primitive parts of
--   trees.
data Store m e k v
Store :: (Id -> m (Either e (Depth, ValueCount, Map k Id))) -> (Id -> m (Either e v)) -> (Id -> Depth -> ValueCount -> Map k Id -> m (Maybe e)) -> (Id -> v -> m (Maybe e)) -> Store m e k v
loadTree :: Store m e k v -> Id -> m (Either e (Depth, ValueCount, Map k Id))
loadValue :: Store m e k v -> Id -> m (Either e v)
storeTree :: Store m e k v -> Id -> Depth -> ValueCount -> Map k Id -> m (Maybe e)
storeValue :: Store m e k v -> Id -> v -> m (Maybe e)

-- | Typeclass to generate unique <a>ByteString</a>s for StableTree keys
--   and values. Used to generate the unique identities for values and
--   branches.
class Build t
build :: Build t => t -> Builder

-- | 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

-- | The opaque type to identify values and branches of trees.
data Id

-- | Convert an Id into a 32-byte ByteString. Useful for actual storage of
--   Ids
encodeId :: Id -> ByteString

-- | Convert a stored ByteString back into an Id. Gives a <a>Left err</a>
--   if the given ByteString isn't 32 bytes long
decodeId :: ByteString -> Either String Id

-- | Retrieve a tree given its id.
load :: (Monad m, IsKey k, Ord k, Error e) => Store m e k v -> Id -> m (Either e (StableTree k v))

-- | Store a tree using a <a>Store</a> and return its calculated <a>Id</a>
store :: (Monad m, Build k, Ord k, Build v) => Store m e k v -> StableTree k v -> m (Either e Id)

-- | Generate a builder for something that is already a <tt>Binary</tt>
buildBinary :: Binary t => t -> Builder

-- | Generate a builder for something that is already a <tt>Serialize</tt>
buildSerialize :: Serialize t => t -> Builder
instance Show Id
instance Eq Id
instance Ord Id
instance Build ByteString
instance Build ByteString
instance Build Word64
instance Build Word32
instance Build Word16
instance Build Word8
instance Build Word
instance Build Integer
instance Build Int64
instance Build Int32
instance Build Int16
instance Build Int8
instance Build Int
instance Build Float
instance Build Double
instance Build Char
instance Build Id


-- | A sample implementation of StableTree storage that just writes stuff
--   to some Maps that are wrapped in IORefs.
module Data.StableTree.Persist.Ram

-- | Error type for RAM storage. Not a lot can go wrong in RAM...
data RamError
NoTree :: Id -> RamError
NoVal :: Id -> RamError
ApiError :: Text -> RamError

-- | Create a new RAM store
storage :: IO (Store IO RamError k v, IORef (Map Id (Int, Int, Map k Id)), IORef (Map Id v))
instance Show RamError
instance Error RamError