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