úÎ`¿[H7      !"#$%&'()*+,-./0123456 Jeremy GrovenBSD3None ÿ: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 "hash". 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  ,  , or   when writing their  functions.Generate an 8-bit hashA sum type to contain either a  or a  *A wrapper for keys; this has an ephemeral t that will be either  or  depending on the result of hash k.Used to indicate that a  is not terminalUsed to indicate that a  is terminal )Do the magic of wrapping up a key into a  +Extract the original key from a wrapped one $Calculate a hash for an instance of 7 $Calculate a hash for an instance of 8 Calculate a hash for a 9 : ;<=>?@ABCDEFGHIJK  : ;<=>?@ABCDEFGHIJK Jeremy GrovenBSD3None!" MThe actual Rose Tree structure. StableTree is built on one main idea: every  is either  or  . A complete Ä 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 ¾ 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: ( |D| |B| |F| |A| |C| |E| |G| 7Now, suppose that we want to delete the data stored in |A|W. Then, we'll get a new structure that shares nothing in common with the original one: $ |E| |C| |G| |B| |D| |F| ÿ‘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.ÿoInstead, 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!Used to indicate that a  is completeUsed to indicate that a  is not complete!Wrap up some of a k/v map into a . A Lk result gives a complete tree and the map updated to not have the key/values that went into that tree. A MX result gives an incomplete tree that contains everything that the given map contained.&Generate a parent for a k/Tree map. A Lj result gives a complete tree and the map updated to not have the key/trees that went into that tree. A MX result gives an incomplete tree that contains everything that the given map contained.XGet the key of the first entry in this branch. If the branch is empty, returns Nothing.OGet the key of the fist entry in this complete branch. This function is total.&Convert an entire Tree into a k/v map.=Get the number of levels of branches that live below this oneoNon-recursive function to simply get the immediate children of the given branch. This will either give the key!value map of a Bottom, or the key!tree map of a non-bottom branch.NO NO Jeremy GrovenBSD3None StableTree* is the opaque type that wraps the actual @ implementation. All the public functions operate on this type." Convert a P into a .# Convert a  back into a P !"#Q !"#! "#! "#Q Jeremy GrovenBSD3NoneT$Typeclass to generate unique 9bs for StableTree keys and values. Used to generate the unique identities for values and branches.&MWrite appropriate functions here to load and store primitive parts of trees.,9The opaque type to identify values and branches of trees.-pThings go wrong with end-user storage, but things can also go wrong with reconstructing tree values. Implement . to allow / and 0 to report their own errors./Retrieve a tree given its id.0Store a tree using a & and return its calculated ,13Generate a builder for something that is already a Binary23Generate a builder for something that is already a  Serialize'$%&'()*+,R-./S0TUVWX12YZ[\]^_`abcdefghi$%&'()*+,-./012&'()*+$%-.,/012$%&'()*+,R-./S0TUVWX12YZ[\]^_`abcdefghi Jeremy GrovenBSD3None3<Error type for RAM storage. Not a lot can go wrong in RAM...6Create a new RAM store3456j345635463546jk      !"#$%&'()*+,,-./0123456789:;<=>?@ABCD EFGHIJKLMNOPQRSTUVWXVWYZ[\]^_1`abcdefghijklmnopqrstuvwxstable-tree-0.0.2Data.StableTree.Types.KeyData.StableTree.TypesData.StableTreeData.StableTree.IOData.StableTree.IO.RamIsKeyhashSomeKey SomeKey_N SomeKey_TKeyfromKey NonterminalTerminalwrapunwrap hashSerialize hashBinaryhashByteStringTreeIBranch2IBranch1IBranch0IBottom1IBottom0BranchBottomComplete Incomplete nextBottom nextBranchgetKey completeKey treeContentsgetDepthbranchContents StableTree StableTree_C StableTree_IfromMaptoMapBuildbuildStoreloadTree loadValue storeTree storeValueIdErrorstableTreeErrorloadstore buildBinarybuildSerializeRamErrorApiErrorNoKeystoragecereal-0.4.1.0Data.Serialize Serializebinary-0.7.1.0Data.Binary.ClassBinarybytestring-0.10.4.0Data.ByteString.Internal ByteStringfnv1a$fIsKeyByteString$fIsKeyByteString0 $fIsKeyWord64 $fIsKeyWord32 $fIsKeyWord16 $fIsKeyWord8 $fIsKeyWord$fIsKeyInteger $fIsKeyInt64 $fIsKeyInt32 $fIsKeyInt16 $fIsKeyInt8 $fIsKeyInt $fIsKeyFloat $fIsKeyDouble $fIsKeyCharbase Data.EitherRightLeft branchShow $fShowTreecontainers-0.5.5.1 Data.Map.BaseMap$fShowStableTreeload'store'treeHashcalcId liftEitherIO liftMaybeIO$fBuildByteString$fBuildByteString0 $fBuildWord64 $fBuildWord32 $fBuildWord16 $fBuildWord8 $fBuildWord$fBuildInteger $fBuildInt64 $fBuildInt32 $fBuildInt16 $fBuildInt8 $fBuildInt $fBuildFloat $fBuildDouble $fBuildChar $fBuildId$fErrorRamError