[−][src]Crate skiplist

A skiplist is a way of storing sorted elements in such a way that they can be accessed, inserted and removed, all in O(log(n)) on average.

Conceptually, a skiplist is arranged as follows:

<head> ----------> [2] --------------------------------------------------> [9] ---------->
<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->

Each node contains at the very least a link to the next element in the list (corresponding to the lowest level in the above diagram), but it can randomly contain more links which skip further down the list (the towers in the above diagram). This allows for the algorithm to move down the list faster than having to visit every element.

Conceptually, the skiplist can be thought of as a stack of linked lists. At the very bottom is the full linked list with every element, and each layer above corresponds to a linked list containing a random subset of the elements from the layer immediately below it. The probability distribution that determines this random subset can be customized, but typically a layer will contain half the nodes from the layer below.

Safety

The ordered skiplist relies on a well-behaved comparison function. Specifically, given some ordering function f(a, b), it must satisfy the following properties:

Be well defined: f(a, b) should always return the same value
Be anti-symmetric: f(a, b) == Greater if and only if f(b, a) == Less, and f(a, b) == Equal == f(b, a).
By transitive: If f(a, b) == Greater and f(b, c) == Greater then f(a, c) == Greater.

Failure to satisfy these properties can result in unexpected behavior at best, and at worst will cause a segfault, null deref, or some other bad behavior.

Re-exports

pub use crate::ordered_skiplist::OrderedSkipList;

pub use crate::skiplist::SkipList;

pub use crate::skipmap::SkipMap;

Modules

level_generator	SkipLists use a probabilistic distribution of nodes over the internal levels, whereby the lowest level (level 0) contains all the nodes, and each level `n > 0` will contain a random subset of the nodes on level `n - 1`.
ordered_skiplist	An always-ordered skiplist.
skiplist	A skiplist implementation which allows faster random access than a standard linked list.
skipmap	SkipMap stores key-value pairs, with the keys being unique and always sorted.