ordered_map/
lib.rs

1#[cfg(test)]
2extern crate quickcheck;
3#[cfg(test)]
4#[macro_use(quickcheck)]
5extern crate quickcheck_macros;
6
7use std::collections::HashMap;
8use std::fmt;
9use std::hash::Hash;
10use std::iter::DoubleEndedIterator;
11use std::ops::Index;
12use std::vec::Vec;
13
14type ExtractComparable<V, C> = fn(&V) -> C;
15
16/// An `OrderedMap` is like a `std::collections::HashMap`,
17/// but it is sorted according to the value in descending order.
18/// It doesn't require the value of the map, `V`, to be comparable,
19/// the comparison of the value is done on `C`,
20/// which is the return value of `extract_comparable(&V)`.
21#[derive(Clone)]
22pub struct OrderedMap<K, V, C> {
23    map: HashMap<K, V>,
24
25    descending_pairs: Vec<(K, C)>,
26
27    extract_comparable: ExtractComparable<V, C>,
28}
29
30impl<K: fmt::Debug, V: fmt::Debug, C: fmt::Debug> fmt::Debug for OrderedMap<K, V, C> {
31    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32        f.debug_struct("OrderedMap")
33            .field("map", &self.map)
34            .field("descending_pairs", &self.descending_pairs)
35            .finish()
36    }
37}
38
39pub struct DescendingKeys<'a, K: 'a, C: 'a> {
40    inner: std::slice::Iter<'a, (K, C)>,
41}
42
43impl<'a, K: 'a, C: 'a> Iterator for DescendingKeys<'a, K, C> {
44    type Item = &'a K;
45
46    fn next(&mut self) -> Option<Self::Item> {
47        match self.inner.next() {
48            None => None,
49            Some((k, _)) => Some(k),
50        }
51    }
52}
53
54impl<'a, K: 'a, C: 'a> DoubleEndedIterator for DescendingKeys<'a, K, C> {
55    fn next_back(&mut self) -> Option<Self::Item> {
56        match self.inner.next_back() {
57            None => None,
58            Some((k, _)) => Some(k),
59        }
60    }
61}
62
63pub struct DescendingValues<'a, K, V, C> {
64    map: &'a HashMap<K, V>,
65    keys: DescendingKeys<'a, K, C>,
66}
67
68impl<'a, K, V, C> Iterator for DescendingValues<'a, K, V, C>
69where
70    K: Eq + Hash,
71{
72    type Item = &'a V;
73
74    fn next(&mut self) -> Option<Self::Item> {
75        match self.keys.next() {
76            None => None,
77            Some(k) => Some(self.map.index(k)),
78        }
79    }
80}
81
82impl<'a, K, V, C> DoubleEndedIterator for DescendingValues<'a, K, V, C>
83where
84    K: Eq + Hash,
85{
86    fn next_back(&mut self) -> Option<Self::Item> {
87        match self.keys.next_back() {
88            None => None,
89            Some(k) => Some(self.map.index(k)),
90        }
91    }
92}
93
94pub struct DescendingItems<'a, K, V, C> {
95    map: &'a HashMap<K, V>,
96    keys: DescendingKeys<'a, K, C>,
97}
98
99impl<'a, K, V, C> Iterator for DescendingItems<'a, K, V, C>
100where
101    K: Eq + Hash,
102{
103    type Item = (&'a K, &'a V);
104
105    fn next(&mut self) -> Option<Self::Item> {
106        match self.keys.next() {
107            None => None,
108            Some(k) => Some((k, self.map.index(k))),
109        }
110    }
111}
112
113impl<'a, K, V, C> DoubleEndedIterator for DescendingItems<'a, K, V, C>
114where
115    K: Eq + Hash,
116{
117    fn next_back(&mut self) -> Option<Self::Item> {
118        match self.keys.next_back() {
119            None => None,
120            Some(k) => Some((k, self.map.index(k))),
121        }
122    }
123}
124
125impl<'a, K: 'a, V: 'a, C: 'a> OrderedMap<K, V, C>
126where
127    K: Eq + Hash + Copy,
128    C: PartialOrd,
129{
130    /// The function `extract_comparable` is used to convert the value of type `&V`
131    /// to something comparable of type `C`
132    pub fn new(extract_comparable: ExtractComparable<V, C>) -> Self {
133        OrderedMap {
134            map: HashMap::new(),
135            descending_pairs: vec![],
136            extract_comparable,
137        }
138    }
139
140    pub fn len(&self) -> usize {
141        self.map.len()
142    }
143
144    /// Keys of this map in descending order
145    pub fn descending_keys(&'a self) -> DescendingKeys<'a, K, C> {
146        DescendingKeys {
147            inner: self.descending_pairs.iter(),
148        }
149    }
150
151    /// Values of this map in descending order
152    pub fn descending_values(&'a self) -> DescendingValues<'a, K, V, C> {
153        DescendingValues {
154            map: &self.map,
155            keys: self.descending_keys(),
156        }
157    }
158
159    /// (K, V) pairs of this map in descending order
160    pub fn descending_items(&'a self) -> DescendingItems<'a, K, V, C> {
161        DescendingItems {
162            map: &self.map,
163            keys: self.descending_keys(),
164        }
165    }
166
167    fn insert_into_pairs(&mut self, k: K, c: C) {
168        let mut insert_index = None;
169        for (i, (_ek, ec)) in self.descending_pairs.iter().enumerate() {
170            if &c >= ec {
171                insert_index = Some(i);
172                break;
173            }
174        }
175        let idx = match insert_index {
176            None => self.descending_pairs.len(),
177            Some(i) => i,
178        };
179        self.descending_pairs.insert(idx, (k, c));
180    }
181
182    /// Insert a new key-value pair to the map,
183    /// the old value is returned as `Option<V>`
184    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
185        let new_c = (self.extract_comparable)(&v);
186        match self.map.insert(k, v) {
187            None => {
188                self.insert_into_pairs(k, new_c);
189                None
190            }
191            Some(v) => {
192                remove_from_pairs(&mut self.descending_pairs, &k);
193                self.insert_into_pairs(k, new_c);
194                Some(v)
195            }
196        }
197    }
198
199    /// Remove a key-value pair from the map
200    pub fn remove(&mut self, k: &K) -> Option<V> {
201        match self.map.remove(k) {
202            None => None,
203            Some(v) => {
204                remove_from_pairs(&mut self.descending_pairs, k);
205                Some(v)
206            }
207        }
208    }
209}
210
211fn remove_from_pairs<K, C>(pairs: &mut Vec<(K, C)>, k: &K) -> bool
212where
213    K: Eq,
214{
215    let mut removed = false;
216    for i in 0..pairs.len() {
217        if pairs[i].0 == *k {
218            pairs.remove(i);
219            removed = true;
220            break;
221        }
222    }
223    removed
224}
225
226#[cfg(test)]
227mod tests {
228    use std::collections::HashMap;
229
230    use super::OrderedMap;
231
232    fn to_comparable(t: &(f32, f64)) -> f32 {
233        t.0
234    }
235
236    #[quickcheck]
237    fn descending_order(kvs: Vec<(i32, (f32, f64))>) -> bool {
238        let empty = kvs.is_empty();
239
240        let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
241        let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
242
243        let mut map = OrderedMap::new(to_comparable);
244
245        for (k, v) in ks.iter().zip(vs.iter()) {
246            map.insert(k.clone(), v.clone());
247        }
248
249        let mut tuples: Vec<(i32, f32)> = ks
250            .iter()
251            .zip(vs.iter())
252            .map(|(k, v)| (k.clone(), to_comparable(v)))
253            .collect();
254        let mut count = HashMap::new();
255        for k in ks.iter() {
256            count.insert(k, 0);
257        }
258        for k in ks.iter() {
259            count.insert(k, count.get(k).unwrap() + 1);
260        }
261        let mut i = 0;
262        for _ in 0..tuples.len() {
263            if i < tuples.len() {
264                let (k, _c) = tuples[i];
265                let cnt = count.get_mut(&k).unwrap();
266                if *cnt > 1 {
267                    tuples.remove(i);
268                    *cnt = *cnt - 1;
269                } else {
270                    i = i + 1;
271                }
272            } else {
273                break;
274            }
275        }
276        tuples.sort_by(|(_, c1), (_, c2)| c1.partial_cmp(c2).unwrap());
277        tuples.reverse();
278
279        let truth_keys: Vec<i32> = tuples.iter().map(|(k, _)| k.clone()).collect();
280
281        let have_keys: Vec<i32> = map.descending_keys().map(|x| x.clone()).collect();
282
283        let property = truth_keys == have_keys;
284
285        let safe1 = empty || !truth_keys.is_empty();
286
287        property && safe1
288    }
289
290    #[quickcheck]
291    fn same_length(kvs: Vec<(i32, (f32, f64))>) -> bool {
292        let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
293        let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
294
295        let mut map = OrderedMap::new(to_comparable);
296
297        for (k, v) in ks.iter().zip(vs.iter()) {
298            map.insert(k.clone(), v.clone());
299        }
300
301        map.map.len() == map.descending_keys().collect::<Vec<_>>().len()
302    }
303
304    #[quickcheck]
305    fn same_keys(kvs: Vec<(i32, (f32, f64))>) -> bool {
306        let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
307        let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
308
309        let mut map = OrderedMap::new(to_comparable);
310
311        for (k, v) in ks.iter().zip(vs.iter()) {
312            map.insert(k.clone(), v.clone());
313        }
314
315        let mut a = map.descending_keys().map(|x| x.clone()).collect::<Vec<_>>();
316        a.sort();
317
318        let mut b = map.map.keys().map(|x| x.clone()).collect::<Vec<_>>();
319        b.sort();
320
321        let mut ks = ks;
322        ks.sort();
323        ks.dedup();
324
325        a == b && b == ks
326    }
327
328    #[quickcheck]
329    fn insert_then_remove_all_is_empty(kvs: Vec<(i32, (f32, f64))>, other_keys: Vec<i32>) -> bool {
330        let ks: Vec<i32> = kvs.iter().map(|(k, _)| k.clone()).collect();
331        let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
332
333        let mut map = OrderedMap::new(to_comparable);
334
335        for (k, v) in ks.iter().zip(vs.iter()) {
336            map.insert(k.clone(), v.clone());
337        }
338
339        for k in ks.iter() {
340            map.remove(k);
341        }
342
343        let a = 0 == map.map.len() && 0 == map.descending_keys().collect::<Vec<_>>().len();
344
345        for k in other_keys.iter() {
346            map.remove(k);
347        }
348
349        let b = 0 == map.map.len() && 0 == map.descending_keys().collect::<Vec<_>>().len();
350
351        a && b
352    }
353
354    #[quickcheck]
355    fn insert_then_remove_is_identity(kvs: Vec<(u32, (f32, f64))>, new_v: (f32, f64)) -> bool {
356        let ks: Vec<u32> = kvs.iter().map(|(k, _)| k.clone()).collect();
357        let vs: Vec<(f32, f64)> = kvs.iter().map(|(_, v)| v.clone()).collect();
358
359        let mut map = OrderedMap::new(to_comparable);
360
361        for (k, v) in ks.iter().zip(vs.iter()) {
362            map.insert(k.clone(), v.clone());
363        }
364
365        let old_map = map.map.clone();
366        let old_keys = map
367            .descending_keys()
368            .map(|k| k.clone())
369            .collect::<Vec<u32>>();
370
371        // create a unique key
372        let k: u32 = ks.iter().sum();
373        let k: u32 = k + 1;
374        map.insert(k.clone(), new_v);
375        map.remove(&k);
376
377        let new_map = map.map.clone();
378        let new_keys = map.descending_keys().map(|k| k.clone()).collect::<Vec<_>>();
379
380        old_map == new_map && old_keys == new_keys
381    }
382}
ordered_map/lib.rs

ordered_map/
lib.rs
