1use core::borrow::Borrow;
2use core::cmp::Ordering;
3use core::fmt;
4use core::mem;
5use core::ptr;
6use core::slice;
7
8use alloc::vec;
9use alloc::vec::Vec;
10
11#[derive(Clone, PartialEq, Eq, Hash)]
12pub struct VecSet<T>(Vec<T>);
13
14impl<T> VecSet<T> {
15 #[inline]
16 #[must_use]
17 pub const fn new() -> Self {
18 Self(Vec::new())
19 }
20
21 #[inline]
22 #[must_use]
23 pub fn from_single(val: T) -> Self {
24 Self(vec![val])
25 }
26
27 #[inline]
28 #[must_use]
29 pub fn with_capacity(cap: usize) -> Self {
30 Self(Vec::with_capacity(cap))
31 }
32
33 #[inline]
34 #[must_use]
35 pub fn len(&self) -> usize {
36 self.0.len()
37 }
38
39 #[inline]
40 #[must_use]
41 pub fn is_empty(&self) -> bool {
42 self.0.is_empty()
43 }
44
45 #[inline]
46 #[must_use]
47 pub fn as_slice(&self) -> &[T] {
48 self.0.as_slice()
49 }
50
51 #[inline]
52 #[must_use]
53 pub fn iter(&self) -> Iter<'_, T> {
54 Iter(self.0.as_slice().iter())
55 }
56
57 #[inline]
58 #[must_use]
59 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
60 IterMut(self.0.as_mut_slice().iter_mut())
61 }
62}
63
64impl<T: Ord> VecSet<T> {
65 #[inline]
66 #[must_use]
67 pub fn from_vec(mut v: Vec<T>) -> Self {
68 v.sort_unstable();
69 v.dedup_by(|x, first| x == first);
70 Self(v)
71 }
72
73 fn search<Q>(&self, val: &Q) -> Result<usize, usize>
74 where
75 T: Borrow<Q>,
76 Q: Ord + ?Sized,
77 {
78 self.0.binary_search_by(|probe| probe.borrow().cmp(val))
79 }
80
81 #[inline]
82 #[must_use]
83 pub fn contains<Q>(&self, val: &Q) -> bool
84 where
85 T: Borrow<Q>,
86 Q: Ord + ?Sized,
87 {
88 self.search(val).is_ok()
89 }
90
91 #[inline]
92 #[must_use]
93 pub fn insert(&mut self, val: T) -> Option<T> {
94 match self.search(&val) {
95 Ok(idx) => {
96 let prev = unsafe { &mut self.0.get_unchecked_mut(idx) };
97 Some(mem::replace(prev, val))
98 }
99 Err(idx) => {
100 self.0.insert(idx, val);
101 None
102 }
103 }
104 }
105
106 #[inline]
107 #[must_use]
108 pub fn remove<Q>(&mut self, val: &Q) -> Option<T>
109 where
110 T: Borrow<Q>,
111 Q: Ord + ?Sized,
112 {
113 match self.search(val) {
114 Ok(idx) => Some(self.0.remove(idx)),
115 Err(_) => None,
116 }
117 }
118
119 #[inline]
120 pub fn union_copied_inplace(&mut self, other: &Self)
121 where
122 T: Copy,
123 {
124 let lhs = &mut self.0;
125 let rhs = &other.0;
126
127 let ans_cap = lhs.len().checked_add(rhs.len()).unwrap();
128 lhs.reserve(ans_cap);
129
130 unsafe {
131 let p1 = lhs.as_ptr();
132 let p2 = rhs.as_ptr();
133 let p3 = lhs.as_mut_ptr().add(lhs.len());
134 let e1 = p1.add(lhs.len());
135 let e2 = p2.add(rhs.len());
136
137 let end = raw_union_copied(p1, p2, p3, e1, e2);
138
139 let dst = lhs.as_mut_ptr();
140 let src = dst.add(lhs.len());
141 let cnt = end.offset_from(src) as usize;
142 ptr::copy(src, dst, cnt);
143 lhs.set_len(cnt)
144 }
145 }
146
147 #[inline]
148 #[must_use]
149 pub fn union_copied(&self, other: &Self) -> Self
150 where
151 T: Copy,
152 {
153 let lhs = &self.0;
154 let rhs = &other.0;
155
156 let ans_cap = lhs.len().checked_add(rhs.len()).unwrap();
157 let mut ans = Vec::with_capacity(ans_cap);
158
159 unsafe {
160 let p1 = lhs.as_ptr();
161 let p2 = rhs.as_ptr();
162 let p3 = ans.as_mut_ptr();
163 let e1 = p1.add(lhs.len());
164 let e2 = p2.add(rhs.len());
165
166 let end = raw_union_copied(p1, p2, p3, e1, e2);
167 let cnt = end.offset_from(p3) as usize;
168 ans.set_len(cnt);
169 }
170
171 Self(ans)
172 }
173
174 #[inline]
175 #[must_use]
176 pub fn intersection_copied(&self, other: &Self) -> Self
177 where
178 T: Copy,
179 {
180 let lhs = &self.0;
181 let rhs = &other.0;
182
183 let ans_cap = lhs.len().min(rhs.len());
184 let mut ans = Vec::with_capacity(ans_cap);
185
186 unsafe {
187 let p1 = lhs.as_ptr();
188 let p2 = rhs.as_ptr();
189 let p3 = ans.as_mut_ptr();
190 let e1 = p1.add(lhs.len());
191 let e2 = p2.add(rhs.len());
192
193 let end = raw_intersection_copied(p1, p2, p3, e1, e2);
194 let cnt = end.offset_from(p3) as usize;
195 ans.set_len(cnt)
196 }
197
198 Self(ans)
199 }
200
201 #[inline]
202 pub fn difference_copied_inplace(&mut self, other: &Self)
203 where
204 T: Copy,
205 {
206 let lhs = &mut self.0;
207 let rhs = &other.0;
208
209 let ans_cap = lhs.len();
210 lhs.reserve(ans_cap);
211
212 unsafe {
213 let p1 = lhs.as_ptr();
214 let p2 = rhs.as_ptr();
215 let p3 = lhs.as_mut_ptr().add(lhs.len());
216 let e1 = p1.add(lhs.len());
217 let e2 = p2.add(rhs.len());
218
219 let end = raw_difference_copied(p1, p2, p3, e1, e2);
220
221 let dst = lhs.as_mut_ptr();
222 let src = dst.add(lhs.len());
223 let cnt = end.offset_from(src) as usize;
224 ptr::copy(src, dst, cnt);
225 lhs.set_len(cnt)
226 }
227 }
228}
229
230impl<T: Ord> From<Vec<T>> for VecSet<T> {
231 #[inline]
232 fn from(v: Vec<T>) -> Self {
233 Self::from_vec(v)
234 }
235}
236
237impl<T: Ord> FromIterator<T> for VecSet<T> {
238 #[inline]
239 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
240 Self::from_vec(iter.into_iter().collect())
241 }
242}
243
244impl<T> Default for VecSet<T> {
245 #[inline]
246 #[must_use]
247 fn default() -> Self {
248 Self::new()
249 }
250}
251
252impl<T: fmt::Debug> fmt::Debug for VecSet<T> {
253 #[inline]
254 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255 f.debug_set().entries(self.0.iter()).finish()
256 }
257}
258
259pub struct Iter<'a, T>(slice::Iter<'a, T>);
260
261impl<'a, T> Iterator for Iter<'a, T> {
262 type Item = &'a T;
263
264 #[inline]
265 fn next(&mut self) -> Option<Self::Item> {
266 self.0.next()
267 }
268
269 #[inline]
270 fn size_hint(&self) -> (usize, Option<usize>) {
271 self.0.size_hint()
272 }
273}
274
275impl<'a, T> IntoIterator for &'a VecSet<T> {
276 type Item = &'a T;
277
278 type IntoIter = Iter<'a, T>;
279
280 #[inline]
281 fn into_iter(self) -> Self::IntoIter {
282 self.iter()
283 }
284}
285
286pub struct IterMut<'a, T>(slice::IterMut<'a, T>);
287
288impl<'a, T> Iterator for IterMut<'a, T> {
289 type Item = &'a mut T;
290
291 #[inline]
292 fn next(&mut self) -> Option<Self::Item> {
293 self.0.next()
294 }
295
296 #[inline]
297 fn size_hint(&self) -> (usize, Option<usize>) {
298 self.0.size_hint()
299 }
300}
301
302impl<'a, T> IntoIterator for &'a mut VecSet<T> {
303 type Item = &'a mut T;
304
305 type IntoIter = IterMut<'a, T>;
306
307 #[inline]
308 fn into_iter(self) -> Self::IntoIter {
309 self.iter_mut()
310 }
311}
312
313pub struct IntoIter<T>(vec::IntoIter<T>);
314
315impl<T> Iterator for IntoIter<T> {
316 type Item = T;
317
318 #[inline]
319 fn next(&mut self) -> Option<Self::Item> {
320 self.0.next()
321 }
322
323 #[inline]
324 fn size_hint(&self) -> (usize, Option<usize>) {
325 self.0.size_hint()
326 }
327}
328
329impl<T> IntoIterator for VecSet<T> {
330 type Item = T;
331
332 type IntoIter = IntoIter<T>;
333
334 #[inline]
335 fn into_iter(self) -> Self::IntoIter {
336 IntoIter(self.0.into_iter())
337 }
338}
339
340unsafe fn raw_union_copied<T: Copy + Ord>(
341 mut p1: *const T,
342 mut p2: *const T,
343 mut p3: *mut T,
344 e1: *const T,
345 e2: *const T,
346) -> *mut T {
347 while p1 < e1 && p2 < e2 {
348 match Ord::cmp(&*p1, &*p2) {
349 Ordering::Less => {
350 ptr::copy_nonoverlapping(p1, p3, 1);
351 p1 = p1.add(1);
352 }
353 Ordering::Greater => {
354 ptr::copy_nonoverlapping(p2, p3, 1);
355 p2 = p2.add(1);
356 }
357 Ordering::Equal => {
358 ptr::copy_nonoverlapping(p1, p3, 1);
359 p1 = p1.add(1);
360 p2 = p2.add(1);
361 }
362 }
363 p3 = p3.add(1);
364 }
365 if p1 < e1 {
366 let cnt = e1.offset_from(p1) as usize;
367 ptr::copy_nonoverlapping(p1, p3, cnt);
368 p3 = p3.add(cnt);
369 }
370 if p2 < e2 {
371 let cnt = e2.offset_from(p2) as usize;
372 ptr::copy_nonoverlapping(p2, p3, cnt);
373 p3 = p3.add(cnt);
374 }
375 p3
376}
377
378unsafe fn raw_intersection_copied<T: Copy + Ord>(
379 mut p1: *const T,
380 mut p2: *const T,
381 mut p3: *mut T,
382 e1: *const T,
383 e2: *const T,
384) -> *mut T {
385 while p1 < e1 && p2 < e2 {
386 match Ord::cmp(&*p1, &*p2) {
387 Ordering::Less => {
388 p1 = p1.add(1);
389 }
390 Ordering::Greater => {
391 p2 = p2.add(1);
392 }
393 Ordering::Equal => {
394 ptr::copy_nonoverlapping(p1, p3, 1);
395 p1 = p1.add(1);
396 p2 = p2.add(1);
397 p3 = p3.add(1);
398 }
399 }
400 }
401 p3
402}
403
404unsafe fn raw_difference_copied<T: Copy + Ord>(
405 mut p1: *const T,
406 mut p2: *const T,
407 mut p3: *mut T,
408 e1: *const T,
409 e2: *const T,
410) -> *mut T {
411 while p1 < e1 && p2 < e2 {
412 match Ord::cmp(&*p1, &*p2) {
413 Ordering::Less => {
414 ptr::copy_nonoverlapping(p1, p3, 1);
415 p1 = p1.add(1);
416 p3 = p3.add(1);
417 }
418 Ordering::Greater => {
419 p2 = p2.add(1);
420 }
421 Ordering::Equal => {
422 p1 = p1.add(1);
423 p2 = p2.add(1);
424 }
425 }
426 }
427 if p1 < e1 {
428 let cnt = e1.offset_from(p1) as usize;
429 ptr::copy_nonoverlapping(p1, p3, cnt);
430 p3 = p3.add(cnt);
431 }
432 p3
433}
434
435#[cfg(test)]
436mod tests {
437 use super::*;
438
439 #[test]
440 fn from_vec() {
441 let s = VecSet::<u64>::from_vec(vec![1, 4, 3, 2, 5, 7, 9, 2, 4, 6, 7, 8, 0]);
442 assert_eq!(s.as_slice(), &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
443 }
444
445 #[test]
446 fn union() {
447 {
448 let mut s1 = VecSet::<u64>::from_iter([1, 2, 3, 5]);
449 let s2 = VecSet::<u64>::from_iter([2, 4, 5, 6]);
450 s1.union_copied_inplace(&s2);
451 assert_eq!(s1.as_slice(), &[1, 2, 3, 4, 5, 6])
452 }
453 {
454 let s1 = VecSet::<u64>::from_iter([1, 2, 3, 5]);
455 let s2 = VecSet::<u64>::from_iter([2, 4, 5, 6]);
456 let s3 = s1.union_copied(&s2);
457 assert_eq!(s3.as_slice(), &[1, 2, 3, 4, 5, 6])
458 }
459 }
460
461 #[test]
462 fn intersection() {
463 let s1 = VecSet::<u64>::from_vec(vec![1, 2, 3, 5]);
464 let s2 = VecSet::<u64>::from_vec(vec![2, 4, 5, 6]);
465 let s3 = s1.intersection_copied(&s2);
466 assert_eq!(s3.as_slice(), &[2, 5])
467 }
468
469 #[test]
470 fn difference() {
471 {
472 let mut s1 = VecSet::<u64>::from_iter([1, 2, 3, 5]);
473 let s2 = VecSet::<u64>::from_iter([2, 4, 5, 6]);
474 s1.difference_copied_inplace(&s2);
475 assert_eq!(s1.as_slice(), &[1, 3])
476 }
477 {
478 let mut s1 = VecSet::<u64>::from_iter([1, 2, 3, 5]);
479 let s2 = VecSet::<u64>::from_iter([]);
480 s1.difference_copied_inplace(&s2);
481 assert_eq!(s1.as_slice(), &[1, 2, 3, 5])
482 }
483 {
484 let mut s1 = VecSet::<u64>::from_iter([3]);
485 let s2 = VecSet::<u64>::from_iter([1, 2, 4, 5]);
486 s1.difference_copied_inplace(&s2);
487 assert_eq!(s1.as_slice(), &[3])
488 }
489 }
490}
491
492#[cfg(feature = "serde")]
493mod serde_impl {
494 use super::*;
495
496 use serde::{Deserialize, Serialize};
497
498 impl<'de, T: Ord + Deserialize<'de>> Deserialize<'de> for VecSet<T> {
499 #[inline]
500 fn deserialize<D>(deserializer: D) -> Result<VecSet<T>, D::Error>
501 where
502 D: ::serde::de::Deserializer<'de>,
503 {
504 <Vec<T>>::deserialize(deserializer).map(VecSet::from_vec)
505 }
506 }
507
508 impl<T: Serialize> Serialize for VecSet<T> {
509 #[inline]
510 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
511 where
512 S: ::serde::ser::Serializer,
513 {
514 <[T]>::serialize(self.as_slice(), serializer)
515 }
516 }
517}