stable_skiplist/
skipnode.rs

1use std::fmt;
2use std::iter;
3
4// /////////////////////////////////////////////////////////////////////////////////////////////////
5// SkipNode
6// /////////////////////////////////////////////////////////////////////////////////////////////////
7
8/// SkipNodes are make up the SkipList.  The SkipList owns the first head-node
9/// (which has no value) and each node has ownership of the next node through
10/// `next`.
11///
12/// The node has a `level` which corresponds to how 'high' the node reaches, and
13/// this should be equal to the length of the vector of links.  There is a
14/// corresponding vector of link lengths which is used to reach a particular index.
15///
16/// Lastly, each node contains a link to the immediately previous node in case
17/// one needs to parse the list backwards.
18///
19/// In cases where the value is not applicable, `None` should be used.  In
20/// particular, as there is no tail node, the value of `next` in the last node
21/// should be `None`.
22#[derive(Clone, Debug)]
23pub struct SkipNode<V> {
24    // key and value should never be None, with the sole exception being the head node.
25    pub value: Option<V>,
26    // how high the node reaches.  This should be equal to the vector length.
27    pub level: usize,
28    // The immediately next element (and owns that next node).
29    pub next: Option<Box<SkipNode<V>>>,
30    // The immediately previous element.
31    pub prev: Option<*mut SkipNode<V>>,
32    // Vector of links to the next node at the respective level.  This vector *must* be of length
33    // `self.level + 1`.  links[0] stores a pointer to the same node as next.
34    pub links: Vec<Option<*mut SkipNode<V>>>,
35    // The corresponding length of each link
36    pub links_len: Vec<usize>,
37}
38
39// ///////////////////////////////////////////////
40// Inherent methods
41// ///////////////////////////////////////////////
42
43impl<V> SkipNode<V> {
44    /// Create a new head node.
45    pub fn head(total_levels: usize) -> Self {
46        SkipNode {
47            value: None,
48            level: total_levels - 1,
49            next: None,
50            prev: None,
51            links: iter::repeat(None).take(total_levels).collect(),
52            links_len: iter::repeat(0).take(total_levels).collect(),
53        }
54    }
55
56    /// Create a new SkipNode with the given value.  The values of `prev` and
57    /// `next` will all be `None` and have to be adjusted.
58    pub fn new(value: V, level: usize) -> Self {
59        SkipNode {
60            value: Some(value),
61            level: level,
62            next: None,
63            prev: None,
64            links: iter::repeat(None).take(level + 1).collect(),
65            links_len: iter::repeat(0).take(level + 1).collect(),
66        }
67    }
68
69    /// Consumes the node returning the value it contains.
70    pub fn into_inner(self) -> Option<V> {
71        if self.value.is_some() {
72            Some(self.value.unwrap())
73        } else {
74            None
75        }
76    }
77
78    /// Returns `true` is the node is a head-node.
79    pub fn is_head(&self) -> bool {
80        self.prev.is_none()
81    }
82
83    /// Returns `true` is the node is a tail-node.
84    pub fn is_tail(&self) -> bool {
85        self.next.is_none()
86    }
87}
88
89// ///////////////////////////////////////////////
90// Trait implementation
91// ///////////////////////////////////////////////
92
93impl<V> fmt::Display for SkipNode<V> where V: fmt::Display
94{
95    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
96        if let &Some(ref v) = &self.value {
97            write!(f, "{}", v)
98        } else {
99            Ok(())
100        }
101    }
102}
stable_skiplist/skipnode.rs

stable_skiplist/
skipnode.rs
