btree_range_map/generic/
multimap.rs

1use crate::{
2	generic::{
3		map::{IntoIter, Iter},
4		RangeMap,
5	},
6	AnyRange, AsRange,
7};
8use btree_slab::generic::Node;
9use cc_traits::{SetMut, SimpleCollectionMut, SimpleCollectionRef, Slab, SlabMut};
10use range_traits::{Measure, PartialEnum};
11
12/// Multi map.
13///
14/// In a multi map, each key is associated to a set of values.
15/// The type parameter `S` is the set type. It can be replaced by anything
16/// implementing the [`cc_traits::SetMut`] trait, such as the standard
17/// [`BTreeSet`](std::collections::BTreeSet) and [`HashSet`](std::collections::HashSet).
18#[derive(Clone)]
19pub struct RangeMultiMap<K, S, C> {
20	map: RangeMap<K, S, C>,
21}
22
23impl<K, S, C> RangeMultiMap<K, S, C> {
24	pub fn new() -> RangeMultiMap<K, S, C>
25	where
26		C: Default,
27	{
28		RangeMultiMap {
29			map: RangeMap::new(),
30		}
31	}
32}
33
34impl<K, S, C: Default> Default for RangeMultiMap<K, S, C> {
35	fn default() -> Self {
36		Self::new()
37	}
38}
39
40impl<K, S, C: Slab<Node<AnyRange<K>, S>>> RangeMultiMap<K, S, C>
41where
42	C: SimpleCollectionRef,
43{
44	pub fn iter(&self) -> Iter<K, S, C> {
45		self.map.iter()
46	}
47}
48
49impl<'a, K: Clone + PartialOrd + Measure, S, C: Slab<Node<AnyRange<K>, S>>> IntoIterator
50	for &'a RangeMultiMap<K, S, C>
51where
52	C: SimpleCollectionRef,
53{
54	type Item = (&'a AnyRange<K>, &'a S);
55	type IntoIter = Iter<'a, K, S, C>;
56
57	fn into_iter(self) -> Self::IntoIter {
58		self.iter()
59	}
60}
61
62impl<K, S, C: SlabMut<Node<AnyRange<K>, S>>> RangeMultiMap<K, S, C>
63where
64	C: SimpleCollectionRef,
65	C: SimpleCollectionMut,
66{
67	pub fn insert<R: AsRange<Item = K>, V>(&mut self, key: R, value: V)
68	where
69		K: Clone + PartialEnum + Measure,
70		V: PartialEq + Clone,
71		S: SetMut<V> + PartialEq + Clone + Default,
72	{
73		self.map.update(key, |set_opt| {
74			let mut result = match set_opt {
75				Some(set) => set.clone(),
76				None => S::default(),
77			};
78
79			result.insert(value.clone());
80			Some(result)
81		})
82	}
83
84	pub fn remove<R: AsRange<Item = K>, V>(&mut self, key: R, value: &V)
85	where
86		K: Clone + PartialEnum + Measure,
87		V: PartialEq + Clone,
88		S: SetMut<V> + PartialEq + Clone + Default,
89	{
90		self.map.update(key, |set_opt| match set_opt {
91			Some(set) => {
92				let mut result = set.clone();
93				result.remove(value);
94				if result.is_empty() {
95					None
96				} else {
97					Some(result)
98				}
99			}
100			None => None,
101		})
102	}
103}
104
105impl<K: Clone + PartialOrd + Measure, S, C: SlabMut<Node<AnyRange<K>, S>>> IntoIterator
106	for RangeMultiMap<K, S, C>
107where
108	C: SimpleCollectionRef,
109	C: SimpleCollectionMut,
110{
111	type Item = (AnyRange<K>, S);
112	type IntoIter = IntoIter<K, S, C>;
113
114	fn into_iter(self) -> Self::IntoIter {
115		self.map.into_iter()
116	}
117}
btree_range_map/generic/multimap.rs

btree_range_map/generic/
multimap.rs
