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

use std::collections::btree_map;
use std::default::Default;
use std::iter::FromIterator;

use super::map::{map, Map};
use super::set::Set;

pub struct Multimap<K, C: Collection> {
    map: Map<K, C>,
}

pub trait Collection: Default {
    type Item;

    /// Push `item` into the collection and return `true` if
    /// collection changed.
    fn push(&mut self, item: Self::Item) -> bool;
}

impl<K: Ord, C: Collection> Multimap<K, C> {
    pub fn new() -> Multimap<K, C> {
        Multimap { map: map() }
    }

    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Push `value` to the collection associated with `key`. Returns
    /// true if the collection was changed from the default.
    pub fn push(&mut self, key: K, value: C::Item) -> bool {
        let mut inserted = false;
        let pushed = self
            .map
            .entry(key)
            .or_insert_with(|| {
                inserted = true;
                C::default()
            })
            .push(value);
        inserted || pushed
    }

    pub fn get(&self, key: &K) -> Option<&C> {
        self.map.get(key)
    }

    pub fn iter(&self) -> btree_map::Iter<K, C> {
        self.map.iter()
    }

    pub fn into_iter(self) -> btree_map::IntoIter<K, C> {
        self.map.into_iter()
    }
}

impl<K: Ord, C: Collection> IntoIterator for Multimap<K, C> {
    type Item = (K, C);
    type IntoIter = btree_map::IntoIter<K, C>;
    fn into_iter(self) -> btree_map::IntoIter<K, C> {
        self.into_iter()
    }
}

impl<'iter, K: Ord, C: Collection> IntoIterator for &'iter Multimap<K, C> {
    type Item = (&'iter K, &'iter C);
    type IntoIter = btree_map::Iter<'iter, K, C>;
    fn into_iter(self) -> btree_map::Iter<'iter, K, C> {
        self.iter()
    }
}

impl<K: Ord, C: Collection> FromIterator<(K, C::Item)> for Multimap<K, C> {
    fn from_iter<T>(iterator: T) -> Self
    where
        T: IntoIterator<Item = (K, C::Item)>,
    {
        let mut map = Multimap::new();
        for (key, value) in iterator {
            map.push(key, value);
        }
        map
    }
}

impl Collection for () {
    type Item = ();
    fn push(&mut self, _item: ()) -> bool {
        false
    }
}

impl<T> Collection for Vec<T> {
    type Item = T;

    fn push(&mut self, item: T) -> bool {
        self.push(item);
        true // always changes
    }
}

impl<T: Ord> Collection for Set<T> {
    type Item = T;

    fn push(&mut self, item: T) -> bool {
        self.insert(item)
    }
}

impl<K: Ord, C: Collection> Default for Multimap<K, C> {
    fn default() -> Self {
        Multimap::new()
    }
}

impl<K: Ord, C: Collection<Item = I>, I> Collection for Multimap<K, C> {
    type Item = (K, I);

    fn push(&mut self, item: (K, I)) -> bool {
        let (key, value) = item;
        self.push(key, value)
    }
}

#[test]
fn push() {
    let mut m: Multimap<u32, Set<char>> = Multimap::new();
    assert!(m.push(0, 'a'));
    assert!(m.push(0, 'b'));
    assert!(!m.push(0, 'b'));
    assert!(m.push(1, 'a'));
}

#[test]
fn push_nil() {
    let mut m: Multimap<u32, ()> = Multimap::new();
    assert!(m.push(0, ()));
    assert!(!m.push(0, ()));
    assert!(m.push(1, ()));
    assert!(!m.push(0, ()));
}