úÎf`Žh      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefg(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableUnsafe !"&'24<>INUVZA < is a reference from a struct to a normal Haskell data type.;We can compose slots to get a nested slot or field accessorA 2 is a reference to another unboxed mutable object. An instance for   t5 is a witness to the machine-level equivalence of t and Object. The argument to : is ignored and is only present to help type inference.A ' reifies an instance of the constraint p into a value.Truly imperative.cRun an ST calculation inside of a PrimMonad. This lets us avoid dispatching everything through the h dictionary.!Allocate a structure made out of n3 slots. Initialize the structure before proceeding! The  at the given position in a  !Get the value from a "Set the value of a #>Store the reference to the Haskell data type in a normal field$VStore the reference in the nth slot of the nth argument, treated as a MutableByteArray%$Get the value of a field in a struct&$Set the value of a field in a struct+  !"#$%&'()*'  !"#$%&+  *) ( !"'#$%&!   !"#$%&'()*(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableUnsafe +'Logarithmic time list labeling solution2.Construct an explicit list labeling structure.x <- makeLabel 0 Nil NilisNil xFalsen <- get next xisNil nTruep <- get prev xisNil pTrue3gO(1). Create a new labeling structure. Labels from different list labeling structures are incomparable.4O(1). Remove a label5;O(log n) amortized. Insert a new label after a given label.63O(1). Split off all labels after the current label.74O(1). Split off all labels before the current label.8O(n). Retrieve the least label9!O(n). Retrieve the greatest label:&O(1). Compare two labels for ordering.<”O(1). Extract the current value assignment for this label. Any label mutation, even on other labels in this label structure, may change this answer.=9O(n). Get the keys of every label from here to the right.+,-./0123456789:;<=>?+,-./0123456789:;<=-./01+,?>23456789:;<=+,-./0123456789:;<=>?(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portable Trustworthy +3456789: +3548967:(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableNone @GAmortized Link-Cut trees via splay trees based on Tarjan's little book.5These support O(log n) operations for a lot of stuff.The parameter af is an arbitrary user-supplied monoid that will be summarized along the path to the root of the tree.In this example the choice of i is j>, so we can get a textual description of the path to the root. x <- new "x" y <- new "y"!link x y -- now x is a child of yx == yFalse connected x yTrue z <- new "z"!link z x -- now z is a child of y(y ==) <$> root zTruecost z"yxz" w <- new "w" u <- new "u" v <- new "v"link u wlink v zlink w zcost u"yxzwu"(y ==) <$> root vTrue connected x vTruecut z D y x z y z ==> w v x w v u u  connected x vFalsecost u"zwu"(z ==) <$> root vTrueHAO(1). Allocate a new link-cut tree with a given monoidal summary.I O(log n). I v removes the linkage between v, upwards to whatever tree it was in, making v a root node.HRepeated calls on the same value without intermediate accesses are O(1).J O(log n). J v w inserts v3 which must be the root of a tree in as a child of w. v and w must not be K.K O(log n). K v w determines if v and w inhabit the same tree.L O(log n). L v( computes the root-to-leaf path cost of v under whatever i was built into the tree.HRepeated calls on the same value without intermediate accesses are O(1).M"O(log n). Find the root of a tree.HRepeated calls on the same value without intermediate accesses are O(1).N O(log n). Move upward one level.This will return  if the parent is not available.NNote: Repeated calls on the same value without intermediate accesses are O(1).OO(1)PO(log n)Q(O(log n). Splay within an auxiliary tree@ABCDEFGHIJKLMNOPQRS@ABCDEFGHIJKLMNOPQ@ASRBCDEFGHIJKLMNOPQ@ABCDEFGHIJKLMNOPQRS(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableNoneT$O(log n). Find the parent of a node.This will return Nil if the parent does not exist.HRepeated calls on the same value without intermediate accesses are O(1).T@HIJKLMT@HJIMLTKT(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableUnsafeUWThis structure maintains an order-maintenance structure as two levels of list-labeling. The upper labeling scheme holds  (n / log w) elements in a universe of size w^25, operating in O(log n) amortized time per operation.zIt is accelerated by an indirection structure where each smaller universe holds O(log w) elements, with total label space  2^log w = wi and O(1) expected update cost, so we can charge rebuilds to the upper structure to the lower structure.8Every insert to the upper structure is amortized across O(log w) operations below.UThis means that inserts are O(1) amortized, while comparisons remain O(1) worst-case.]$O(1) compareM, O(1) amortized insertUVWXYZ[\]^_`abcdefgUVWXYZ[\]^_`abcdeUVWgfXYZ[\]^_`abcdeUVWXYZ[\]^_`abcdefg(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portable TrustworthyU^_cUc^_(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett <ekmett@gmail.com> experimental non-portableUnsafeZ  !"#$%&   !"#$%&k         !"#$%&'()*+,,-./0123456789:;<=>?@@ABCD<E3FGHIJKLMNOPBQQR/01BS:54TUV3<WXYZ[\]^_]^`astruc_CFmSN591DUmHJRreZgfYmJ Data.StructData.Struct.InternalData.Struct.LabelData.Struct.Internal.LabelData.Struct.LinkCutData.Struct.Internal.LinkCutData.Struct.OrderData.Struct.Internal.OrderField Precomposable#SlotNullBoxObject runObjectStructstructDictNullPointerExceptionNilstdestruct constructunsafeCoerceStructeqStructallocisNil!writeSmallMutableArraySmallArray# readSmallMutableArraySmallArray# writeMutableByteArraySmallArray#readMutableByteArraySmallArray#slotgetsetfield unboxedFieldgetFieldsetField$fPrecomposablek*Field$fPrecomposablekkSlot $fEqObject$fStructObjectLabelKeymidBoundkeynextprev makeLabelnewdelete insertAftercutAfter cutBeforeleastgreatestcompareMdeltavaluekeys $fStructLabel $fEqLabelLinkCutpathparentleftrightsummarycutlink connectedcostrootup summarizeaccesssplay $fEqLinkCut$fStructLinkCutOrderrunOrder makeOrderlogUloglogUdeltaUvalues $fStructOrder $fEqOrderprimi_4EFP5cvZDduIYCPc8lT1lVControl.Monad.Primitive PrimMonadbaseGHC.BaseMonoidString