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 57 58
//! 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.
#![warn(missing_docs)]
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;