linked_list_r4l 0.3.0

Linked lists that supports arbitrary removal in constant time
Documentation 
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use linked_list_r4l::*;
use std::{fmt, sync::Arc};

def_node! {
    struct Node(String);
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.inner.eq(other.inner())
    }
}
impl PartialEq<str> for Node {
    fn eq(&self, other: &str) -> bool {
        self.inner.eq(other)
    }
}
impl fmt::Debug for Node {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Node").field("inner", &self.inner).finish()
    }
}

#[test]
fn cursor_front_mut() {
    let mut list = List::<Box<Node>>::new();
    list.push_back(Box::new(Node::new("hello".to_owned())));
    list.push_back(Box::new(Node::new("world".to_owned())));

    let mut cursor = list.cursor_front_mut();
    assert_eq!(cursor.current().unwrap(), "hello");

    // SAFETY: we have unique access through Box
    unsafe {
        cursor.peek_next().unwrap().inner.push('!');
    }

    cursor.move_next();

    // SAFETY: we have unique access through Box
    unsafe {
        assert_eq!(cursor.current_mut().unwrap(), "world!");
        cursor.peek_prev().unwrap().inner = "Hello".to_owned();
    }

    // `CommonCursor::move_next` stops at None when it reaches the end of list,
    // because `raw_list::Iterator` stops at None.
    cursor.move_next();
    assert_eq!(cursor.current(), None);

    // Then restart from the head.
    cursor.move_next();
    assert_eq!(cursor.current().unwrap(), "Hello");
}

#[test]
fn cursor_front() {
    let mut list = List::<Arc<Node>>::new();
    list.push_back(Arc::new(Node::new("hello".to_owned())));
    list.push_back(Arc::new(Node::new("world".to_owned())));

    let mut cursor = list.cursor_front();
    assert_eq!(cursor.peek_next().unwrap(), "world");
    assert_eq!(cursor.current().unwrap(), "hello");
    cursor.move_next();
    assert_eq!(cursor.current().unwrap(), "world");
    assert_eq!(cursor.peek_prev().unwrap(), "hello");

    cursor.move_next();
    assert_eq!(cursor.current(), None);

    cursor.move_next();
    assert_eq!(cursor.current().unwrap(), "hello");
}

#[test]
fn insert_after() {
    let mut list = List::<Box<Node>>::new();
    list.push_back(Box::new(Node::new("Hello".to_owned())));

    let existing = list.cursor_front().current_ptr().unwrap();
    let data = Box::new(Node::new("world".to_owned()));
    unsafe {
        assert!(list.insert_after(existing, data));
    }

    let mut cursor = list.cursor_front_mut();
    let data = Box::new(Node::new(", ".to_owned()));
    assert!(cursor.insert_after(data));

    cursor.move_next(); // ", "
    cursor.move_next(); // "world"
    let data = Box::new(Node::new("!".to_owned()));
    assert!(cursor.insert_after(data));

    cursor.move_next(); // "!"
    cursor.move_next(); // end
    assert_eq!(cursor.current(), None);

    assert_eq!(&*v_list(list.iter()), ["Hello", ", ", "world", "!"]);
}

fn v_list<'a>(iter: impl IntoIterator<Item = &'a Node>) -> Box<[&'a str]> {
    iter.into_iter().map(|node| node.inner.as_str()).collect()
}

#[test]
fn remove() {
    let mut list = List::<Arc<Node>>::new();
    let hello = Arc::new(Node::new("hello".to_owned()));
    list.push_back(hello.clone());
    let world = Arc::new(Node::new("world".to_owned()));
    list.push_back(world);

    unsafe {
        assert_eq!(&*list.remove(&hello).unwrap(), "hello");
    }

    let mut cursor = list.cursor_front_mut();
    let world = cursor.remove_current().unwrap();

    assert_eq!(cursor.current(), None);

    list.push_back(hello);
    list.push_back(world);
    assert_eq!(&*v_list(list.iter()), ["hello", "world"]);
}