rbe/
pending.rs

1use indexmap::{map::Entry, IndexMap, IndexSet};
2use std::fmt::{Debug, Display};
3use std::hash::Hash;
4
5/// Indicates a map of values `V` that depend on some references `R`
6#[derive(Clone, Default, PartialEq, Eq, Debug)]
7pub struct Pending<V, R>
8where
9    V: Hash + Eq,
10    R: Hash + Eq,
11{
12    pending_map: IndexMap<V, IndexSet<R>>,
13}
14
15impl<V, R> Pending<V, R>
16where
17    V: Hash + Eq + Clone + Debug,
18    R: Hash + Eq + Clone + Debug,
19{
20    pub fn new() -> Pending<V, R> {
21        Pending {
22            pending_map: IndexMap::new(),
23        }
24    }
25
26    pub fn empty() -> Pending<V, R> {
27        Pending::new()
28    }
29
30    pub fn from_pair(v: V, r: R) -> Pending<V, R> {
31        let mut pending_map = IndexMap::new();
32        pending_map.insert(v, IndexSet::from([r]));
33        Pending { pending_map }
34    }
35
36    pub fn get(&self, k: &V) -> Option<&IndexSet<R>> {
37        self.pending_map.get(k)
38    }
39
40    pub fn len(&self) -> usize {
41        let mut counter = 0;
42        for key in self.pending_map.keys() {
43            counter += self.pending_map.get(key).unwrap().len();
44        }
45        counter
46    }
47
48    pub fn contains(&self, v: &V, r: &R) -> bool {
49        if let Some(rs) = self.pending_map.get(v) {
50            rs.contains(r)
51        } else {
52            false
53        }
54    }
55
56    pub fn merge(&mut self, other: Pending<V, R>) {
57        for (k, vs) in other.pending_map.into_iter() {
58            match self.pending_map.entry(k) {
59                Entry::Occupied(mut v) => v.get_mut().extend(vs),
60                Entry::Vacant(vacant) => {
61                    vacant.insert(vs);
62                }
63            }
64        }
65    }
66
67    pub fn insert(&mut self, v: V, r: R) {
68        match self.pending_map.entry(v) {
69            Entry::Occupied(mut v) => {
70                v.get_mut().insert(r);
71            }
72            Entry::Vacant(vacant) => {
73                vacant.insert(IndexSet::from([r]));
74            }
75        }
76    }
77
78    pub fn insert_values<T: IntoIterator<Item = R>>(&mut self, v: V, iter: T) {
79        match self.pending_map.entry(v) {
80            Entry::Occupied(mut v) => {
81                v.get_mut().extend(iter);
82            }
83            Entry::Vacant(vacant) => {
84                vacant.insert(IndexSet::from_iter(iter));
85            }
86        }
87    }
88
89    pub fn insert_from_iter<T: IntoIterator<Item = (V, R)>>(&mut self, iter: T) {
90        for (v, r) in iter {
91            self.insert(v, r)
92        }
93    }
94
95    pub fn is_empty(&self) -> bool {
96        self.pending_map.is_empty()
97    }
98
99    pub fn from<T: IntoIterator<Item = (V, RS)>, RS: IntoIterator<Item = R>>(
100        iter: T,
101    ) -> Pending<V, R> {
102        let mut result = Pending::new();
103        for (v, rs) in iter {
104            result.insert_values(v, rs)
105        }
106        result
107    }
108
109    pub fn iter(&self) -> PendingIterator<'_, V, R> {
110        PendingIterator {
111            pending_iter: self.pending_map.iter(),
112            current_state: None,
113        }
114    }
115
116    fn select_v(&self) -> Option<V> {
117        self.pending_map.first().map(|(v, _)| v.clone())
118    }
119
120    pub fn pop(&mut self) -> Option<(V, R)> {
121        match self.select_v() {
122            Some(v) => match self.pending_map.get_mut(&v) {
123                Some(rs) => match rs.pop() {
124                    Some(r) => {
125                        if rs.is_empty() {
126                            self.pending_map.swap_remove(&v);
127                        }
128                        Some((v.clone(), r.clone()))
129                    }
130                    None => {
131                        panic!("Internal error in penidng map: Cannot pop from value {v:?}");
132                    }
133                },
134                None => {
135                    panic!("Internal error in pending map: Key {v:?} without value?");
136                }
137            },
138            None => None,
139        }
140    }
141}
142
143pub struct PendingIterator<'a, V, R>
144where
145    V: Hash + Eq,
146{
147    pending_iter: indexmap::map::Iter<'a, V, IndexSet<R>>,
148    current_state: Option<(&'a V, indexmap::set::Iter<'a, R>)>,
149}
150
151impl<'a, V, R> Iterator for PendingIterator<'a, V, R>
152where
153    V: Hash + Eq,
154{
155    type Item = (&'a V, &'a R);
156
157    fn next(&mut self) -> Option<Self::Item> {
158        match &mut self.current_state {
159            None => match self.pending_iter.next() {
160                None => None,
161                Some((v, rs)) => {
162                    self.current_state = Some((v, rs.into_iter()));
163                    self.next()
164                }
165            },
166            Some((v, it)) => match it.next() {
167                None => {
168                    self.current_state = None;
169                    match self.pending_iter.next() {
170                        None => None,
171                        Some((v, rs)) => {
172                            self.current_state = Some((v, rs.iter()));
173                            self.next()
174                        }
175                    }
176                }
177                Some(r) => Some((v, r)),
178            },
179        }
180    }
181}
182
183impl<V, R> Display for Pending<V, R>
184where
185    V: Hash + Eq + Debug + Display,
186    R: Hash + Eq + Debug + Display,
187{
188    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189        write!(f, "Pending {{")?;
190        for (v, r) in self.pending_map.iter() {
191            write!(f, "{}@", v)?;
192            for r in r.iter() {
193                write!(f, "{} ", r)?;
194            }
195            write!(f, "| ")?;
196        }
197        write!(f, "}}")
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use crate::Pending;
204    use indexmap::IndexSet;
205
206    #[test]
207    fn test_from() {
208        let pending = Pending::from(vec![('a', vec![1, 2]), ('b', vec![3])]);
209        let expected = IndexSet::from_iter([1, 2]);
210        assert_eq!(pending.get(&'a'), Some(&expected));
211    }
212
213    #[test]
214    fn test_pending_merge() {
215        let mut pending1 = Pending::from(vec![('a', vec![1, 2]), ('b', vec![3])]);
216        let pending2 = Pending::from(vec![('a', vec![3, 4]), ('c', vec![4])]);
217        let expected = Pending::from(vec![
218            ('a', vec![1, 2, 3, 4]),
219            ('c', vec![4]),
220            ('b', vec![3]),
221        ]);
222
223        pending1.merge(pending2);
224        assert_eq!(pending1, expected);
225    }
226
227    #[test]
228    fn test_pending_iter() {
229        let pending = Pending::from(vec![('a', vec![1, 2]), ('b', vec![3])]);
230        let hash_set: IndexSet<(&char, &i32)> = pending.iter().collect();
231        let expected = IndexSet::from([(&'a', &1), (&'b', &3), (&'a', &2)]);
232        assert_eq!(hash_set, expected);
233    }
234
235    #[test]
236    fn test_pop() {
237        let mut pending = Pending::from(vec![('a', vec![1, 2]), ('b', vec![3])]);
238        let (v1, r1) = pending.pop().unwrap();
239        let (v2, r2) = pending.pop().unwrap();
240        let (v3, r3) = pending.pop().unwrap();
241        let final_pop = pending.pop();
242        assert_eq!(final_pop, None);
243        let mut new_pending = Pending::new();
244        new_pending.insert(v1, r1);
245        new_pending.insert(v2, r2);
246        new_pending.insert(v3, r3);
247        let expected = Pending::from(vec![('a', vec![1, 2]), ('b', vec![3])]);
248        assert_eq!(new_pending, expected);
249    }
250}
rbe/pending.rs

rbe/
pending.rs
