chj_rustbin/
index_map.rs

1//! A Vec that automatically grows to accommodate the index passed to
2//! `insert`, and tracks occupancy of its slots.
3
4// Also offer a variant that requires T to implement Default?
5
6use std::{
7    mem::replace,
8    ops::{Index, IndexMut},
9};
10
11#[derive(Debug)]
12pub struct IndexMap<T>(Vec<Option<T>>);
13
14impl<T> IndexMap<T> {
15    pub fn new() -> Self {
16        Self(Vec::new())
17    }
18
19    pub fn insert(&mut self, key: usize, val: T) -> Option<T> {
20        let oldlen = self.0.len();
21        if key >= oldlen {
22            if key > oldlen {
23                self.0.resize_with(key, || None);
24            }
25            self.0.push(Some(val));
26            None
27        } else {
28            replace(&mut self.0[key], Some(val))
29        }
30    }
31
32    pub fn get(&self, key: usize) -> Option<&T> {
33        if key < self.0.len() {
34            self.0[key].as_ref()
35        } else {
36            None
37        }
38    }
39
40    pub fn get_mut(&mut self, key: usize) -> Option<&mut T> {
41        if key < self.0.len() {
42            self.0[key].as_mut()
43        } else {
44            None
45        }
46    }
47}
48
49impl<T> Index<usize> for IndexMap<T> {
50    type Output = T;
51
52    fn index(&self, index: usize) -> &Self::Output {
53        self.get(index).expect("index within bounds")
54    }
55}
56
57impl<T> IndexMut<usize> for IndexMap<T> {
58    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
59        self.get_mut(index).expect("index within bounds")
60    }
61}
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn t_general() {
69        let mut m = IndexMap::new();
70        assert_eq!(m.insert(10, 10), None);
71        assert_eq!(m.insert(10, 101), Some(10));
72        assert_eq!(m.insert(11, 11), None);
73        assert_eq!(m.insert(0, 1000), None);
74        assert_eq!(m.insert(0, 100), Some(1000));
75        assert_eq!(m.insert(12, 12), None);
76
77        assert_eq!(m.get(0), Some(&100));
78        assert_eq!(m.get(1), None);
79        assert_eq!(m.get(10), Some(&101));
80        assert_eq!(m.get(11), Some(&11));
81        assert_eq!(m.get(12), Some(&12));
82        assert_eq!(m.get(13), None);
83
84        assert_eq!(&m[0], &100);
85        assert_eq!(m[10], 101);
86
87        m[10] = 10101;
88
89        assert_eq!(m.get(10), Some(&10101));
90    }
91
92    #[test]
93    #[should_panic]
94    fn t_inaccessible() {
95        let m = IndexMap::<u32>::new();
96        m[0];
97    }
98
99    #[test]
100    #[should_panic]
101    fn t_inaccessible_1() {
102        let mut m = IndexMap::new();
103        m.insert(10, 10);
104        m[3];
105    }
106}
chj_rustbin/index_map.rs

chj_rustbin/
index_map.rs
