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
mod node;
#[cfg(test)]
mod tests;
pub use node::Id;
use node::{Node, Nullable};
#[derive(Default, Clone)]
pub struct List<T> {
nodes: Vec<Node<T>>,
count: usize,
tail_id: Id,
}
impl<T> List<T> {
pub fn new(initial_capacity: usize) -> List<T> {
let nodes = Vec::with_capacity(initial_capacity);
List {
nodes,
count: 0,
tail_id: 0,
}
}
pub fn push_back(&mut self, data: T) -> usize {
let (new_id, prev_id) =
match self.nodes.get(self.tail_id) {
Some(node) => {
(node.next, self.tail_id)
}
None => {
(self.tail_id, Id::NULL)
}
};
match self.nodes.get_mut(new_id) {
Some(node) => {
node.prev = prev_id;
node.next = Id::NULL;
node.data = Some(data);
self.tail_id = new_id;
}
None => {
self.nodes.push(Node::new(data, prev_id, Id::NULL));
self.tail_id = self.nodes.len() - 1
}
}
if let Some(prev) = self.nodes.get_mut(prev_id) {
prev.next = self.tail_id;
}
self.count += 1;
self.tail_id
}
pub fn pop(&mut self, id: Id) {
let pool_object = self.nodes.get_mut(id).expect("Invalid object id");
pool_object.next = Id::NULL;
pool_object.data = None;
self.nodes[self.tail_id].next = id;
self.count -= 1;
}
pub fn get(&self, id: Id) -> &T {
self.nodes.get(id)
.and_then(|node| node.data.as_ref())
.expect("Invalid object id")
}
pub fn get_mut(&mut self, id: Id) -> &mut T {
self.nodes.get_mut(id)
.and_then(|node| node.data.as_mut())
.expect("Invalid object id")
}
pub fn len(&self) -> usize {
self.count
}
pub fn is_empty(&self) -> bool {
self.count == 0
}
pub fn unordered_iter(&self) -> impl Iterator<Item = (Id, &T)> {
self.nodes.iter()
.enumerate()
.filter_map(|(id, node)| {
node.data.as_ref().map(|object| (id, object))
})
}
pub fn unordered_iter_mut(&mut self) -> impl Iterator<Item = (Id, &mut T)> {
self.nodes.iter_mut()
.enumerate()
.filter_map(|(id, node)| {
node.data.as_mut().map(|object| (id, object))
})
}
}