obj-pool 0.7.0

A simple object arena
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
128
129
130
131
132

use obj_pool::{ObjId, ObjPool};

struct Node<T> {
    /// Previous node in the list.
    prev: Option<ObjId>,

    /// Next node in the list.
    next: Option<ObjId>,

    /// Actual value stored in node.
    value: T,
}

struct List<T> {
    /// This is where nodes are stored.
    obj_pool: ObjPool<Node<T>>,

    /// First node in the list.
    head: Option<ObjId>,

    /// Last node in the list.
    tail: Option<ObjId>,
}

impl<T> List<T> {
    /// Constructs a new, empty doubly linked list.
    fn new() -> Self {
        List {
            obj_pool: ObjPool::new(),
            head: None,
            tail: None,
        }
    }

    /// Returns the number of elements in the list.
    fn len(&self) -> usize {
        self.obj_pool.len() as usize
    }

    /// Links nodes `a` and `b` together, so that `a` comes before `b` in the list.
    fn link(&mut self, a: Option<ObjId>, b: Option<ObjId>) {
        if let Some(a) = a {
            self.obj_pool[a].next = b;
        }
        if let Some(b) = b {
            self.obj_pool[b].prev = a;
        }
    }

    /// Appends `value` to the back of the list.
    fn push_back(&mut self, value: T) -> usize {
        let node = self.obj_pool.insert(Node {
            prev: None,
            next: None,
            value,
        });

        let tail = self.tail;
        self.link(tail, Some(node));

        self.tail = Some(node);
        if self.head.is_none() {
            self.head = Some(node);
        }
        self.obj_pool.obj_id_to_index(node) as usize
    }

    /// Pops and returns the value at the front of the list.
    fn pop_front(&mut self) -> T {
        let head = self.head.expect("the list is empty");
        let node = self.obj_pool.remove(head).unwrap();

        self.link(None, node.next);
        self.head = node.next;
        if node.next.is_none() {
            self.tail = None;
        }
        node.value
    }

    /// Removes the element specified by `index`.
    fn remove(&mut self, index: usize) -> T {
        let obj_id = self.obj_pool.index_to_obj_id(index as u32);
        let node = self.obj_pool.remove(obj_id).unwrap();

        self.link(node.prev, node.next);
        if self.head == Some(obj_id) {
            self.head = node.next;
        }
        if self.tail == Some(obj_id) {
            self.tail = node.prev;
        }

        node.value
    }
}

fn main() {
    let mut list = List::new();

    // The list is now [].

    let one = list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    // The list is now [1, 2, 3].

    list.push_back(10);
    let twenty = list.push_back(20);
    list.push_back(30);

    // The list is now [1, 2, 3, 10, 20, 30].

    assert_eq!(list.len(), 6);

    assert_eq!(list.remove(one), 1);
    assert_eq!(list.remove(twenty), 20);

    // The list is now [2, 3, 10, 30].

    assert_eq!(list.len(), 4);

    assert_eq!(list.pop_front(), 2);
    assert_eq!(list.pop_front(), 3);
    assert_eq!(list.pop_front(), 10);
    assert_eq!(list.pop_front(), 30);

    // The list is now [].

    assert_eq!(list.len(), 0);
}