static_mapset/ordered_slice_set.rs
1use core::{
2 borrow::Borrow,
3 ops::{Bound, RangeBounds}
4};
5
6use crate::{
7 internal::ordered_set::{self as internal, order},
8 ordered::Ordered
9};
10
11type Iter<'a, T> = internal::Iter<'a, T>;
12type Cursor<'a, T> = internal::Cursor<'a, T>;
13
14type Difference<'a, T, I1, I2> = internal::Difference<'a, T, I1, I2>;
15type Intersection<'a, T, I1, I2> = internal::Intersection<'a, T, I1, I2>;
16type Union<'a, T, I1, I2> = internal::Union<'a, T, I1, I2>;
17
18#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
19/// An ordered set based on an ordered slice.
20/// This structures provides a subset of the methods offered by the standard library's
21/// `BTreeSet`.
22///
23/// # Examples
24///
25/// ```
26/// use static_mapset::OrderedSliceSet;
27///
28/// let data = [
29/// "A Dance With Dragons",
30/// "To Kill a Mockingbird",
31/// "The Odyssey",
32/// "The Great Gatsby"
33/// ];
34/// let books = OrderedSliceSet::new_unchecked(&data);
35///
36/// // Check for a specific one.
37/// if !books.contains("The Winds of Winter") {
38/// println!("We have {} books, but The Winds of Winter ain't one.",
39/// books.iter().count());
40/// }
41///
42/// // Iterate over everything.
43/// for book in &books {
44/// println!("{book}");
45/// }
46/// ```
47pub struct OrderedSliceSet<'a, T> {
48 inner: &'a [T],
49 len: usize
50}
51
52impl<'a, T> Clone for OrderedSliceSet<'a, T> {
53 fn clone(&self) -> Self {
54 *self
55 }
56}
57
58impl<'a, T> Copy for OrderedSliceSet<'a, T> {}
59
60impl<'a, T> OrderedSliceSet<'a, T> {
61 /// Sorts the slice and creates an `OrderedSliceSet`.
62 /// Duplicate keys are removed, keeping the last occurrence.
63 ///
64 /// # Complexity
65 ///
66 /// Linearithmic in `self.len()`.
67 ///
68 /// # Examples
69 ///
70 /// ```
71 /// use static_mapset::OrderedSliceSet;
72 ///
73 /// let mut data = [3, 1, 2];
74 /// let set = OrderedSliceSet::new(&mut data);
75 /// assert_eq!(set.first(), Some(&1));
76 /// ```
77 pub fn new(items: &'a mut [T]) -> Self
78 where
79 T: Ord
80 {
81 let len = order(items);
82 OrderedSliceSet { inner: items, len }
83 }
84
85 /// Creates an `OrderedSliceSet` from an immutable slice without sorting.
86 ///
87 /// The slice must be sorted in ascending order with no duplicate keys.
88 ///
89 /// # Complexity
90 ///
91 /// Constant.
92 ///
93 /// # Examples
94 ///
95 /// ```
96 /// use static_mapset::OrderedSliceSet;
97 ///
98 /// static MAP: OrderedSliceSet<i32> = OrderedSliceSet::new_unchecked(&[1, 2]);
99 /// assert!(MAP.contains(&2));
100 ///
101 /// // Incorrect key order or duplicates cause undefined behavior:
102 /// // let map = OrderedSliceSet::new_unchecked(&[3, 2]);
103 /// // let map = OrderedSliceSet::new_unchecked(&[2, 2]);
104 /// ```
105 pub const fn new_unchecked(ordered_items: &'a [T]) -> Self {
106 let len = ordered_items.len();
107 OrderedSliceSet {
108 inner: ordered_items,
109 len
110 }
111 }
112
113 /// Returns `true` if the map is ordered correctly.
114 ///
115 /// # Complexity
116 ///
117 /// Linear in `self.len()`.
118 ///
119 /// # Examples
120 ///
121 /// ```
122 /// use static_mapset::OrderedSliceSet;
123 ///
124 /// let map = OrderedSliceSet::new_unchecked(&[1, 2, 3]);
125 /// assert!(map.is_valid());
126 ///
127 /// let map = OrderedSliceSet::new_unchecked(&[1, 2, 2]);
128 /// assert!(!map.is_valid());
129 /// let map = OrderedSliceSet::new_unchecked(&[1.0, 2.0, f64::NAN]);
130 /// assert!(!map.is_valid());
131 /// ```
132 pub fn is_valid(&self) -> bool
133 where
134 T: PartialOrd
135 {
136 internal::is_valid(&self.inner[..self.len])
137 }
138
139 /// Returns `true` if the set contains an element equal to the value.
140 ///
141 /// The value may be any borrowed form of the set's element type,
142 /// but the ordering on the borrowed form *must* match the
143 /// ordering on the element type.
144 /// If equal elements are present, this returns `true` if any matching element exists.
145 ///
146 /// # Complexity
147 ///
148 /// Logarithmic in `self.len()`.
149 ///
150 /// # Examples
151 ///
152 /// ```
153 /// use static_mapset::OrderedSliceSet;
154 ///
155 /// let data = [1, 2, 3];
156 /// let set = OrderedSliceSet::new_unchecked(&data);
157 /// assert_eq!(set.contains(&1), true);
158 /// assert_eq!(set.contains(&4), false);
159 ///
160 /// let data = [1.0, 2.0, 3.0];
161 /// let set = OrderedSliceSet::new_unchecked(&data);
162 /// // f64::NAN is incomparable, so value lookups by NaN never match.
163 /// assert_eq!(set.contains(&f64::NAN), false);
164 /// ```
165 pub fn contains<Q>(&self, value: &Q) -> bool
166 where
167 T: Borrow<Q>,
168 Q: PartialOrd + ?Sized
169 {
170 internal::contains(&self.inner[..self.len], value)
171 }
172
173 /// Visits the elements representing the difference,
174 /// i.e., the elements that are in `self` but not in `other`,
175 /// in ascending order.
176 ///
177 /// # Complexity
178 ///
179 /// Linear in `self.len() + other.len()` to iterate all elements.
180 ///
181 /// # Examples
182 ///
183 /// ```
184 /// use static_mapset::OrderedSliceSet;
185 ///
186 /// let mut a_data = [1, 2];
187 /// let a = OrderedSliceSet::new(&mut a_data);
188 ///
189 /// let mut b_data = [2, 3];
190 /// let b = OrderedSliceSet::new(&mut b_data);
191 ///
192 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
193 /// assert_eq!(diff, [1]);
194 /// ```
195 pub fn difference<O: Ordered<'a, T>>(&'a self, other: &'a O) -> Difference<'a, T, Iter<'a, T>, O::Iter>
196 where
197 T: PartialOrd
198 {
199 internal::difference(self, other)
200 }
201
202 /// Returns a reference to the first element in the set, if any.
203 /// This element is always the minimum of all elements in the set.
204 ///
205 /// # Complexity
206 ///
207 /// Constant.
208 ///
209 /// # Examples
210 ///
211 /// Basic usage:
212 ///
213 /// ```
214 /// use static_mapset::OrderedSliceSet;
215 ///
216 /// let empty: &[i32] = &[];
217 /// let set = OrderedSliceSet::new_unchecked(empty);
218 /// assert_eq!(set.first(), None);
219 ///
220 /// let mut data = [1, 2];
221 /// let set = OrderedSliceSet::new(&mut data);
222 /// assert_eq!(set.first(), Some(&1));
223 /// ```
224 pub fn first(&self) -> Option<&T> {
225 self.inner[..self.len].first()
226 }
227
228 /// Returns a reference to the element in the set, if any, that is equal to
229 /// the value.
230 ///
231 /// The value may be any borrowed form of the set's element type,
232 /// but the ordering on the borrowed form *must* match the
233 /// ordering on the element type.
234 ///
235 /// # Complexity
236 ///
237 /// Logarithmic in `self.len()`.
238 ///
239 /// # Examples
240 ///
241 /// ```
242 /// use static_mapset::OrderedSliceSet;
243 ///
244 /// let data = [1, 2, 3];
245 /// let set = OrderedSliceSet::new_unchecked(&data);
246 /// assert_eq!(set.get(&2), Some(&2));
247 /// assert_eq!(set.get(&4), None);
248 ///
249 /// let data = [1.0, 2.0, 3.0];
250 /// let set = OrderedSliceSet::new_unchecked(&data);
251 /// // f64::NAN is incomparable, so value lookups by NaN never match.
252 /// assert_eq!(set.get(&f64::NAN), None);
253 /// ```
254 pub fn get<Q>(&self, value: &Q) -> Option<&T>
255 where
256 T: Borrow<Q>,
257 Q: PartialOrd + ?Sized
258 {
259 internal::get(&self.inner[..self.len], value)
260 }
261
262 /// Visits the elements representing the intersection,
263 /// i.e., the elements that are both in `self` and `other`,
264 /// in ascending order.
265 ///
266 /// # Complexity
267 ///
268 /// Linear in `self.len() + other.len()` to iterate all elements.
269 ///
270 /// # Examples
271 ///
272 /// ```
273 /// use static_mapset::OrderedSliceSet;
274 ///
275 /// let mut a_data = [1, 2];
276 /// let a = OrderedSliceSet::new(&mut a_data);
277 ///
278 /// let mut b_data = [2, 3];
279 /// let b = OrderedSliceSet::new(&mut b_data);
280 ///
281 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
282 /// assert_eq!(intersection, [2]);
283 /// ```
284 pub fn intersection<O: Ordered<'a, T>>(&'a self, other: &'a O) -> Intersection<'a, T, Iter<'a, T>, O::Iter>
285 where
286 T: PartialOrd
287 {
288 internal::intersection(self, other)
289 }
290
291 /// Returns `true` if `self` has no elements in common with `other`.
292 /// This is equivalent to checking for an empty intersection.
293 ///
294 /// # Complexity
295 ///
296 /// Linear in `self.len() + other.len()`.
297 ///
298 /// # Examples
299 ///
300 /// ```
301 /// use static_mapset::OrderedSliceSet;
302 ///
303 /// let mut a_data = [1, 2, 3];
304 /// let a = OrderedSliceSet::new(&mut a_data);
305 ///
306 /// let mut b_data = [4, 5];
307 /// let b = OrderedSliceSet::new(&mut b_data);
308 ///
309 /// let mut c_data = [1, 5];
310 /// let c = OrderedSliceSet::new(&mut c_data);
311 ///
312 /// assert_eq!(a.is_disjoint(&b), true);
313 /// assert_eq!(a.is_disjoint(&c), false);
314 /// ```
315 pub fn is_disjoint<O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
316 where
317 T: PartialOrd
318 {
319 internal::is_disjoint(self, other)
320 }
321
322 /// Returns `true` if the set contains no elements.
323 ///
324 /// # Complexity
325 ///
326 /// Constant.
327 ///
328 /// # Examples
329 ///
330 /// ```
331 /// use static_mapset::OrderedSliceSet;
332 ///
333 /// let data: &[i32] = &[];
334 /// let set = OrderedSliceSet::new_unchecked(data);
335 /// assert!(set.is_empty());
336 /// let data = &[1];
337 /// let set = OrderedSliceSet::new_unchecked(data);
338 /// assert!(!set.is_empty());
339 /// ```
340 pub const fn is_empty(&self) -> bool {
341 self.len == 0
342 }
343
344 /// Returns `true` if the set is a subset of another,
345 /// i.e., `other` contains at least all the elements in `self`.
346 ///
347 /// # Complexity
348 ///
349 /// Linear in `self.len() + other.len()`.
350 ///
351 /// # Examples
352 ///
353 /// ```
354 /// use static_mapset::OrderedSliceSet;
355 ///
356 /// let mut sup_data = [1, 2, 3];
357 /// let sup = OrderedSliceSet::new(&mut sup_data);
358 ///
359 /// let mut set_data = [2];
360 /// let set = OrderedSliceSet::new(&mut set_data);
361 ///
362 /// let mut not_subset_data = [2, 4];
363 /// let not_subset = OrderedSliceSet::new(&mut not_subset_data);
364 ///
365 /// assert_eq!(set.is_subset(&sup), true);
366 /// assert_eq!(not_subset.is_subset(&sup), false);
367 /// ```
368 pub fn is_subset<O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
369 where
370 T: PartialOrd
371 {
372 internal::is_subset(self, other)
373 }
374
375 /// Returns `true` if the set is a superset of another,
376 /// i.e., `self` contains at least all the elements in `other`.
377 ///
378 /// # Complexity
379 ///
380 /// Linear in `self.len() + other.len()`.
381 ///
382 /// # Examples
383 ///
384 /// ```
385 /// use static_mapset::OrderedSliceSet;
386 ///
387 /// let mut sub_data = [1, 2];
388 /// let sub = OrderedSliceSet::new(&mut sub_data);
389 ///
390 /// let mut set_data = [0, 1, 2];
391 /// let set = OrderedSliceSet::new(&mut set_data);
392 ///
393 /// let mut not_superset_data = [0, 1];
394 /// let not_superset = OrderedSliceSet::new(&mut not_superset_data);
395 ///
396 /// assert_eq!(set.is_superset(&sub), true);
397 /// assert_eq!(not_superset.is_superset(&sub), false);
398 /// ```
399 pub fn is_superset<O: Ordered<'a, T>>(&'a self, other: &'a O) -> bool
400 where
401 T: PartialOrd
402 {
403 internal::is_superset(self, other)
404 }
405
406 /// Gets an iterator that visits the elements in the set in ascending order.
407 ///
408 /// # Complexity
409 ///
410 /// Linear in `self.len()` to iterate all elements.
411 ///
412 /// # Examples
413 ///
414 /// ```
415 /// use static_mapset::OrderedSliceSet;
416 ///
417 /// let mut data = [2, 1];
418 /// let set = OrderedSliceSet::new(&mut data);
419 ///
420 /// let items: Vec<_> = set.iter().cloned().collect();
421 /// assert_eq!(items, [1, 2]);
422 /// ```
423 pub fn iter(&self) -> Iter<'_, T> {
424 internal::iter(&self.inner[..self.len])
425 }
426
427 /// Returns a reference to the last element in the set, if any.
428 /// This element is always the maximum of all elements in the set.
429 ///
430 /// # Complexity
431 ///
432 /// Constant.
433 ///
434 /// # Examples
435 ///
436 /// Basic usage:
437 ///
438 /// ```
439 /// use static_mapset::OrderedSliceSet;
440 ///
441 /// let empty: &[i32] = &[];
442 /// let set = OrderedSliceSet::new_unchecked(empty);
443 /// assert_eq!(set.last(), None);
444 ///
445 /// let mut data = [1];
446 /// let set = OrderedSliceSet::new(&mut data);
447 /// assert_eq!(set.last(), Some(&1));
448 ///
449 /// let mut data = [1, 2];
450 /// let set = OrderedSliceSet::new(&mut data);
451 /// assert_eq!(set.last(), Some(&2));
452 /// ```
453 pub fn last(&self) -> Option<&T> {
454 self.inner[..self.len].last()
455 }
456
457 /// Returns a [`Cursor`] pointing at the gap before the smallest element
458 /// greater than the given bound.
459 ///
460 /// Passing `Bound::Included(x)` will return a cursor pointing to the
461 /// gap before the smallest element greater than or equal to `x`.
462 ///
463 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
464 /// gap before the smallest element greater than `x`.
465 ///
466 /// Passing `Bound::Unbounded` will return a cursor pointing to the
467 /// gap before the smallest element in the set.
468 /// With equal elements, `Included` points before the first equal element and `Excluded` points after the last equal element.
469 ///
470 /// # Complexity
471 ///
472 /// Logarithmic in `self.len()` to find the bounds, and linear in the number of yielded elements to iterate them all.
473 ///
474 /// # Examples
475 ///
476 /// ```
477 ///
478 /// use static_mapset::OrderedSliceSet;
479 /// use std::ops::Bound;
480 ///
481 /// let data = [1, 2, 3, 4];
482 /// let set = OrderedSliceSet::new_unchecked(&data);
483 ///
484 /// let cursor = set.lower_bound(Bound::Included(&2));
485 /// assert_eq!(cursor.peek_prev(), Some(&1));
486 /// assert_eq!(cursor.peek_next(), Some(&2));
487 ///
488 /// let cursor = set.lower_bound(Bound::Excluded(&2));
489 /// assert_eq!(cursor.peek_prev(), Some(&2));
490 /// assert_eq!(cursor.peek_next(), Some(&3));
491 ///
492 /// let cursor = set.lower_bound(Bound::Unbounded);
493 /// assert_eq!(cursor.peek_prev(), None);
494 /// assert_eq!(cursor.peek_next(), Some(&1));
495 ///
496 /// let data = [1.0, 2.0, 3.0];
497 /// let set = OrderedSliceSet::new_unchecked(&data);
498 /// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
499 /// let cursor = set.lower_bound(Bound::Included(&f64::NAN));
500 /// assert_eq!(cursor.peek_prev(), Some(&3.0));
501 /// ```
502 pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
503 where
504 T: Borrow<Q>,
505 Q: PartialOrd + ?Sized
506 {
507 internal::lower_bound(&self.inner[..self.len], bound)
508 }
509
510 /// Constructs a double-ended iterator over a sub-range of elements in the set.
511 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
512 /// yield elements from min (inclusive) to max (exclusive).
513 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
514 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
515 /// range from 4 to 10.
516 ///
517 /// # Panics
518 ///
519 /// Panics if range `start > end`.
520 /// Panics if range `start == end` and both bounds are `Excluded`.
521 /// Panics if `start` (or `end`() is incomparable and `end` (or `start`) is bounded.
522 ///
523 /// # Complexity
524 ///
525 /// Logarithmic in `self.len()`.
526 ///
527 /// # Examples
528 ///
529 /// ```
530 /// use static_mapset::OrderedSliceSet;
531 /// use std::ops::Bound::Included;
532 ///
533 /// let data = [3, 5, 8];
534 /// let set = OrderedSliceSet::new_unchecked(&data);
535 /// for &elem in set.range((Included(&4), Included(&8))) {
536 /// println!("{elem}");
537 /// }
538 /// assert_eq!(Some(&5), set.range(4..).next());
539 /// ```
540 pub fn range<Q, R>(&self, range: R) -> Iter<'_, T>
541 where
542 T: Borrow<Q>,
543 Q: PartialOrd + ?Sized,
544 R: RangeBounds<Q>
545 {
546 internal::range(&self.inner[..self.len], range)
547 }
548
549 /// Visits the elements representing the union,
550 /// i.e., all the elements in `self` or `other`, without duplicates,
551 /// in ascending order.
552 ///
553 /// # Complexity
554 ///
555 /// Linear in `self.len() + other.len()` to iterate all elements.
556 ///
557 /// # Examples
558 ///
559 /// ```
560 /// use static_mapset::OrderedSliceSet;
561 ///
562 /// let mut a_data = [1];
563 /// let a = OrderedSliceSet::new(&mut a_data);
564 ///
565 /// let mut b_data = [2];
566 /// let b = OrderedSliceSet::new(&mut b_data);
567 ///
568 /// let union: Vec<_> = a.union(&b).cloned().collect();
569 /// assert_eq!(union, [1, 2]);
570 /// ```
571 pub fn union<O: Ordered<'a, T>>(&'a self, other: &'a O) -> Union<'a, T, Iter<'a, T>, O::Iter>
572 where
573 T: PartialOrd
574 {
575 internal::union(self, other)
576 }
577
578 /// Returns a [`Cursor`] pointing at the gap after the greatest element
579 /// smaller than the given bound.
580 ///
581 /// Passing `Bound::Included(x)` will return a cursor pointing to the
582 /// gap after the greatest element smaller than or equal to `x`.
583 ///
584 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
585 /// gap after the greatest element smaller than `x`.
586 ///
587 /// Passing `Bound::Unbounded` will return a cursor pointing to the
588 /// gap after the greatest element in the set.
589 /// With equal elements, `Excluded` points before the first equal element and `Included` points after the last equal element.
590 ///
591 /// # Complexity
592 ///
593 /// Logarithmic in `self.len()`.
594 ///
595 /// # Examples
596 ///
597 /// ```
598 ///
599 /// use static_mapset::OrderedSliceSet;
600 /// use std::ops::Bound;
601 ///
602 /// let data = [1, 2, 3, 4];
603 /// let set = OrderedSliceSet::new_unchecked(&data);
604 ///
605 /// let cursor = set.upper_bound(Bound::Included(&3));
606 /// assert_eq!(cursor.peek_prev(), Some(&3));
607 /// assert_eq!(cursor.peek_next(), Some(&4));
608 ///
609 /// let cursor = set.upper_bound(Bound::Excluded(&3));
610 /// assert_eq!(cursor.peek_prev(), Some(&2));
611 /// assert_eq!(cursor.peek_next(), Some(&3));
612 ///
613 /// let cursor = set.upper_bound(Bound::Unbounded);
614 /// assert_eq!(cursor.peek_prev(), Some(&4));
615 /// assert_eq!(cursor.peek_next(), None);
616 ///
617 /// let data = [1.0, 2.0, 3.0];
618 /// let set = OrderedSliceSet::new_unchecked(&data);
619 /// // f64::NAN is incomparable, so the cursor points to the gap after the last key.
620 /// let cursor = set.upper_bound(Bound::Included(&f64::NAN));
621 /// assert_eq!(cursor.peek_prev(), Some(&3.0));
622 /// ```
623 pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
624 where
625 T: Borrow<Q>,
626 Q: PartialOrd + ?Sized
627 {
628 internal::upper_bound(&self.inner[..self.len], bound)
629 }
630}
631
632impl<'a, T: PartialOrd> Ordered<'a, T> for OrderedSliceSet<'a, T> {
633 type Iter = Iter<'a, T>;
634
635 fn ordered_iter(&'a self) -> Self::Iter {
636 self.iter()
637 }
638}
639
640impl<'a, T> IntoIterator for &'a OrderedSliceSet<'a, T> {
641 type Item = &'a T;
642 type IntoIter = Iter<'a, T>;
643
644 fn into_iter(self) -> Self::IntoIter {
645 self.iter()
646 }
647}
648
649#[cfg(test)]
650mod tests {
651 use core::ops::Bound;
652
653 use super::*;
654
655 #[test]
656 fn test_new() {
657 let mut data = [5, 1, 3, 1];
658 let set = OrderedSliceSet::new(&mut data);
659 assert_eq!(set.iter().collect::<Vec<_>>(), vec![&1, &3, &5]);
660 }
661
662 #[test]
663 fn test_contains() {
664 let data = [1, 3, 5, 7];
665 let set = OrderedSliceSet::new_unchecked(&data);
666 assert!(set.contains(&1));
667 assert!(set.contains(&7));
668 assert!(!set.contains(&2));
669 assert!(!set.contains(&8));
670 }
671
672 #[test]
673 fn test_get() {
674 let data = [10, 20, 30];
675 let set = OrderedSliceSet::new_unchecked(&data);
676 assert_eq!(set.get(&20), Some(&20));
677 assert_eq!(set.get(&15), None);
678 }
679
680 #[test]
681 fn test_first_last() {
682 let data = [2, 4, 6, 8];
683 let set = OrderedSliceSet::new_unchecked(&data);
684 assert_eq!(set.first(), Some(&2));
685 assert_eq!(set.last(), Some(&8));
686
687 let empty: &[i32] = &[];
688 let empty_set = OrderedSliceSet::new_unchecked(empty);
689 assert_eq!(empty_set.first(), None);
690 assert_eq!(empty_set.last(), None);
691 }
692
693 #[test]
694 fn test_iter_and_into_iter() {
695 let data = [1, 2, 3];
696 let set = OrderedSliceSet::new_unchecked(&data);
697 let v1: Vec<_> = set.iter().collect();
698 let v2: Vec<_> = set.into_iter().collect();
699 assert_eq!(v1, vec![&1, &2, &3]);
700 assert_eq!(v2, vec![&1, &2, &3]);
701 }
702
703 #[test]
704 fn test_subset_superset_disjoint() {
705 let a_data = [1, 2, 3];
706 let b_data = [1, 2, 3, 4, 5];
707 let c_data = [6, 7, 8];
708 let a = OrderedSliceSet::new_unchecked(&a_data);
709 let b = OrderedSliceSet::new_unchecked(&b_data);
710 let c = OrderedSliceSet::new_unchecked(&c_data);
711
712 assert!(a.is_subset(&b));
713 assert!(b.is_superset(&a));
714 assert!(a.is_disjoint(&c));
715 assert!(!a.is_disjoint(&b));
716 assert!(c.is_disjoint(&a));
717 }
718
719 #[test]
720 fn test_difference() {
721 let a_data = [1, 2, 3, 4, 5];
722 let b_data = [2, 4];
723 let a = OrderedSliceSet::new_unchecked(&a_data);
724 let b = OrderedSliceSet::new_unchecked(&b_data);
725 let diff: Vec<_> = a.difference(&b).collect();
726 assert_eq!(diff, vec![&1, &3, &5]);
727 }
728
729 #[test]
730 fn test_intersection() {
731 let a_data = [1, 2, 3, 4, 5];
732 let b_data = [2, 4, 6];
733 let a = OrderedSliceSet::new_unchecked(&a_data);
734 let b = OrderedSliceSet::new_unchecked(&b_data);
735 let inter: Vec<_> = a.intersection(&b).collect();
736 assert_eq!(inter, vec![&2, &4]);
737 }
738
739 #[test]
740 fn test_union() {
741 let a_data = [1, 3, 5];
742 let b_data = [2, 3, 4];
743 let a = OrderedSliceSet::new_unchecked(&a_data);
744 let b = OrderedSliceSet::new_unchecked(&b_data);
745 let uni: Vec<_> = a.union(&b).collect();
746 assert_eq!(uni, vec![&1, &2, &3, &4, &5]);
747 }
748
749 #[test]
750 fn test_lower_bound() {
751 let data = [1, 3, 5, 7];
752 let set = OrderedSliceSet::new_unchecked(&data);
753 assert_eq!(set.lower_bound(Bound::Included(&3)).next(), Some(&3));
754 assert_eq!(set.lower_bound(Bound::Excluded(&3)).next(), Some(&5));
755 assert_eq!(set.lower_bound(Bound::Included(&4)).next(), Some(&5));
756 assert_eq!(set.lower_bound(Bound::Included(&8)).next(), None);
757 }
758
759 #[test]
760 fn test_upper_bound() {
761 let data = [1, 3, 5, 7];
762 let set = OrderedSliceSet::new_unchecked(&data);
763 assert_eq!(set.upper_bound(Bound::Included(&3)).next(), Some(&5));
764 assert_eq!(set.upper_bound(Bound::Excluded(&3)).next(), Some(&3));
765 assert_eq!(set.upper_bound(Bound::Unbounded).next(), None);
766 }
767
768 #[test]
769 fn test_range() {
770 let data = [1, 2, 3, 4, 5];
771 let set = OrderedSliceSet::new_unchecked(&data);
772 assert_eq!(set.range(2..=4).copied().collect::<Vec<_>>(), vec![2, 3, 4]);
773 assert_eq!(set.range(2..4).copied().collect::<Vec<_>>(), vec![2, 3]);
774 assert_eq!(set.range(..3).copied().collect::<Vec<_>>(), vec![1, 2]);
775 assert_eq!(set.range(3..).copied().collect::<Vec<_>>(), vec![3, 4, 5]);
776 }
777
778 #[test]
779 fn test_is_valid() {
780 let mut sorted = [1, 2, 3, 4];
781 assert!(OrderedSliceSet::new(&mut sorted).iter().is_sorted());
782 let mut unsorted = [3, 1, 2];
783 assert!(OrderedSliceSet::new(&mut unsorted).iter().is_sorted());
784 }
785}