úÎÂÒ»mP      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNO  Jeremy GrovenBSD3None Type class for  StableTree keysˆGet the "hash" of a key; this is just a single-byte, of which only four bits are really used. Just enough to allow one key in 16 to be A 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 one #Calculate a single-byte hash for a P3Q RSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw   .Q RSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvw Jeremy GrovenBSD3None!"*:MT Get the depth (height?) of a  or  :Get the total number of key/value pairs stored under this  or 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 completeUsed 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 treeFAlias to indicate how deep a branch in a tree is. Bottoms have depth 0x yz{|}~€  x yz{|}~€ 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 tree"ZGet the value associated with the given key, or Nothing if there is no value for the key.#Get the keys in the map$"Get the elements stored in the map%"Get the key/value pairs in the map&&Convert an entire Tree into a k/v map.' Convert a  into a normal key/value Map(*Either get the StableTree "children" of a <, or get the key/value map if the tree is already a bottom.)oNon-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.*Get the gs stored under the given Tree. The Tree type prevents this function from being called on bottom Trees.+ÿ½Choose 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.  !"#$%&'()*+  !"#$%&'()*+  !"#$%&'()*+  !"#$%&'()*+ Jeremy GrovenBSD3None!",/Monadic fold over a StableTree in the style of  .-)Right fold over a StableTree. Similar to  ..(Left fold over a StableTree. Similar to  .,-.,-.,-.,-. Jeremy GrovenBSD3None!":MT /Result of the <& function; values are described below.30Convert a simple key/value map into a StableTree4Create a new empty StableTree50Smash two StableTree instances into a single one6=Smash a whole bunch of StableTree instances into a single one7lHelper 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.8ÿ=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.9ÿCGiven 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.:ŸGiven 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 92 function, but it's a convenient function to have.;!Wrap up some of a k/v map into a . A ‚k result gives a complete tree and the map updated to not have the key/values that went into that tree. A ƒX result gives an incomplete tree that contains everything that the given map contained.<'Generate a parent for a k/Tree map. An 2B result means that the function was called with an empty Map and „ for an incomplete. A 1Y result means that an incomplete Tree was build and there is no more work to be done. A 0W result means that a complete Tree was built, and there is (possibly) more work to do.=ÿTree 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./0123456789:;<=…/0123456789:;<=3456789:;/210<=/2103456789:;<=… Jeremy GrovenBSD3None!"T>Insert a key/value into a 8. If the key exists, its existing value is overwritten.?Remove a key from the ;. If the key is not found, the tree is returned unchanged.†Same as >, 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.‡Same as ?, 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.ˆÿFind 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.>?†‡ˆ>?>?>?†‡ˆ Jeremy GrovenBSD3None!"T @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. See G and H< for functions to convert between Fragments and Trees. see  and < for functions related to storing and retrieving Fragments.G 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.‰ Convert a  into @8s. This returns a pair, where the first element is the @ that came directly from the 1, and the second element is the list of all the @s beneath the  , and the ‘s fragment itself. The list is always sorted lowest to highest, so its last element is always the same entity as the first element of the pair. ŠSMake a Bottom element into a FragmentBottom. Always returns (fragment, [fragment])‹'Make a Branch into a bunch of FragmentsH Recover a  from a single @. and a map of the fragments as returned from GÖ. 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).IDirectly convert a bunch of @s and a root fragment into a Œ= instance. Mostly useful for testing the correctness of the H function.@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.ŽCalculate the @s ?, and patch it into place. This is generally used to create a @ , like so: ^fixFragmentID $ FragmentBottom undefined foo fixFragmentID $ FragmentBranch undefined foo bar @ABCDEFG‰Š‹HIŽ @ABCDEFGHI @CADEFDBGHI @CADEFDBG‰Š‹HIŽ Jeremy GrovenBSD3NoneTJpThings go wrong with end-user storage, but things can also go wrong with reconstructing tree values. Implement K to allow N and L to report their own errors.Lÿÿ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 (CÐ 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.MDAlternate store function that acts more like a map than a fold. See L for details.N Reverse of L . As with L*, this acts like a fold, but converts an ] into a tree, rather than storing a tree. This will always build the tree from the top down.O Version of N) that acts like a map rather than a fold.JKLMNO @ABCDEFJKLMNOJK@CADEFDBLMNOJKLMNO Jeremy GrovenBSD3None !"#$%'3456>? 34>?!"#$%56'‘ !"#$%&'()*+,-./0123456789:;<= >?@ABCDEFGHIJKLM NOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“‘’”‘•–—˜™š›œžŸ ¡¢£¤¥¦§stable-tree-0.7.0Data.StableTree.KeyData.StableTree.TypesData.StableTree.PropertiesData.StableTree.WalkData.StableTree.BuildData.StableTree.MutateData.StableTree.ConversionData.StableTree.Persistmerge Control.MonadfoldMData.Map foldrWithKey foldlWithKeystoreloadData.StableTree StableKeyhashSomeKey SomeKey_N SomeKey_TKeyfromKey NonterminalTerminalwrapunwraphashBsgetDepth getValueCountTreeIBranch2IBranch1IBranch0BranchIBottom1IBottom0BottomSZComplete Incomplete StableTree StableTree_C StableTree_I ValueCountDepthgetKey completeKeysizelookupkeyselemsassocs treeContentstoMapstableChildrenbottomChildrenbranchChildren selectNodefoldrfoldl NextBranchMoreFinalEmptyfromMapemptyappendconcatconsume consumeMapconsumeBranchesconsumeBranches' nextBottom nextBranchinsertdeleteFragmentFragmentBottom fragmentMapFragmentBranchfragmentObjectID fragmentDepthfragmentChildren toFragments fromFragments fragsToMapErrorstableTreeErrorstore'load'bytestring-0.10.4.0Data.ByteString.Internal ByteStringfnv1a$fStableKey(,,,,,,,,,)$fStableKey(,,,,,,,,)$fStableKey(,,,,,,,)$fStableKey(,,,,,,)$fStableKey(,,,,,)$fStableKey(,,,,)$fStableKey(,,,)$fStableKey(,,)$fStableKeyMap$fStableKey(,)$fStableKeyEither$fStableKeySeq$fStableKeyTree$fStableKeySet$fStableKeyIntMap$fStableKeyMaybe$fStableKeyRatio $fStableKey[]$fStableKeyIntSet$fStableKeyByteString$fStableKeyByteString0$fStableKeyWord64$fStableKeyWord32$fStableKeyWord16$fStableKeyWord8$fStableKeyWord$fStableKeyOrdering$fStableKeyInteger$fStableKeyInt64$fStableKeyInt32$fStableKeyInt16$fStableKeyInt8$fStableKeyInt$fStableKeyFloat$fStableKeyDouble$fStableKeyChar$fStableKeyBoolTreeNodeequalsntEquals$fFunctorStableTree $fFunctorTree$fEqStableTree$fEqTree$fTreeNodeStableTree$fTreeNodeTreeprunebase Data.EitherRightLeft Data.MaybeNothingconcat'insert'delete' mutateBottom toFragments'bottomToFragmentsbranchToFragmentscontainers-0.5.5.1 Data.Map.BaseMapfragsToBottoms fixFragmentIDobjectid-0.1.0.2 Data.ObjectIDObjectID$fSerializeFragment