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

//! A skiplist is a way of storing elements in such a way that elements can be efficiently
//! accessed, inserted and removed, all in `O(log(n))` on average.
//!
//! Conceptually, a skiplist resembles something like:
//!
//! ```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] ->
//! ```
//!
//! where we each node `[x]` has references to nodes further down the list, allowing the algorithm
//! to effectively skip ahead.
//!
//! The ordered skiplist has an associated sorting function which **must** be well-behaved.
//! Specifically, given some ordering function `f(a, b)`, it must satisfy the folowing properties:
//!
//! - Be well defined: `f(a, b)` should always return the same value
//! - Be anti-symmetric: `f(a, b) == Greater` iff `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 behaviour at best, and at worst
//! will cause a segfault, null deref, or some other bad behaviour.**

#![allow(dead_code)]

extern crate rand;

mod level_generator;
mod skipnode;
pub mod ordered_skiplist;
pub mod skipmap;
pub mod skiplist;

/// An endpoint of a range of keys.
#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
pub enum Bound<T> {
    /// An inclusive bound.
    Included(T),
    /// An exclusive bound.
    Excluded(T),
    /// An infinite endpoint. Indicates that there is no bound in this direction.
    Unbounded,
}

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