Copyright	(C) 2015 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <ekmett@gmail.com>
Stability	experimental
Portability	non-portable
Safe Haskell	Unsafe
Language	Haskell2010

Data.Struct.Internal.Label

Contents

Description

Synopsis

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

Logarithmic time list labeling solution

Constructors

Instances

Struct Label Source
Eq (Label s) Source

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.