skip_linked_list/
list.rs

1extern crate rand;
2
3use rand::{thread_rng, Rng};
4use std::ptr::NonNull;
5use std::fmt::Display;
6
7/// # SkipLinkedList
8///
9/// `SkipLinkedList` is a skiplist-backed linked-list that supports fast random access.
10/// The (amortized) time complexity is `O(log n)` for both reads and writes, regardless of the position.
11/// It is more efficient than `Vec` and `Linkedlist` for large list that requires lots of random access.
12///
13/// # Examples
14/// ```
15/// let mut list = skip_linked_list::SkipLinkedList::new();
16///
17/// list.push_front(1);
18/// list.push_back(2);
19/// list.insert(1, 3);
20/// list.insert(1, 4);
21/// list.insert(1, 5);
22/// // current list is: [1, 5, 4, 3, 2]
23///
24/// assert_eq!(list.get(1), Some(&5));
25/// assert_eq!(list.get(3), Some(&3));
26/// assert_eq!(list.remove(2), 4);
27/// ```
28pub struct SkipLinkedList<T> {
29    size: usize,
30    entry: Link<T>,
31}
32
33type Link<T> = Box<Node<T>>;
34type WeakLink<T> = NonNull<Node<T>>;
35
36enum Node<T> {
37    Sentinel { right: Option<Link<T>>, down: Option<Link<T>>, delta: usize },
38    Index { right: Option<Link<T>>, down: WeakLink<T>, delta: usize },
39    Content { right: Option<Link<T>>, elem: T },
40}
41
42impl<T> SkipLinkedList<T> {
43
44    /// Creates a new list.
45    pub fn new() -> Self {
46        Self {
47            size: 0,
48            entry: Box::new(Node::Sentinel { right: None, down: None, delta: 1}),
49        }
50    }
51
52    /// Inserts an element at position index within the list, shifting all elements after it to the right.
53    ///
54    /// # Examples
55    ///
56    /// ```
57    /// let mut list = skip_linked_list::SkipLinkedList::new();
58    /// list.insert(0, 10);
59    /// list.insert(1, 30);
60    /// list.insert(1, 20);
61    /// assert_eq!(list.into_iter().collect::<Vec<i32>>(), vec![10, 20, 30]);
62    /// ```
63    ///
64    /// # Panics
65    ///
66    /// Panics if `i > len`.
67    pub fn insert(&mut self, i: usize, elem: T) {
68        if i > self.size {
69            panic!("insert position {} should be <= len (is {})", i, self.size);
70        }
71
72        let i = i + 1; // relative to sentinel
73        let top_level_inserted = Node::insert(&mut self.entry, i, elem);
74        self.size += 1;
75        match (top_level_inserted, thread_rng().gen_bool(0.5)) {
76            (Some(raw_node), true) => {
77                let new_index = Node::Index { right: None, down: raw_node, delta: self.size - i + 1 };
78                let mut entry = Box::new(Node::Sentinel { right: Some(Box::new(new_index)), down: None, delta: i });
79                std::mem::swap(&mut self.entry, &mut entry);
80                match self.entry.as_mut() {
81                    Node::Sentinel { down, .. } => *down = Some(entry),
82                    _ => (),
83                }
84            },
85            _ => (),
86        }
87    }
88
89    /// Gets the element at position index within the list.
90    ///
91    /// # Examples
92    ///
93    /// ```
94    /// let mut list = skip_linked_list::SkipLinkedList::new();
95    /// list.insert(0, 10);
96    /// assert_eq!(list.get(0), Some(&10));
97    /// assert_eq!(list.get(1), None);
98    /// ```
99    pub fn get(&self, i: usize) -> Option<&T> {
100        if i >= self.size {
101            return None;
102        }
103        Node::get(&self.entry, i + 1)
104    }
105
106    /// Removes an element at position index within the list, shifting all elements after it to the left.
107    ///
108    /// # Examples
109    ///
110    /// ```
111    /// let mut list = skip_linked_list::SkipLinkedList::new();
112    /// list.insert(0, 10);
113    /// list.insert(1, 20);
114    /// assert_eq!(list.remove(0), 10);
115    /// assert_eq!(list.remove(0), 20);
116    /// ```
117    ///
118    /// # Panics
119    ///
120    /// Panics if `i >= len`.
121
122    pub fn remove(&mut self, i: usize) -> T {
123        if i >= self.size {
124            panic!("remove position {} should be < len (is {})", i, self.size);
125        }
126        self.size -= 1;
127        Node::remove(&mut self.entry, i)
128    }
129
130    /// Returns the length of the list.
131    pub fn len(&self) -> usize {
132        self.size
133    }
134
135    /// Inserts an element at the start of the list.
136    pub fn push_front(&mut self, elem: T) {
137        self.insert(0, elem);
138    }
139
140    /// Inserts an element at the end of the list.
141    pub fn push_back(&mut self, elem: T) {
142        self.insert(self.size, elem);
143    }
144
145    /// Removes an element at the start of the list.
146    /// # Panics
147    ///
148    /// Panics if list is empty.
149    pub fn pop_front(&mut self) -> T {
150        if self.size > 0 {
151            self.remove(0)
152        } else {
153            panic!("can't pop an empty list")
154        }
155    }
156
157    /// Removes an element at the end of the list.
158    /// # Panics
159    ///
160    /// Panics if list is empty.
161    pub fn pop_back(&mut self) -> T {
162        if self.size > 0 {
163            self.remove(self.size - 1)
164        } else {
165            panic!("can't pop an empty list")
166        }
167    }
168
169    /// Returns an iterator over the list.
170    pub fn iter(&self) -> Iter<T> {
171        let mut node = self.entry.as_ref();
172        while let Node::Sentinel{ down: Some(next_node), .. } = node {
173            node = next_node;
174        }
175        Iter(node.right())
176    }
177
178    /// Returns an mut iterator over the list.
179    pub fn iter_mut(&mut self) -> IterMut<T> {
180        let mut node = self.entry.as_mut();
181        while let Node::Sentinel{ down: Some(next_node), .. } = node {
182            node = next_node;
183        }
184        IterMut(node.right_mut().as_mut())
185    }
186
187    /// Consumes the list into an iterator.
188    pub fn into_iter(self) -> IntoIter<T> {
189        IntoIter(self)
190    }
191}
192
193pub struct IntoIter<T>(SkipLinkedList<T>);
194
195impl<T> Iterator for IntoIter<T> {
196    type Item = T;
197
198    fn next(&mut self) -> Option<Self::Item> {
199        if self.0.len() > 0 {
200            Some(self.0.pop_front())
201        } else {
202            None
203        }
204    }
205}
206
207pub struct IterMut<'a, T>(Option<&'a mut Link<T>>);
208
209impl<'a, T> Iterator for IterMut<'a, T> {
210    type Item = &'a mut T;
211
212    fn next(&mut self) -> Option<Self::Item> {
213        self.0.take().and_then(|node| {
214            if let Node::Content { elem, right } = node.as_mut() {
215                self.0 = right.as_mut();
216                Some(elem)
217            } else {
218                None
219            }
220        })
221    }
222}
223
224pub struct Iter<'a, T>(Option<&'a Link<T>>);
225
226impl<'a, T> Iterator for Iter<'a, T> {
227    type Item = &'a T;
228
229    fn next(&mut self) -> Option<Self::Item> {
230        self.0.take().and_then(|node| {
231            if let Node::Content { elem, right } = node.as_ref() {
232                self.0 = right.as_ref();
233                Some(elem)
234            } else {
235                None
236            }
237        })
238    }
239}
240
241const WIDTH: usize = 4;
242
243impl<T> SkipLinkedList<T> where T: Display {
244
245    /// Prints the internals of the list.
246    pub fn visualize(&self) {
247        let mut option_node = Some(&self.entry);
248        while let Some(node) = option_node.take() {
249            Self::visualize_level(Some(node));
250            match node.as_ref() {
251                Node::Sentinel { down, .. } => option_node = down.as_ref(),
252                _ => break,
253            }
254        }
255    }
256
257    fn visualize_level(option_node: Option<&Box<Node<T>>>) {
258        let mut option_node = option_node;
259        let mut last_delta = 0;
260        while let Some(node) = option_node.take() {
261            match node.as_ref() {
262                Node::Sentinel { right, delta, .. } => {
263                    print!("{delta:>width$}", delta=format!("+{}", delta), width=WIDTH);
264                    last_delta = *delta;
265                    option_node = right.as_ref();
266                },
267                Node::Index { right, delta, .. } => {
268                    print!("{delta:>width$}", delta=format!("+{}", delta), width=(last_delta*WIDTH));
269                    last_delta = *delta;
270                    option_node = right.as_ref();
271                },
272                Node::Content { right, elem, .. } => {
273                    print!("{elem:>width$}", elem=elem, width=WIDTH);
274                    option_node = right.as_ref();
275                },
276            }
277        }
278        println!();
279    }
280}
281
282impl<T> Node<T> {
283    fn right_mut(&mut self) -> &mut Option<Link<T>> {
284        match self {
285            Node::Sentinel { right, .. } => right,
286            Node::Content { right, .. }  => right,
287            Node::Index { right, .. } => right,
288        }
289    }
290
291    fn right(&self) -> Option<&Link<T>> {
292        match self {
293            Node::Sentinel { right, .. } => right.as_ref(),
294            Node::Content { right, .. }  => right.as_ref(),
295            Node::Index { right, .. } => right.as_ref(),
296        }
297    }
298
299    fn insert(start_node: &mut Node<T>, start_i: usize, elem: T) -> Option<WeakLink<T>> {
300        let mut node = start_node;
301        let mut i = start_i;
302
303        while node.delta() < i {
304            i -= node.delta();
305            node = node.right_mut().as_mut().unwrap();
306        }
307        node.insert_at(i, elem)
308    }
309
310    fn get(start_node: &Node<T>, start_i: usize) -> Option<&T> {
311        let mut node = start_node;
312        let mut i = start_i;
313
314        while node.delta() <= i {
315            i -= node.delta();
316            node = node.right().unwrap();
317        }
318        node.get_at(i)
319    }
320
321    fn get_at(&self, i: usize) -> Option<&T> {
322        match self {
323            Node::Sentinel { down: Some(node), .. } => Node::get(node, i),
324            Node::Index { down: raw_node, .. } => Node::get(unsafe { raw_node.as_ref() }, i),
325            Node::Content { elem, .. } if i == 0 => Some(&elem),
326            _ => None,
327        }
328    }
329
330    fn insert_content_after(&mut self, elem: T) -> Option<WeakLink<T>> {
331        let right = self.right_mut();
332        let mut new_node = Box::new(Node::Content { elem, right: right.take() });
333        let raw_new_node: *mut _ = &mut *new_node;
334        *right = Some(new_node);
335        NonNull::new(raw_new_node)
336    }
337
338    fn insert_index_after(&mut self, i: usize, next_level_inserted: WeakLink<T>) -> Option<WeakLink<T>> {
339        let delta = self.delta();
340        let right = self.right_mut();
341        let mut new_node = Box::new(Node::Index {
342            right: right.take(),
343            down: next_level_inserted,
344            delta: delta - i,
345        });
346        let raw_new_node: *mut _ = &mut *new_node;
347        *right = Some(new_node);
348        *self.delta_mut().unwrap() = i;
349        NonNull::new(raw_new_node)
350    }
351
352    fn insert_at(&mut self, i: usize, elem: T) -> Option<WeakLink<T>> {
353        match self {
354            Node::Content { .. } | Node:: Sentinel { down: None, .. } => self.insert_content_after(elem),
355            Node::Sentinel { down: Some(node), delta, .. } => {
356                *delta += 1;
357                match (Node::insert(node, i, elem), thread_rng().gen_bool(0.5)) {
358                    (Some(next_level_inserted), true) => self.insert_index_after(i, next_level_inserted),
359                    _ => None,
360                }
361            },
362            Node::Index { down: raw_node, delta, .. } => {
363                *delta += 1;
364                match (Node::insert(unsafe { raw_node.as_mut() }, i, elem), thread_rng().gen_bool(0.5)) {
365                    (Some(next_level_inserted), true) => self.insert_index_after(i, next_level_inserted),
366                    _ => None,
367                }
368            },
369        }
370    }
371
372    fn remove(start_node: &mut Node<T>, i: usize) -> T {
373        let mut i = i;
374        let mut node = start_node;
375
376        while node.delta() <= i {
377            i -= node.delta();
378            node = node.right_mut().as_mut().unwrap();
379        }
380        node.remove_after(i)
381    }
382
383    fn remove_after(&mut self, i: usize) -> T {
384        match self {
385            Node::Sentinel { down: Some(node), delta, .. } => {
386                let removed = Node::remove(node, i);
387                if *delta == i + 1 {
388                    self.remove_right();
389                } else {
390                    *delta -= 1;
391                };
392                removed
393            },
394            Node::Index { down: raw_node, delta, .. } => {
395                let removed = Node::remove(unsafe { raw_node.as_mut() }, i);
396                if *delta == i + 1 {
397                    self.remove_right();
398                } else {
399                    *delta -= 1;
400                }
401                removed
402            },
403            Node::Sentinel { down: None, .. } => self.remove_right().unwrap(),
404            Node::Content {.. } => self.remove_right().unwrap(),
405        }
406    }
407
408    fn remove_right(&mut self) -> Option<T> {
409        let right = self.right_mut();
410        let mut removed = right.take().unwrap();
411        *right = removed.right_mut().take();
412        self.delta_mut().map (|delta| *delta += removed.delta() - 1);
413        match *removed {
414            Node::Content { elem, .. } => Some(elem),
415            _ => None,
416        }
417    }
418
419    fn delta(&self) -> usize {
420        match self {
421            Node::Sentinel { delta, .. } => *delta,
422            Node::Content { .. } => 1,
423            Node::Index { delta, .. } => *delta,
424        }
425    }
426
427    fn delta_mut(&mut self) -> Option<&mut usize> {
428        match self {
429            Node::Sentinel { delta, .. } => Some(delta),
430            Node::Content { .. } => None,
431            Node::Index { delta, .. } => Some(delta),
432        }
433    }
434
435    fn drop_after(sentinel: &mut Node<T>) {
436        sentinel.right_mut().take().map(|mut node| {
437            while let Some(next_node) = node.right_mut().take() {
438                node = next_node;
439            }
440        });
441        if let Node::Sentinel { down: Some(next_sentinel), .. } = sentinel {
442            Node::drop_after(next_sentinel);
443        }
444    }
445}
446
447impl<T> Drop for SkipLinkedList<T> {
448    fn drop(&mut self) {
449        Node::drop_after(&mut self.entry);
450    }
451}
452
453#[cfg(test)]
454mod test {
455    use super::*;
456
457    fn setup_list() -> SkipLinkedList<i32> {
458        let mut list = SkipLinkedList::new();
459        list.push_back(1);
460        list.push_back(2);
461        list.push_back(3);
462        list.push_front(30);
463        list.push_front(20);
464        list.push_front(10);
465        list.insert(3, 100);
466        list
467    }
468
469    #[test]
470    fn basics() {
471        let mut list = setup_list();
472        assert_eq!(list.len(), 7);
473        let expected = vec![10, 20, 30, 100, 1, 2, 3];
474        for (i, elem) in expected.iter().enumerate() {
475            assert_eq!(list.get(i), Some(elem));
476        }
477        assert_eq!(list.get(10), None);
478        assert_eq!(list.remove(0), 10);
479        assert_eq!(list.remove(0), 20);
480        assert_eq!(list.remove(4), 3);
481        assert_eq!(list.remove(2), 1);
482    }
483
484    #[test]
485    fn small_random() {
486        let mut list = SkipLinkedList::new();
487        let mut vec = Vec::new();
488
489        let mut size = 0;
490        for _ in 0..1000 {
491            size += 1;
492            let elem: i32 = thread_rng().gen();
493            let idx: usize = thread_rng().gen_range(0, size);
494            list.insert(idx, elem);
495            vec.insert(idx, elem);
496        }
497        assert_eq!(list.len(), vec.len());
498        for i in 0..1000 {
499            assert_eq!(list.get(i), vec.get(i));
500        }
501    }
502
503    #[test]
504    fn iter() {
505        let list = setup_list();
506        let mut iter = list.iter();
507        let expected = vec![10, 20, 30, 100, 1, 2, 3];
508        for elem in expected.iter() {
509            assert_eq!(iter.next(), Some(elem));
510        }
511        assert_eq!(iter.next(), None);
512    }
513
514    #[test]
515    fn iter_mut() {
516        let mut list = setup_list();
517        let mut iter_mut = list.iter_mut();
518        while let Some(elem) = iter_mut.next() {
519            *elem += 1;
520        }
521        let expected = vec![11, 21, 31, 101, 2, 3, 4];
522        let mut iter = list.iter();
523        for elem in expected.iter() {
524            assert_eq!(iter.next(), Some(elem));
525        }
526        assert_eq!(iter.next(), None);
527    }
528
529    #[test]
530    fn into_iter() {
531        let list = setup_list();
532        let expected = vec![10, 20, 30, 100, 1, 2, 3];
533        let mut into_iter = list.into_iter();
534
535        for elem in expected {
536            assert_eq!(into_iter.next(), Some(elem));
537        }
538        assert_eq!(into_iter.next(), None);
539    }
540
541    #[test]
542    fn drop() {
543        let size = 50000;
544        let mut list = SkipLinkedList::new();
545        for _ in 0..size {
546            list.push_front(1);
547        }
548    }
549
550    #[test]
551    fn pops() {
552        let mut list = SkipLinkedList::new();
553        list.push_front(1);
554        list.push_front(2);
555        assert_eq!(list.pop_front(), 2);
556        assert_eq!(list.pop_front(), 1);
557
558        list.push_back(1);
559        list.push_back(2);
560        assert_eq!(list.pop_back(), 2);
561        assert_eq!(list.pop_back(), 1);
562    }
563
564    #[test]
565    #[should_panic]
566    fn panic_pop_front() {
567        let mut list: SkipLinkedList<i32> = SkipLinkedList::new();
568        list.pop_front();
569    }
570
571    #[test]
572    #[should_panic]
573    fn panic_pop_back() {
574        let mut list: SkipLinkedList<i32> = SkipLinkedList::new();
575        list.pop_back();
576    }
577
578    #[test]
579    #[should_panic]
580    fn panic_insert() {
581        let mut list = SkipLinkedList::new();
582        list.insert(1, 3);
583    }
584}
skip_linked_list/list.rs

skip_linked_list/
list.rs
