obj-pool 0.6.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

extern crate obj_pool;

use obj_pool::{ObjPool, ObjId};

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 {
        let obj_pool = ObjPool::new();
        List {
            obj_pool,
            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 a.is_some() { self.obj_pool[a].next = b; }
        if b.is_some() { 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, node);

        self.tail = node;
        if self.head.is_none() {
            self.head = 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 node = self.obj_pool.remove(self.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 == obj_id { self.head = node.next; }
        if self.tail == 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);
}