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
|
//! Stable vec is a vector that guarantees its content access position does not change.
use std::ops::Deref;
use std::slice::IterMut;
/// Works like Vec, but with an additional field, where the position information is saved. Does not
/// support inserting elements in arbitrary positions, since that may shift the data. Removing data
/// in the middle is fine, however.
pub struct StableVec<T> {
data: Vec<(usize, T)>,
}
/// Mutable iterator over a stable vector. Similar to enumerate, but since only the elements actually
/// in the vector are iterated there can be holes in the enumeration (i -> i+1 not guaranteed).
pub struct IdIterMut<'a, T> {
internal: IterMut<'a, (usize, T)>,
}
impl<T> StableVec<T> {
/// Create a new, empty StableVec
pub fn new() -> Self {
Self { data: Vec::new() }
}
/// Add an item to the end of the vector. Returns its stable id. (`len()-1 != last_element_id`)
pub fn push(&mut self, item: T) -> usize {
if self.data.is_empty() {
self.data.push((0, item));
0
} else {
let id = self.data.last().unwrap().0 + 1;
self.data.push((id, item));
id
}
}
// Find the internal position of the given id in `O(log n)`
fn find_pos(&self, id: usize) -> Result<usize, usize> {
self.data.binary_search_by(|x| x.0.cmp(&id))
}
/// Get the item with the given id from the vec, if it exists. Unlike in a normal vec, this is
/// not `O(1)` but `O(log n)`.
pub fn get(&self, id: usize) -> Option<&T> {
match self.find_pos(id) {
Ok(pos) => Some(&self.data[pos].1),
Err(_) => None,
}
}
/// Get the item with the id mutably. Like `get()` this is also `O(log n)`
pub fn get_mut(&mut self, id: usize) -> Option<&mut T> {
match self.find_pos(id) {
Ok(pos) => Some(&mut self.data[pos].1),
Err(_) => None,
}
}
/// Remove the item with the given id from the vector, returning it, if it existed.
pub fn remove(&mut self, id: usize) -> Option<T> {
match self.find_pos(id) {
Ok(pos) => Some(self.data.remove(pos).1),
Err(_) => None,
}
}
/// Create an id enumerating iterator over the StableVec.
pub fn id_iter_mut(&mut self) -> IdIterMut<'_, T> {
IdIterMut::new(&mut self.data)
}
}
impl<T> Default for StableVec<T> {
fn default() -> Self {
Self::new()
}
}
impl<T> Deref for StableVec<T> {
type Target = Vec<(usize, T)>;
fn deref(&self) -> &Self::Target {
&self.data
}
}
impl<'a, T> IdIterMut<'a, T> {
pub(super) fn new(id_vec: &'a mut [(usize, T)]) -> Self {
Self {
internal: id_vec.iter_mut(),
}
}
}
impl<'a, T> Iterator for IdIterMut<'a, T> {
type Item = (usize, &'a mut T);
fn next(&mut self) -> Option<Self::Item> {
self.internal.next().map(|(id, item)| (*id, item))
}
}
impl<'a, T> DoubleEndedIterator for IdIterMut<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.internal.next_back().map(|(id, item)| (*id, item))
}
}
|
