h$#!      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcd e f g hijklmnopqrstuv (C) 2015-2017 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portableUnsafe&'(-.9:? structsA < is a reference from a struct to a normal Haskell data type. structs;We can compose slots to get a nested slot or field accessor structsA  2 is a reference to another unboxed mutable object.structs>Box is designed to mirror object's single field but using the  type instead of a mutable array. This hack relies on GHC reusing the same  data constructor for all occurrences. Box's field must not be strict to prevent the compiler from making assumptions about its contents.structsAn instance for  t5 is a witness to the machine-level equivalence of t and Object.structsA ' reifies an instance of the constraint p into a value.structsTruly imperative.structsRun an ST calculation inside of a PrimMonad. This lets us avoid dispatching everything through the w dictionary.$structs!Allocate a structure made out of n3 slots. Initialize the structure before proceeding!%structs"Predicate to check if a struct is .$isNil (Nil :: Object (PrimState IO))True*o <- alloc 1 :: IO (Object (PrimState IO))isNil oFalse+structsThe   at the given position in a ,structsGet the value from a  -structsSet the value of a  .structsCompare-and-swap the value of the slot. Takes the expected old value, the new value and returns if it succeeded and the value found./structs>Store the reference to the Haskell data type in a normal field0structsStore the reference in the nth slot in the nth argument, treated as a MutableByteArray1structs&Initialized the mutable array used by 0. Returns the array after storing it in the struct to help with initialization.2structs$Get the value of a field in a struct3structs$Set the value of a field in a struct+structsslot /structsslot 0structsslot structs argument 1structs slot structs elements structs element size structs struct .  !"#$%&'()*+,-./012345. !"#$%&'()* +,-. /012345(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portableUnsafe   !#$%+,-/02345 !#$% +,-/02345 (C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portableUnsafe <structs'Logarithmic time list labeling solutionCstructs.Construct an explicit list labeling structure.x <- makeLabel 0 Nil NilisNil xFalsen <- get next xisNil nTruep <- get prev xisNil pTrueDstructsO(1). Create a new labeling structure. Labels from different list labeling structures are incomparable.EstructsO(1). Remove a labelFstructs;O(log n) amortized. Insert a new label after a given label.Gstructs3O(1). Split off all labels after the current label.Hstructs4O(1). Split off all labels before the current label.IstructsO(n). Retrieve the least labelJstructs!O(n). Retrieve the greatest labelKstructs&O(1). Compare two labels for ordering.MstructsO(1). Extract the current value assignment for this label. Any label mutation, even on other labels in this label structure, may change this answer.Nstructs9O(n). Get the keys of every label from here to the right.<=>?@ABCDEFGHIJKLMN>?@AB<=CDEFGHIJKLMN(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portable Trustworthy  experimental non-portableUnsafeDQstructsThis 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.It is accelerated by an indirection structure where each smaller universe holds O(log w) elements, with total label space  2^log w = w 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.This means that inserts are O(1) amortized, while comparisons remain O(1) worst-case.Zstructs$O(1) compareM, O(1) amortized insertQRSTUVWXYZ[\]^_`aQRSTUVWXYZ[\]^_`a(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portable TrustworthyQU[\`Q`U[\ NonedstructsGenerate allocators, slots, fields, unboxed fields, Eq instances, and Struct instances for the given "data types".Inputs are expected to be "data types" parameterized by a state type. Strict fields are considered to be slots, Non-strict fields are considered to be boxed types, Unpacked fields are considered to be unboxed primitives.The data type should use record syntax and have a single constructor. The field names will be used to generate slot, field, and unboxedField values of the same name.An allocator for the struct is generated by prefixing "alloc" to the data type name.dd(C) 2015-2017 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portableNone  structsAmortized 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 a 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 x is y>, 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  y x z y z ==> w v x w v u u  connected x vFalsecost u"zwu"(z ==) <$> root vTruejstructsO(1). Allocate a new link-cut tree with a given monoidal summary.kstructs O(log n). k v removes the linkage between v, upwards to whatever tree it was in, making v a root node.Repeated calls on the same value without intermediate accesses are O(1).lstructs O(log n). l v w inserts v3 which must be the root of a tree in as a child of w. v and w must not be m.mstructs O(log n). m v w determines if v and w inhabit the same tree.nstructs O(log n). n v( computes the root-to-leaf path cost of v under whatever x was built into the tree.Repeated calls on the same value without intermediate accesses are O(1).ostructs"O(log n). Find the root of a tree.Repeated calls on the same value without intermediate accesses are O(1).pstructs O(log n). Move upward one level.This will return  if the parent is not available.Note: Repeated calls on the same value without intermediate accesses are O(1).qstructsO(1)rstructsO(log n)sstructs(O(log n). Splay within an auxiliary treehijklmnopqrsihjklmnopqrs(C) 2015 Edward Kmett BSD-style (see the file LICENSE)Edward Kmett  experimental non-portableNone!vstructs$O(log n). Find the parent of a node.This will return Nil if the parent does not exist.Repeated calls on the same value without intermediate accesses are O(1).jklmnovjlkonvm      !"#$%&'()*+,-./0123456789:;<==>?@ABCDEFGHIJKLMNOPPQ@AB RKFESTUDMVW X Y Z [\]D^_`abcdefgh ijklmnlmo#structs-0.1.5-AUN1qHa2aa1CS54VmxEwuData.Struct.LinkCutData.Struct.Internal.LinkCut Data.StructData.Struct.InternalData.Struct.LabelData.Struct.Internal.LabelData.Struct.OrderData.Struct.Internal.OrderData.Struct.THLinkCutpathparentleftrightvaluesummaryField Precomposable#SlotNullBoxObject runObjectStructstructDictNullPointerExceptionNilstcoerceFcoerceBdestruct constructunsafeCoerceStructeqStructallocisNil!writeSmallMutableArraySmallArray# readSmallMutableArraySmallArray# writeMutableByteArraySmallArray#readMutableByteArraySmallArray#casSmallMutableArraySmallArray#slotgetsetcasfield unboxedFieldinitializeUnboxedFieldgetFieldsetField modifyField modifyField' $fEqObject$fStructObject$fPrecomposablekkSlot$fPrecomposablekTYPEField$fShowNullPointerException$fExceptionNullPointerExceptionLabelKeymidBoundkeynextprev makeLabelnewdelete insertAftercutAfter cutBeforeleastgreatestcompareMdeltakeys $fStructLabel $fEqLabelOrderrunOrder makeOrderlogUloglogUdeltaU $fStructOrder $fEqOrder makeStruct$fShowStructRep $fShowMember$fShowRepresentation newLinkCut allocLinkCutcutlink connectedcostrootup summarizeaccesssplay $fEqLinkCut$fStructLinkCut'primitive-0.7.1.0-Jxsyd70oUttYiCXCa0HqVControl.Monad.Primitive PrimMonadbaseGHC.BaseMonoidString