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 HaskellTrustworthy
LanguageHaskell2010

Data.Struct.Order

Description

 

Synopsis

Documentation

data Order a s Source

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

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

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

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