Skip to main content

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}