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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
//! Stable vec is a vector that guarantees its content access position does not change.
use serde::{Deserialize, Serialize};
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.
#[derive(Clone, Debug, Deserialize, Serialize)]
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() }
}
/// Create a stable vec from a sorted (by id, T.0) vector. Don't use if you're
/// not absolutely sure the data is valid.
pub fn from_raw_unchecked(data: Vec<(usize, T)>) -> Self {
Self { data }
}
/// 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
}
}
/// Remove all data from this vec, leaving it like a StableVec created with `new` datawise.
pub fn clear(&mut self) {
self.data.clear()
}
/// Find the next free space in the vec. If there is space at the end, this will be preferred,
/// otherwise low ids are. After checking this, `try_insert` will not fail and the returned
/// id can be used to insert an item at that position.
pub fn next_free(&self) -> usize {
// Check if the item can be pushed at the end.
if self.data.is_empty() {
0
} else if self.data.last().unwrap().0 < usize::MAX {
self.data.last().unwrap().0
} else {
// Try to find a position in the vector that is still free, starting at the bottom.
let mut prev_id = self.data.first().unwrap().0;
for (_, (id, _)) in self.data.iter().enumerate().skip(1) {
if *id > prev_id + 1 {
return *id - 1;
}
prev_id = *id;
}
panic!("There is no free space in the vector. This should never happen.");
}
}
/// Attempts to insert the item at the given position. If there is no free space, an Err value
/// will be returned.
pub fn try_insert(&mut self, id: usize, item: T) -> Result<(), ()> {
match self.find_pos(id) {
// The item already exists, this is an error.
Ok(_) => Err(()),
Err(pos) => {
self.data.insert(pos, (id, item));
Ok(())
}
}
}
/// Tries to push the item into the vector, but if it doesn't work, it searches for an opening in
/// the vector where no item currently is and places it there, favouring low ids (low ids contain
/// potentially older changes).
pub fn insert_anywhere(&mut self, item: T) -> usize {
// Check if the item can be pushed at the end and do so if possible.
if self.data.is_empty() || self.data.last().unwrap().0 < usize::MAX {
self.push(item)
} else {
// Try to find a position in the vector that is still free, starting at the bottom.
let mut prev_id = self.data.first().unwrap().0;
for (place, (id, _)) in self.data.iter().enumerate().skip(1) {
if *id > prev_id + 1 {
let id = *id - 1;
self.data.insert(place, (id, item));
return id;
}
prev_id = *id;
}
panic!("Unable to insert element. No space left in the vector.");
}
}
// 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<T> Into<Vec<(usize, T)>> for StableVec<T> {
fn into(self) -> Vec<(usize, T)> {
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))
}
}
|
