cnetworks/
vecmap.rs

1/*!
2A lightweight alternative to [`std::collections::HashMap`] indexed only with `usize`.
3Useful in  scenarios where you simply want a [`Vec`] with arbitrary indexes - this structure
4achieves that by filling non-existant indexes with `None` values. It trades space for speed by not
5utilizing a hashing algorithm, as a call to [`VecMap::contains`] is roughly 8 times faster than
6[`rustc_hash::FxHashMap::contains_key`].
7
8If *i* denotes maximum index present in the map, then both iteration over items and spacial
9complexity is O(*i*). Inserting at a new index `m` extends the underlying vector by (*i - m*) and
10is therefore O(*i - m*). Other operations (including [`VecMap::len`]) are O(1).
11*/
12
13use crate::cn;
14use std::ops::{Index, IndexMut};
15
16/// A vector-based map, indexed by arbitrary `usize` values.
17#[derive(Debug, Clone)]
18pub struct VecMap<T> {
19    /// Vector of actual contained data
20    data: Vec<Option<T>>,
21    /// Vector of valid indexes
22    indexes: Vec<usize>,
23}
24
25impl<T> VecMap<T> {
26    /// Create a new, empty [`VecMap`].
27    pub fn new() -> Self {
28        VecMap {
29            data: Vec::new(),
30            indexes: Vec::new(),
31        }
32    }
33
34    /// Create a new [`VecMap`] with specified `capacity`.
35    pub fn with_capacity(capacity: usize) -> Self {
36        let mut map = VecMap {
37            data: Vec::with_capacity(capacity),
38            indexes: Vec::with_capacity(capacity),
39        };
40        for _ in 0..capacity {
41            map.data.push(None);
42        }
43        map
44    }
45
46    /// Return the total number of non-empty entries in the map.
47    pub fn len(&self) -> usize {
48        self.indexes.len()
49    }
50
51    /// Return `true` if the total number of non-empty entries in the map is 0.
52    pub fn is_empty(&self) -> bool {
53        self.indexes.is_empty()
54    }
55
56    /// Returns immutable reference to the item at specified `index`, `None` if the entry is
57    /// vacant.
58    pub fn get(&self, index: usize) -> Option<&T> {
59        self.data.get(index).unwrap_or(&None).as_ref()
60    }
61
62    /// Returns mutable reference to the item at specified `index`, `None` if the entry is vacant.
63    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
64        self.data
65            .get_mut(index)
66            .map(|opt| opt.as_mut())
67            .unwrap_or(None)
68    }
69
70    /// Insert `item` at `index`. Returns the old value or `None` if the entry was vacant.
71    pub fn insert(&mut self, index: usize, item: T) -> Option<T> {
72        // Grow to fill the gaps
73        while index >= self.data.len() {
74            self.data.push(None);
75        }
76        let old = std::mem::replace(&mut self.data[index], Some(item));
77        if old.is_none() {
78            // This index now has data
79            self.indexes.push(index)
80        }
81        old
82    }
83
84    /// Removes item at specified `index`, returning the removed value or `None` if the entry was
85    /// vacant.
86    pub fn remove(&mut self, index: usize) -> Option<T> {
87        let mut old = None;
88        if self.contains(index) {
89            old = std::mem::replace(&mut self.data[index], None);
90            // We know that old is "Some" now and that we have removed something
91            self.indexes.retain(|&idx| idx != index);
92            self.shrink();
93        }
94        old
95    }
96
97    /// Shrinks the map from to the maximum required size, by removing empty entries from the rear.
98    pub fn shrink(&mut self) {
99        while let Some(None) = self.data.last() {
100            self.data.pop();
101        }
102    }
103
104    /// Returns `true` if there exists a value at specified `index`.
105    pub fn contains(&self, index: usize) -> bool {
106        self.data.get(index).unwrap_or(&None).is_some()
107    }
108
109    /// Returns iterator of valid indexes.
110    pub fn indexes(&self) -> impl cn::Iter<usize> + '_ {
111        self.indexes.iter().copied()
112    }
113
114    /// Returns iterator of (index, item) pairs.
115    pub fn iter(&self) -> impl cn::Iter<(usize, &T)> + '_ {
116        self.data
117            .iter()
118            .enumerate()
119            .filter_map(|(idx, item)| item.as_ref().map(|item| (idx, item)))
120    }
121
122    /// Returns immutable reference to the underlying `Vec<Option<T>>`.
123    pub fn as_vec(&self) -> &Vec<Option<T>> {
124        &self.data
125    }
126
127    /// Returns mutable reference to the underlying `Vec<Option<T>>`.
128    pub fn as_vec_mut(&mut self) -> &mut Vec<Option<T>> {
129        &mut self.data
130    }
131}
132
133/// Convert [`Vec`] into a [`VecMap`].
134impl<T> From<Vec<T>> for VecMap<T> {
135    fn from(vec: Vec<T>) -> Self {
136        let mut map = VecMap::default();
137        for (index, item) in vec.into_iter().enumerate() {
138            map.insert(index, item);
139        }
140        map
141    }
142}
143
144impl<T: PartialEq> PartialEq for VecMap<T> {
145    fn eq(&self, other: &Self) -> bool {
146        self.data == other.data
147    }
148}
149
150impl<T: Eq> Eq for VecMap<T> {}
151
152/// Provides non-guarded immutable access to the map's contents.
153impl<T> Index<usize> for VecMap<T> {
154    type Output = T;
155
156    fn index(&self, index: usize) -> &Self::Output {
157        self.data[index].as_ref().unwrap()
158    }
159}
160
161/// Provides non-guarded mutable access to the map's contents.
162impl<T> IndexMut<usize> for VecMap<T> {
163    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
164        self.data[index].as_mut().unwrap()
165    }
166}
167
168/// Alias for [`VecMap::new`].
169impl<T> Default for VecMap<T> {
170    fn default() -> Self {
171        VecMap::new()
172    }
173}
174
175impl<T> std::iter::FromIterator<(usize, T)> for VecMap<T> {
176    fn from_iter<I: IntoIterator<Item = (usize, T)>>(iter: I) -> Self {
177        let mut map = VecMap::new();
178        for (idx, item) in iter {
179            map.insert(idx, item);
180        }
181        map
182    }
183}
184
185#[derive(Debug, Clone, PartialEq, Eq)]
186pub struct VecSet(cn::VecMap<()>);
187
188impl VecSet {
189    /// Create a new, empty [`VecSet`].
190    pub fn new() -> Self {
191        VecSet(cn::VecMap::new())
192    }
193
194    /// Create a new [`VecSet`] with specified `capacity`.
195    pub fn with_capacity(capacity: usize) -> Self {
196        VecSet(cn::VecMap::with_capacity(capacity))
197    }
198
199    /// Return the total number of non-empty entries in the set.
200    pub fn len(&self) -> usize {
201        self.0.len()
202    }
203
204    /// Return `true` if the total number of non-empty entries in the set is 0.
205    pub fn is_empty(&self) -> bool {
206        self.0.is_empty()
207    }
208
209    /// Returns `true` if the set contains given `index`.
210    pub fn contains(&self, index: usize) -> bool {
211        self.0.contains(index)
212    }
213
214    /// Inserts `index` into the set. Returns `true` if the set did not have this index.
215    pub fn insert(&mut self, index: usize) -> bool {
216        self.0.insert(index, ()).is_none()
217    }
218
219    /// Removes `index` from the set. Returns `true` if set did have this index.
220    pub fn remove(&mut self, index: usize) -> bool {
221        self.0.remove(index).is_some()
222    }
223
224    /// Returns vector with contained indexes.
225    pub fn indexes(&self) -> impl cn::Iter<usize> + '_ {
226        self.0.indexes()
227    }
228
229    pub fn iter(&self) -> impl cn::Iter<usize> + '_ {
230        self.0.iter().map(|(idx, _item)| idx)
231    }
232}
233
234/// Alias for [`VecSet::new`].
235impl Default for VecSet {
236    fn default() -> Self {
237        VecSet::new()
238    }
239}
240
241impl std::iter::FromIterator<usize> for VecSet {
242    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
243        let mut set = VecSet::new();
244        for idx in iter {
245            set.insert(idx);
246        }
247        set
248    }
249}
250
251#[test]
252fn test_remove() {
253    let mut map: VecMap<usize> = VecMap::new();
254    assert!(map.data.is_empty());
255    for i in [3, 10, 12] {
256        assert!(map.insert(i, 0).is_none());
257    }
258    assert_eq!(map.data.len(), 13);
259    assert_eq!(map.len(), 3);
260
261    assert!(map.remove(100).is_none());
262    assert_eq!(map.data.len(), 13);
263    assert_eq!(map.len(), 3);
264
265    assert_eq!(map.remove(3), Some(0));
266    assert_eq!(map.data.len(), 13);
267    assert_eq!(map.len(), 2);
268    assert_eq!(map.indexes, vec![10, 12]);
269}
270
271#[test]
272fn test_new() {
273    let map: VecMap<usize> = VecMap::new();
274    assert!(map.data.is_empty());
275    assert_eq!(map.len(), 0);
276    let map: VecMap<i32> = [(1, 0), (10, 0), (3, 0)].iter().cloned().collect();
277    for i in [1, 10, 3] {
278        assert_eq!(map[i], 0);
279    }
280    assert_eq!(map.len(), 3);
281    assert_eq!(map.indexes, vec![1, 10, 3]);
282}
283
284#[test]
285fn test_insert() {
286    let mut map: VecMap<usize> = VecMap::new();
287    assert!(map.data.is_empty());
288
289    assert!(map.insert(3, 0).is_none());
290    assert_eq!(map.data.len(), 4);
291    assert_eq!(map.indexes.len(), 1);
292    assert_eq!(map.len(), map.indexes.len());
293    assert_eq!(map.data[3], Some(0));
294
295    assert!(map.insert(10, 0).is_none());
296    assert_eq!(map.indexes.len(), 2);
297    assert_eq!(map.data.len(), 11);
298    assert_eq!(map.data[10], Some(0));
299
300    assert_eq!(map.insert(3, 12), Some(0));
301    assert_eq!(map.indexes.len(), 2);
302    assert_eq!(map.len(), map.indexes.len());
303    assert_eq!(map.data.len(), 11);
304    assert_eq!(map.data[3], Some(12));
305}
cnetworks/vecmap.rs

cnetworks/
vecmap.rs
