nekolib/ds/
btree_bimap.rs

1//! 双方向連想配列。
2
3use std::borrow::Borrow;
4use std::collections::{btree_map::Range, BTreeMap};
5use std::fmt::Debug;
6use std::ops::RangeBounds;
7
8/// 双方向連想配列。
9///
10/// $k\\mapsto v$ ではなく、全単射となるように $k\_l\\mapsto k\_r$ と
11/// $k\_r\\mapsto k\_l$ を管理する。
12///
13/// # Examples
14/// ```
15/// use nekolib::ds::BTreeBimap;
16///
17/// let mut bimap = BTreeBimap::new();
18///
19/// bimap.insert(1, 'a');
20/// bimap.insert(2, 'b');
21/// bimap.insert(3, 'c');
22///
23/// bimap.insert(1, 'b');
24/// assert_eq!(bimap.len(), 2); // {1: 'b', 3, 'c'}
25///
26/// bimap.remove_left(&1);
27/// bimap.remove_right(&'c');
28/// assert!(bimap.is_empty());
29/// ```
30#[derive(Clone, Debug, Default)]
31pub struct BTreeBimap<L: Ord, R: Ord> {
32    left: BTreeMap<L, R>,
33    right: BTreeMap<R, L>,
34}
35
36impl<L: Clone + Ord, R: Clone + Ord> BTreeBimap<L, R> {
37    pub fn new() -> Self {
38        Self { left: BTreeMap::new(), right: BTreeMap::new() }
39    }
40    pub fn is_empty(&self) -> bool { self.left.is_empty() }
41    pub fn len(&self) -> usize { self.left.len() }
42    pub fn insert(&mut self, l: L, r: R) {
43        if let Some(old_r) = self.left.insert(l.clone(), r.clone()) {
44            self.right.remove(&old_r);
45        }
46        if let Some(old_l) = self.right.insert(r, l) {
47            self.left.remove(&old_l);
48        }
49    }
50    pub fn remove_left(&mut self, l: &L) {
51        if let Some(old_r) = self.left.remove(l) {
52            self.right.remove(&old_r);
53        }
54    }
55    pub fn remove_right(&mut self, r: &R) {
56        if let Some(old_l) = self.right.remove(r) {
57            self.left.remove(&old_l);
58        }
59    }
60
61    // {iter|entry}_{left|right} とかも欲しいよね
62    // .or_insert() は両方に入れたりする必要があるので注意。
63
64    pub fn range_left<T, B>(&self, range: B) -> Range<'_, L, R>
65    where
66        T: Ord,
67        L: Borrow<T>,
68        B: RangeBounds<T>,
69    {
70        self.left.range(range)
71    }
72    pub fn range_right<T, B>(&self, range: B) -> Range<'_, R, L>
73    where
74        T: Ord,
75        R: Borrow<T>,
76        B: RangeBounds<T>,
77    {
78        self.right.range(range)
79    }
80}
81
82#[test]
83fn test_eq() {
84    let mut b = BTreeBimap::new();
85    b.insert(2, 20);
86    b.insert(2, 20);
87    assert_eq!(b.len(), 1);
88}
nekolib/ds/btree_bimap.rs

nekolib/ds/
btree_bimap.rs
