-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Strict GC'd imperative object-oriented programming with cheap pointers.
--
-- This project is an experiment with a small GC'd strict mutable
-- imperative universe with cheap pointers inside of the GHC runtime
-- system.
@package structs
@version 0
module Data.Struct.Internal
data NullPointerException
[NullPointerException] :: NullPointerException
-- | A Dict reifies an instance of the constraint p into a
-- value.
data Dict p
[Dict] :: Dict p
-- | Run an ST calculation inside of a PrimMonad. This lets us avoid
-- dispatching everything through the PrimMonad dictionary.
st :: PrimMonad m => ST (PrimState m) a -> m a
-- | An instance for Struct t is a witness to the
-- machine-level equivalence of t and Object. The
-- argument to struct is ignored and is only present to help type
-- inference.
class Struct t
struct :: Struct t => proxy t -> Dict (Coercible (t s) (Object s))
data Object s
[Object] :: SmallMutableArray# s Any -> Object s
[runObject] :: Object s -> SmallMutableArray# s Any
destruct :: Struct t => t s -> SmallMutableArray# s Any
construct :: Struct t => SmallMutableArray# s Any -> t s
unsafeCoerceStruct :: (Struct x, Struct y) => x s -> y s
eqStruct :: Struct t => t s -> t s -> Bool
-- | Allocate a structure made out of n slots. Initialize the
-- structure before proceeding!
alloc :: (PrimMonad m, Struct t) => Int -> m (t (PrimState m))
data Box
[Box] :: !Null -> Box
data Null
[Null] :: Null
isNil :: Struct t => t s -> Bool
-- | Truly imperative.
writeSmallMutableArraySmallArray# :: SmallMutableArray# s Any -> Int# -> SmallMutableArray# s Any -> State# s -> State# s
readSmallMutableArraySmallArray# :: SmallMutableArray# s Any -> Int# -> State# s -> (# State# s, SmallMutableArray# s Any #)
writeMutableByteArraySmallArray# :: SmallMutableArray# s Any -> Int# -> MutableByteArray# s -> State# s -> State# s
readMutableByteArraySmallArray# :: SmallMutableArray# s Any -> Int# -> State# s -> (# State# s, MutableByteArray# s #)
-- | A Slot is a reference to another unboxed mutable object.
data Slot x y
[Slot] :: (forall s. SmallMutableArray# s Any -> State# s -> (# State# s, SmallMutableArray# s Any #)) -> (forall s. SmallMutableArray# s Any -> SmallMutableArray# s Any -> State# s -> State# s) -> Slot x y
-- | We can compose slots to get a nested slot or field accessor
class Precomposable t
(#) :: Precomposable t => Slot x y -> t y z -> t x z
-- | The Slot at the given position in a Struct
slot :: Int -> Slot s t
-- | Get the value from a Slot
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))
-- | Set the value of a Slot
set :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> m ()
-- | A Field is a reference from a struct to a normal Haskell data
-- type.
data Field x a
[Field] :: (forall s. SmallMutableArray# s Any -> State# s -> (# State# s, a #)) -> (forall s. SmallMutableArray# s Any -> a -> State# s -> State# s) -> Field x a
-- | Store the reference to the Haskell data type in a normal field
field :: Int -> Field s a
-- | Store the reference in the nth slot of the nth argument, treated as a
-- MutableByteArray
unboxedField :: Prim a => Int -> Int -> Field s a
-- | Get the value of a field in a struct
getField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> m a
-- | Set the value of a field in a struct
setField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> a -> m ()
instance Exception NullPointerException
instance Show NullPointerException
instance Struct Object
instance Eq (Object s)
instance Precomposable Slot
instance Precomposable Field
module Data.Struct.Internal.Label
type Key = Word64
midBound :: Key
key :: Field Label Key
next :: Slot Label Label
prev :: Slot Label Label
-- | Logarithmic time list labeling solution
newtype Label s
[Label] :: (Object s) -> Label s
-- | Construct an explicit list labeling structure.
--
--
-- >>> x <- makeLabel 0 Nil Nil
--
-- >>> isNil x
-- False
--
-- >>> n <- get next x
--
-- >>> isNil n
-- True
--
-- >>> p <- get prev x
--
-- >>> isNil p
-- True
--
makeLabel :: PrimMonad m => Key -> Label (PrimState m) -> Label (PrimState m) -> m (Label (PrimState m))
-- | O(1). Create a new labeling structure. Labels from different list
-- labeling structures are incomparable.
new :: PrimMonad m => m (Label (PrimState m))
-- | O(1). Remove a label
delete :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(log n) amortized. Insert a new label after a given label.
insertAfter :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(1). Split off all labels after the current label.
cutAfter :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(1). Split off all labels before the current label.
cutBefore :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(n). Retrieve the least label
least :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(n). Retrieve the greatest label
greatest :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(1). Compare two labels for ordering.
compareM :: PrimMonad m => Label (PrimState m) -> Label (PrimState m) -> m Ordering
delta :: Key -> Word64 -> Key
-- | 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.
value :: PrimMonad m => Label (PrimState m) -> m Key
-- | O(n). Get the keys of every label from here to the right.
keys :: PrimMonad m => Label (PrimState m) -> m [Key]
instance Eq (Label s)
instance Struct Label
module Data.Struct.Label
-- | Logarithmic time list labeling solution
data Label s
-- | O(1). Create a new labeling structure. Labels from different list
-- labeling structures are incomparable.
new :: PrimMonad m => m (Label (PrimState m))
-- | O(log n) amortized. Insert a new label after a given label.
insertAfter :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(1). Remove a label
delete :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(n). Retrieve the least label
least :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(n). Retrieve the greatest label
greatest :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))
-- | O(1). Split off all labels after the current label.
cutAfter :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(1). Split off all labels before the current label.
cutBefore :: PrimMonad m => Label (PrimState m) -> m ()
-- | O(1). Compare two labels for ordering.
compareM :: PrimMonad m => Label (PrimState m) -> Label (PrimState m) -> m Ordering
module Data.Struct.Internal.LinkCut
-- | Amortized Link-Cut trees via splay trees based on Tarjan's little
-- book.
--
-- These 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 Monoid is String, 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 y
--
-- >>> x == y
-- False
--
-- >>> connected x y
-- True
--
-- >>> z <- new "z"
--
-- >>> link z x -- now z is a child of y
--
-- >>> (y ==) <$> root z
-- True
--
-- >>> cost z
-- "yxz"
--
-- >>> w <- new "w"
--
-- >>> u <- new "u"
--
-- >>> v <- new "v"
--
-- >>> link u w
--
-- >>> link v z
--
-- >>> link w z
--
-- >>> cost u
-- "yxzwu"
--
-- >>> (y ==) <$> root v
-- True
--
-- >>> connected x v
-- True
--
-- >>> cut z
--
--
--
-- y
-- x z y
-- z ==> w v x
-- w v u
-- u
--
--
--
-- >>> connected x v
-- False
--
-- >>> cost u
-- "zwu"
--
-- >>> (z ==) <$> root v
-- True
--
newtype LinkCut a s
[LinkCut] :: (Object s) -> LinkCut a s
path :: Slot (LinkCut a) (LinkCut a)
parent :: Slot (LinkCut a) (LinkCut a)
left :: Slot (LinkCut a) (LinkCut a)
right :: Slot (LinkCut a) (LinkCut a)
value :: Field (LinkCut a) a
summary :: Field (LinkCut a) a
-- | O(1). Allocate a new link-cut tree with a given monoidal summary.
new :: (PrimMonad m, Monoid a) => a -> m (LinkCut a (PrimState m))
-- | O(log n). cut 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).
cut :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m ()
-- | O(log n). link v w inserts v which must be
-- the root of a tree in as a child of w. v and
-- w must not be connected.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()
-- | O(log n). connected v w determines if v and
-- w inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool
-- | O(log n). cost v computes the root-to-leaf path cost
-- of v under whatever Monoid was built into the tree.
--
-- Repeated calls on the same value without intermediate accesses are
-- O(1).
cost :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m a
-- | O(log n). Find the root of a tree.
--
-- Repeated calls on the same value without intermediate accesses are
-- O(1).
root :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))
-- | O(log n). Move upward one level.
--
-- This will return Nil if the parent is not available.
--
-- Note: Repeated calls on the same value without intermediate accesses
-- are O(1).
up :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))
-- | O(1)
summarize :: Monoid a => LinkCut a s -> ST s a
-- | O(log n)
access :: Monoid a => LinkCut a s -> ST s ()
-- | O(log n). Splay within an auxiliary tree
splay :: Monoid a => LinkCut a s -> ST s ()
instance Struct (LinkCut a)
instance Eq (LinkCut a s)
module Data.Struct.LinkCut
-- | Amortized Link-Cut trees via splay trees based on Tarjan's little
-- book.
--
-- These 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 Monoid is String, 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 y
--
-- >>> x == y
-- False
--
-- >>> connected x y
-- True
--
-- >>> z <- new "z"
--
-- >>> link z x -- now z is a child of y
--
-- >>> (y ==) <$> root z
-- True
--
-- >>> cost z
-- "yxz"
--
-- >>> w <- new "w"
--
-- >>> u <- new "u"
--
-- >>> v <- new "v"
--
-- >>> link u w
--
-- >>> link v z
--
-- >>> link w z
--
-- >>> cost u
-- "yxzwu"
--
-- >>> (y ==) <$> root v
-- True
--
-- >>> connected x v
-- True
--
-- >>> cut z
--
--
--
-- y
-- x z y
-- z ==> w v x
-- w v u
-- u
--
--
--
-- >>> connected x v
-- False
--
-- >>> cost u
-- "zwu"
--
-- >>> (z ==) <$> root v
-- True
--
data LinkCut a s
-- | O(1). Allocate a new link-cut tree with a given monoidal summary.
new :: (PrimMonad m, Monoid a) => a -> m (LinkCut a (PrimState m))
-- | O(log n). link v w inserts v which must be
-- the root of a tree in as a child of w. v and
-- w must not be connected.
link :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m ()
-- | O(log n). cut 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).
cut :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m ()
-- | O(log n). Find the root of a tree.
--
-- Repeated calls on the same value without intermediate accesses are
-- O(1).
root :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))
-- | O(log n). cost v computes the root-to-leaf path cost
-- of v under whatever Monoid was built into the tree.
--
-- Repeated calls on the same value without intermediate accesses are
-- O(1).
cost :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m a
-- | 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).
parent :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> m (LinkCut a (PrimState m))
-- | O(log n). connected v w determines if v and
-- w inhabit the same tree.
connected :: (PrimMonad m, Monoid a) => LinkCut a (PrimState m) -> LinkCut a (PrimState m) -> m Bool
module Data.Struct.Internal.Order
-- | This 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^2, 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.
--
-- Every 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.
newtype Order s
[Order] :: Object s -> Order s
[runOrder] :: Order s -> Object s
key :: Field Order Key
next :: Slot Order Order
prev :: Slot Order Order
parent :: Slot Order Label
makeOrder :: PrimMonad m => Label (PrimState m) -> Key -> Order (PrimState m) -> Order (PrimState m) -> m (Order (PrimState m))
-- | O(1) compareM, O(1) amortized insert
compareM :: PrimMonad m => Order (PrimState m) -> Order (PrimState m) -> m Ordering
insertAfter :: PrimMonad m => Order (PrimState m) -> m (Order (PrimState m))
delete :: PrimMonad m => Order (PrimState m) -> m ()
logU :: Int
loglogU :: Int
deltaU :: Key
new :: PrimMonad m => m (Order (PrimState m))
value :: PrimMonad m => Order (PrimState m) -> m (Key, Key)
values :: PrimMonad m => Order (PrimState m) -> m [(Key, Key)]
instance Eq (Order s)
instance Struct Order
module Data.Struct.Order
-- | This 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^2, 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.
--
-- Every 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.
data Order s
new :: PrimMonad m => m (Order (PrimState m))
insertAfter :: PrimMonad m => Order (PrimState m) -> m (Order (PrimState m))
delete :: PrimMonad m => Order (PrimState m) -> m ()
module Data.Struct
-- | An instance for Struct t is a witness to the
-- machine-level equivalence of t and Object. The
-- argument to struct is ignored and is only present to help type
-- inference.
class Struct t
struct :: Struct t => proxy t -> Dict (Coercible (t s) (Object s))
data Object s
destruct :: Struct t => t s -> SmallMutableArray# s Any
construct :: Struct t => SmallMutableArray# s Any -> t s
eqStruct :: Struct t => t s -> t s -> Bool
-- | Allocate a structure made out of n slots. Initialize the
-- structure before proceeding!
alloc :: (PrimMonad m, Struct t) => Int -> m (t (PrimState m))
-- | Truly imperative.
isNil :: Struct t => t s -> Bool
data NullPointerException
[NullPointerException] :: NullPointerException
-- | A Slot is a reference to another unboxed mutable object.
data Slot x y
-- | The Slot at the given position in a Struct
slot :: Int -> Slot s t
-- | Get the value from a Slot
get :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> m (y (PrimState m))
-- | Set the value of a Slot
set :: (PrimMonad m, Struct x, Struct y) => Slot x y -> x (PrimState m) -> y (PrimState m) -> m ()
-- | A Field is a reference from a struct to a normal Haskell data
-- type.
data Field x a
-- | Store the reference to the Haskell data type in a normal field
field :: Int -> Field s a
-- | Store the reference in the nth slot of the nth argument, treated as a
-- MutableByteArray
unboxedField :: Prim a => Int -> Int -> Field s a
-- | Get the value of a field in a struct
getField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> m a
-- | Set the value of a field in a struct
setField :: (PrimMonad m, Struct x) => Field x a -> x (PrimState m) -> a -> m ()
-- | We can compose slots to get a nested slot or field accessor
class Precomposable t
(#) :: Precomposable t => Slot x y -> t y z -> t x z