# [−][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 |

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