Data.Struct.Internal.Label

Documentation

>>> import Data.Struct.Internal
>>> import Data.Struct.Internal.Label

List Labeling: Maintain n keys each labeled with n^2 bits w/ log n update time.

type Key = Word64

midBound :: Key

key :: Field Label Key

next :: Slot Label Label

prev :: Slot Label Label

newtype Label s

Logarithmic time list labeling solution

Constructors

Label (Object s)

Instances

Struct Label

Defined in Data.Struct.Internal.Label

Methods

struct :: Dict (Coercible (Label s) (Object s))

Eq (Label s)

Defined in Data.Struct.Internal.Label

Methods

(==) :: Label s -> Label s -> Bool

(/=) :: Label s -> Label s -> Bool

makeLabel :: PrimMonad m => Key -> Label (PrimState m) -> Label (PrimState m) -> m (Label (PrimState m))

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

new :: PrimMonad m => m (Label (PrimState m))

O(1). Create a new labeling structure. Labels from different list labeling structures are incomparable.

delete :: PrimMonad m => Label (PrimState m) -> m ()

O(1). Remove a label

insertAfter :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

O(log n) amortized. Insert a new label after a given label.

cutAfter :: PrimMonad m => Label (PrimState m) -> m ()

O(1). Split off all labels after the current label.

cutBefore :: PrimMonad m => Label (PrimState m) -> m ()

O(1). Split off all labels before the current label.

least :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

O(n). Retrieve the least label

greatest :: PrimMonad m => Label (PrimState m) -> m (Label (PrimState m))

O(n). Retrieve the greatest label

compareM :: PrimMonad m => Label (PrimState m) -> Label (PrimState m) -> m Ordering

O(1). Compare two labels for ordering.

delta :: Key -> Word64 -> Key

value :: PrimMonad m => Label (PrimState m) -> m 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.

keys :: PrimMonad m => Label (PrimState m) -> m [Key]

O(n). Get the keys of every label from here to the right.