1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162

//! A two-way map data structure for cloneable keys and values.
//!
//! Most functions come in `_fwd` and `_rev` variants; where the `_fwd` variant acts on the second
//! entry given the first, and `_rev` is the opposite.
//!
//! This crate is best for values that are cheap to clone, since internally it stores two copies
//! of each element. To use it with large values, consider wrapping them in `Rc` to make them cheap
//! to clone.

use std::borrow::Borrow;
use std::collections::hash_map::*;
use std::default::Default;
use std::hash::{BuildHasher, Hash};

#[derive(Clone)]
pub struct Bimap<K, V, S = RandomState> {
    fwd: HashMap<K, V, S>,
    rev: HashMap<V, K, S>,
}

impl<K, V> Bimap<K, V, RandomState>
where
    K: Eq + Hash + Clone,
    V: Eq + Hash + Clone,
{
    /// Creates an empty `Bimap`.
    pub fn new() -> Self {
        Self {
            fwd: HashMap::new(),
            rev: HashMap::new(),
        }
    }
}

impl<K, V, S> Bimap<K, V, S>
where
    K: Eq + Hash + Clone,
    V: Eq + Hash + Clone,
    S: BuildHasher + Clone + Default,
{
    /// Creates a `Bimap` with the given hasher.
    pub fn with_hasher(hash_builder: S) -> Self {
        Self {
            fwd: HashMap::with_hasher(hash_builder.clone()),
            rev: HashMap::with_hasher(hash_builder),
        }
    }

    /// Creates a bimap from a `HashMap`.
    pub fn from_hash_map(fwd: HashMap<K, V, S>) -> Self {
        let rev = fwd.iter().map(|(k, v)| (v.clone(), k.clone())).collect();
        Self { fwd, rev }
    }

    /// Returns the number of elements in the bimap.
    pub fn len(&self) -> usize {
        self.fwd.len()
    }

    /// Returns whether the bimap is empty.
    pub fn is_empty(&self) -> bool {
        self.fwd.is_empty()
    }

    /// Removes all elements from the bimap.
    pub fn clear(&mut self) {
        self.fwd.clear();
        self.rev.clear();
    }

    /// Inserts a (key, value) pair into the bimap. Panics if either the key or value is already
    /// present in the bimap; to change a key or value, call either `remove_fwd` or
    /// `remove_rev` before inserting the new (key, value) pair.
    pub fn insert(&mut self, k: K, v: V) {
        match self.fwd.entry(k.clone()) {
            Entry::Vacant(entry) => {
                entry.insert(v.clone());
            }
            Entry::Occupied(_) => panic!("Element aready in bimap"),
        }
        match self.rev.entry(v) {
            Entry::Vacant(entry) => {
                entry.insert(k);
            }
            Entry::Occupied(_) => panic!("Element aready in bimap"),
        }
    }

    /// Gets the value corresponding to a key.
    pub fn get_fwd<KeyBorrow: ?Sized>(&self, k: &KeyBorrow) -> Option<&V>
    where
        K: Borrow<KeyBorrow>,
        KeyBorrow: Hash + Eq,
    {
        self.fwd.get(k)
    }

    /// Gets the key corresponding to a value.
    pub fn get_rev<ValBorrow: ?Sized>(&self, v: &ValBorrow) -> Option<&K>
    where
        V: Borrow<ValBorrow>,
        ValBorrow: Hash + Eq,
    {
        self.rev.get(v)
    }

    /// Removes the (key, value) pair with the given key; returns the corresponding value.
    pub fn remove_fwd<KeyBorrow: ?Sized>(&mut self, k: &KeyBorrow) -> V
    where
        K: Borrow<KeyBorrow>,
        KeyBorrow: Hash + Eq,
    {
        let v = self.fwd.remove(k).unwrap();
        self.rev.remove(&v);
        v
    }

    /// Removes the (key, value) pair with the given value; returns the corresponding key.
    pub fn remove_rev<ValBorrow: ?Sized>(&mut self, v: &ValBorrow) -> K
    where
        V: Borrow<ValBorrow>,
        ValBorrow: Hash + Eq,
    {
        let k = self.rev.remove(v).unwrap();
        self.fwd.remove(&k);
        k
    }

    /// Returns whether the bimap contains a (key, value) pair with the given key.
    pub fn contains_fwd<KeyBorrow: ?Sized>(&self, k: &KeyBorrow) -> bool
    where
        K: Borrow<KeyBorrow>,
        KeyBorrow: Hash + Eq,
    {
        self.fwd.contains_key(k)
    }

    /// Returns whether the bimap contains a (key, value) pair with the given value.
    pub fn contains_rev<ValBorrow: ?Sized>(&self, v: &ValBorrow) -> bool
    where
        V: Borrow<ValBorrow>,
        ValBorrow: Hash + Eq,
    {
        self.rev.contains_key(v)
    }

    /// Iterates over all (key, value) pairs in the bimap.
    pub fn iter(&self) -> Iter<K, V> {
        self.fwd.iter()
    }
}

impl<K, V, S> Default for Bimap<K, V, S>
where
    K: Eq + Hash + Clone,
    V: Eq + Hash + Clone,
    S: BuildHasher + Clone + Default,
{
    fn default() -> Self {
        Bimap::with_hasher(Default::default())
    }
}