| 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.Order
Contents
Description
- newtype Order a s = Order {}
- key :: Field (Order a) Key
- value :: Field (Order a) a
- next :: Slot (Order a) (Order a)
- prev :: Slot (Order a) (Order a)
- parent :: Slot (Order a) Label
- makeOrder :: PrimMonad m => Label (PrimState m) -> Key -> a -> Order a (PrimState m) -> Order a (PrimState m) -> m (Order a (PrimState m))
- compareM :: PrimMonad m => Order a (PrimState m) -> Order a (PrimState m) -> m Ordering
- insertAfter :: PrimMonad m => Order a (PrimState m) -> a -> m (Order a (PrimState m))
- delete :: PrimMonad m => Order a (PrimState m) -> m ()
- logU :: Int
- loglogU :: Int
- deltaU :: Key
- new :: PrimMonad m => a -> m (Order a (PrimState m))
- keys :: PrimMonad m => Order a (PrimState m) -> m (Key, Key)
Order Maintenance
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.
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