úÎ!ŽEŠ1     (c) Arnau Abella 2020MITarnauabell@gmail.com experimental non-portableNone0 "#$&',-./12456789;<=>?@ACHIMPSUVX_dfke!-rbstA random state in the  monad.rbst6A random state transformer for the pseudo-random bits.rbst data structure.rbst8 data structure. The node contains the rank of the tree.rbst Size of the  data structure.rbst7A pure mersenne twister pseudo-random number generator.It is created using a fixed seed. rbst7A pure mersenne twister pseudo-random number generator.AIt is created using a pseudo-random seed from the internal clock. rbst The empty . .> empty == fromList [] > size empty == 0 !rbstReturns an empty  from a ". rbst Single node .size (one 1 'a')1#rbstReturns a single node  from a ".$rbst Single node . rbst O(1) . Return the size of the .%rbst O(1)  . Return the  of the .&rbst O(1) . Return the size of the . rbst O(n) . Height of the tree.height (empty :: RBST Char Int)-1height (one 'x' 1)0height (one 'x' 1 <> one 'y' 2)1rbst O(\log \ n) *. Lookup the value at the key in the tree.#lookup 'A' (empty :: RBST Char Int)Nothinglookup 'A' (one 'A' 7)Just 7rbst O(\log \ n) *. Insert a new key/value pair in the tree.dIf the key is already present in the map, the associated value is replaced with the supplied value.  > insert x 1 empty == one x 1 'rbst for 'Tree'\' s in the .rbst O(\log \ n) q. Delete a key and its value from the map. When the key is not a member of the map, the original map is returned. > delete 1 (one (1, A )) == empty (rbst for 'Tree'\' s in the .rbst O(\log \ n) #. Get the i-th element of the tree.NOTE: 0 \leq i \leq n, where n is the size of the tree.Alet tree = fromList [('a',1), ('b', 2), ('c',3)] :: RBST Char Int at 0 tree Just ('a',1) at 2 tree Just ('c',3)rbst O(\log \ n) &. Delete the i-th element of the tree.NOTE: 0 \leq i \leq n, where n is the size of the tree.Alet tree = fromList [('a',1), ('b', 2), ('c',3)] :: RBST Char InttoList $ remove 0 tree[('b',2),('c',3)]rbst O(\log n) . Returns the first i-th elements of the given tree t of size n.Note: If  i \leq 0 , then the result is  .If  i \geq n , then the result is t.rbst O(\log n) . Returns the tree t without the first i -th elements.Note: If  i \leq 0 , then the result is t.If  i \geq n , then the result is  .rbst \theta(m + n) . Union of two .@In case of duplication, only one key remains by a random choice.rbst \theta(m + n) . Intersection of two .rbst \theta(m + n) ". Difference (subtraction) of two .rbst \theta(m + n) (. Difference (disjunctive union) of two .)rbstReturn a uniformly random * in the given range.+rbstGiven a random computation ! and an initial state, returns a .,rbstReturns the key of the  or -^. getKey :: Tree k a -> Maybe k getKey Empty = Nothing getKey (Node _ k _ _ _) = Just k {- INLINE getKey -}!Return the left subtree or empty..rbst"Return the right subtree or empty./rbst0 over z. overGen :: (Random.PureMT -> Random.PureMT) -> RBST k a -> RBST k a overGen f RBST{..} = RBST (f rbstGen) rbstTree {- INLINE overGen -} Set a new ^. setGen :: Random.PureMT -> RBST k a -> RBST k a setGen newGen = overGen (const newGen) {- INLINE setGen -}Lift a function from  to .1rbst O(1) (. Recompute tree size after modification2rbst O(1) . Rotate tree to the left.BeforeS%q%r %q %r %q %r %q %r %q%r C %q %r %q %r A BAfterd%q%r %q %r %q %r %q %r A %q%r %q %r %q %r B CàrotateR :: Tree k a -> Tree k a rotateR Empty = Empty rotateR node@(Node _ _ Empty _ _) = node rotateR (Node s k (Node _ k2 l2 c2 r2) c r) = Node s k2 l2 c2 newR where newR = recomputeSize $ Node s k r2 c r {- INLINEABLE rotateR -} O(1) . Rotate tree to the left.Befored%q%r %q %r %q %r %q %r A %q%r %q %r %q %r B CAfterS%q%r %q %r %q %r %q %r %q%r C %q %r %q %r A BàrotateL :: Tree k a -> Tree k a rotateL Empty = Empty rotateL node@(Node _ _ _ _ Empty) = node rotateL (Node s k l c (Node _ k2 l2 c2 r2)) = Node s k2 newL c2 r2 where newL = recomputeSize $ Node s k l c l2 {- INLINE rotateL -} O(1) .. Update the left node with the given subtree.FNotice, the size is not recomputed so you will probably need to call 1.3rbst O(1) /. Update the right node with the given subtree.FNotice, the size is not recomputed so you will probably need to call 1.4rbst O(\log \n ). Insert node at root using 5 and recompute the size.NOTE>: duplicated keys are removed by randomly picking one of them.5rbst"O(\log \n )\. Split the tree \( T  into two trees  T_<  and  T_> , which contain the keys of  T 9 that are smaller than x and larger than x, respectively.7This is a sligh variant which removes any duplicate of k" and returns a bool indicating so.6rbstYGiven a BST where left and right subtrees are random BST, returns a completly random BST.NOTE: the input can't be .7rbst O(\log \ n )J. Invariant: : All keys from p must be strictly smaller than any key of q.^Theorem. The join of two independent random binary search tree is a random binary search tree.8rbst<Create a tree from a list of key/value pairs, and viceversa.NOTE: This requires -XOverloadedLists enabled.-Functions have the following time complexity: 9:  O(n \cdot \log \ n) ::  O(n) .import GHC.Exts>let tree = (fromList $ zip ['a'..'e'] [1..5]) :: RBST Char IntPretty.prettyPrint tree ('d',4) [5] %q%r %q %r %q %r %q %r %q %r %q %r %q %r %q %r! %q %r# ('b',2) [3] ('e',5) [1] %q%r %q %r %q %r %q %r %q %r %q %r('a',1) [1] ('c',3) [1] toList tree)[('a',1),('b',2),('c',3),('d',4),('e',5)];rbst/(==) is implemented via (==) of the underlying .<rbstmempty is implemented via  .=rbst(<>) is implemented via merge.Note: Unlawful instance."TODO: require Semigroup a and use  unionWith"  ! # % )/(C) Arnau Abella 2020MIT (see the file LECENSE)!Arnau Abella arnauabell@gmail.com experimental non-portableNone0 "#$&',-./12456789;<=>?@ACHIMPSUVX_dfk…Ú>rbst1Intermidiate structure to help string conversion.rbst(Pretty 2-dimensional ASCII drawing of a .See  for an example.rbstCall , function and output the result directly to stdout.>let tree = (fromList $ zip ['a'..'e'] [1..5]) :: RBST Char IntprettyPrint tree ('d',4) [5] %q%r %q %r %q %r %q %r %q %r %q %r %q %r %q %r! %q %r# ('b',2) [3] ('e',5) [1] %q%r %q %r %q %r %q %r %q %r %q %r('a',1) [1] ('c',3) [1]rbst*Comptact 2-dimensional ASCII drawing of a .See  for an example.rbstCall comptact, function and output the result directly to stdout.>let tree = (fromList $ zip ['a'..'e'] [1..5]) :: RBST Char IntcompactPrint tree ('d',4) [5] | |-- ('e',5) [1] | \__ ('b',2) [3] | |-- ('c',3) [1] | \__ ('a',1) [1]?rbstShows a  with the size attached to it.@rbstDraw a & using one of the visualization modes.ArbstDraw a & using one of the visualization modes.BrbstShow 8 in a comptact way using given function to display node.CrbstShow 6 in a pretty way using given function to display node.Drbst8Hardcore function responsible for pretty showing of the > data type.Erbst Generates strings containing of n spaces.Frbst>Calculates position of middle of non-space part of the string. s = " abc "length s7middleLabelPos s4GrbstLike H but doesn't add "n" to the end.Irbst#Draws branches of the given height."putStrLn $ toLines $ branchLines 1%q%r"putStrLn $ toLines $ branchLines 2 %q%r%q %r"putStrLn $ toLines $ branchLines 3 %q%r %q %r%q %r(c) Arnau Abella 2020MIT (see the file LICENSE)!Arnau Abella arnauabell@gmail.com experimental non-portableNone0 "#$&',-./12456789;<=>?@ACHIMPSUVX_dfk‰U   J       !"#$%&'()*+,-./012340567809:;<=>?@AB0CD0CEFGHIJKLMNOPQR0STUV#rbst-0.0.0.0-5OlfDihuJlmLakDOq7NeyURBST RBST.Pretty RBST.Internal Data.FunctorIdentity comptactPrint$sel:rbstGen:RBST$sel:rbstTree:RBSTTreeNodeEmptySize$sel:unSize:Sizeemptyonesizeheightlookupinsertdeleteatremovetakedropunion intersection subtraction differencepretty prettyPrintcompact compactPrint MonadRand MonadRandTdefaultRandomGeneratorclockRandomGenerator emptyWithGen5mersenne-random-pure64-0.2.2.0-35EpKrD8qln9Nj0HmCyrfT&System.Random.Mersenne.Pure64.InternalPureMT oneWithGenoneTreesizeTree sizeTreeIntinsert'delete'uniformRbaseGHC.WordWord64runRandgetL GHC.MaybeNothinggetRwithTreeGHC.Basefmap recomputeSizeupdateLupdateR insertRootsplitpushDownjoin $fIsListRBSTGHC.ExtsfromListtoList$fEqRBST $fMonoidRBST$fSemigroupRBSTBinTreeshowNode drawComptact drawPretty comptactWith prettyWithshowTreespacesmiddleLabelPostoLines Data.OldListunlines branchLines