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

Contents

Description

 

Synopsis

Order Maintenance

newtype 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.

Constructors

Order 

Fields

runOrder :: Object s
 

Instances

makeOrder :: PrimMonad m => Label (PrimState m) -> Key -> a -> Order a (PrimState m) -> Order a (PrimState m) -> m (Order a (PrimState m)) Source

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

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

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

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

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

keys :: PrimMonad m => Order a (PrimState m) -> m (Key, Key) Source