Data.Struct.Order

Documentation

data Order a 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.

Instances

Struct (Order a)

Defined in Data.Struct.Internal.Order

Methods

struct :: Dict (Coercible (Order a s) (Object s))

Eq (Order a s)

Defined in Data.Struct.Internal.Order

Methods

(==) :: Order a s -> Order a s -> Bool

(/=) :: Order a s -> Order a s -> Bool

new :: PrimMonad m => a -> m (Order a (PrimState m))

value :: Field (Order a) a

insertAfter :: PrimMonad m => Order a (PrimState m) -> a -> m (Order a (PrimState m))

delete :: PrimMonad m => Order a (PrimState m) -> m ()