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