low_map/
lib.rs

1////////////////////////////////////////////////////////////////////////////////
2//! A non contiguous `Vec` that optionally holds a value for a given index.
3//!
4//! It is called a `LowMap` because it maps a given index to a value, and this
5//! index must be small as it will be used as the inner `Vec` index.
6
7
8use std::ops::{Index, IndexMut};
9use std::iter::{
10    IntoIterator,
11    FromIterator,
12    FusedIterator,
13    ExactSizeIterator,
14    DoubleEndedIterator
15};
16
17////////////////////////////////////////////////////////////////////////////////
18/// A convenient wrapper around a `Vec<Option<T>>`.
19///
20/// It is called a `LowMap` because it maps a given index to a value, and this
21/// index must be small as it will be used as the inner `Vec` index.
22///
23/// ```
24/// # use low_map::LowMap;
25/// let mut map = LowMap::new();
26/// map.insert(0, "hey");
27/// map.insert(2, "hoy");
28/// map.insert(3, "foo");
29/// map.insert(2, "bar");
30///
31/// assert_eq!(map.get(0), Some(&"hey"));
32/// assert_eq!(map.get(1), None);
33/// assert_eq!(map.get(2), Some(&"bar"));
34/// assert_eq!(map.get(3), Some(&"foo"));
35///
36/// map[2] = "hoho";
37/// assert_eq!(map.get(2), Some(&"hoho"));
38/// ```
39#[derive(Clone, Debug)]
40pub struct LowMap<T> {
41    len: usize,
42    vec: Vec<Option<T>>,
43}
44impl<T> Default for LowMap<T> {
45    fn default() -> Self {
46        Self::new()
47    }
48}
49
50impl<T> LowMap<T> {
51    /// Constructs a new empty `LowMap<T>`.
52    pub fn new() -> Self {
53        Self{ len: 0, vec: Vec::new() }
54    }
55
56    /// Constructs a new empty `LowMap<T>` with the given `capacity`.
57    pub fn with_capacity(capacity: usize) -> Self {
58        Self{ len: 0, vec: Vec::with_capacity(capacity) }
59    }
60
61    /// Returns the number of stored elements.
62    pub fn len(&self) -> usize {
63        self.len
64    }
65
66    /// Returns the capacity.
67    pub fn capacity(&self) -> usize {
68        self.vec.capacity()
69    }
70
71    /// Inserts an element at position `index` within the vector, returning the
72    /// previous value if present.
73    pub fn insert(&mut self, index: usize, value: T) -> Option<T> {
74        if index >= self.vec.len() {
75            self.vec.resize_with(index + 1, || None)
76        }
77        if !self.contains(index) {
78            self.len += 1;
79        }
80        self.vec[index].replace(value)
81    }
82
83    /// Constructs a wrapper that temporarily inserts an element.
84    ///
85    /// The returned wrapper will undo the insert when dropped.
86    pub fn stack_insert(&mut self, index: usize, value: T) -> StackInsert<T> {
87        let elem = self.insert(index, value);
88        StackInsert {
89            inner: self,
90            index,
91            elem,
92        }
93    }
94
95    /// Removes and returns the element at position `index` if present.
96    pub fn remove(&mut self, index: usize) -> Option<T> {
97        if self.contains(index) {
98            self.len -= 1;
99        }
100        self.vec.get_mut(index)?.take()
101    }
102
103    /// Returns a reference to the element at position `index` if present.
104    pub fn get(&self, index: usize) -> Option<&T> {
105        self.vec.get(index)?.as_ref()
106    }
107
108    /// Returns a mutable reference to the element at position `index` if
109    /// present.
110    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
111        self.vec.get_mut(index)?.as_mut()
112    }
113
114    /// Tests whether an element is present at position `index` or not.
115    pub fn contains(&self, index: usize) -> bool {
116        match self.vec.get(index) {
117            Some(elem) => elem.is_some(),
118            None       => false,
119        }
120    }
121
122    /// Finds the first free index to store the given `elem`.
123    ///
124    /// Has a maxium complexity of *O*(n).
125    pub fn push(&mut self, elem: T) -> usize {
126        if let Some(index) = self.vec.iter().position(|e| e.is_none()) {
127            self.insert(index, elem);
128            index
129        }
130        else {
131            self.vec.push(Some(elem));
132            self.len += 1;
133            self.len
134        }
135    }
136
137    /// Returns an iterator over the value of stored elements.
138    pub fn values(&self) -> Values<T> {
139        Values { inner: self.vec.iter(), count: self.len }
140    }
141
142    /// Returns a mutable iterator over the value of stored elements.
143    pub fn values_mut(&mut self) -> ValuesMut<T> {
144        ValuesMut { inner: self.vec.iter_mut(), count: self.len }
145    }
146    
147    /// Returns an iterator over the index and value of stored elements.
148    pub fn iter(&self) -> Iter<T> {
149        Iter { inner: self.vec.iter().enumerate(), count: self.len }
150    }
151
152    /// Returns a mutable iterator over the index and value of stored elements.
153    pub fn iter_mut(&mut self) -> IterMut<T> {
154        IterMut{
155            inner: self.vec.iter_mut().enumerate(),
156            count: self.len,
157        }
158    }
159    
160    /// Returns an iterator over the index of stored elements.
161    pub fn indexes(&self) -> Indexes<T> {
162        Indexes { inner: self.vec.iter().enumerate(), count: self.len }
163    }
164
165    /// Returns the wrapped vec as a slice.
166    pub fn as_slice(&self) -> &[Option<T>] {
167        self.vec.as_slice()
168    }
169}
170
171pub struct Drain<'a, T> {
172    inner: std::iter::Enumerate<std::vec::Drain<'a, Option<T>>>,
173    count: usize,
174}
175impl<'a, T> Iterator for Drain<'a, T> {
176    type Item = (usize, T);
177    fn next(&mut self) -> Option<Self::Item> {
178        while let Some((index, elem)) = self.inner.next() {
179            if let Some(elem) = elem {
180                self.count -= 1;
181                return Some((index, elem));
182            }
183        }
184        None
185    }
186    fn size_hint(&self) -> (usize, Option<usize>) {
187        (self.count, Some(self.count))
188    }
189    fn count(self) -> usize {
190        self.inner.count();
191        self.count
192    }
193}
194impl<'a, T> ExactSizeIterator for Drain<'a, T> {}
195impl<'a, T> FusedIterator for Drain<'a, T> {}
196impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
197    fn next_back(&mut self) -> Option<Self::Item> {
198        while let Some((index, elem)) = self.inner.next_back() {
199            if let Some(elem) = elem {
200                self.count -= 1;
201                return Some((index, elem));
202            }
203        }
204        None
205    }
206}
207
208impl<T> From<Vec<Option<T>>> for LowMap<T> {
209    fn from(vec: Vec<Option<T>>) -> Self {
210        Self{
211            len: vec.iter().filter(|e| e.is_some()).count(),
212            vec
213        }
214    }
215}
216
217impl<T> From<LowMap<T>> for Vec<Option<T>> {
218    fn from(LowMap{vec, ..}: LowMap<T>) -> Self {
219        vec
220    }
221}
222
223pub struct Indexes<'a, T> {
224    inner: std::iter::Enumerate<std::slice::Iter<'a, Option<T>>>,
225    count: usize,
226}
227impl<'a, T> Iterator for Indexes<'a, T> {
228    type Item = usize;
229    fn next(&mut self) -> Option<Self::Item> {
230        while let Some((index, elem)) = self.inner.next() {
231            if elem.is_some() {
232                self.count -= 1;
233                return Some(index);
234            }
235        }
236        None
237    }
238    fn size_hint(&self) -> (usize, Option<usize>) {
239        (self.count, Some(self.count))
240    }
241    fn count(self) -> usize {
242        self.inner.count();
243        self.count
244    }
245}
246impl<'a, T> FusedIterator for Indexes<'a, T> {}
247impl<'a, T> ExactSizeIterator for Indexes<'a, T> {}
248impl<'a, T> DoubleEndedIterator for Indexes<'a, T> {
249    fn next_back(&mut self) -> Option<Self::Item> {
250        while let Some((index, elem)) = self.inner.next_back() {
251            if elem.is_some() {
252                self.count -= 1;
253                return Some(index);
254            }
255        }
256        None
257    }
258}
259
260pub struct IterMut<'a, T> {
261    inner: std::iter::Enumerate<std::slice::IterMut<'a, Option<T>>>,
262    count: usize,
263}
264impl<'a, T> Iterator for IterMut<'a, T> {
265    type Item = (usize, &'a mut T);
266    fn next(&mut self) -> Option<Self::Item> {
267        while let Some((index, elem)) = self.inner.next() {
268            if let Some(elem) = elem.as_mut() {
269                self.count -= 1;
270                return Some((index, elem));
271            }
272        }
273        None
274    }
275    fn size_hint(&self) -> (usize, Option<usize>) {
276        (self.count, Some(self.count))
277    }
278    fn count(self) -> usize {
279        self.inner.count();
280        self.count
281    }
282}
283impl<'a, T> FusedIterator for IterMut<'a, T> {}
284impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
285impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
286    fn next_back(&mut self) -> Option<Self::Item> {
287        while let Some((index, elem)) = self.inner.next_back() {
288            if let Some(elem) = elem.as_mut() {
289                self.count -= 1;
290                return Some((index, elem));
291            }
292        }
293        None
294    }
295}
296
297pub struct Iter<'a, T> {
298    inner: std::iter::Enumerate<std::slice::Iter<'a, Option<T>>>,
299    count: usize,
300}
301impl<'a, T> Iterator for Iter<'a, T> {
302    type Item = (usize, &'a T);
303    fn next(&mut self) -> Option<Self::Item> {
304        while let Some((index, elem)) = self.inner.next() {
305            if let Some(elem) = elem.as_ref() {
306                self.count -= 1;
307                return Some((index, elem));
308            }
309        }
310        None
311    }
312    fn size_hint(&self) -> (usize, Option<usize>) {
313        (self.count, Some(self.count))
314    }
315    fn count(self) -> usize {
316        self.inner.count();
317        self.count
318    }
319}
320impl<'a, T> FusedIterator for Iter<'a, T> {}
321impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
322impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
323    fn next_back(&mut self) -> Option<Self::Item> {
324        while let Some((index, elem)) = self.inner.next_back() {
325            if let Some(elem) = elem.as_ref() {
326                self.count -= 1;
327                return Some((index, elem));
328            }
329        }
330        None
331    }
332}
333
334pub struct Values<'a, T> {
335    inner: std::slice::Iter<'a, Option<T>>,
336    count: usize,
337}
338impl<'a, T> Iterator for Values<'a, T> {
339    type Item = &'a T;
340    fn next(&mut self) -> Option<Self::Item> {
341        while let Some(elem) = self.inner.next() {
342            if let Some(elem) = elem.as_ref() {
343                self.count -= 1;
344                return Some(elem);
345            }
346        }
347        None
348    }
349}
350impl<'a, T> FusedIterator for Values<'a, T> {}
351impl<'a, T> ExactSizeIterator for Values<'a, T> {}
352impl<'a, T> DoubleEndedIterator for Values<'a, T> {
353    fn next_back(&mut self) -> Option<Self::Item> {
354        while let Some(elem) = self.inner.next_back() {
355            if let Some(elem) = elem.as_ref() {
356                self.count -= 1;
357                return Some(elem);
358            }
359        }
360        None
361    }
362}
363
364pub struct ValuesMut<'a, T> {
365    inner: std::slice::IterMut<'a, Option<T>>,
366    count: usize,
367}
368impl<'a, T> Iterator for ValuesMut<'a, T> {
369    type Item = &'a mut T;
370    fn next(&mut self) -> Option<Self::Item> {
371        while let Some(elem) = self.inner.next() {
372            if let Some(elem) = elem.as_mut() {
373                self.count -= 1;
374                return Some(elem);
375            }
376        }
377        None
378    }
379    fn size_hint(&self) -> (usize, Option<usize>) {
380        (self.count, Some(self.count))
381    }
382    fn count(self) -> usize {
383        self.inner.count();
384        self.count
385    }
386}
387impl<'a, T> FusedIterator for ValuesMut<'a, T> {}
388impl<'a, T> ExactSizeIterator for ValuesMut<'a, T> {}
389impl<'a, T> DoubleEndedIterator for ValuesMut<'a, T> {
390    fn next_back(&mut self) -> Option<Self::Item> {
391        while let Some(elem) = self.inner.next_back() {
392            if let Some(elem) = elem.as_mut() {
393                self.count -= 1;
394                return Some(elem);
395            }
396        }
397        None
398    }
399}
400
401impl<T> Index<usize> for LowMap<T> {
402    type Output = T;
403    fn index(&self, index: usize) -> &Self::Output {
404        self.get(index).unwrap()
405    }
406}
407impl<T> IndexMut<usize> for LowMap<T> {
408    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
409        self.get_mut(index).unwrap()
410    }
411}
412
413pub struct StackInsert<'a, T> {
414    inner: &'a mut LowMap<T>,
415    index: usize,
416    elem: Option<T>,
417}
418impl<'a, T> Drop for StackInsert<'a, T> {
419    fn drop(&mut self) {
420        let index = self.index;
421        if let Some(elem) = self.elem.take() {
422            self.insert(index, elem);
423        }
424        else {
425            self.remove(index);
426        }
427    }
428}
429impl<'a, T> std::ops::Deref for StackInsert<'a, T> {
430    type Target = LowMap<T>;
431    fn deref(&self) -> &Self::Target {
432        self.inner
433    }
434}
435impl<'a, T> std::ops::DerefMut for StackInsert<'a, T> {
436    fn deref_mut(&mut self) -> &mut Self::Target {
437        self.inner
438    }
439}
440
441impl<T> Extend<(usize, T)> for LowMap<T> {
442    fn extend<I>(&mut self, iter: I)
443    where I: IntoIterator<Item = (usize, T)>
444    {
445        for (i, e) in iter {
446            self.insert(i, e);
447        }
448    }
449}
450
451impl<T> FromIterator<(usize, T)> for LowMap<T> {
452    fn from_iter<I>(iter: I) -> Self
453    where I: IntoIterator<Item = (usize, T)>
454    {
455        let iter = iter.into_iter();
456        let (min, _) = iter.size_hint();
457        let mut map = LowMap::with_capacity(min);
458        map.extend(iter);
459        map
460    }
461}
462
463pub struct IntoIter<T> {
464    inner: std::iter::Enumerate<std::vec::IntoIter<Option<T>>>,
465    count: usize,
466}
467impl<T> Iterator for IntoIter<T> {
468    type Item = (usize, T);
469    fn next(&mut self) -> Option<Self::Item> {
470        while let Some((index, elem)) = self.inner.next() {
471            if let Some(elem) = elem {
472                self.count -= 1;
473                return Some((index, elem));
474            }
475        }
476        None
477    }
478    fn size_hint(&self) -> (usize, Option<usize>) {
479        (self.count, Some(self.count))
480    }
481    fn count(self) -> usize {
482        self.inner.count();
483        self.count
484    }
485}
486impl<T> FusedIterator for IntoIter<T> {}
487impl<T> ExactSizeIterator for IntoIter<T> {}
488impl<T> DoubleEndedIterator for IntoIter<T> {
489    fn next_back(&mut self) -> Option<Self::Item> {
490        while let Some((index, elem)) = self.inner.next_back() {
491            if let Some(elem) = elem {
492                self.count -= 1;
493                return Some((index, elem));
494            }
495        }
496        None
497    }
498}
499
500impl<T> IntoIterator for LowMap<T> {
501    type Item = (usize, T);
502    type IntoIter = IntoIter<T>;
503    fn into_iter(self) -> Self::IntoIter {
504        IntoIter{
505            inner: self.vec.into_iter().enumerate(),
506            count: self.len,
507        }
508    }    
509}
510
511// #[cfg(test)]
512// mod tests {
513//     use super::*;
514//     #[test]
515//     fn test_1() {
516//         let mut map = LowMap::new();
517//         map.insert(2, "hey")
518//     }
519// }
low_map/lib.rs

low_map/
lib.rs
