toolbox_rs/
renumbering_table.rs

1use fxhash::FxHashMap;
2
3enum Implementation {
4    Vec(Vec<usize>),
5    Map(FxHashMap<usize, usize>),
6}
7
8pub struct RenumberingTable {
9    table: Implementation,
10}
11
12impl RenumberingTable {
13    pub fn new_with_size_hint(universe_size: usize, usage_bound: usize) -> Self {
14        debug_assert!(universe_size >= usage_bound);
15
16        let factor = universe_size / usage_bound;
17        if factor > 8 {
18            // the table will filled with at most 12.5% of the number of elements
19            return Self {
20                table: Implementation::Map(FxHashMap::default()),
21            };
22        }
23
24        let mut vector = Vec::new();
25        vector.resize(universe_size, usize::MAX);
26        Self {
27            table: Implementation::Vec(vector),
28        }
29    }
30
31    pub fn set(&mut self, key: usize, value: usize) {
32        match &mut self.table {
33            Implementation::Vec(vector) => vector[key] = value,
34            Implementation::Map(map) => {
35                map.insert(key, value);
36            }
37        }
38    }
39
40    pub fn get(&self, key: usize) -> usize {
41        match &self.table {
42            Implementation::Vec(vector) => vector[key],
43            Implementation::Map(map) => *map.get(&key).unwrap(),
44        }
45    }
46
47    pub fn contains_key(&self, key: usize) -> bool {
48        match &self.table {
49            Implementation::Vec(vector) => vector[key] != usize::MAX,
50            Implementation::Map(map) => map.contains_key(&key),
51        }
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use super::RenumberingTable;
58
59    #[test]
60    fn full_universe() {
61        let mut table = RenumberingTable::new_with_size_hint(10, 10);
62        for i in 0..10 {
63            table.set(i, 10 - i);
64        }
65        for i in 0..10 {
66            assert_eq!(10 - i, table.get(i));
67        }
68    }
69
70    #[test]
71    fn sparse_universe() {
72        let mut table = RenumberingTable::new_with_size_hint(10000, 10);
73        for i in 0..10 {
74            table.set(1234 + i, i);
75        }
76        for i in 0..10 {
77            assert_eq!(i, table.get(1234 + i));
78        }
79        for i in 0..1234 {
80            assert!(!table.contains_key(i));
81        }
82        for i in 1234..1244 {
83            assert!(table.contains_key(i));
84        }
85        for i in 1244..10000 {
86            assert!(!table.contains_key(i));
87        }
88    }
89}
toolbox_rs/renumbering_table.rs

toolbox_rs/
renumbering_table.rs
