bimap/
btree.rs

1//! A bimap backed by two `BTreeMap`s.
2
3use crate::{
4    mem::{Ref, Wrapper},
5    Overwritten,
6};
7use alloc::{
8    collections::{btree_map, BTreeMap},
9    rc::Rc,
10};
11use core::{
12    borrow::Borrow,
13    cmp::Ordering,
14    fmt,
15    hash::{Hash, Hasher},
16    iter::{Extend, FromIterator, FusedIterator},
17    ops::RangeBounds,
18};
19
20/// A bimap backed by two `BTreeMap`s.
21///
22/// See the [module-level documentation] for more details and examples.
23///
24/// [module-level documentation]: crate
25pub struct BiBTreeMap<L, R> {
26    left2right: BTreeMap<Ref<L>, Ref<R>>,
27    right2left: BTreeMap<Ref<R>, Ref<L>>,
28}
29
30impl<L, R> BiBTreeMap<L, R>
31where
32    L: Ord,
33    R: Ord,
34{
35    /// Creates an empty `BiBTreeMap`.
36    ///
37    /// # Examples
38    ///
39    /// ```
40    /// use bimap::BiBTreeMap;
41    ///
42    /// let bimap = BiBTreeMap::<char, i32>::new();
43    /// ```
44    pub fn new() -> Self {
45        Self {
46            left2right: BTreeMap::new(),
47            right2left: BTreeMap::new(),
48        }
49    }
50
51    /// Returns the number of left-right pairs in the bimap.
52    ///
53    /// # Examples
54    ///
55    /// ```
56    /// use bimap::BiBTreeMap;
57    ///
58    /// let mut bimap = BiBTreeMap::new();
59    /// bimap.insert('a', 1);
60    /// bimap.insert('b', 2);
61    /// bimap.insert('c', 3);
62    /// assert_eq!(bimap.len(), 3);
63    /// ```
64    pub fn len(&self) -> usize {
65        self.left2right.len()
66    }
67
68    /// Returns `true` if the bimap contains no left-right pairs, and `false`
69    /// otherwise.
70    ///
71    /// # Examples
72    ///
73    /// ```
74    /// use bimap::BiBTreeMap;
75    ///
76    /// let mut bimap = BiBTreeMap::new();
77    /// assert!(bimap.is_empty());
78    /// bimap.insert('a', 1);
79    /// assert!(!bimap.is_empty());
80    /// bimap.remove_by_right(&1);
81    /// assert!(bimap.is_empty());
82    /// ```
83    pub fn is_empty(&self) -> bool {
84        self.left2right.is_empty()
85    }
86
87    /// Removes all left-right pairs from the bimap.
88    ///
89    /// # Examples
90    ///
91    /// ```
92    /// use bimap::BiBTreeMap;
93    ///
94    /// let mut bimap = BiBTreeMap::new();
95    /// bimap.insert('a', 1);
96    /// bimap.insert('b', 2);
97    /// bimap.insert('c', 3);
98    /// bimap.clear();
99    /// assert!(bimap.len() == 0);
100    /// ```
101    pub fn clear(&mut self) {
102        self.left2right.clear();
103        self.right2left.clear();
104    }
105
106    /// Creates an iterator over the left-right pairs in the bimap in ascending
107    /// order by left value.
108    ///
109    /// The iterator element type is `(&L, &R)`.
110    ///
111    /// # Examples
112    ///
113    /// ```
114    /// use bimap::BiBTreeMap;
115    ///
116    /// let mut bimap = BiBTreeMap::new();
117    /// bimap.insert('a', 1);
118    /// bimap.insert('b', 2);
119    /// bimap.insert('c', 3);
120    ///
121    /// for (left, right) in bimap.iter() {
122    ///     println!("({}, {})", left, right);
123    /// }
124    /// ```
125    pub fn iter(&self) -> Iter<'_, L, R> {
126        Iter {
127            inner: self.left2right.iter(),
128        }
129    }
130
131    /// Creates an iterator over the left values in the bimap in ascending
132    /// order.
133    ///
134    /// The iterator element type is `&L`.
135    ///
136    /// # Examples
137    ///
138    /// ```
139    /// use bimap::BiBTreeMap;
140    ///
141    /// let mut bimap = BiBTreeMap::new();
142    /// bimap.insert('a', 1);
143    /// bimap.insert('b', 2);
144    /// bimap.insert('c', 3);
145    ///
146    /// for char_value in bimap.left_values() {
147    ///     println!("{}", char_value);
148    /// }
149    /// ```
150    pub fn left_values(&self) -> LeftValues<'_, L, R> {
151        LeftValues {
152            inner: self.left2right.iter(),
153        }
154    }
155
156    /// Creates an iterator over the right values in the bimap in ascending
157    /// order.
158    ///
159    /// The iterator element type is `&R`.
160    ///
161    /// # Examples
162    ///
163    /// ```
164    /// use bimap::BiBTreeMap;
165    ///
166    /// let mut bimap = BiBTreeMap::new();
167    /// bimap.insert('a', 1);
168    /// bimap.insert('b', 2);
169    /// bimap.insert('c', 3);
170    ///
171    /// for int_value in bimap.right_values() {
172    ///     println!("{}", int_value);
173    /// }
174    /// ```
175    pub fn right_values(&self) -> RightValues<'_, L, R> {
176        RightValues {
177            inner: self.right2left.iter(),
178        }
179    }
180
181    /// Returns a reference to the right value corresponding to the given left
182    /// value.
183    ///
184    /// The input may be any borrowed form of the bimap's left type, but the
185    /// ordering on the borrowed form *must* match the ordering on the left
186    /// type.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use bimap::BiBTreeMap;
192    ///
193    /// let mut bimap = BiBTreeMap::new();
194    /// bimap.insert('a', 1);
195    /// assert_eq!(bimap.get_by_left(&'a'), Some(&1));
196    /// assert_eq!(bimap.get_by_left(&'z'), None);
197    /// ```
198    pub fn get_by_left<Q>(&self, left: &Q) -> Option<&R>
199    where
200        L: Borrow<Q>,
201        Q: Ord + ?Sized,
202    {
203        self.left2right.get(Wrapper::wrap(left)).map(|l| &*l.0)
204    }
205
206    /// Returns a reference to the left value corresponding to the given right
207    /// value.
208    ///
209    /// The input may be any borrowed form of the bimap's right type, but the
210    /// ordering on the borrowed form *must* match the ordering on the right
211    /// type.
212    ///
213    /// # Examples
214    ///
215    /// ```
216    /// use bimap::BiBTreeMap;
217    ///
218    /// let mut bimap = BiBTreeMap::new();
219    /// bimap.insert('a', 1);
220    /// assert_eq!(bimap.get_by_right(&1), Some(&'a'));
221    /// assert_eq!(bimap.get_by_right(&2), None);
222    /// ```
223    pub fn get_by_right<Q>(&self, right: &Q) -> Option<&L>
224    where
225        R: Borrow<Q>,
226        Q: Ord + ?Sized,
227    {
228        self.right2left.get(Wrapper::wrap(right)).map(|r| &*r.0)
229    }
230
231    /// Returns `true` if the bimap contains the given left value and `false`
232    /// otherwise.
233    ///
234    /// The input may be any borrowed form of the bimap's left type, but the
235    /// ordering on the borrowed form *must* match the ordering on the left
236    /// type.
237    ///
238    /// # Examples
239    ///
240    /// ```
241    /// use bimap::BiBTreeMap;
242    ///
243    /// let mut bimap = BiBTreeMap::new();
244    /// bimap.insert('a', 1);
245    /// assert!(bimap.contains_left(&'a'));
246    /// assert!(!bimap.contains_left(&'b'));
247    /// ```
248    pub fn contains_left<Q>(&self, left: &Q) -> bool
249    where
250        L: Borrow<Q>,
251        Q: Ord + ?Sized,
252    {
253        self.left2right.contains_key(Wrapper::wrap(left))
254    }
255
256    /// Returns `true` if the map contains the given right value and `false`
257    /// otherwise.
258    ///
259    /// The input may be any borrowed form of the bimap's right type, but the
260    /// ordering on the borrowed form *must* match the ordering on the right
261    /// type.
262    ///
263    /// # Examples
264    ///
265    /// ```
266    /// use bimap::BiBTreeMap;
267    ///
268    /// let mut bimap = BiBTreeMap::new();
269    /// bimap.insert('a', 1);
270    /// assert!(bimap.contains_right(&1));
271    /// assert!(!bimap.contains_right(&2));
272    /// ```
273    pub fn contains_right<Q>(&self, right: &Q) -> bool
274    where
275        R: Borrow<Q>,
276        Q: Ord + ?Sized,
277    {
278        self.right2left.contains_key(Wrapper::wrap(right))
279    }
280
281    /// Removes the left-right pair corresponding to the given left value.
282    ///
283    /// Returns the previous left-right pair if the map contained the left value
284    /// and `None` otherwise.
285    ///
286    /// The input may be any borrowed form of the bimap's left type, but the
287    /// ordering on the borrowed form *must* match the ordering on the left
288    /// type.
289    ///
290    /// # Examples
291    ///
292    /// ```
293    /// use bimap::BiBTreeMap;
294    ///
295    /// let mut bimap = BiBTreeMap::new();
296    /// bimap.insert('a', 1);
297    /// bimap.insert('b', 2);
298    /// bimap.insert('c', 3);
299    ///
300    /// assert_eq!(bimap.remove_by_left(&'b'), Some(('b', 2)));
301    /// assert_eq!(bimap.remove_by_left(&'b'), None);
302    /// ```
303    pub fn remove_by_left<Q>(&mut self, left: &Q) -> Option<(L, R)>
304    where
305        L: Borrow<Q>,
306        Q: Ord + ?Sized,
307    {
308        self.left2right.remove(Wrapper::wrap(left)).map(|right_rc| {
309            // unwrap is safe because we know right2left contains the key (it's a bimap)
310            let left_rc = self.right2left.remove(&right_rc).unwrap();
311            // at this point we can safely unwrap because the other pointers are gone
312            (
313                Rc::try_unwrap(left_rc.0).ok().unwrap(),
314                Rc::try_unwrap(right_rc.0).ok().unwrap(),
315            )
316        })
317    }
318
319    /// Removes the left-right pair corresponding to the given right value.
320    ///
321    /// Returns the previous left-right pair if the map contained the right
322    /// value and `None` otherwise.
323    ///
324    /// The input may be any borrowed form of the bimap's right type, but the
325    /// ordering on the borrowed form *must* match the ordering on the right
326    /// type.
327    ///
328    /// # Examples
329    ///
330    /// ```
331    /// use bimap::BiBTreeMap;
332    ///
333    /// let mut bimap = BiBTreeMap::new();
334    /// bimap.insert('a', 1);
335    /// bimap.insert('b', 2);
336    /// bimap.insert('c', 3);
337    ///
338    /// assert_eq!(bimap.remove_by_right(&2), Some(('b', 2)));
339    /// assert_eq!(bimap.remove_by_right(&2), None);
340    /// ```
341    pub fn remove_by_right<Q>(&mut self, right: &Q) -> Option<(L, R)>
342    where
343        R: Borrow<Q>,
344        Q: Ord + ?Sized,
345    {
346        self.right2left.remove(Wrapper::wrap(right)).map(|left_rc| {
347            // unwrap is safe because we know left2right contains the key (it's a bimap)
348            let right_rc = self.left2right.remove(&left_rc).unwrap();
349            // at this point we can safely unwrap because the other pointers are gone
350            (
351                Rc::try_unwrap(left_rc.0).ok().unwrap(),
352                Rc::try_unwrap(right_rc.0).ok().unwrap(),
353            )
354        })
355    }
356
357    /// Retains only elements specified by a predicate
358    ///
359    /// In other words, remove all left-right pairs `(l, r)` such that `f(&l,
360    /// &r)` returns `false`.
361    ///
362    /// # Example
363    ///
364    /// ```
365    /// use bimap::BiBTreeMap;
366    ///
367    /// let mut bimap = BiBTreeMap::new();
368    /// bimap.insert('a', 1);
369    /// bimap.insert('b', 2);
370    /// bimap.insert('c', 3);
371    ///
372    /// bimap.retain(|&l, _| l != 'b');
373    /// assert_eq!(bimap.len(), 2);
374    /// assert_eq!(bimap.get_by_right(&1), Some(&'a'));
375    /// assert_eq!(bimap.get_by_right(&2), None);
376    /// assert_eq!(bimap.get_by_right(&3), Some(&'c'));
377    /// ```
378    pub fn retain<F>(&mut self, f: F)
379    where
380        F: FnMut(&L, &R) -> bool,
381    {
382        let mut f = f;
383        let right2left = &mut self.right2left;
384        self.left2right.retain(|l, r| {
385            let to_retain = f(&l.0, &r.0);
386            if !to_retain {
387                right2left.remove(r);
388            }
389            to_retain
390        })
391    }
392
393    /// Inserts the given left-right pair into the bimap.
394    ///
395    /// Returns an enum `Overwritten` representing any left-right pairs that
396    /// were overwritten by the call to `insert`. The example below details
397    /// all possible enum variants that can be returned.
398    ///
399    /// # Warnings
400    ///
401    /// Somewhat paradoxically, calling `insert()` can actually reduce the size
402    /// of the bimap! This is because of the invariant that each left value
403    /// maps to exactly one right value and vice versa.
404    ///
405    /// # Examples
406    ///
407    /// ```
408    /// use bimap::{BiBTreeMap, Overwritten};
409    ///
410    /// let mut bimap = BiBTreeMap::new();
411    /// assert_eq!(bimap.len(), 0); // {}
412    ///
413    /// // no values are overwritten.
414    /// assert_eq!(bimap.insert('a', 1), Overwritten::Neither);
415    /// assert_eq!(bimap.len(), 1); // {'a' <> 1}
416    ///
417    /// // no values are overwritten.
418    /// assert_eq!(bimap.insert('b', 2), Overwritten::Neither);
419    /// assert_eq!(bimap.len(), 2); // {'a' <> 1, 'b' <> 2}
420    ///
421    /// // ('a', 1) already exists, so inserting ('a', 4) overwrites 'a', the left value.
422    /// // the previous left-right pair ('a', 1) is returned.
423    /// assert_eq!(bimap.insert('a', 4), Overwritten::Left('a', 1));
424    /// assert_eq!(bimap.len(), 2); // {'a' <> 4, 'b' <> 2}
425    ///
426    /// // ('b', 2) already exists, so inserting ('c', 2) overwrites 2, the right value.
427    /// // the previous left-right pair ('b', 2) is returned.
428    /// assert_eq!(bimap.insert('c', 2), Overwritten::Right('b', 2));
429    /// assert_eq!(bimap.len(), 2); // {'a' <> 1, 'c' <> 2}
430    ///
431    /// // both ('a', 4) and ('c', 2) already exist, so inserting ('a', 2) overwrites both.
432    /// // ('a', 4) has the overwritten left value ('a'), so it's the first tuple returned.
433    /// // ('c', 2) has the overwritten right value (2), so it's the second tuple returned.
434    /// assert_eq!(bimap.insert('a', 2), Overwritten::Both(('a', 4), ('c', 2)));
435    /// assert_eq!(bimap.len(), 1); // {'a' <> 2} // bimap is smaller than before!
436    ///
437    /// // ('a', 2) already exists, so inserting ('a', 2) overwrites the pair.
438    /// // the previous left-right pair ('a', 2) is returned.
439    /// assert_eq!(bimap.insert('a', 2), Overwritten::Pair('a', 2));
440    /// assert_eq!(bimap.len(), 1); // {'a' <> 2}
441    /// ```
442    pub fn insert(&mut self, left: L, right: R) -> Overwritten<L, R> {
443        let retval = match (self.remove_by_left(&left), self.remove_by_right(&right)) {
444            (None, None) => Overwritten::Neither,
445            (None, Some(r_pair)) => Overwritten::Right(r_pair.0, r_pair.1),
446            (Some(l_pair), None) => {
447                // since remove_by_left() was called first, it's possible the right value was
448                // removed if a duplicate pair is being inserted
449                if l_pair.1 == right {
450                    Overwritten::Pair(l_pair.0, l_pair.1)
451                } else {
452                    Overwritten::Left(l_pair.0, l_pair.1)
453                }
454            }
455            (Some(l_pair), Some(r_pair)) => Overwritten::Both(l_pair, r_pair),
456        };
457        self.insert_unchecked(left, right);
458        retval
459    }
460
461    /// Inserts the given left-right pair into the bimap without overwriting any
462    /// existing values.
463    ///
464    /// Returns `Ok(())` if the pair was successfully inserted into the bimap.
465    /// If either value exists in the map, `Err((left, right)` is returned
466    /// with the attempted left-right pair and the map is unchanged.
467    ///
468    /// # Examples
469    ///
470    /// ```
471    /// use bimap::BiBTreeMap;
472    ///
473    /// let mut bimap = BiBTreeMap::new();
474    /// assert_eq!(bimap.insert_no_overwrite('a', 1), Ok(()));
475    /// assert_eq!(bimap.insert_no_overwrite('b', 2), Ok(()));
476    /// assert_eq!(bimap.insert_no_overwrite('a', 3), Err(('a', 3)));
477    /// assert_eq!(bimap.insert_no_overwrite('c', 2), Err(('c', 2)));
478    /// ```
479    pub fn insert_no_overwrite(&mut self, left: L, right: R) -> Result<(), (L, R)> {
480        if self.contains_left(&left) || self.contains_right(&right) {
481            Err((left, right))
482        } else {
483            self.insert_unchecked(left, right);
484            Ok(())
485        }
486    }
487
488    /// Inserts the given left-right pair into the bimap without checking if the
489    /// pair already exists.
490    fn insert_unchecked(&mut self, left: L, right: R) {
491        let left = Ref(Rc::new(left));
492        let right_rc = Ref(Rc::new(right));
493        self.left2right.insert(left.clone(), right_rc.clone());
494        self.right2left.insert(right_rc, left);
495    }
496
497    /// Creates an iterator over the left-right pairs lying within a range of
498    /// left values in the bimap in ascending order by left.
499    ///
500    /// The iterator element type is `(&L, &R)`.
501    ///
502    /// The range bounds may be any borrowed form of the bimap's left type, but
503    /// the ordering on the borrowed form *must* match the ordering on the left
504    /// type.
505    ///
506    /// # Examples
507    ///
508    /// ```
509    /// use bimap::BiBTreeMap;
510    ///
511    /// let mut bimap = BiBTreeMap::new();
512    /// bimap.insert('a', 1);
513    /// bimap.insert('b', 2);
514    /// bimap.insert('c', 3);
515    /// bimap.insert('d', 4);
516    ///
517    /// for (left, right) in bimap.left_range('b'..'d') {
518    ///     println!("({}, {})", left, right);
519    /// }
520    /// ```
521    pub fn left_range<T, A>(&self, range: A) -> LeftRange<'_, L, R>
522    where
523        L: Borrow<T>,
524        A: RangeBounds<T>,
525        T: Ord + ?Sized,
526    {
527        let start = Wrapper::wrap_bound(range.start_bound());
528        let end = Wrapper::wrap_bound(range.end_bound());
529        LeftRange {
530            inner: self.left2right.range::<Wrapper<_>, _>((start, end)),
531        }
532    }
533
534    /// Creates an iterator over the left-right pairs lying within a range of
535    /// right values in the bimap in ascending order by right.
536    ///
537    /// The iterator element type is `(&L, &R)`.
538    ///
539    /// The range bounds may be any borrowed form of the bimap's right type, but
540    /// the ordering on the borrowed form *must* match the ordering on the right
541    /// type.
542    ///
543    /// # Examples
544    ///
545    /// ```
546    /// use bimap::BiBTreeMap;
547    ///
548    /// let mut bimap = BiBTreeMap::new();
549    /// bimap.insert('a', 1);
550    /// bimap.insert('b', 2);
551    /// bimap.insert('c', 3);
552    /// bimap.insert('d', 4);
553    ///
554    /// for (left, right) in bimap.right_range(2..4) {
555    ///     println!("({}, {})", left, right);
556    /// }
557    /// ```
558    pub fn right_range<T, A>(&self, range: A) -> RightRange<'_, L, R>
559    where
560        R: Borrow<T>,
561        A: RangeBounds<T>,
562        T: Ord + ?Sized,
563    {
564        let start = Wrapper::wrap_bound(range.start_bound());
565        let end = Wrapper::wrap_bound(range.end_bound());
566        RightRange {
567            inner: self.right2left.range::<Wrapper<_>, _>((start, end)),
568        }
569    }
570}
571
572impl<L, R> Clone for BiBTreeMap<L, R>
573where
574    L: Clone + Ord,
575    R: Clone + Ord,
576{
577    fn clone(&self) -> BiBTreeMap<L, R> {
578        self.iter().map(|(l, r)| (l.clone(), r.clone())).collect()
579    }
580}
581
582impl<L, R> fmt::Debug for BiBTreeMap<L, R>
583where
584    L: fmt::Debug + Ord,
585    R: fmt::Debug + Ord,
586{
587    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
588        write!(f, "{{")?;
589        for (i, (left, right)) in self.left2right.iter().enumerate() {
590            let comma = if i == 0 { "" } else { ", " };
591            write!(f, "{}{:?} <> {:?}", comma, left, right)?;
592        }
593        write!(f, "}}")?;
594        Ok(())
595    }
596}
597
598impl<L, R> Default for BiBTreeMap<L, R>
599where
600    L: Ord,
601    R: Ord,
602{
603    fn default() -> BiBTreeMap<L, R> {
604        BiBTreeMap {
605            left2right: BTreeMap::default(),
606            right2left: BTreeMap::default(),
607        }
608    }
609}
610
611impl<L, R> Eq for BiBTreeMap<L, R>
612where
613    L: Ord,
614    R: Ord,
615{
616}
617
618impl<L, R> FromIterator<(L, R)> for BiBTreeMap<L, R>
619where
620    L: Ord,
621    R: Ord,
622{
623    fn from_iter<I>(iter: I) -> BiBTreeMap<L, R>
624    where
625        I: IntoIterator<Item = (L, R)>,
626    {
627        let mut bimap = BiBTreeMap::new();
628        for (left, right) in iter {
629            bimap.insert(left, right);
630        }
631        bimap
632    }
633}
634
635impl<'a, L, R> IntoIterator for &'a BiBTreeMap<L, R>
636where
637    L: Ord,
638    R: Ord,
639{
640    type Item = (&'a L, &'a R);
641    type IntoIter = Iter<'a, L, R>;
642
643    fn into_iter(self) -> Iter<'a, L, R> {
644        self.iter()
645    }
646}
647
648impl<L, R> IntoIterator for BiBTreeMap<L, R>
649where
650    L: Ord,
651    R: Ord,
652{
653    type Item = (L, R);
654    type IntoIter = IntoIter<L, R>;
655
656    fn into_iter(self) -> IntoIter<L, R> {
657        IntoIter {
658            inner: self.left2right.into_iter(),
659        }
660    }
661}
662
663impl<L, R> Extend<(L, R)> for BiBTreeMap<L, R>
664where
665    L: Ord,
666    R: Ord,
667{
668    fn extend<T: IntoIterator<Item = (L, R)>>(&mut self, iter: T) {
669        iter.into_iter().for_each(move |(l, r)| {
670            self.insert(l, r);
671        });
672    }
673}
674
675impl<L, R> Ord for BiBTreeMap<L, R>
676where
677    L: Ord,
678    R: Ord,
679{
680    fn cmp(&self, other: &Self) -> Ordering {
681        self.left2right.cmp(&other.left2right)
682    }
683}
684
685impl<L, R> PartialEq for BiBTreeMap<L, R>
686where
687    L: Ord,
688    R: Ord,
689{
690    fn eq(&self, other: &Self) -> bool {
691        self.left2right == other.left2right
692    }
693}
694
695impl<L, R> PartialOrd for BiBTreeMap<L, R>
696where
697    L: Ord,
698    R: Ord,
699{
700    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
701        self.left2right.partial_cmp(&other.left2right)
702    }
703}
704
705impl<L, R> Hash for BiBTreeMap<L, R>
706where
707    L: Hash,
708    R: Hash,
709{
710    fn hash<H: Hasher>(&self, state: &mut H) {
711        self.left2right.hash(state);
712    }
713}
714
715/// An owning iterator over the left-right pairs in a `BiBTreeMap`.
716pub struct IntoIter<L, R> {
717    inner: btree_map::IntoIter<Ref<L>, Ref<R>>,
718}
719
720impl<L, R> DoubleEndedIterator for IntoIter<L, R> {
721    fn next_back(&mut self) -> Option<Self::Item> {
722        // unwraps are safe because right2left is gone
723        self.inner.next_back().map(|(l, r)| {
724            (
725                Rc::try_unwrap(l.0).ok().unwrap(),
726                Rc::try_unwrap(r.0).ok().unwrap(),
727            )
728        })
729    }
730}
731
732impl<L, R> ExactSizeIterator for IntoIter<L, R> {}
733
734impl<L, R> FusedIterator for IntoIter<L, R> {}
735
736impl<L, R> Iterator for IntoIter<L, R> {
737    type Item = (L, R);
738
739    fn next(&mut self) -> Option<Self::Item> {
740        // unwraps are safe because right2left is gone
741        self.inner.next().map(|(l, r)| {
742            (
743                Rc::try_unwrap(l.0).ok().unwrap(),
744                Rc::try_unwrap(r.0).ok().unwrap(),
745            )
746        })
747    }
748
749    fn size_hint(&self) -> (usize, Option<usize>) {
750        self.inner.size_hint()
751    }
752}
753
754/// An iterator over the left-right pairs in a `BiBTreeMap`.
755///
756/// This struct is created by the [`iter`] method of `BiBTreeMap`.
757///
758/// [`iter`]: BiBTreeMap::iter
759#[derive(Debug, Clone)]
760pub struct Iter<'a, L, R> {
761    inner: btree_map::Iter<'a, Ref<L>, Ref<R>>,
762}
763
764impl<'a, L, R> DoubleEndedIterator for Iter<'a, L, R> {
765    fn next_back(&mut self) -> Option<Self::Item> {
766        self.inner.next_back().map(|(l, r)| (&*l.0, &*r.0))
767    }
768}
769
770impl<'a, L, R> ExactSizeIterator for Iter<'a, L, R> {}
771
772impl<'a, L, R> FusedIterator for Iter<'a, L, R> {}
773
774impl<'a, L, R> Iterator for Iter<'a, L, R> {
775    type Item = (&'a L, &'a R);
776
777    fn next(&mut self) -> Option<Self::Item> {
778        self.inner.next().map(|(l, r)| (&*l.0, &*r.0))
779    }
780
781    fn size_hint(&self) -> (usize, Option<usize>) {
782        self.inner.size_hint()
783    }
784}
785
786/// An iterator over the left values in a `BiBTreeMap`.
787///
788/// This struct is created by the [`left_values`] method of `BiBTreeMap`.
789///
790/// [`left_values`]: BiBTreeMap::left_values
791#[derive(Debug, Clone)]
792pub struct LeftValues<'a, L, R> {
793    inner: btree_map::Iter<'a, Ref<L>, Ref<R>>,
794}
795
796impl<'a, L, R> DoubleEndedIterator for LeftValues<'a, L, R> {
797    fn next_back(&mut self) -> Option<Self::Item> {
798        self.inner.next_back().map(|(l, _)| &*l.0)
799    }
800}
801
802impl<'a, L, R> ExactSizeIterator for LeftValues<'a, L, R> {}
803
804impl<'a, L, R> FusedIterator for LeftValues<'a, L, R> {}
805
806impl<'a, L, R> Iterator for LeftValues<'a, L, R> {
807    type Item = &'a L;
808
809    fn next(&mut self) -> Option<Self::Item> {
810        self.inner.next().map(|(l, _)| &*l.0)
811    }
812
813    fn size_hint(&self) -> (usize, Option<usize>) {
814        self.inner.size_hint()
815    }
816}
817
818/// An iterator over the right values in a `BiBTreeMap`.
819///
820/// This struct is created by the [`right_values`] method of `BiBTreeMap`.
821///
822/// [`right_values`]: BiBTreeMap::right_values
823#[derive(Debug, Clone)]
824pub struct RightValues<'a, L, R> {
825    inner: btree_map::Iter<'a, Ref<R>, Ref<L>>,
826}
827
828impl<'a, L, R> DoubleEndedIterator for RightValues<'a, L, R> {
829    fn next_back(&mut self) -> Option<Self::Item> {
830        self.inner.next_back().map(|(r, _)| &*r.0)
831    }
832}
833
834impl<'a, L, R> ExactSizeIterator for RightValues<'a, L, R> {}
835
836impl<'a, L, R> FusedIterator for RightValues<'a, L, R> {}
837
838impl<'a, L, R> Iterator for RightValues<'a, L, R> {
839    type Item = &'a R;
840
841    fn next(&mut self) -> Option<Self::Item> {
842        self.inner.next().map(|(r, _)| &*r.0)
843    }
844
845    fn size_hint(&self) -> (usize, Option<usize>) {
846        self.inner.size_hint()
847    }
848}
849
850/// An iterator over a range of left-right pairs in a `BiBTreeMap`.
851///
852/// This struct is created by the [`left_range`] method of `BiBTreeMap`.
853///
854/// [`left_range`]: BiBTreeMap::left_range
855#[derive(Debug, Clone)]
856pub struct LeftRange<'a, L, R> {
857    inner: btree_map::Range<'a, Ref<L>, Ref<R>>,
858}
859
860impl<'a, L, R> DoubleEndedIterator for LeftRange<'a, L, R> {
861    fn next_back(&mut self) -> Option<Self::Item> {
862        self.inner.next_back().map(|(l, r)| (&*l.0, &*r.0))
863    }
864}
865
866impl<'a, L, R> ExactSizeIterator for LeftRange<'a, L, R> {}
867
868impl<'a, L, R> FusedIterator for LeftRange<'a, L, R> {}
869
870impl<'a, L, R> Iterator for LeftRange<'a, L, R> {
871    type Item = (&'a L, &'a R);
872
873    fn next(&mut self) -> Option<Self::Item> {
874        self.inner.next().map(|(l, r)| (&*l.0, &*r.0))
875    }
876
877    fn size_hint(&self) -> (usize, Option<usize>) {
878        self.inner.size_hint()
879    }
880}
881
882/// An iterator over a range of left-right pairs in a `BiBTreeMap`.
883///
884/// This struct is created by the [`right_range`] method of `BiBTreeMap`.
885///
886/// [`right_range`]: BiBTreeMap::right_range
887#[derive(Debug, Clone)]
888pub struct RightRange<'a, L, R> {
889    inner: btree_map::Range<'a, Ref<R>, Ref<L>>,
890}
891
892impl<'a, L, R> DoubleEndedIterator for RightRange<'a, L, R> {
893    fn next_back(&mut self) -> Option<Self::Item> {
894        self.inner.next_back().map(|(r, l)| (&*l.0, &*r.0))
895    }
896}
897
898impl<'a, L, R> ExactSizeIterator for RightRange<'a, L, R> {}
899
900impl<'a, L, R> FusedIterator for RightRange<'a, L, R> {}
901
902impl<'a, L, R> Iterator for RightRange<'a, L, R> {
903    type Item = (&'a L, &'a R);
904
905    fn next(&mut self) -> Option<Self::Item> {
906        self.inner.next().map(|(r, l)| (&*l.0, &*r.0))
907    }
908
909    fn size_hint(&self) -> (usize, Option<usize>) {
910        self.inner.size_hint()
911    }
912}
913
914// safe because internal Rcs are not exposed by the api and the reference counts
915// only change in methods with &mut self
916unsafe impl<L, R> Send for BiBTreeMap<L, R>
917where
918    L: Send,
919    R: Send,
920{
921}
922
923unsafe impl<L, R> Sync for BiBTreeMap<L, R>
924where
925    L: Sync,
926    R: Sync,
927{
928}
929
930#[cfg(test)]
931mod tests {
932    use super::*;
933
934    #[cfg(not(feature = "std"))]
935    use alloc::vec::Vec;
936
937    #[test]
938    fn clone() {
939        let mut bimap = BiBTreeMap::new();
940        bimap.insert('a', 1);
941        bimap.insert('b', 2);
942        let bimap2 = bimap.clone();
943        assert_eq!(bimap, bimap2);
944    }
945
946    #[test]
947    fn deep_clone() {
948        let mut bimap = BiBTreeMap::new();
949        bimap.insert('a', 1);
950        bimap.insert('b', 2);
951        let mut bimap2 = bimap.clone();
952
953        // would panic if clone() didn't deep clone
954        bimap.insert('b', 5);
955        bimap2.insert('a', 12);
956        bimap2.remove_by_left(&'a');
957        bimap.remove_by_right(&2);
958    }
959
960    #[test]
961    fn debug() {
962        let mut bimap = BiBTreeMap::new();
963        assert_eq!("{}", format!("{:?}", bimap));
964
965        bimap.insert('a', 1);
966        assert_eq!("{'a' <> 1}", format!("{:?}", bimap));
967
968        bimap.insert('b', 2);
969        assert_eq!("{'a' <> 1, 'b' <> 2}", format!("{:?}", bimap));
970    }
971
972    #[test]
973    fn default() {
974        let _ = BiBTreeMap::<char, i32>::default();
975    }
976
977    #[test]
978    fn eq() {
979        let mut bimap = BiBTreeMap::new();
980        assert_eq!(bimap, bimap);
981        bimap.insert('a', 1);
982        assert_eq!(bimap, bimap);
983        bimap.insert('b', 2);
984        assert_eq!(bimap, bimap);
985
986        let mut bimap2 = BiBTreeMap::new();
987        assert_ne!(bimap, bimap2);
988        bimap2.insert('a', 1);
989        assert_ne!(bimap, bimap2);
990        bimap2.insert('b', 2);
991        assert_eq!(bimap, bimap2);
992        bimap2.insert('c', 3);
993        assert_ne!(bimap, bimap2);
994    }
995
996    #[test]
997    fn from_iter() {
998        let bimap = BiBTreeMap::from_iter(vec![
999            ('a', 1),
1000            ('b', 2),
1001            ('c', 3),
1002            ('b', 2),
1003            ('a', 4),
1004            ('b', 3),
1005        ]);
1006        let mut bimap2 = BiBTreeMap::new();
1007        bimap2.insert('a', 4);
1008        bimap2.insert('b', 3);
1009        assert_eq!(bimap, bimap2);
1010    }
1011
1012    #[test]
1013    fn into_iter() {
1014        let mut bimap = BiBTreeMap::new();
1015        bimap.insert('a', 3);
1016        bimap.insert('b', 2);
1017        bimap.insert('c', 1);
1018        let pairs = bimap.into_iter().collect::<Vec<_>>();
1019        assert_eq!(pairs, vec![('a', 3), ('b', 2), ('c', 1)]);
1020    }
1021
1022    #[test]
1023    fn into_iter_ref() {
1024        let mut bimap = BiBTreeMap::new();
1025        bimap.insert('a', 3);
1026        bimap.insert('b', 2);
1027        bimap.insert('c', 1);
1028        let pairs = (&bimap).into_iter().collect::<Vec<_>>();
1029        assert_eq!(pairs, vec![(&'a', &3), (&'b', &2), (&'c', &1)]);
1030    }
1031
1032    #[test]
1033    fn extend() {
1034        let mut bimap = BiBTreeMap::new();
1035        bimap.insert('a', 3);
1036        bimap.insert('b', 2);
1037        bimap.extend(vec![('c', 3), ('b', 1), ('a', 4)]);
1038        let mut bimap2 = BiBTreeMap::new();
1039        bimap2.insert('a', 4);
1040        bimap2.insert('b', 1);
1041        bimap2.insert('c', 3);
1042        assert_eq!(bimap, bimap2);
1043    }
1044
1045    #[test]
1046    fn cmp() {
1047        let bimap = BiBTreeMap::from_iter(vec![('a', 2)]);
1048        let bimap2 = BiBTreeMap::from_iter(vec![('b', 1)]);
1049
1050        assert_eq!(bimap.partial_cmp(&bimap2), Some(Ordering::Less));
1051        assert_eq!(bimap.cmp(&bimap2), Ordering::Less);
1052
1053        assert_eq!(bimap2.partial_cmp(&bimap), Some(Ordering::Greater));
1054        assert_eq!(bimap2.cmp(&bimap), Ordering::Greater);
1055
1056        assert_eq!(bimap.cmp(&bimap), Ordering::Equal);
1057        assert_eq!(bimap2.cmp(&bimap2), Ordering::Equal);
1058    }
1059
1060    #[test]
1061    fn iter() {
1062        let mut bimap = BiBTreeMap::new();
1063        bimap.insert('a', 1);
1064        bimap.insert('b', 2);
1065        bimap.insert('c', 3);
1066        let pairs = bimap.iter().map(|(c, i)| (*c, *i)).collect::<Vec<_>>();
1067        assert_eq!(pairs, vec![('a', 1), ('b', 2), ('c', 3)]);
1068    }
1069
1070    #[test]
1071    fn iter_rev() {
1072        let mut bimap = BiBTreeMap::new();
1073        bimap.insert('a', 1);
1074        bimap.insert('b', 2);
1075        bimap.insert('c', 3);
1076
1077        let mut iter = bimap.iter();
1078        assert_eq!(iter.next_back(), Some((&'c', &3)));
1079        assert_eq!(iter.next_back(), Some((&'b', &2)));
1080        assert_eq!(iter.next_back(), Some((&'a', &1)));
1081    }
1082
1083    #[test]
1084    fn into_iter_rev() {
1085        let mut bimap = BiBTreeMap::new();
1086        bimap.insert('a', 1);
1087        bimap.insert('b', 2);
1088        bimap.insert('c', 3);
1089
1090        let mut iter = bimap.into_iter();
1091        assert_eq!(iter.next_back(), Some(('c', 3)));
1092        assert_eq!(iter.next_back(), Some(('b', 2)));
1093        assert_eq!(iter.next_back(), Some(('a', 1)));
1094    }
1095
1096    #[test]
1097    fn left_values() {
1098        let mut bimap = BiBTreeMap::new();
1099        bimap.insert('a', 3);
1100        bimap.insert('b', 2);
1101        bimap.insert('c', 1);
1102        let left_values = bimap.left_values().cloned().collect::<Vec<_>>();
1103        assert_eq!(left_values, vec!['a', 'b', 'c'])
1104    }
1105
1106    #[test]
1107    fn left_values_rev() {
1108        let mut bimap = BiBTreeMap::new();
1109        bimap.insert('a', 3);
1110        bimap.insert('b', 2);
1111        bimap.insert('c', 1);
1112
1113        let mut iter = bimap.left_values();
1114        assert_eq!(iter.next_back(), Some(&'c'));
1115        assert_eq!(iter.next_back(), Some(&'b'));
1116        assert_eq!(iter.next_back(), Some(&'a'));
1117    }
1118
1119    #[test]
1120    fn right_values() {
1121        let mut bimap = BiBTreeMap::new();
1122        bimap.insert('a', 3);
1123        bimap.insert('b', 2);
1124        bimap.insert('c', 1);
1125        let right_values = bimap.right_values().cloned().collect::<Vec<_>>();
1126        assert_eq!(right_values, vec![1, 2, 3])
1127    }
1128
1129    #[test]
1130    fn right_values_rev() {
1131        let mut bimap = BiBTreeMap::new();
1132        bimap.insert('a', 3);
1133        bimap.insert('b', 2);
1134        bimap.insert('c', 1);
1135
1136        let mut iter = bimap.right_values();
1137        assert_eq!(iter.next_back(), Some(&3));
1138        assert_eq!(iter.next_back(), Some(&2));
1139        assert_eq!(iter.next_back(), Some(&1));
1140    }
1141
1142    #[test]
1143    fn left_range() {
1144        let mut bimap = BiBTreeMap::new();
1145        bimap.insert('a', 4);
1146        bimap.insert('b', 3);
1147        bimap.insert('c', 2);
1148        bimap.insert('d', 1);
1149        let left_range = bimap
1150            .left_range('b'..'d')
1151            .map(|(l, r)| (*l, *r))
1152            .collect::<Vec<_>>();
1153        assert_eq!(left_range, vec![('b', 3), ('c', 2)])
1154    }
1155
1156    #[test]
1157    fn left_range_rev() {
1158        let mut bimap = BiBTreeMap::new();
1159        bimap.insert('a', 4);
1160        bimap.insert('b', 3);
1161        bimap.insert('c', 2);
1162        bimap.insert('d', 1);
1163        let mut left_range = bimap.left_range('b'..'d');
1164
1165        assert_eq!(left_range.next_back(), Some((&'c', &2)));
1166        assert_eq!(left_range.next_back(), Some((&'b', &3)));
1167        assert_eq!(left_range.next_back(), None);
1168    }
1169
1170    #[test]
1171    fn right_range() {
1172        let mut bimap = BiBTreeMap::new();
1173        bimap.insert('a', 4);
1174        bimap.insert('b', 3);
1175        bimap.insert('c', 2);
1176        bimap.insert('d', 1);
1177        let right_range = bimap
1178            .right_range(2..4)
1179            .map(|(l, r)| (*l, *r))
1180            .collect::<Vec<_>>();
1181        assert_eq!(right_range, vec![('c', 2), ('b', 3)])
1182    }
1183
1184    #[test]
1185    fn right_range_rev() {
1186        let mut bimap = BiBTreeMap::new();
1187        bimap.insert('a', 4);
1188        bimap.insert('b', 3);
1189        bimap.insert('c', 2);
1190        bimap.insert('d', 1);
1191        let mut right_range = bimap.right_range(2..4);
1192
1193        assert_eq!(right_range.next_back(), Some((&'b', &3)));
1194        assert_eq!(right_range.next_back(), Some((&'c', &2)));
1195        assert_eq!(right_range.next_back(), None);
1196    }
1197
1198    #[test]
1199    fn clear() {
1200        let mut bimap = BiBTreeMap::from_iter(vec![('a', 1)]);
1201        assert_eq!(bimap.len(), 1);
1202        assert!(!bimap.is_empty());
1203
1204        bimap.clear();
1205
1206        assert_eq!(bimap.len(), 0);
1207        assert!(bimap.is_empty());
1208    }
1209
1210    #[test]
1211    fn get_contains() {
1212        let bimap = BiBTreeMap::from_iter(vec![('a', 1)]);
1213
1214        assert_eq!(bimap.get_by_left(&'a'), Some(&1));
1215        assert!(bimap.contains_left(&'a'));
1216
1217        assert_eq!(bimap.get_by_left(&'b'), None);
1218        assert!(!bimap.contains_left(&'b'));
1219
1220        assert_eq!(bimap.get_by_right(&1), Some(&'a'));
1221        assert!(bimap.contains_right(&1));
1222
1223        assert_eq!(bimap.get_by_right(&2), None);
1224        assert!(!bimap.contains_right(&2));
1225    }
1226
1227    #[test]
1228    fn insert() {
1229        let mut bimap = BiBTreeMap::new();
1230
1231        assert_eq!(bimap.insert('a', 1), Overwritten::Neither);
1232        assert_eq!(bimap.insert('a', 2), Overwritten::Left('a', 1));
1233        assert_eq!(bimap.insert('b', 2), Overwritten::Right('a', 2));
1234        assert_eq!(bimap.insert('b', 2), Overwritten::Pair('b', 2));
1235
1236        assert_eq!(bimap.insert('c', 3), Overwritten::Neither);
1237        assert_eq!(bimap.insert('b', 3), Overwritten::Both(('b', 2), ('c', 3)));
1238    }
1239
1240    #[test]
1241    fn insert_no_overwrite() {
1242        let mut bimap = BiBTreeMap::new();
1243
1244        assert!(bimap.insert_no_overwrite('a', 1).is_ok());
1245        assert!(bimap.insert_no_overwrite('a', 2).is_err());
1246        assert!(bimap.insert_no_overwrite('b', 1).is_err());
1247    }
1248
1249    #[test]
1250    #[cfg(feature = "std")]
1251    fn hash() {
1252        use core::iter::{self, FromIterator};
1253        use std::collections::HashSet;
1254
1255        let mut hashset = HashSet::new();
1256
1257        hashset.insert(BiBTreeMap::new());
1258
1259        hashset.insert(BiBTreeMap::from_iter(iter::once((0, '0'))));
1260
1261        hashset.insert(BiBTreeMap::from_iter(vec![(0, '0'), (0, '1'), (1, '0')]));
1262        hashset.insert(BiBTreeMap::from_iter(vec![(1, '0'), (0, '1'), (0, '0')]));
1263        hashset.insert(BiBTreeMap::from_iter(vec![(0, '0'), (0, '1'), (1, '0')]));
1264
1265        assert_eq!(
1266            hashset,
1267            HashSet::from_iter(vec![
1268                BiBTreeMap::new(),
1269                BiBTreeMap::from_iter(iter::once((0, '0'))),
1270                BiBTreeMap::from_iter(vec![(0, '0'), (1, '0'), (0, '1')]),
1271            ])
1272        );
1273    }
1274}
bimap/btree.rs

bimap/
btree.rs
