ds_ext/
map.rs

1//! A hash map ordered by key using a linked hash set
2
3use std::borrow::Borrow;
4use std::cmp::Ordering;
5use std::collections::{hash_map, HashMap as Inner};
6use std::fmt;
7use std::hash::Hash;
8use std::sync::Arc;
9
10use get_size::GetSize;
11use get_size_derive::*;
12
13use super::set::OrdHashSet;
14
15/// An iterator to drain the contents of an [`OrdHashMap`]
16pub struct Drain<'a, K, V> {
17    inner: &'a mut Inner<Arc<K>, V>,
18    order: super::set::Drain<'a, Arc<K>>,
19}
20
21impl<'a, K: Eq + Hash + fmt::Debug, V> Drain<'a, K, V> {
22    fn next_entry(&mut self, key: Arc<K>) -> Option<(K, V)> {
23        let value = self.inner.remove(&*key).expect("value");
24        let key = Arc::try_unwrap(key).expect("key");
25        Some((key, value))
26    }
27}
28
29impl<'a, K: Eq + Hash + fmt::Debug, V> Iterator for Drain<'a, K, V> {
30    type Item = (K, V);
31
32    fn next(&mut self) -> Option<Self::Item> {
33        let key = self.order.next()?;
34        self.next_entry(key)
35    }
36
37    fn size_hint(&self) -> (usize, Option<usize>) {
38        self.order.size_hint()
39    }
40}
41
42impl<'a, K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for Drain<'a, K, V> {
43    fn next_back(&mut self) -> Option<Self::Item> {
44        let key = self.order.next_back()?;
45        self.next_entry(key)
46    }
47}
48
49/// An iterator to drain the contents of an [`OrdHashMap`] conditionally
50pub struct DrainWhile<'a, K, V, Cond> {
51    inner: &'a mut Inner<Arc<K>, V>,
52    order: &'a mut OrdHashSet<Arc<K>>,
53    cond: Cond,
54}
55
56impl<'a, K, V, Cond> Iterator for DrainWhile<'a, K, V, Cond>
57where
58    K: Eq + Hash + Ord + fmt::Debug,
59    Cond: Fn((&K, &V)) -> bool,
60{
61    type Item = (K, V);
62
63    fn next(&mut self) -> Option<Self::Item> {
64        let should_drain = {
65            let key = self.order.first()?;
66            let value = self.inner.get(&**key).expect("value");
67            (self.cond)((&**key, value))
68        };
69
70        if should_drain {
71            let key = self.order.pop_first().expect("key");
72            let value = self.inner.remove(&*key).expect("value");
73            let key = Arc::try_unwrap(key).expect("key");
74            Some((key, value))
75        } else {
76            None
77        }
78    }
79
80    fn size_hint(&self) -> (usize, Option<usize>) {
81        (0, Some(self.inner.len()))
82    }
83}
84
85/// An iterator over the contents of an [`OrdHashMap`]
86pub struct IntoIter<K, V> {
87    inner: Inner<Arc<K>, V>,
88    order: super::set::IntoIter<Arc<K>>,
89}
90
91impl<K: Eq + Hash + fmt::Debug, V> IntoIter<K, V> {
92    fn next_entry(&mut self, key: Arc<K>) -> Option<(K, V)> {
93        let value = self.inner.remove(&*key).expect("value");
94        let key = Arc::try_unwrap(key).expect("key");
95        Some((key, value))
96    }
97}
98
99impl<K: Eq + Hash + fmt::Debug, V> Iterator for IntoIter<K, V> {
100    type Item = (K, V);
101
102    fn next(&mut self) -> Option<Self::Item> {
103        let key = self.order.next()?;
104        self.next_entry(key)
105    }
106
107    fn size_hint(&self) -> (usize, Option<usize>) {
108        self.order.size_hint()
109    }
110}
111
112impl<K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for IntoIter<K, V> {
113    fn next_back(&mut self) -> Option<Self::Item> {
114        let key = self.order.next_back()?;
115        self.next_entry(key)
116    }
117}
118
119/// An iterator over the entries in an [`OrdHashMap`]
120pub struct Iter<'a, K, V> {
121    inner: &'a Inner<Arc<K>, V>,
122    order: super::set::Iter<'a, Arc<K>>,
123}
124
125impl<'a, K: Eq + Hash + fmt::Debug, V> Iterator for Iter<'a, K, V> {
126    type Item = (&'a K, &'a V);
127
128    fn next(&mut self) -> Option<Self::Item> {
129        let key = &**self.order.next()?;
130        let (key, value) = self.inner.get_key_value(key).expect("entry");
131        Some((&**key, value))
132    }
133
134    fn size_hint(&self) -> (usize, Option<usize>) {
135        self.order.size_hint()
136    }
137}
138
139impl<'a, K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for Iter<'a, K, V> {
140    fn next_back(&mut self) -> Option<Self::Item> {
141        let key = self.order.next_back()?;
142        let (key, value) = self.inner.get_key_value(&**key).expect("entry");
143        Some((&**key, value))
144    }
145}
146
147/// An iterator over the keys in an [`OrdHashMap`]
148pub struct Keys<'a, K, V> {
149    inner: &'a Inner<Arc<K>, V>,
150    order: super::set::Iter<'a, Arc<K>>,
151}
152
153impl<'a, K: Eq + Hash + fmt::Debug, V> Iterator for Keys<'a, K, V> {
154    type Item = &'a K;
155
156    fn next(&mut self) -> Option<Self::Item> {
157        let key = self.order.next()?;
158        let (key, _) = self.inner.get_key_value(&**key).expect("entry");
159        Some(&**key)
160    }
161
162    fn size_hint(&self) -> (usize, Option<usize>) {
163        self.order.size_hint()
164    }
165}
166
167impl<'a, K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for Keys<'a, K, V> {
168    fn next_back(&mut self) -> Option<Self::Item> {
169        let key = self.order.next_back()?;
170        let (key, _) = self.inner.get_key_value(&**key).expect("entry");
171        Some(&**key)
172    }
173}
174
175/// An owned iterator over the values in an [`OrdHashMap`]
176pub struct IntoValues<K, V> {
177    inner: Inner<Arc<K>, V>,
178    order: super::set::IntoIter<Arc<K>>,
179}
180
181impl<K: Eq + Hash + fmt::Debug, V> Iterator for IntoValues<K, V> {
182    type Item = V;
183
184    fn next(&mut self) -> Option<Self::Item> {
185        let key = self.order.next()?;
186        self.inner.remove(&*key)
187    }
188
189    fn size_hint(&self) -> (usize, Option<usize>) {
190        self.order.size_hint()
191    }
192}
193
194impl<K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for IntoValues<K, V> {
195    fn next_back(&mut self) -> Option<Self::Item> {
196        let key = self.order.next_back()?;
197        self.inner.remove(&*key)
198    }
199}
200
201/// An iterator over the values in an [`OrdHashMap`]
202pub struct Values<'a, K, V> {
203    inner: &'a Inner<Arc<K>, V>,
204    order: super::set::Iter<'a, Arc<K>>,
205}
206
207impl<'a, K: Eq + Hash + fmt::Debug, V> Iterator for Values<'a, K, V> {
208    type Item = &'a V;
209
210    fn next(&mut self) -> Option<Self::Item> {
211        let key = self.order.next()?;
212        self.inner.get(&**key)
213    }
214
215    fn size_hint(&self) -> (usize, Option<usize>) {
216        self.order.size_hint()
217    }
218}
219
220impl<'a, K: Eq + Hash + fmt::Debug, V> DoubleEndedIterator for Values<'a, K, V> {
221    fn next_back(&mut self) -> Option<Self::Item> {
222        let key = self.order.next_back()?;
223        self.inner.get(&**key)
224    }
225}
226
227/// An occupied entry in an [`OrdHashMap`]
228pub type OccupiedEntry<'a, K, V> = hash_map::OccupiedEntry<'a, Arc<K>, V>;
229
230/// A vacant entry in an [`OrdHashMap`]
231pub struct VacantEntry<'a, K, V> {
232    order: &'a mut OrdHashSet<Arc<K>>,
233    entry: hash_map::VacantEntry<'a, Arc<K>, V>,
234}
235
236impl<'a, K, V> VacantEntry<'a, K, V>
237where
238    K: Eq + Hash + Ord,
239{
240    /// Create a new entry with the given `value`
241    pub fn insert(self, value: V) -> &'a mut V {
242        self.order.insert(self.entry.key().clone());
243        self.entry.insert(value)
244    }
245}
246
247/// An entry in an [`OrdHashMap`]
248pub enum Entry<'a, K, V> {
249    Occupied(hash_map::OccupiedEntry<'a, Arc<K>, V>),
250    Vacant(VacantEntry<'a, K, V>),
251}
252
253/// A `HashMap` ordered by key using a [`OrdHashSet`]
254#[derive(GetSize)]
255pub struct OrdHashMap<K, V> {
256    inner: Inner<Arc<K>, V>,
257    order: OrdHashSet<Arc<K>>,
258}
259
260impl<K: Clone + Eq + Hash + Ord + fmt::Debug, V: Clone> Clone for OrdHashMap<K, V> {
261    fn clone(&self) -> Self {
262        let mut inner = Inner::with_capacity(self.inner.capacity());
263        let mut order = OrdHashSet::<Arc<K>>::with_capacity(inner.capacity());
264
265        for key in &self.order {
266            let key = Arc::new(K::clone(&**key));
267            let value = self.inner.get(&key).cloned().expect("value");
268            inner.insert(key.clone(), value);
269            order.insert(key);
270        }
271
272        Self { inner, order }
273    }
274}
275impl<K, V> OrdHashMap<K, V> {
276    /// Construct a new [`OrdHashMap`].
277    pub fn new() -> Self {
278        Self {
279            inner: Inner::new(),
280            order: OrdHashSet::new(),
281        }
282    }
283    /// Construct a new [`OrdHashMap`] with the given `capacity`.
284    pub fn with_capacity(capacity: usize) -> Self {
285        Self {
286            inner: Inner::with_capacity(capacity),
287            order: OrdHashSet::with_capacity(capacity),
288        }
289    }
290
291    /// Return the size of this [`OrdHashMap`].
292    pub fn len(&self) -> usize {
293        self.inner.len()
294    }
295}
296
297impl<K, V> Default for OrdHashMap<K, V> {
298    fn default() -> Self {
299        Self::new()
300    }
301}
302
303impl<K: Eq + Hash + Ord, V> OrdHashMap<K, V> {
304    /// Bisect this map to match a key using the provided comparison, and return its value (if any).
305    ///
306    /// The first key for which the comparison returns `Some(Ordering::Equal)` will be returned.
307    /// This method assumes that any partially-ordered keys (where `cmp(key).is_none()`) lie at the
308    /// beginning and/or end of the distribution.
309    pub fn bisect<Cmp>(&self, cmp: Cmp) -> Option<&V>
310    where
311        Cmp: Fn(&K) -> Option<Ordering> + Copy,
312    {
313        self.order
314            .bisect(|key| cmp(key))
315            .map(|key| self.get(&**key).expect("value"))
316    }
317
318    /// Remove all entries from this [`OrdHashMap`].
319    pub fn clear(&mut self) {
320        self.inner.clear();
321        self.order.clear();
322    }
323
324    /// Return `true` if there is an entry for the given `key` in this [`OrdHashMap`].
325    pub fn contains_key<Q>(&self, key: &Q) -> bool
326    where
327        Arc<K>: Borrow<Q>,
328        Q: Eq + Hash + ?Sized,
329    {
330        self.inner.contains_key(key)
331    }
332
333    /// Drain all entries from this [`OrdHashMap`].
334    pub fn drain(&mut self) -> Drain<'_, K, V> {
335        Drain {
336            inner: &mut self.inner,
337            order: self.order.drain(),
338        }
339    }
340
341    /// Drain all entries from this [`OrdHashMap`].
342    pub fn drain_while<Cond>(&mut self, cond: Cond) -> DrainWhile<'_, K, V, Cond>
343    where
344        Cond: Fn((&K, &V)) -> bool,
345    {
346        DrainWhile {
347            inner: &mut self.inner,
348            order: &mut self.order,
349            cond,
350        }
351    }
352
353    /// Return a mutable [`Entry`] in this [`OrdHashMap`].
354    pub fn entry<Q: Into<Arc<K>>>(&mut self, key: Q) -> Entry<'_, K, V> {
355        match self.inner.entry(key.into()) {
356            hash_map::Entry::Occupied(entry) => Entry::Occupied(entry),
357            hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
358                entry,
359                order: &mut self.order,
360            }),
361        }
362    }
363
364    /// Consume `iter` and insert all its elements into this [`OrdHashMap`].
365    pub fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
366        for (key, value) in iter {
367            self.insert(key, value);
368        }
369    }
370
371    /// Borrow the first value in this [`OrdHashMap`].
372    pub fn first(&self) -> Option<&V> {
373        let key = self.order.first()?;
374        self.inner.get(&**key)
375    }
376
377    /// Borrow the first value in this [`OrdHashMap`] mutably.
378    pub fn first_mut(&mut self) -> Option<&mut V> {
379        let key = self.order.first()?;
380        self.inner.get_mut(&**key)
381    }
382
383    /// Borrow the value at the given `key`, if present.
384    pub fn get<Q>(&self, key: &Q) -> Option<&V>
385    where
386        Arc<K>: Borrow<Q>,
387        Q: Eq + Hash + ?Sized,
388    {
389        self.inner.get(key)
390    }
391
392    /// Borrow the entry at the given `key`, if present.
393    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
394    where
395        Arc<K>: Borrow<Q>,
396        Q: Eq + Hash + ?Sized,
397    {
398        self.inner
399            .get_key_value(key)
400            .map(|(key, value)| (&**key, value))
401    }
402
403    /// Borrow the value at the given `key` mutably, if present.
404    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
405    where
406        Arc<K>: Borrow<Q>,
407        Q: Eq + Hash + ?Sized,
408    {
409        self.inner.get_mut(key)
410    }
411
412    /// Insert a new `value` at `key` and return the previous value, if any.
413    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
414        let key = Arc::new(key);
415        self.order.insert(key.clone());
416        self.inner.insert(key, value)
417    }
418
419    /// Construct an iterator over the entries in this [`OrdHashMap`].
420    pub fn iter(&self) -> Iter<'_, K, V> {
421        Iter {
422            inner: &self.inner,
423            order: self.order.iter(),
424        }
425    }
426
427    /// Return `true` if this [`OrdHashMap`] is empty.
428    pub fn is_empty(&self) -> bool {
429        self.inner.is_empty()
430    }
431
432    /// Construct an iterator over keys of this [`OrdHashMap`].
433    pub fn keys(&self) -> Keys<'_, K, V> {
434        Keys {
435            inner: &self.inner,
436            order: self.order.iter(),
437        }
438    }
439
440    /// Borrow the last value in this [`OrdHashMap`].
441    pub fn last(&self) -> Option<&V> {
442        let key = self.order.last()?;
443        self.inner.get(&**key)
444    }
445
446    /// Borrow the last value in this [`OrdHashMap`] mutably.
447    pub fn last_mut(&mut self) -> Option<&mut V> {
448        let key = self.order.last()?;
449        self.inner.get_mut(&**key)
450    }
451
452    /// Remove and return the first value in this [`OrdHashMap`].
453    pub fn pop_first(&mut self) -> Option<V>
454    where
455        K: fmt::Debug,
456    {
457        let key = self.order.pop_first()?;
458        self.inner.remove(&*key)
459    }
460
461    /// Remove and return the last value in this [`OrdHashMap`].
462    pub fn pop_last(&mut self) -> Option<V>
463    where
464        K: fmt::Debug,
465    {
466        let key = self.order.pop_last()?;
467        self.inner.remove(&*key)
468    }
469
470    /// Remove an entry from this [`OrdHashMap`] and return its value, if present.
471    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
472    where
473        Arc<K>: Borrow<Q>,
474        Q: Hash + Eq + ?Sized,
475    {
476        let (key, value) = self.inner.remove_entry(key)?;
477        assert!(self.order.remove(&key));
478        Some(value)
479    }
480
481    /// Return `true` if the first elements in this [`OrdHashMap`] equal those in the given `iter`.
482    pub fn starts_with<'a, I: IntoIterator<Item = (&'a K, &'a V)>>(&self, other: I) -> bool
483    where
484        K: fmt::Debug + 'a,
485        V: PartialEq + 'a,
486    {
487        let mut this = self.iter();
488        let that = other.into_iter();
489
490        for item in that {
491            if this.next() != Some(item) {
492                return false;
493            }
494        }
495
496        true
497    }
498
499    /// Construct an owned iterator over the values in this [`OrdHashMap`].
500    pub fn into_values(self) -> IntoValues<K, V>
501    where
502        K: fmt::Debug,
503    {
504        IntoValues {
505            inner: self.inner,
506            order: self.order.into_iter(),
507        }
508    }
509
510    /// Construct an iterator over the values in this [`OrdHashMap`].
511    pub fn values(&self) -> Values<'_, K, V> {
512        Values {
513            inner: &self.inner,
514            order: self.order.iter(),
515        }
516    }
517}
518
519impl<K: Eq + Hash + Ord + fmt::Debug, V> OrdHashMap<K, V> {
520    /// Bisect this map to match and remove an entry using the provided comparison.
521    ///
522    /// The first key for which the comparison returns `Some(Ordering::Equal)` will be returned.
523    /// This method assumes that any partially-ordered keys (where `cmp(key).is_none()`) lie at the
524    /// beginning and/or end of the distribution.
525    pub fn bisect_and_remove<Cmp>(&mut self, cmp: Cmp) -> Option<(K, V)>
526    where
527        Cmp: Fn(&K) -> Option<Ordering> + Copy,
528    {
529        let key = self.order.bisect_and_remove(|key| cmp(key))?;
530        let value = self.inner.remove(&*key).expect("value");
531        let key = Arc::try_unwrap(key).expect("key");
532        Some((key, value))
533    }
534
535    /// Remove and return the first entry in this [`OrdHashMap`].
536    pub fn pop_first_entry(&mut self) -> Option<(K, V)> {
537        let key = self.order.pop_first()?;
538        let (key, value) = self.inner.remove_entry(&*key).expect("entry");
539        let key = Arc::try_unwrap(key).expect("key");
540        Some((key, value))
541    }
542
543    /// Remove and return the last entry in this [`OrdHashMap`].
544    pub fn pop_last_entry(&mut self) -> Option<(K, V)> {
545        let key = self.order.pop_last()?;
546        let (key, value) = self.inner.remove_entry(&*key).expect("entry");
547        let key = Arc::try_unwrap(key).expect("key");
548        Some((key, value))
549    }
550
551    /// Remove and return an entry from this [`OrdHashMap`], if present.
552    pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
553    where
554        Arc<K>: Borrow<Q>,
555        Q: Hash + Eq + ?Sized,
556    {
557        let (key, value) = self.inner.remove_entry(key)?;
558        assert!(self.order.remove(&key));
559        let key = Arc::try_unwrap(key).expect("key");
560        Some((key, value))
561    }
562}
563
564impl<K: Eq + Hash + Ord + fmt::Debug, V: PartialEq> PartialEq<Self> for OrdHashMap<K, V> {
565    fn eq(&self, other: &Self) -> bool {
566        if self.len() != other.len() {
567            return false;
568        }
569
570        self.iter()
571            .zip(other)
572            .all(|((lk, lv), (rk, rv))| lk == rk && lv == rv)
573    }
574}
575
576impl<K: Eq + Hash + Ord + fmt::Debug, V: Eq> Eq for OrdHashMap<K, V> {}
577
578impl<K: Eq + Hash + Ord + fmt::Debug, V> FromIterator<(K, V)> for OrdHashMap<K, V> {
579    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
580        let iter = iter.into_iter();
581        let mut map = match iter.size_hint() {
582            (_, Some(max)) => Self::with_capacity(max),
583            (min, None) if min > 0 => Self::with_capacity(min),
584            _ => Self::new(),
585        };
586
587        map.extend(iter);
588        map
589    }
590}
591
592impl<K: Eq + Hash + fmt::Debug, V> IntoIterator for OrdHashMap<K, V> {
593    type Item = (K, V);
594    type IntoIter = IntoIter<K, V>;
595
596    fn into_iter(self) -> Self::IntoIter {
597        IntoIter {
598            inner: self.inner,
599            order: self.order.into_iter(),
600        }
601    }
602}
603
604impl<'a, K: Ord + Eq + Hash + fmt::Debug, V> IntoIterator for &'a OrdHashMap<K, V> {
605    type Item = (&'a K, &'a V);
606    type IntoIter = Iter<'a, K, V>;
607
608    fn into_iter(self) -> Self::IntoIter {
609        self.iter()
610    }
611}
612
613impl<K: Eq + Hash + Ord + fmt::Debug, V: fmt::Debug> fmt::Debug for OrdHashMap<K, V> {
614    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
615        f.write_str("{")?;
616
617        for (key, value) in self.iter() {
618            write!(f, "{:?}: {:?}, ", key, value)?;
619        }
620
621        f.write_str("}")
622    }
623}
624
625#[cfg(test)]
626mod tests {
627    use super::*;
628
629    #[test]
630    fn test_find() {
631        let mut map = OrdHashMap::<&str, u32>::new();
632        map.insert(".tmp", 0);
633        map.insert("1", 1);
634        map.insert("2", 2);
635        map.insert("3", 3);
636        map.insert("five", 5);
637        map.insert("six", 6);
638
639        assert_eq!(
640            map.bisect(|key| key.parse().ok().map(|key: u32| 1.cmp(&key))),
641            Some(&1)
642        );
643
644        assert_eq!(
645            map.bisect(|key| key.parse().ok().map(|key: u32| 2.cmp(&key))),
646            Some(&2)
647        );
648
649        assert_eq!(
650            map.bisect(|key| key.parse().ok().map(|key: u32| 3.cmp(&key))),
651            Some(&3)
652        );
653    }
654
655    #[test]
656    fn test_drain() {
657        let mut map: OrdHashMap<u32, String> =
658            (0..10).map(|i| (i, i.to_string())).collect();
659
660        assert_eq!(
661            map.drain().collect::<Vec<_>>(),
662            (0..10)
663                .map(|i| (i, i.to_string()))
664                .collect::<Vec<_>>()
665        );
666    }
667
668    #[test]
669    fn test_drain_partial() {
670        let mut map: OrdHashMap<u32, String> =
671            (0..10).map(|i| (i, i.to_string())).collect();
672
673        assert_eq!(
674            map.drain().take_while(|(k, _v)| *k < 5).collect::<Vec<_>>(),
675            (0..5)
676                .map(|i| (i, i.to_string()))
677                .collect::<Vec<_>>()
678        );
679
680        assert_eq!(
681            map,
682            (6..10).map(|i| (i, i.to_string())).collect()
683        );
684    }
685
686    #[test]
687    fn test_drain_while() {
688        let mut map: OrdHashMap<u32, String> =
689            (0..10).map(|i| (i, i.to_string())).collect();
690
691        assert_eq!(
692            map.drain_while(|(k, _v)| *k < 5).collect::<Vec<_>>(),
693            (0..5)
694                .map(|i| (i, i.to_string()))
695                .collect::<Vec<_>>()
696        );
697
698        assert_eq!(
699            map,
700            (5..10).map(|i| (i, i.to_string())).collect()
701        );
702    }
703
704    #[test]
705    fn test_order_invariants_after_ops() {
706        let mut map: OrdHashMap<u32, String> =
707            (0..100).rev().map(|i| (i, i.to_string())).collect();
708
709        let keys: Vec<u32> = map.iter().map(|(k, _)| *k).collect();
710        assert_eq!(keys, (0..100).collect::<Vec<_>>());
711
712        for i in 0..50 {
713            assert!(map.remove(&i).is_some());
714        }
715
716        let keys: Vec<u32> = map.iter().map(|(k, _)| *k).collect();
717        assert_eq!(keys, (50..100).collect::<Vec<_>>());
718
719        let drained: Vec<_> = map.drain_while(|(k, _)| *k < 75).collect();
720        assert_eq!(drained.len(), 25);
721
722        let keys: Vec<u32> = map.iter().map(|(k, _)| *k).collect();
723        assert_eq!(keys, (75..100).collect::<Vec<_>>());
724    }
725
726    #[test]
727    fn test_duplicate_insert_and_remove_missing() {
728        let mut map = OrdHashMap::new();
729
730        assert_eq!(map.insert(1, "one".to_string()), None);
731        assert_eq!(map.insert(1, "uno".to_string()), Some("one".to_string()));
732        assert_eq!(map.get(&1).map(|v| v.as_str()), Some("uno"));
733
734        assert_eq!(map.remove(&2), None);
735        assert_eq!(map.len(), 1);
736        assert_eq!(map.iter().map(|(k, _)| *k).collect::<Vec<_>>(), vec![1]);
737    }
738
739    #[test]
740    fn test_bisect_boundaries() {
741        let mut map = OrdHashMap::new();
742        map.insert(10u32, "ten".to_string());
743        map.insert(20, "twenty".to_string());
744
745        assert_eq!(map.bisect(|key| 5u32.partial_cmp(key)), None);
746        assert_eq!(map.bisect(|key| 10u32.partial_cmp(key)).map(|s| s.as_str()), Some("ten"));
747        assert_eq!(map.bisect(|key| 20u32.partial_cmp(key)).map(|s| s.as_str()), Some("twenty"));
748        assert_eq!(map.bisect(|key| 25u32.partial_cmp(key)), None);
749    }
750}
ds_ext/map.rs

ds_ext/
map.rs
