structs-0: Strict GC'd imperative object-oriented programming with cheap pointers.

Copyright(C) 2015 Edward Kmett
LicenseBSD-style (see the file LICENSE)
MaintainerEdward Kmett <ekmett@gmail.com>
Stabilityexperimental
Portabilitynon-portable
Safe HaskellUnsafe
LanguageHaskell2010

Data.Struct.Internal.Label

Contents

Description

 

Synopsis

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

newtype Label s Source

Logarithmic time list labeling solution

Constructors

Label (Object s) 

Instances

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

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)) Source

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

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

O(1). Remove a label

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

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

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

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

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

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

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

O(n). Retrieve the least label

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

O(n). Retrieve the greatest label

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

O(1). Compare two labels for ordering.

value :: PrimMonad m => Label (PrimState m) -> m Key Source

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] Source

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