guava_table/
lib.rs

1use core::hash::Hash;
2use std::collections::{HashMap, HashSet};
3
4pub trait TableKV: Eq + PartialEq + Hash {
5    fn id(&self) -> usize;
6}
7
8#[derive(Clone, Debug)]
9pub struct Table<C: TableKV, R: TableKV, V: TableKV> {
10    // Intersection of column and row has these values
11    pub tuples: HashMap<(usize, usize), HashSet<usize>>,
12    // A given column has these values with all rows
13    pub cols2values: HashMap<usize, HashSet<usize>>,
14    // A given row has these values with all columns
15    pub rows2values: HashMap<usize, HashSet<usize>>,
16    pub values: HashMap<usize, V>,
17    pub cols: HashMap<usize, C>,
18    pub rows: HashMap<usize, R>,
19}
20
21impl<C: TableKV, R: TableKV, V: TableKV> Table<C, R, V> {
22    pub fn new() -> Self {
23        Table {
24            tuples: HashMap::new(),
25            cols2values: HashMap::new(),
26            rows2values: HashMap::new(),
27            values: HashMap::new(),
28            cols: HashMap::new(),
29            rows: HashMap::new(),
30        }
31    }
32
33    pub fn insert(&mut self, column: C, row: R, value: V) {
34        let column_key = column.id();
35        let row_key = row.id();
36
37        self.insert_value(column_key, row_key, value);
38        self.cols.insert(column_key, column);
39        self.rows.insert(row_key, row);
40    }
41
42    pub fn insert_column_value(&mut self, column: C, row_key: usize, value: V) {
43        // It is assumed here that row has already been inserted previously
44        let column_key = column.id();
45
46        self.insert_value(column_key, row_key, value);
47        self.cols.insert(column_key, column);
48    }
49
50    pub fn insert_row_value(&mut self, column_key: usize, row: R, value: V) {
51        // It is assumed here that column has already been inserted previously
52        let row_key = row.id();
53
54        self.insert_value(column_key, row_key, value);
55        self.rows.insert(row_key, row);
56    }
57
58    pub fn insert_value(&mut self, column_key: usize, row_key: usize, value: V) {
59        let column_row_key = (column_key, row_key);
60        let value_key = value.id();
61
62        self.tuples.entry(column_row_key).or_insert_with(HashSet::new).insert(value_key);
63        self.cols2values.entry(column_key).or_insert_with(HashSet::new).insert(value_key);
64        self.rows2values.entry(row_key).or_insert_with(HashSet::new).insert(value_key);
65
66        self.values.insert(value_key, value);
67    }
68
69    pub fn remove(&mut self, column_key: usize, row_key: usize, value_key: usize) {
70        remove_from_set_and_map(&mut self.tuples, &(column_key, row_key), &value_key);
71        remove_from_set_and_map(&mut self.cols2values, &column_key, &value_key);
72        remove_from_set_and_map(&mut self.rows2values, &row_key, &value_key);
73
74        self.values.remove(&value_key);
75
76        if !self.cols2values.contains_key(&column_key) {
77            self.cols.remove(&column_key);
78        }
79
80        if !self.rows2values.contains_key(&row_key) {
81            self.rows.remove(&row_key);
82        }
83    }
84
85    pub fn remove_by_row(&mut self, row_key_to_remove: usize) {
86        let mut items_to_remove = HashSet::<(usize, usize)>::new();
87
88        for (tuple, vals) in &self.tuples {
89            if tuple.1 == row_key_to_remove {
90                for value_key in vals {
91                    let item = (tuple.0, *value_key);
92                    items_to_remove.insert(item);
93                }
94            }
95        }
96
97        for (column_key, value_key) in items_to_remove {
98            self.remove(column_key, row_key_to_remove, value_key);
99        }
100    }
101
102    pub fn remove_by_column(&mut self, column_key_to_remove: usize) {
103        let mut items_to_remove = HashSet::<(usize, usize)>::new();
104
105        for (tuple, vals) in &self.tuples {
106            if tuple.0 == column_key_to_remove {
107                for value_key in vals {
108                    let item = (tuple.1, *value_key);
109                    items_to_remove.insert(item);
110                }
111            }
112        }
113
114        for (row_key, value_key) in items_to_remove {
115            self.remove(column_key_to_remove, row_key, value_key);
116        }
117    }
118
119    pub fn is_empty(&self) -> bool {
120        let all_empty = self.tuples.is_empty() && self.cols2values.is_empty() && self.rows2values.is_empty();
121        let all_non_empty = !self.tuples.is_empty() && !self.cols2values.is_empty() && !self.rows2values.is_empty();
122        assert!(all_empty || all_non_empty);
123        all_empty
124    }
125}
126
127#[derive(Clone, Debug)]
128pub struct InverseTable {
129    // This column has these values except those at intersection with this row
130    pub column_value_keys_except: HashMap<(usize, usize), HashSet<usize>>,
131    // This row has these values except those at intersection with this column
132    pub row_value_keys_except: HashMap<(usize, usize), HashSet<usize>>,
133}
134
135impl InverseTable {
136    pub fn rebuild_from<C: TableKV, R: TableKV, V: TableKV>(table: &Table<C, R, V>) -> Self {
137        let mut column_value_keys_except = HashMap::<(usize, usize), HashSet<usize>>::new();
138        let mut row_value_keys_except = HashMap::<(usize, usize), HashSet<usize>>::new();
139
140        for key @ (column_key, row_key) in table.tuples.keys() {
141            let column_value_keys = table.cols2values.get(column_key).unwrap();
142            let row_value_keys = table.rows2values.get(row_key).unwrap();
143
144            let column_values_diff = column_value_keys.difference(row_value_keys).cloned().collect();
145            let row_values_diff = row_value_keys.difference(column_value_keys).cloned().collect();
146
147            column_value_keys_except.insert(*key, column_values_diff);
148            row_value_keys_except.insert(*key, row_values_diff);
149        }
150
151        InverseTable {
152            column_value_keys_except,
153            row_value_keys_except,
154        }
155    }
156}
157
158// A utility to remove a value from HashSet which is a value of HashMap, and then remove a HashMap key if set becomes empty
159pub fn remove_from_set_and_map<K: Eq + Hash, V: Eq + Hash>(map: &mut HashMap<K, HashSet<V>>, key: &K, value: &V) {
160    if let Some(inner_set) = map.get_mut(key) {
161        inner_set.remove(value);
162
163        if inner_set.is_empty() {
164            map.remove(key);
165        }
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172
173    #[derive(Debug, Eq, PartialEq, Hash)]
174    struct Container(usize);
175
176    impl TableKV for Container {
177        fn id(&self) -> usize {
178            self.0
179        }
180    }
181
182    #[test]
183    fn basic_ops() {
184        let mut table: Table<Container, Container, Container> = Table::new();
185        table.insert(Container(1), Container(2), Container(11));
186        table.insert(Container(1), Container(2), Container(11));
187        table.insert(Container(1), Container(2), Container(12));
188        table.insert(Container(1), Container(3), Container(12));
189
190        assert_eq!(table.tuples.get(&(1, 2)).unwrap().len(), 2);
191        assert_eq!(table.tuples.get(&(1, 3)).unwrap().len(), 1);
192        assert!(table.tuples.get(&(4, 2)).is_none());
193    }
194
195    #[test]
196    fn remove_handle_duplicate() {
197        let mut table: Table<Container, Container, Container> = Table::new();
198        table.insert(Container(1), Container(2), Container(11));
199        table.insert(Container(1), Container(2), Container(11));
200        table.remove(1, 2, 11);
201        assert!(table.is_empty());
202    }
203
204    #[test]
205    fn remove_by_column() {
206        let mut table: Table<Container, Container, Container> = Table::new();
207        table.insert(Container(1), Container(2), Container(11));
208        table.insert(Container(1), Container(2), Container(12));
209        table.insert(Container(1), Container(3), Container(14));
210        table.insert(Container(1), Container(3), Container(15));
211        table.remove_by_column(1);
212        assert!(table.is_empty());
213    }
214
215    #[test]
216    fn remove_by_row() {
217        let mut table: Table<Container, Container, Container> = Table::new();
218        table.insert(Container(2), Container(1), Container(11));
219        table.insert(Container(3), Container(1), Container(12));
220        table.insert(Container(4), Container(1), Container(13));
221        table.insert(Container(5), Container(1), Container(14));
222        table.remove_by_row(1);
223        assert!(table.is_empty());
224    }
225
226    #[test]
227    fn inverse_table() {
228        let hs0 = HashSet::<usize>::new();
229        let mut hs1 = HashSet::<usize>::new();
230        hs1.insert(12);
231        hs1.insert(15);
232
233        let mut hs2 = HashSet::<usize>::new();
234        hs2.insert(17);
235
236        let mut table: Table<Container, Container, Container> = Table::new();
237        table.insert(Container(1), Container(2), Container(12));
238        table.insert(Container(1), Container(3), Container(14));
239        table.insert(Container(1), Container(2), Container(15));
240        table.insert(Container(4), Container(5), Container(16));
241        table.insert(Container(2), Container(5), Container(17));
242        table.insert(Container(2), Container(6), Container(17));
243
244        let inverse: InverseTable = InverseTable::rebuild_from(&table);
245        assert_eq!(inverse.row_value_keys_except.get(&(2, 6)).unwrap(), &hs0);
246        assert_eq!(inverse.column_value_keys_except.get(&(1, 3)).unwrap(), &hs1);
247        assert_eq!(inverse.row_value_keys_except.get(&(4, 5)).unwrap(), &hs2);
248        assert!(inverse.row_value_keys_except.get(&(4, 6)).is_none());
249    }
250}
guava_table/lib.rs

guava_table/
lib.rs
