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

// SPDX-License-Identifier: AGPL-3.0-or-later
//! This module contains the [Bijection] type.

use super::HashMapWithDefault;
use log::error;
use std::{borrow::Borrow, hash::Hash};

/// Implements a bijection (one-to-one function) between a set of keys and a set of values.
/// Mapping from key to value and from value to key are both O(1) operations.
pub struct Bijection<K, V> {
    k2v: HashMapWithDefault<K, V>,
    v2k: HashMapWithDefault<V, K>,
}

impl<K, V> Bijection<K, V> {
    /// Creates a new [Bijection] with the given default key and value.
    pub fn new(default_key: K, default_value: V) -> Self {
        let k2v = HashMapWithDefault::new(default_value);
        let v2k = HashMapWithDefault::new(default_key);
        Self { k2v, v2k }
    }

    /// Returns a reference to the hash table which maps keys to values.
    pub fn k2v(&self) -> &HashMapWithDefault<K, V> {
        &self.k2v
    }

    /// Returns a reference to the hash table which maps values to keys.
    pub fn v2k(&self) -> &HashMapWithDefault<V, K> {
        &self.v2k
    }
}

impl<K: Clone + Hash + Eq, V: Clone + Hash + Eq> Bijection<K, V> {
    /// Inserts the given `(key, value)` pair. If this replaces an existing pair, then the old
    /// pair is returned.
    pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)> {
        let key_clone = key.clone();
        let value_clone = value.clone();
        let old_value = self.k2v.get_mut().insert(key, value);
        let old_key = self.v2k.get_mut().insert(value_clone, key_clone);
        match (old_key, old_value) {
            (Some(old_key), Some(old_value)) => Some((old_key, old_value)),
            (None, None) => None,
            _ => {
                error!("logic error: unmatched key-value pair encountered in bijection insert");
                None
            }
        }
    }
}

impl<K: Hash + Eq, V> Bijection<K, V> {
    /// Returns the value associated with the given key. If no value is associated, then the default
    /// value is returned.
    pub fn value<Q: ?Sized + Hash + Eq>(&self, key: &Q) -> &V
    where
        K: Borrow<Q>,
    {
        self.k2v.get(key)
    }
}

impl<K, V: Hash + Eq> Bijection<K, V> {
    /// Returns the key associated with the given value. If no key is associated, then the default
    /// key is returned.
    pub fn key<R: ?Sized + Hash + Eq>(&self, value: &R) -> &K
    where
        V: Borrow<R>,
    {
        self.v2k.get(value)
    }
}