Data.Struct.Internal.Order

Order Maintenance

newtype Order s

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.

Constructors

Order

Fields

runOrder :: Object s

Instances

Struct Order

Eq (Order 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))

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

O(1) compareM, O(1) amortized insert

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