modern_multiset/multiset.rs
1#![warn(missing_docs)]
2
3use std::borrow::Borrow;
4use std::collections::hash_map;
5use std::collections::hash_map::{Entry, Keys};
6use std::collections::HashMap;
7use std::fmt;
8use std::hash::Hash;
9use std::iter::{FromIterator, IntoIterator};
10use std::ops::{Add, Sub};
11
12/// A hash-based multiset.
13#[derive(Clone, Default, Eq)]
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15pub struct HashMultiSet<K>
16where
17 K: Eq + Hash,
18{
19 elem_counts: HashMap<K, usize>,
20 size: usize,
21}
22
23/// An iterator over the items of a `HashMultiSet`.
24///
25/// This `struct` is created by the [`iter`] method on [`HashMultiSet`].
26#[derive(Clone)]
27pub struct Iter<'a, K: 'a> {
28 iter: hash_map::Iter<'a, K, usize>,
29 duplicate: Option<(&'a K, &'a usize)>,
30 duplicate_index: usize,
31}
32
33impl<'a, K> Iterator for Iter<'a, K> {
34 type Item = &'a K;
35
36 fn next(&mut self) -> Option<&'a K> {
37 if self.duplicate.is_none() {
38 self.duplicate = self.iter.next();
39 }
40 if let Some((key, count)) = self.duplicate {
41 self.duplicate_index += 1;
42 if self.duplicate_index >= *count {
43 self.duplicate = None;
44 self.duplicate_index = 0;
45 }
46 Some(key)
47 } else {
48 None
49 }
50 }
51}
52
53impl<K> HashMultiSet<K>
54where
55 K: Eq + Hash,
56{
57 /// Creates a new empty `HashMultiSet`.
58 ///
59 /// # Examples
60 ///
61 /// ```
62 /// use modern_multiset::HashMultiSet;
63 ///
64 /// let multiset: HashMultiSet<char> = HashMultiSet::new();
65 /// ```
66 pub fn new() -> Self {
67 HashMultiSet {
68 elem_counts: HashMap::new(),
69 size: 0,
70 }
71 }
72
73 /// An iterator visiting all elements in arbitrary order, including each duplicate.
74 /// The iterator element type is `&'a K`.
75 ///
76 /// # Examples
77 ///
78 /// ```
79 /// use modern_multiset::HashMultiSet;
80 /// let mut multiset = HashMultiSet::new();
81 /// multiset.insert(0);
82 /// multiset.insert(0);
83 /// multiset.insert(1);
84 ///
85 /// // Will print in an arbitrary order.
86 /// for x in multiset.iter() {
87 /// println!("{}", x);
88 /// }
89 /// assert_eq!(3, multiset.iter().count());
90 /// ```
91 pub fn iter(&self) -> Iter<K> {
92 Iter {
93 iter: self.elem_counts.iter(),
94 duplicate: None,
95 duplicate_index: 0,
96 }
97 }
98
99 /// Returns true if the multiset contains no elements.
100 ///
101 /// # Examples
102 ///
103 /// ```
104 /// use modern_multiset::HashMultiSet;
105 ///
106 /// let mut multiset = HashMultiSet::new();
107 /// assert!(multiset.is_empty());
108 /// multiset.insert(1);
109 /// assert!(!multiset.is_empty());
110 /// ```
111 pub fn is_empty(&self) -> bool {
112 self.elem_counts.is_empty()
113 }
114
115 /// Returns `true` if the multiset contains a value.
116 ///
117 /// The value may be any borrowed form of the set's value type, but
118 /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
119 /// the value type.
120 ///
121 /// # Examples
122 ///
123 /// ```
124 /// use modern_multiset::HashMultiSet;
125 ///
126 /// let set: HashMultiSet<_> = [1, 2, 3].iter().cloned().collect();
127 /// assert_eq!(set.contains(&1), true);
128 /// assert_eq!(set.contains(&4), false);
129 /// ```
130 pub fn contains<Q>(&self, value: &Q) -> bool
131 where
132 K: Borrow<Q>,
133 Q: Hash + Eq + ?Sized,
134 {
135 self.elem_counts.contains_key(value)
136 }
137
138 /// Counts all the elements, including each duplicate.
139 ///
140 /// # Examples
141 ///
142 /// A new empty `HashMultiSet` with 0 total elements:
143 ///
144 /// ```
145 /// use modern_multiset::HashMultiSet;
146 ///
147 /// let multiset: HashMultiSet<char> = HashMultiSet::new();
148 /// assert_eq!(0, multiset.len());
149 /// ```
150 ///
151 /// A `HashMultiSet` from `vec![1,1,2]` has 3 total elements:
152 ///
153 /// ```
154 /// use modern_multiset::HashMultiSet;
155 /// use std::iter::FromIterator;
156 ///
157 /// let multiset: HashMultiSet<i32> = FromIterator::from_iter(vec![1,1,2]);
158 /// assert_eq!(3, multiset.len());
159 /// ```
160 pub fn len(&self) -> usize {
161 self.size
162 }
163
164 /// Returns all the distinct elements in the `HashMultiSet`.
165 ///
166 /// # Examples
167 ///
168 /// A `HashMultiSet` from `vec![1,1,2]` has 2 distinct elements,
169 /// namely `1` and `2`, but not `3`:
170 ///
171 /// ```
172 /// use modern_multiset::HashMultiSet;
173 /// use std::collections::HashSet;
174 /// use std::iter::FromIterator;
175 ///
176 /// let multiset: HashMultiSet<i64> = FromIterator::from_iter(vec![1,1,2]);
177 /// let distinct = multiset.distinct_elements().collect::<HashSet<_>>();
178 /// assert_eq!(2, distinct.len());
179 /// assert!(distinct.contains(&1));
180 /// assert!(distinct.contains(&2));
181 /// assert!(!distinct.contains(&3));
182 /// ```
183 pub fn distinct_elements(&self) -> Keys<K, usize> {
184 self.elem_counts.keys()
185 }
186
187 /// Inserts an element.
188 ///
189 /// # Examples
190 ///
191 /// Insert `5` into a new `HashMultiSet`:
192 ///
193 /// ```
194 /// use modern_multiset::HashMultiSet;
195 ///
196 /// let mut multiset: HashMultiSet<i32> = HashMultiSet::new();
197 /// assert_eq!(0, multiset.count_of(&5));
198 /// multiset.insert(5);
199 /// assert_eq!(1, multiset.count_of(&5));
200 /// ```
201 pub fn insert(&mut self, val: K) {
202 self.insert_times(val, 1);
203 }
204
205 /// Inserts an element `n` times.
206 ///
207 /// # Examples
208 ///
209 /// Insert three `5`s into a new `HashMultiSet`:
210 ///
211 /// ```
212 /// use modern_multiset::HashMultiSet;
213 ///
214 /// let mut multiset: HashMultiSet<i32> = HashMultiSet::new();
215 /// assert_eq!(0, multiset.count_of(&5));
216 /// multiset.insert_times(5,3);
217 /// assert_eq!(3, multiset.count_of(&5));
218 /// ```
219 pub fn insert_times(&mut self, val: K, n: usize) {
220 self.size += n;
221 match self.elem_counts.entry(val) {
222 Entry::Vacant(view) => {
223 view.insert(n);
224 }
225 Entry::Occupied(mut view) => {
226 let v = view.get_mut();
227 *v += n;
228 }
229 }
230 }
231
232 /// Remove an element. Removal of a nonexistent element
233 /// has no effect.
234 ///
235 /// # Examples
236 ///
237 /// Remove `5` from a new `HashMultiSet`:
238 ///
239 /// ```
240 /// use modern_multiset::HashMultiSet;
241 ///
242 /// let mut multiset: HashMultiSet<i32> = HashMultiSet::new();
243 /// multiset.insert(5);
244 /// assert_eq!(1, multiset.count_of(&5));
245 /// assert!(multiset.remove(&5));
246 /// assert_eq!(0, multiset.count_of(&5));
247 /// assert!(!multiset.remove(&5));
248 /// ```
249 pub fn remove(&mut self, val: &K) -> bool {
250 self.remove_times(val, 1) > 0
251 }
252
253 /// Remove an element `n` times. If an element is
254 /// removed as many or more times than it appears,
255 /// it is entirely removed from the multiset.
256 ///
257 /// # Examples
258 ///
259 /// Remove `5`s from a `HashMultiSet` containing 3 of them.
260 ///
261 /// ```
262 /// use modern_multiset::HashMultiSet;
263 ///
264 /// let mut multiset: HashMultiSet<i32> = HashMultiSet::new();
265 /// multiset.insert_times(5, 3);
266 /// assert!(multiset.count_of(&5) == 3);
267 /// assert!(multiset.remove_times(&5, 2) == 2);
268 /// assert!(multiset.len() == 1);
269 /// assert!(multiset.count_of(&5) == 1);
270 /// assert!(multiset.remove_times(&5, 1) == 1);
271 /// assert!(multiset.len() == 0);
272 /// assert!(multiset.count_of(&5) == 0);
273 /// assert!(multiset.remove_times(&5, 1) == 0);
274 /// assert!(multiset.count_of(&5) == 0);
275 /// ```
276 pub fn remove_times(&mut self, val: &K, times: usize) -> usize {
277 if let Some(count) = self.elem_counts.get_mut(val) {
278 if *count > times {
279 *count -= times;
280 self.size -= times;
281 return times;
282 }
283 self.size -= *count;
284 }
285 self.elem_counts.remove(val).unwrap_or(0)
286 }
287
288 /// Remove all of an element from the multiset.
289 ///
290 /// # Examples
291 ///
292 /// Remove all `5`s from a `HashMultiSet` containing 3 of them.
293 ///
294 /// ```
295 /// use modern_multiset::HashMultiSet;
296 ///
297 /// let mut multiset: HashMultiSet<i32> = HashMultiSet::new();
298 /// multiset.insert_times(5,3);
299 /// assert!(multiset.count_of(&5) == 3);
300 /// multiset.remove_all(&5);
301 /// assert!(multiset.count_of(&5) == 0);
302 /// assert!(multiset.len() == 0);
303 /// ```
304 pub fn remove_all(&mut self, val: &K) {
305 self.size -= self.elem_counts.get(val).unwrap_or(&0);
306 self.elem_counts.remove(val);
307 }
308
309 /// Counts the occurrences of `val`.
310 ///
311 /// # Examples
312 ///
313 /// ```
314 /// use modern_multiset::HashMultiSet;
315 ///
316 /// let mut multiset: HashMultiSet<u8> = HashMultiSet::new();
317 /// multiset.insert(0);
318 /// multiset.insert(0);
319 /// multiset.insert(1);
320 /// multiset.insert(0);
321 /// assert_eq!(3, multiset.count_of(&0));
322 /// assert_eq!(1, multiset.count_of(&1));
323 /// ```
324 pub fn count_of(&self, val: &K) -> usize {
325 self.elem_counts.get(val).map_or(0, |x| *x)
326 }
327}
328
329impl<T> Add for HashMultiSet<T>
330where
331 T: Eq + Hash + Clone,
332{
333 type Output = HashMultiSet<T>;
334
335 /// Combine two `HashMultiSet`s by adding the number of each
336 /// distinct element.
337 ///
338 /// # Examples
339 ///
340 /// ```
341 /// use modern_multiset::HashMultiSet;
342 /// use std::iter::FromIterator;
343 ///
344 /// let lhs: HashMultiSet<isize> = FromIterator::from_iter(vec![1,2,3]);
345 /// let rhs: HashMultiSet<isize> = FromIterator::from_iter(vec![1,1,4]);
346 /// let combined = lhs + rhs;
347 /// assert_eq!(3, combined.count_of(&1));
348 /// assert_eq!(1, combined.count_of(&2));
349 /// assert_eq!(1, combined.count_of(&3));
350 /// assert_eq!(1, combined.count_of(&4));
351 /// assert_eq!(0, combined.count_of(&5));
352 /// ```
353 fn add(mut self, rhs: HashMultiSet<T>) -> HashMultiSet<T> {
354 for (val, count) in rhs.elem_counts {
355 self.insert_times(val, count);
356 }
357 self
358 }
359}
360
361impl<T> Sub for HashMultiSet<T>
362where
363 T: Eq + Hash + Clone,
364{
365 type Output = HashMultiSet<T>;
366
367 /// Combine two `HashMultiSet`s by removing elements
368 /// in the second multiset from the first. As with `remove()`
369 /// (and set difference), excess elements in the second
370 /// multiset are ignored.
371 ///
372 /// # Examples
373 ///
374 /// ```
375 /// use modern_multiset::HashMultiSet;
376 /// use std::iter::FromIterator;
377 ///
378 /// let lhs: HashMultiSet<isize> = FromIterator::from_iter(vec![1,2,3]);
379 /// let rhs: HashMultiSet<isize> = FromIterator::from_iter(vec![1,1,4]);
380 /// let combined = lhs - rhs;
381 /// assert_eq!(0, combined.count_of(&1));
382 /// assert_eq!(1, combined.count_of(&2));
383 /// assert_eq!(1, combined.count_of(&3));
384 /// assert_eq!(0, combined.count_of(&4));
385 /// ```
386 fn sub(mut self, rhs: HashMultiSet<T>) -> HashMultiSet<T> {
387 for (val, count) in rhs.elem_counts {
388 self.remove_times(&val, count);
389 }
390 self
391 }
392}
393
394impl<A> FromIterator<A> for HashMultiSet<A>
395where
396 A: Eq + Hash,
397{
398 /// Creates a new `HashMultiSet` from the elements in an iterable.
399 ///
400 /// # Examples
401 ///
402 /// Count occurrences of each `char` in `"hello world"`:
403 ///
404 /// ```
405 /// use modern_multiset::HashMultiSet;
406 /// use std::iter::FromIterator;
407 ///
408 /// let vals = vec!['h','e','l','l','o',' ','w','o','r','l','d'];
409 /// let multiset: HashMultiSet<char> = FromIterator::from_iter(vals);
410 /// assert_eq!(1, multiset.count_of(&'h'));
411 /// assert_eq!(3, multiset.count_of(&'l'));
412 /// assert_eq!(0, multiset.count_of(&'z'));
413 /// ```
414 fn from_iter<T>(iterable: T) -> HashMultiSet<A>
415 where
416 T: IntoIterator<Item = A>,
417 {
418 let mut multiset: HashMultiSet<A> = HashMultiSet::new();
419 for elem in iterable {
420 multiset.insert(elem);
421 }
422 multiset
423 }
424}
425
426impl<T> PartialEq for HashMultiSet<T>
427where
428 T: Eq + Hash,
429{
430 fn eq(&self, other: &HashMultiSet<T>) -> bool {
431 if self.len() != other.len() {
432 return false;
433 }
434
435 self.elem_counts
436 .iter()
437 .all(|(key, count)| other.contains(key) && other.elem_counts.get(key).unwrap() == count)
438 }
439}
440
441impl<T> fmt::Debug for HashMultiSet<T>
442where
443 T: Eq + Hash + fmt::Debug,
444{
445 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
446 f.debug_set().entries(self.iter()).finish()
447 }
448}
449
450#[cfg(test)]
451mod test_multiset {
452 use super::HashMultiSet;
453
454 #[test]
455 fn test_iterate() {
456 let mut a = HashMultiSet::new();
457 for i in 0..16 {
458 a.insert(i);
459 }
460 for i in 0..8 {
461 a.insert(i);
462 }
463 for i in 0..4 {
464 a.insert(i);
465 }
466 let mut observed: u16 = 0;
467 let mut observed_twice: u16 = 0;
468 let mut observed_thrice: u16 = 0;
469 for k in a.iter() {
470 let bit = 1 << *k;
471 if observed & bit == 0 {
472 observed |= bit;
473 } else if observed_twice & bit == 0 {
474 observed_twice |= bit;
475 } else if observed_thrice & bit == 0 {
476 observed_thrice |= bit;
477 }
478 }
479 assert_eq!(observed, 0xFFFF);
480 assert_eq!(observed_twice, 0xFF);
481 assert_eq!(observed_thrice, 0xF);
482 }
483
484 #[test]
485 fn test_eq() {
486 let mut s1 = HashMultiSet::new();
487 s1.insert(0);
488 s1.insert(1);
489 s1.insert(1);
490 let mut s2 = HashMultiSet::new();
491 s2.insert(0);
492 s2.insert(1);
493 assert!(s1 != s2);
494 s2.insert(1);
495 assert_eq!(s1, s2);
496 }
497
498 #[test]
499 fn test_size() {
500 let mut set = HashMultiSet::new();
501
502 assert_eq!(set.len(), 0);
503 set.insert('a');
504 assert_eq!(set.len(), 1);
505 set.remove(&'a');
506 assert_eq!(set.len(), 0);
507
508 set.insert_times('b', 4);
509 assert_eq!(set.len(), 4);
510 set.insert('b');
511 assert_eq!(set.len(), 5);
512 set.remove_all(&'b');
513 assert_eq!(set.len(), 0);
514
515 set.insert_times('c', 6);
516 assert_eq!(set.len(), 6);
517 set.insert_times('c', 3);
518 assert_eq!(set.len(), 9);
519 set.insert('c');
520 assert_eq!(set.len(), 10);
521 set.insert('d');
522 assert_eq!(set.len(), 11);
523 set.insert_times('d', 3);
524 assert_eq!(set.len(), 14);
525 set.remove_all(&'c');
526 assert_eq!(set.len(), 4);
527 set.remove(&'d');
528 assert_eq!(set.len(), 3);
529 set.remove_times(&'d', 2);
530 assert_eq!(set.len(), 1);
531 set.remove(&'d');
532 assert_eq!(set.len(), 0);
533 }
534}