Portability | non-portable (requires STM) |
---|---|

Stability | experimental |

Maintainer | Peter Robinson <robinson@ecs.tuwien.ac.at> |

Provides an implementation of a skip list in the `AdvSTM`

monad.
A skip list is a probabilistic data structure with map-like operations.
In contrast to a balanced tree, a skip list does not need any rebalancing,
which makes it suitable for concurrent programming.
See: *William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees.*

The elements of the skip list are stored in a `TBox`

.
When an element of the skip list is modified, the operation is relegated
to the corresponding `TBox`

.

For a concrete instance see module `Control.Concurrent.TFile.TSkipList`

- data TSkipList t k a
- newIO :: TBox t k a => Float -> Int -> IO (TSkipList t k a)
- insert :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()
- lookup :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Maybe a)
- update :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()
- delete :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM ()
- geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
- leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)
- min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)
- filter :: (Ord k, TBox t k a) => (k -> a -> Bool) -> TSkipList t k a -> AdvSTM (Map k a)
- insertNode :: (Ord k, TBox t k a) => k -> Node t k a -> TSkipList t k a -> AdvSTM ()
- lookupNode :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Maybe (Node t k a))
- readAndValidate :: (Ord k, TBox t k a) => TSkipList t k a -> Node t k a -> AdvSTM (Maybe a)
- newNode :: TBox t k a => k -> t k a -> Int -> AdvSTM (Node t k a)
- contentTBox :: Node t k a -> t k a
- key :: Node t k a -> k
- chooseLevel :: TSkipList t k a -> AdvSTM Int
- toString :: (Ord k, Show k, TBox t k a) => k -> TSkipList t k a -> AdvSTM String

# Data type

:: TBox t k a | |

=> Float | Probability for choosing a new level |

-> Int | Maximum number of levels |

-> IO (TSkipList t k a) |

An empty skiplist.

# Operations

update :: (Ord k, TBox t k a) => k -> a -> TSkipList t k a -> AdvSTM ()Source

Updates an element. Throws `AssertionFailed`

if the element is not in the
list.

geq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)Source

Returns all elements that are greater than the key.
TODO: currently in O(n), can be made more efficient (like `leq`

)

leq :: (Ord k, TBox t k a) => k -> TSkipList t k a -> AdvSTM (Map k a)Source

Returns all elements that are smaller than the key.

min :: (Ord k, TBox t k a) => TSkipList t k a -> AdvSTM (Maybe a)Source

Returns the element with the least key, if it exists. *O(1)*.

filter :: (Ord k, TBox t k a) => (k -> a -> Bool) -> TSkipList t k a -> AdvSTM (Map k a)Source

Returns all elements that satisfy the predicate. O(n).

# Low-level Operations

contentTBox :: Node t k a -> t k aSource

# Utilities

chooseLevel :: TSkipList t k a -> AdvSTM IntSource

Returns a randomly chosen level. Is used for inserting new elements.
Note that this function uses `unsafeIOToAdvSTM`

to access the random
number generator.