resizing_vec/
lib.rs

1#![doc = include_str!("../README.md")]
2
3use std::{
4    iter::repeat_with,
5    ops::{Index, IndexMut},
6};
7
8#[derive(Debug, Clone)]
9pub struct ResizingVec<T> {
10    data: Vec<Option<T>>,
11    /// The amount of positions in `vec`
12    /// that have active (Some(_) values)
13    active: usize,
14}
15
16impl<T> From<Vec<T>> for ResizingVec<T> {
17    fn from(value: Vec<T>) -> Self {
18        let data = value.into_iter().map(|e| Some(e)).collect::<Vec<_>>();
19        let active = data.len();
20        Self { data, active }
21    }
22}
23
24impl<T> Index<usize> for ResizingVec<T> {
25    type Output = Option<T>;
26
27    fn index(&self, index: usize) -> &Self::Output {
28        &self.data[index]
29    }
30}
31
32impl<T> IndexMut<usize> for ResizingVec<T> {
33    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
34        &mut self.data[index]
35    }
36}
37
38impl<T> Default for ResizingVec<T> {
39    fn default() -> Self {
40        Self {
41            data: Vec::default(),
42            active: 0,
43        }
44    }
45}
46
47impl<T> ResizingVec<T> {
48    #[must_use]
49    pub fn new() -> Self {
50        Self::default()
51    }
52
53    /// Pre allocates enough space so that elements with ids < [`reserved_space()`](#method.reserved_space)
54    /// fit without having to resize
55    #[must_use]
56    pub fn prefill(capacity: usize) -> Self {
57        let vec = repeat_with(|| None).take(capacity).collect::<Vec<_>>();
58        Self {
59            data: vec,
60            active: 0,
61        }
62    }
63
64    /// Returns the amount of space length the inner vector has.
65    /// Creating a fresh `ResizingVec` and then inserting elements
66    /// at index 0 & 2 would result in [`reserved_space()`](#method.reserved_space) returning 3
67    /// as at position 1 would be an empty value
68    #[must_use]
69    pub fn reserved_space(&self) -> usize {
70        self.data.len()
71    }
72
73    /// Returns the amount of active values.
74    /// [filled()](#method.filled) <= [`reserved_space()`](#method.reserved_space) will always hold true.
75    #[must_use]
76    pub fn filled(&self) -> usize {
77        self.active
78    }
79
80    /// Returns the element at the given index
81    #[must_use]
82    pub fn get(&self, idx: usize) -> Option<&T> {
83        match self.data.get(idx) {
84            Some(inner) => inner.as_ref(),
85            None => None,
86        }
87    }
88
89    /// Returns a mutable reference to element at the given index
90    #[must_use]
91    pub fn get_mut(&mut self, idx: usize) -> Option<&mut T> {
92        match self.data.get_mut(idx) {
93            Some(inner) => inner.as_mut(),
94            None => None,
95        }
96    }
97
98    // TODO: Use traits
99    pub fn iter(&self) -> impl Iterator<Item = (usize, &T)> + '_ {
100        self.data
101            .iter()
102            .enumerate()
103            .filter_map(|(idx, t)| t.as_ref().map(|e| (idx, e)))
104    }
105
106    /// Removes the element at the given index and returns the
107    /// remove element. If the given index is out of bounds
108    /// than None is being returned
109    pub fn remove(&mut self, idx: usize) -> Option<T> {
110        if self.data.len() > idx {
111            let prev = self.data[idx].take();
112            if prev.is_some() {
113                self.active -= 1;
114            }
115
116            prev
117        } else {
118            None
119        }
120    }
121
122    /// Inserts the element at the given index.
123    /// IMPORTANT: The time complexity of this operation
124    /// depends on whether it has to resize or not.
125    ///
126    /// if [`reserved_space()`](#method.reserved_space) < idx then `insert`
127    /// will first insert (idx - [`reserved_space()`](#method.reserved_space)) elements before
128    /// inserting the given element at the index.
129    pub fn insert(&mut self, idx: usize, t: T) -> Option<T> {
130        while self.data.len() <= idx {
131            self.data.push(None);
132        }
133
134        let prev = std::mem::replace(&mut self.data[idx], Some(t));
135
136        if prev.is_none() {
137            self.active += 1;
138        }
139
140        prev
141    }
142
143    /// Clears the vector, removing all values
144    pub fn clear(&mut self) {
145        *self = Self::default();
146    }
147
148    /// Resizes the vector shrinks it so that every reserved space is being occupied by an element.
149    ///
150    /// # Examples
151    /// ```
152    /// use resizing_vec::{ResizingVec, Position};
153    ///
154    /// let mut r_vec = ResizingVec::new();
155    /// r_vec.insert(5, "6th elem".to_string());
156    /// // ResizingVec { vec: [None, None, None, None, None, Some("5th elem")], active: 1 }
157    /// assert_eq!(6, r_vec.reserved_space());
158    /// assert_eq!(1, r_vec.filled());
159    ///
160    /// let new_positions = r_vec.resize();
161    /// // ResizingVec { vec: [Some("5th elem")], active: 1 }
162    /// assert_eq!(new_positions, [Position {prev_idx: 5, new_idx: 0}]);
163    /// assert_eq!(1, r_vec.reserved_space());
164    /// assert_eq!(1, r_vec.filled());
165    /// ```
166    #[must_use]
167    pub fn resize(&mut self) -> Vec<Position> {
168        let vec = Vec::with_capacity(self.active);
169        let mut positions = Vec::with_capacity(self.active);
170
171        let prev = std::mem::replace(&mut self.data, vec);
172
173        for (idx, elem) in prev.into_iter().enumerate() {
174            if elem.is_some() {
175                self.data.push(elem);
176                positions.push(Position {
177                    prev_idx: idx,
178                    new_idx: self.data.len() - 1,
179                });
180            }
181        }
182
183        self.active = self.data.len();
184
185        positions
186    }
187}
188
189#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
190pub struct Position {
191    /// The previous index of the element before resizing
192    pub prev_idx: usize,
193    /// The new index of the element
194    pub new_idx: usize,
195}
196
197impl Position {
198    #[must_use]
199    pub fn changed(&self) -> bool {
200        self.prev_idx != self.new_idx
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207
208    #[test]
209    fn reserved_space() {
210        let mut rv = ResizingVec::prefill(10);
211        assert_eq!(rv.reserved_space(), 10);
212        assert_eq!(rv.filled(), 0);
213
214        rv.insert(0, "0");
215
216        assert_eq!(rv.reserved_space(), 10);
217        assert_eq!(rv.filled(), 1);
218    }
219
220    #[test]
221    fn get_remove_iter_clear() {
222        let mut rv = ResizingVec::default();
223        assert_eq!(None, rv.get(0));
224
225        rv.insert(0, "0");
226
227        assert_eq!(Some(&"0"), rv.get(0));
228        assert_eq!(None, rv.get(1));
229
230        rv.remove(0);
231
232        assert_eq!(None, rv.get(0));
233        assert_eq!(None, rv.get(1));
234
235        rv.insert(1, "1");
236        rv.insert(2, "2");
237        rv.insert(3, "3");
238
239        assert_eq!(Some(&"1"), rv.get(1));
240        assert_eq!(Some(&"2"), rv.get(2));
241        assert_eq!(Some(&"3"), rv.get(3));
242
243        assert_eq!(3, rv.iter().count());
244
245        rv.clear();
246
247        assert_eq!(0, rv.iter().count());
248
249        assert_eq!(rv.reserved_space(), 0);
250        assert_eq!(rv.filled(), 0);
251    }
252
253    #[test]
254    fn resize() {
255        let mut rv = ResizingVec::default();
256
257        rv.insert(10, "1");
258        rv.insert(22, "2");
259        rv.insert(44, "3");
260        rv.insert(0, "0");
261
262        assert_eq!(rv.reserved_space(), 45);
263        assert_eq!(rv.filled(), 4);
264
265        let new_positions = rv.resize();
266
267        assert_eq!(new_positions.len(), 4);
268
269        assert_eq!(new_positions[0].prev_idx, 0);
270        assert_eq!(new_positions[0].new_idx, 0);
271        assert!(!new_positions[0].changed());
272
273        assert_eq!(new_positions[1].prev_idx, 10);
274        assert_eq!(new_positions[1].new_idx, 1);
275        assert!(new_positions[1].changed());
276
277        assert_eq!(new_positions[2].prev_idx, 22);
278        assert_eq!(new_positions[2].new_idx, 2);
279        assert!(new_positions[2].changed());
280
281        assert_eq!(new_positions[3].prev_idx, 44);
282        assert_eq!(new_positions[3].new_idx, 3);
283        assert!(new_positions[3].changed());
284
285        assert_eq!(rv.reserved_space(), 4);
286        assert_eq!(rv.filled(), 4);
287    }
288}
resizing_vec/lib.rs

resizing_vec/
lib.rs
