1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

//! 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:
//!
//! ```text
//! <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.**

// In this library, the notion of 'height' of a node refers to how many links a
// node has (as a result, the minimum height is 1).  The 'levels' refer to the
// layers in the above diagram, with level 0 being the bottom-most layer, level
// 1 being the one above level 0, etc.

extern crate rand;
pub mod level_generator;
pub mod ordered_skiplist;
pub mod skiplist;
pub mod skipmap;
mod skipnode;

pub use crate::ordered_skiplist::OrderedSkipList;
pub use crate::skiplist::SkipList;
pub use crate::skipmap::SkipMap;