1 use std::collections::btree_map;
2 use std::default::Default;
3 use std::iter::FromIterator;
4
5 use super::map::{map, Map};
6 use super::set::Set;
7
8 pub struct Multimap<K, C: Collection> {
9 map: Map<K, C>,
10 }
11
12 pub trait Collection: Default {
13 type Item;
14
15 /// Push `item` into the collection and return `true` if
16 /// collection changed.
push(&mut self, item: Self::Item) -> bool17 fn push(&mut self, item: Self::Item) -> bool;
18 }
19
20 impl<K: Ord, C: Collection> Multimap<K, C> {
new() -> Multimap<K, C>21 pub fn new() -> Multimap<K, C> {
22 Multimap { map: map() }
23 }
24
is_empty(&self) -> bool25 pub fn is_empty(&self) -> bool {
26 self.map.is_empty()
27 }
28
29 /// Push `value` to the collection associated with `key`. Returns
30 /// true if the collection was changed from the default.
push(&mut self, key: K, value: C::Item) -> bool31 pub fn push(&mut self, key: K, value: C::Item) -> bool {
32 let mut inserted = false;
33 let pushed = self
34 .map
35 .entry(key)
36 .or_insert_with(|| {
37 inserted = true;
38 C::default()
39 })
40 .push(value);
41 inserted || pushed
42 }
43
get(&self, key: &K) -> Option<&C>44 pub fn get(&self, key: &K) -> Option<&C> {
45 self.map.get(key)
46 }
47
iter(&self) -> btree_map::Iter<K, C>48 pub fn iter(&self) -> btree_map::Iter<K, C> {
49 self.map.iter()
50 }
51
into_iter(self) -> btree_map::IntoIter<K, C>52 pub fn into_iter(self) -> btree_map::IntoIter<K, C> {
53 self.map.into_iter()
54 }
55 }
56
57 impl<K: Ord, C: Collection> IntoIterator for Multimap<K, C> {
58 type Item = (K, C);
59 type IntoIter = btree_map::IntoIter<K, C>;
into_iter(self) -> btree_map::IntoIter<K, C>60 fn into_iter(self) -> btree_map::IntoIter<K, C> {
61 self.into_iter()
62 }
63 }
64
65 impl<'iter, K: Ord, C: Collection> IntoIterator for &'iter Multimap<K, C> {
66 type Item = (&'iter K, &'iter C);
67 type IntoIter = btree_map::Iter<'iter, K, C>;
into_iter(self) -> btree_map::Iter<'iter, K, C>68 fn into_iter(self) -> btree_map::Iter<'iter, K, C> {
69 self.iter()
70 }
71 }
72
73 impl<K: Ord, C: Collection> FromIterator<(K, C::Item)> for Multimap<K, C> {
from_iter<T>(iterator: T) -> Self where T: IntoIterator<Item = (K, C::Item)>,74 fn from_iter<T>(iterator: T) -> Self
75 where
76 T: IntoIterator<Item = (K, C::Item)>,
77 {
78 let mut map = Multimap::new();
79 for (key, value) in iterator {
80 map.push(key, value);
81 }
82 map
83 }
84 }
85
86 impl Collection for () {
87 type Item = ();
push(&mut self, _item: ()) -> bool88 fn push(&mut self, _item: ()) -> bool {
89 false
90 }
91 }
92
93 impl<T> Collection for Vec<T> {
94 type Item = T;
95
push(&mut self, item: T) -> bool96 fn push(&mut self, item: T) -> bool {
97 self.push(item);
98 true // always changes
99 }
100 }
101
102 impl<T: Ord> Collection for Set<T> {
103 type Item = T;
104
push(&mut self, item: T) -> bool105 fn push(&mut self, item: T) -> bool {
106 self.insert(item)
107 }
108 }
109
110 impl<K: Ord, C: Collection> Default for Multimap<K, C> {
default() -> Self111 fn default() -> Self {
112 Multimap::new()
113 }
114 }
115
116 impl<K: Ord, C: Collection<Item = I>, I> Collection for Multimap<K, C> {
117 type Item = (K, I);
118
push(&mut self, item: (K, I)) -> bool119 fn push(&mut self, item: (K, I)) -> bool {
120 let (key, value) = item;
121 self.push(key, value)
122 }
123 }
124
125 #[test]
push()126 fn push() {
127 let mut m: Multimap<u32, Set<char>> = Multimap::new();
128 assert!(m.push(0, 'a'));
129 assert!(m.push(0, 'b'));
130 assert!(!m.push(0, 'b'));
131 assert!(m.push(1, 'a'));
132 }
133
134 #[test]
push_nil()135 fn push_nil() {
136 let mut m: Multimap<u32, ()> = Multimap::new();
137 assert!(m.push(0, ()));
138 assert!(!m.push(0, ()));
139 assert!(m.push(1, ()));
140 assert!(!m.push(0, ()));
141 }
142