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

//! This is a very simple crate which you can use for creating many-to-many data structures in Rust, it's intended purpose or use case is for situations where you need to map a set of ids to another set of ids (for example in PubSub, such as `hive_pubsub` which is what this crate was designed for). It does this by using two `HashMap`s, one linking `Left` to a set of `Right` and vice-versa.
//!
//! This crate is like a fusion of `bimap` and `multimap`. I didn't see anything like this on crates.io, or anywhere really so I made my own thing.
//!
//! ## Constraints
//! 
//! Keys on either side (left or right) must implement the following traits:
//! - [std::hash::Hash](std::hash::Hash)
//! - [std::cmp::Eq](std::cmp::Eq)
//! - [core::clone::Clone](core::clone::Clone)
//!
//! ## Example
//!
//! ```rust
//! use many_to_many::ManyToMany;
//! 
//! let mut map = ManyToMany::new();
//! map.insert(1, 2);
//! map.insert(1, 3);
//! map.insert(1, 4);
//! 
//! dbg!(map.get_left(&1));
//! 
//! map.insert(5, 2);
//! map.remove(&1, &4);
//! 
//! dbg!(map.get_left(&1));
//! dbg!(map.get_right(&2));
//! 
//! map.remove(&1, &2);
//! map.remove(&1, &3);
//! 
//! assert_eq!(map.get_left(&1), None);
//! ```
//!
//! <script>console.log("many-to-many, crated by insrt.uk")</script>

use std::collections::{HashMap, HashSet};

/// # Many-To-Many data structure.
pub struct ManyToMany<L: std::hash::Hash + Eq + Clone, R: std::hash::Hash + Eq + Clone> {
    left:  HashMap<L, HashSet<R>>,
    right: HashMap<R, HashSet<L>>
}

impl<L: std::hash::Hash + Eq + Clone, R: std::hash::Hash + Eq + Clone> ManyToMany<L, R> {
    pub fn new() -> ManyToMany<L, R> {
        ManyToMany {
            left:  HashMap::new(),
            right: HashMap::new()
        }
    }

    fn get_mut_left(&mut self, left: &L) -> &mut HashSet<R> {
        if self.left.contains_key(left) {
            self.left.get_mut(left).expect(ERROR)
        } else {
            self.left.insert(left.clone(), HashSet::new());
            self.left.get_mut(left).expect(ERROR)
        }
    }

    fn get_mut_right(&mut self, right: &R) -> &mut HashSet<L> {
        if self.right.contains_key(right) {
            self.right.get_mut(right).expect(ERROR)
        } else {
            self.right.insert(right.clone(), HashSet::new());
            self.right.get_mut(right).expect(ERROR)
        }
    }

    /// Insert a new mapping between Left and Right.
    /// Returns whether the mapping already existed.
    pub fn insert(&mut self, left: L, right: R) -> bool {
        self.get_mut_left(&left).insert(right.clone()) && self.get_mut_right(&right).insert(left)
    }

    /// Remove an existing mapping between Left and Right.
    /// Returns whether the mapping was removed.
    pub fn remove(&mut self, left: &L, right: &R) -> bool {
        let list = self.get_mut_left(&left);
        let removed = list.remove(right);

        if list.len() == 0 {
            self.left.remove(left);
        }

        let list = self.get_mut_right(&right);
        list.remove(left);

        if list.len() == 0 {
            self.right.remove(right);
        }

        // We should have a guarantee that if it was removed from the
        // right list, it should also be present in the left list and
        // hence also removed from the left list.
        removed
    }

    /// Get all mappings to Right from specific Left key.
    pub fn get_left(&self, left: &L) -> Option<Vec<R>> {
        if let Some(entry) = self.left.get(left) {
            Some(entry.iter().cloned().collect())
        } else {
            None
        }
    }

    /// Get all mappings to Left from specific Right key.
    pub fn get_right(&self, right: &R) -> Option<Vec<L>> {
        if let Some(entry) = self.right.get(right) {
            Some(entry.iter().cloned().collect())
        } else {
            None
        }
    }
}

// Reducing memory usage by keeping one instance, every little helps :)
// I mean it's like 75 bytes less, but 75 bytes that could be better used.
// Ironically I'm also using up a fair amount of space writing these comments.
// But obviously that won't affect anything, nobody will read this anyways.
// Although if you do, feel free to tell me that you did. -> https://insrt.uk
static ERROR: &str = "Hit impossible condition.";

#[cfg(test)]
mod tests {
    #[test]
    fn test() {
        use crate::ManyToMany;

        let mut map = ManyToMany::new();
        map.insert(1, 2);
        map.insert(1, 3);
        map.insert(1, 4);

        dbg!(map.get_left(&1));

        map.insert(5, 2);
        map.remove(&1, &4);

        dbg!(map.get_left(&1));
        dbg!(map.get_right(&2));

        map.remove(&1, &2);
        map.remove(&1, &3);

        assert_eq!(map.get_left(&1), None);
    }
}