Skip to main content

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}