KU      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRST Jeremy GrovenBSD3NoneA 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 byte 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 oneU#Calculate a single-byte hash for a V WUX  WUX Jeremy GrovenBSD3None!"*:MT Get the ObjectID of a  or ! Get the depth (height?) of a  or ! :Get the total number of key/value pairs stored under this  or ! $Do the (expensive) calculation of a  or !V; generally used to do the initial ObjectID calculation when constructing an instance lRecalculate the object's ObjectID and return the updated object; pretty much a convenience function around  Get the  representing this exact # node, used for persistent storageA  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, and its serialize instance is also used to calculate Tree ObjectIDs. See  and  < for functions to convert between Fragments and Trees. see   and  < for functions related to storing and retrieving Fragments.HThe actual B-Tree variant. StableTree is built on one main idea: every  is either  or  , and every  is  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 children 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 terminal 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 achieved!?Empty type to indicate a Tree with some known height (a branch)=Empty type to indicate a Tree with Zero depth (a bottom node)Used to indicate that a  is complete Used to indicate that a  is not complete! StableTree0 is the user-visible type that wraps the actual @ implementation. All the public functions operate on this type.$AAlias that indicates the total number of values underneath a tree%FAlias to indicate how deep a branch in a tree is. Bottoms have depth 0&Helper to create a $ instance with a calculated ObjectID'Helper to create an $ instance with a calculated ObjectID(Helper to create an $ instance with a calculated ObjectID)Helper to create a $ instance with a calculated ObjectID*Helper to create an $ instance with a calculated ObjectID+Helper to create an $ instance with a calculated ObjectID,Helper to create an $ instance with a calculated ObjectID+Y  !"#$%&'()*+,Z[\]^_$  !"#$%&'()*+,$%$!#" &'()*+, Y  !#"$%&'()*+,Z[\]^_ Jeremy GrovenBSD3None!" -XGet the key of the first entry in this branch. If the branch is empty, returns Nothing..PGet the key of the first entry in this complete branch. This function is total./-Get the total number of k/v pairs in the tree0ZGet the value associated with the given key, or Nothing if there is no value for the key.1Get the keys in the map2"Get the elements stored in the map3"Get the key/value pairs in the map4&Convert an entire Tree into a k/v map.5 Convert a ! into a normal key/value Map6*Either get the StableTree "children" of a !<, or get the key/value map if the tree is already a bottom.7oNon-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.8Get the gs stored under the given Tree. The Tree type prevents this function from being called on bottom Trees.9Choose the child node most likely to hold the given key. If this returns Left, then the chosen node is the Incomplete node. In the Right case, the sole Complete node is the best node. The Complete nodes in the first slot of the quad are the nodes that came before the chosen node, while the nodes in the third slot are the nodes that came after. This is useful for changing a specific node, and then patching things back together with the   function. -./0123456789 -./0123456789 -./0123456789 -./0123456789 Jeremy GrovenBSD3None!":MT :Result of the G& function; values are described below.>0Convert a simple key/value map into a StableTree?Create a new empty StableTree@0Smash two StableTree instances into a single oneA=Smash a whole bunch of StableTree instances into a single oneBlHelper function to convert a complete bunch of Tree instances (of the same depth) into a single StableTree.`lHelper function to reduce trees to their minimum height by removing root branches that only have one child.C=Convert a single key/value map into Tree bottom (zero-depth) instances. The resulting list of Tree instances will never be overlapping, and will be sorted such that each Tree's highest key is lower than the next Tree's lowest key. This is not guaranteed by types because i don't think that can be done in Haskell.DCGiven a mapping from each Tree's first key to that Tree, (and a final incomplete Tree if desired), this will build the next level of Tree instances. As with consumeMap, the resulting list of Tree instances will be non-overlapping and ordered such that each Tree's highest key is smaller than the next Tree's lowest key.EGiven a simple listing of complete Trees and maybe an incomplete one, this will build the next level ot Trees. This just builds a map and calls the previous D2 function, but it's a convenient function to have.F!Wrap up some of a k/v map into a . A ak result gives a complete tree and the map updated to not have the key/values that went into that tree. A bX result gives an incomplete tree that contains everything that the given map contained.G'Generate a parent for a k/Tree map. An =B result means that the function was called with an empty Map and c for an incomplete. A <Y result means that an incomplete Tree was build and there is no more work to be done. A ;W result means that a complete Tree was built, and there is (possibly) more work to do.HTree mutation functions (insert, delete) will generally wind up with a bunch of Trees that come before the key that was to be changed, and then the result of updating the relevant Tree, and then a bunch of Trees (and maybe an incomplete Tree) that come after it. Merge can splice this result back into a correctly ordered, non-overlapping list of complete Trees and maybe a final incomplete one.:;<=>?@AB`CDEFGHd:;<=>?@ABCDEFGH>?@ABCDEF:=<;GH:=<;>?@AB`CDEFGHdNone!"TI Same as the I instance of eW, but with the restriction that the input and output of the mutation function must be V[-able. Using the real instance would be really cool, but we need that Serialize instance.JInsert a key/value into a !8. If the key exists, its existing value is overwritten.KRemove a key from the !;. If the key is not found, the tree is returned unchanged.fSame as J, but works on a , and returns a list of completes and a maybe incomplete instead of returning something that probably can't be expressed in Haskell's type system.gSame as K, but works on a , and returns a list of completes and a maybe incomplete instead of returning something that probably can't be expressed in Haskell's type system.hFind the 'Tree Z' instance that should contain the given key, and call the given function on its contents. Once that's done, splice the result back into a new tree, which will probably be really similar to the original, but have the desired changes applied. iIJKfghjkIJKJKIiIJKfghjk Jeremy GrovenBSD3NoneL Convert a !  into a list of storable Bs. The resulting list is guaranteed to be in an order where each & will be seen after all its children.M Recover a  from a single . and a map of the fragments as returned from L. If the fragment set was already stored, it is the caller's responsibility to load all the child fragments into a map (probably involving finding children using the fragmentChildren field of the Fragment type).NDirectly convert a bunch of s and a root fragment into a l= instance. Mostly useful for testing the correctness of the M function.m@Build a list of the 'Tree Z' instances that come from the given . The resulting Trees non-overlapping and ordered such that each Tree's highest key is lower than the next Tree's lowest key, but illegal Fragments could break that.LMNmLMNLMNLMNm Jeremy GrovenBSD3NoneTOpThings go wrong with end-user storage, but things can also go wrong with reconstructing tree values. Implement P to allow S and Q to report their own errors.QRecord 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 ( 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.RDAlternate store function that acts more like a map than a fold. See Q for details.S Reverse of Q . As with Q*, this acts like a fold, but converts an n] into a tree, rather than storing a tree. This will always build the tree from the top down.T Version of S) that acts like a map rather than a fold.OPQRST OPQRST OPQRSTOPQRST  Jeremy GrovenBSD3None!/01235>?@AIJK!>?JK/0123I@A5o !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTU VWX YZ[ \ ]^_`abcdefghijklmklnkopqkrstuvwxyz{|}~stable-tree-0.6.0Data.StableTree.KeyData.StableTree.TypesData.StableTree.PropertiesData.StableTree.BuildData.StableTree.MutateData.StableTree.ConversionData.StableTree.Persist toFragments fromFragmentsstoreloadmergeData.StableTreeSomeKey SomeKey_N SomeKey_TKeyfromKey NonterminalTerminalwrapunwrap getObjectIDgetDepth getValueCount calcObjectID fixObjectID makeFragmentFragmentFragmentBottom fragmentMapFragmentBranch fragmentDepthfragmentChildrenTreeIBranch2IBranch1IBranch0BranchIBottom1IBottom0BottomSZComplete Incomplete StableTree StableTree_C StableTree_I ValueCountDepthmkBottom mkIBottom0 mkIBottom1mkBranch mkIBranch0 mkIBranch1 mkIBranch2getKey completeKeysizelookupkeyselemsassocs treeContentstoMapstableChildrenbottomChildrenbranchChildren selectNode NextBranchMoreFinalEmptyfromMapemptyappendconcatconsume consumeMapconsumeBranchesconsumeBranches' nextBottom nextBranchfmapinsertdelete fragsToMapErrorstableTreeErrorstore'load'bytecereal-0.4.1.1Data.Serialize Serializefnv1aTreeNode$fSerializeFragment$fOrdStableTree$fEqStableTree$fEqTree$fTreeNodeStableTree$fTreeNodeTreeprunebase Data.EitherRightLeft Data.MaybeNothingconcat'GHC.BaseFunctorinsert'delete' mutateBottom SerialFunctor$fSerialFunctorStableTree$fSerialFunctorTreecontainers-0.5.5.1 Data.Map.BaseMapfragsToBottomsobjectid-0.1.0.2 Data.ObjectIDObjectID