Portability | non-portable (requires STM) |
---|---|
Stability | experimental |
Maintainer | Peter Robinson <thaldyron@gmail.com> |
Safe Haskell | None |
- data TSkipList k a = TSkipList {
- maxLevel :: Int
- probability :: Float
- curLevel :: TVar Int
- listHead :: ForwardPtrs k a
- newIO :: IO (TSkipList k a)
- newIO' :: Float -> Int -> IO (TSkipList k a)
- new :: STM (TSkipList k a)
- new' :: Float -> Int -> STM (TSkipList k a)
- data Traversal k a b = Traversal {}
- type ForwardPtrs k a = TArray Int (Node k a)
- data Node k a
- = Nil
- | Node {
- key :: k
- contentTVar :: TVar a
- forwardPtrs :: ForwardPtrs k a
- insert :: Ord k => k -> a -> TSkipList k a -> STM ()
- lookup :: Ord k => k -> TSkipList k a -> STM (Maybe a)
- update :: Ord k => k -> a -> TSkipList k a -> STM ()
- delete :: Ord k => k -> TSkipList k a -> STM ()
- filter :: Ord k => (k -> Bool) -> TSkipList k a -> STM (Map k a)
- filterGT :: Ord k => k -> TSkipList k a -> STM (Map k a)
- filterLT :: Ord k => k -> TSkipList k a -> STM (Map k a)
- filterElems :: Ord k => (k -> a -> Bool) -> TSkipList k a -> STM (Map k a)
- minimum :: Ord k => TSkipList k a -> STM (k, a)
- maximum :: Ord k => TSkipList k a -> STM (k, a)
- filterRange :: Ord k => (k, k) -> TSkipList k a -> STM [(k, a)]
- traverse :: Ord k => k -> ForwardPtrs k a -> Int -> Traversal k a b -> b -> STM b
- lookupNode :: Ord k => k -> TSkipList k a -> STM (Maybe (Node k a))
- insertNode :: Ord k => k -> Node k a -> TSkipList k a -> STM ()
- chooseLevel :: TSkipList k a -> Int
- toString :: (Show k, Ord k) => TSkipList k a -> STM String
Data types and Construction
A skip list data type.
TSkipList | |
|
newIO :: IO (TSkipList k a)Source
Creates a skiplist. Default values for storing up to 2^16 elements.
Creates a skiplist.
Creates a skiplist.
Traversal strategy.
type ForwardPtrs k a = TArray Int (Node k a)Source
An entry of the skip list.
Nil | |
Node | |
|
Operations
insert :: Ord k => k -> a -> TSkipList k a -> STM ()Source
Insertsupdates the value for a specific key. O(log n)/.
update :: Ord k => k -> a -> TSkipList k a -> STM ()Source
Updates an element. Throws AssertionFailed
if the element is not in the
list. O(log n).
delete :: Ord k => k -> TSkipList k a -> STM ()Source
Deletes an element. Does nothing if the element is not found. O(log n).
filter :: Ord k => (k -> Bool) -> TSkipList k a -> STM (Map k a)Source
Returns all elements that satisfy the predicate on keys. O(n).
filterGT :: Ord k => k -> TSkipList k a -> STM (Map k a)Source
Returns all elements greater than the key.
TODO: currently in O(n), should be made more efficient (like leq
)
filterLT :: Ord k => k -> TSkipList k a -> STM (Map k a)Source
Returns all elements less than the key. Takes O(m) where m is the number of elements that have a smaller key.
filterElems :: Ord k => (k -> a -> Bool) -> TSkipList k a -> STM (Map k a)Source
Returns all elements that satisfy the predicate on keys and values. O(n).
filterRange :: Ord k => (k, k) -> TSkipList k a -> STM [(k, a)]Source
Finds all elements within a specific key range (k1,k2). O(log n + k2 - k1).
Low-level Operations
:: Ord k | |
=> k | search key |
-> ForwardPtrs k a | forward pointers to the next node |
-> Int | current level |
-> Traversal k a b | traversal strategy |
-> b | default value |
-> STM b |
Utilities
chooseLevel :: TSkipList k a -> IntSource
Returns a randomly chosen level. Used for inserting new elements.
For performance reasons, this function uses unsafePerformIO
to access the
random number generator. (It would be possible to store the random number
generator in a TVar
and thus be able to access it safely from within the
STM monad. This, however, might cause high contention among threads.)