json_ld_core/object/node/
multiset.rs

1use std::hash::{BuildHasher, Hash};
2
3#[derive(Debug, Default, Clone, Copy)]
4pub struct DeterministicHasherBuilder;
5
6impl BuildHasher for DeterministicHasherBuilder {
7	type Hasher = std::collections::hash_map::DefaultHasher;
8
9	fn build_hasher(&self) -> Self::Hasher {
10		Self::Hasher::new()
11	}
12}
13
14use json_ld_syntax::IntoJsonWithContext;
15
16/// Multi-set of values.
17#[derive(Debug, Clone)]
18pub struct Multiset<T, S = DeterministicHasherBuilder> {
19	data: Vec<T>,
20	hasher: S,
21}
22
23impl<T, S: Default> Default for Multiset<T, S> {
24	fn default() -> Self {
25		Self {
26			data: Vec::new(),
27			hasher: S::default(),
28		}
29	}
30}
31
32impl<T, S> Multiset<T, S> {
33	pub fn new() -> Self
34	where
35		S: Default,
36	{
37		Self::default()
38	}
39
40	pub fn with_capacity(cap: usize) -> Self
41	where
42		S: Default,
43	{
44		Self {
45			data: Vec::with_capacity(cap),
46			hasher: S::default(),
47		}
48	}
49
50	pub fn len(&self) -> usize {
51		self.data.len()
52	}
53
54	pub fn is_empty(&self) -> bool {
55		self.data.is_empty()
56	}
57
58	pub fn contains(&self, value: &T) -> bool
59	where
60		T: PartialEq,
61	{
62		self.data.contains(value)
63	}
64
65	pub fn iter(&self) -> core::slice::Iter<T> {
66		self.data.iter()
67	}
68
69	pub fn iter_mut(&mut self) -> core::slice::IterMut<T> {
70		self.data.iter_mut()
71	}
72
73	pub fn as_slice(&self) -> &[T] {
74		&self.data
75	}
76
77	// pub fn into_stripped(self) -> Multiset<locspan::Stripped<T>, S> {
78	// 	Multiset { data: unsafe { core::mem::transmute(self.data) }, hasher: self.hasher }
79	// }
80}
81
82impl<T: Hash, S: BuildHasher> Multiset<T, S> {
83	pub fn singleton(value: T) -> Self
84	where
85		S: Default,
86	{
87		let mut result = Self::new();
88		result.insert(value);
89		result
90	}
91
92	pub fn insert(&mut self, value: T) {
93		self.data.push(value);
94	}
95
96	pub fn insert_unique(&mut self, value: T) -> bool
97	where
98		T: PartialEq,
99	{
100		if self.contains(&value) {
101			false
102		} else {
103			self.insert(value);
104			true
105		}
106	}
107}
108
109impl<'a, T, S> IntoIterator for &'a Multiset<T, S> {
110	type Item = &'a T;
111	type IntoIter = core::slice::Iter<'a, T>;
112
113	fn into_iter(self) -> Self::IntoIter {
114		self.iter()
115	}
116}
117
118impl<'a, T, S> IntoIterator for &'a mut Multiset<T, S> {
119	type Item = &'a mut T;
120	type IntoIter = core::slice::IterMut<'a, T>;
121
122	fn into_iter(self) -> Self::IntoIter {
123		self.iter_mut()
124	}
125}
126
127impl<T, S> IntoIterator for Multiset<T, S> {
128	type Item = T;
129	type IntoIter = std::vec::IntoIter<T>;
130
131	fn into_iter(self) -> Self::IntoIter {
132		self.data.into_iter()
133	}
134}
135
136impl<T: Hash, S: Default + BuildHasher> FromIterator<T> for Multiset<T, S> {
137	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
138		let mut result = Self::new();
139
140		for item in iter {
141			result.insert(item)
142		}
143
144		result
145	}
146}
147
148impl<T: Hash, S: BuildHasher> Extend<T> for Multiset<T, S> {
149	fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
150		for item in iter {
151			self.insert(item)
152		}
153	}
154}
155
156impl<T: PartialEq<U>, U, S, P> PartialEq<Multiset<U, P>> for Multiset<T, S> {
157	fn eq(&self, other: &Multiset<U, P>) -> bool {
158		compare_unordered(&self.data, &other.data)
159	}
160}
161
162pub(crate) fn compare_unordered<T: PartialEq<U>, U>(a: &[T], b: &[U]) -> bool {
163	if a.len() == b.len() {
164		let mut free_indexes = Vec::new();
165		free_indexes.resize(a.len(), true);
166
167		for item in a {
168			match free_indexes
169				.iter_mut()
170				.enumerate()
171				.find(|(i, free)| **free && item == &b[*i])
172			{
173				Some((_, free)) => *free = false,
174				None => return false,
175			}
176		}
177
178		true
179	} else {
180		false
181	}
182}
183
184pub(crate) fn compare_unordered_opt<T: PartialEq<U>, U>(a: Option<&[T]>, b: Option<&[U]>) -> bool {
185	match (a, b) {
186		(Some(a), Some(b)) => compare_unordered(a, b),
187		(None, None) => true,
188		_ => false,
189	}
190}
191
192impl<T: Eq, S> Eq for Multiset<T, S> {}
193
194impl<T: Hash, S: BuildHasher> Hash for Multiset<T, S> {
195	fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
196		let mut hash = 0u64;
197
198		for item in self {
199			hash = hash.wrapping_add(self.hasher.hash_one(item));
200		}
201
202		state.write_u64(hash)
203	}
204}
205
206impl<T: IntoJsonWithContext<N>, S, N> IntoJsonWithContext<N> for Multiset<T, S> {
207	fn into_json_with(self, vocabulary: &N) -> json_syntax::Value {
208		json_syntax::Value::Array(
209			self.into_iter()
210				.map(|item| item.into_json_with(vocabulary))
211				.collect(),
212		)
213	}
214}
json_ld_core/object/node/multiset.rs

json_ld_core/object/node/
multiset.rs
