1mod bitpage;
21mod bitset;
22mod input_bit_stream;
23mod output_bit_stream;
24pub mod sparse_bit_set;
25
26pub use bitset::U32Set;
27use core::ops::{Bound, RangeBounds};
28use font_types::{GlyphId, GlyphId16, NameId, Tag};
29use std::hash::Hash;
30use std::marker::PhantomData;
31use std::ops::RangeInclusive;
32use std::{
33 cmp::Ordering,
34 fmt::{Debug, Display},
35};
36
37#[derive(Clone)]
39pub struct IntSet<T>(Membership, PhantomData<T>);
40
41pub trait Domain: Sized + Copy {
57 fn to_u32(&self) -> u32;
61
62 fn contains(value: u32) -> bool;
64
65 fn from_u32(member: InDomain) -> Self;
69
70 fn is_continuous() -> bool;
72
73 fn ordered_values() -> impl DoubleEndedIterator<Item = u32>;
78
79 fn ordered_values_range(range: RangeInclusive<Self>) -> impl DoubleEndedIterator<Item = u32>;
84
85 fn count() -> u64;
87}
88
89pub struct InDomain(u32);
93
94#[derive(Clone, Debug, Hash, PartialEq, Eq)]
95#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
96enum Membership {
97 Inclusive(U32Set),
99
100 Exclusive(U32Set),
102}
103
104impl InDomain {
105 pub fn value(&self) -> u32 {
106 self.0
107 }
108}
109
110impl<T> Default for IntSet<T> {
111 fn default() -> IntSet<T> {
112 IntSet::empty()
113 }
114}
115
116impl<T: Domain> IntSet<T> {
117 pub fn iter(&self) -> impl DoubleEndedIterator<Item = T> + '_ {
122 let u32_iter = match &self.0 {
123 Membership::Inclusive(s) => Iter::new_bidirectional(s.iter(), None),
124 Membership::Exclusive(s) => {
125 Iter::new_bidirectional(s.iter(), Some(T::ordered_values()))
126 }
127 };
128 u32_iter.map(|v| T::from_u32(InDomain(v)))
129 }
130
131 pub fn inclusive_iter(&self) -> Option<impl DoubleEndedIterator<Item = T> + '_> {
133 match &self.0 {
134 Membership::Inclusive(s) => Some(s.iter().map(|v| T::from_u32(InDomain(v)))),
135 Membership::Exclusive(_) => None,
136 }
137 }
138
139 fn iter_from_u32(&self, value: T) -> impl Iterator<Item = u32> + '_ {
140 match &self.0 {
141 Membership::Inclusive(s) => Iter::new(s.iter_from(value.to_u32()), None),
142 Membership::Exclusive(s) => {
143 let value_u32 = value.to_u32();
144 let max = T::ordered_values().next_back();
145 let it = max.map(|max| T::ordered_values_range(value..=T::from_u32(InDomain(max))));
146 let min = it.and_then(|mut it| it.next());
147
148 if let (Some(min), Some(max)) = (min, max) {
149 Iter::new(
150 s.iter_from(value_u32),
151 Some(T::ordered_values_range(
152 T::from_u32(InDomain(min))..=T::from_u32(InDomain(max)),
153 )),
154 )
155 } else {
156 let mut it = Iter::new(s.iter_from(u32::MAX), None);
158 it.next();
159 it
160 }
161 }
162 }
163 }
164
165 pub fn iter_after(&self, value: T) -> impl Iterator<Item = T> + '_ {
170 self.range((Bound::Excluded(value), Bound::Unbounded))
171 }
172
173 pub fn range<R: RangeBounds<T>>(&self, range: R) -> impl Iterator<Item = T> + '_ {
175 let (first, it) = match range.start_bound() {
176 Bound::Included(start) => (None, self.iter_from_u32(*start)),
177 Bound::Excluded(start) => {
178 let mut it = self.iter_from_u32(*start);
179 let first = it.next().filter(|v| v != &start.to_u32());
180 (first, it)
181 }
182 Bound::Unbounded => {
183 let min = T::from_u32(InDomain(T::ordered_values().next().unwrap()));
184 (None, self.iter_from_u32(min))
185 }
186 };
187
188 let range_end = range.end_bound().cloned();
189 first
190 .into_iter()
191 .chain(it)
192 .take_while(move |v| match range_end {
193 Bound::Included(end) => *v <= end.to_u32(),
194 Bound::Excluded(end) => *v < end.to_u32(),
195 Bound::Unbounded => true,
196 })
197 .map(move |v| T::from_u32(InDomain(v)))
198 }
199
200 pub fn iter_ranges(&self) -> impl Iterator<Item = RangeInclusive<T>> + '_ {
202 self.iter_ranges_invertible(false)
203 }
204
205 pub fn iter_excluded_ranges(&self) -> impl Iterator<Item = RangeInclusive<T>> + '_ {
207 self.iter_ranges_invertible(true)
208 }
209
210 fn iter_ranges_invertible(
211 &self,
212 inverted: bool,
213 ) -> impl Iterator<Item = RangeInclusive<T>> + '_ {
214 let u32_iter = match (&self.0, inverted) {
215 (Membership::Inclusive(s), false) | (Membership::Exclusive(s), true)
216 if T::is_continuous() =>
217 {
218 RangeIter::Inclusive::<_, _, T> {
219 ranges: s.iter_ranges(),
220 }
221 }
222 (Membership::Inclusive(s), false) | (Membership::Exclusive(s), true) => {
223 RangeIter::InclusiveDiscontinuous::<_, _, T> {
224 ranges: s.iter_ranges(),
225 current_range: None,
226 phantom: PhantomData::<T>,
227 }
228 }
229 (Membership::Exclusive(s), false) | (Membership::Inclusive(s), true)
230 if T::is_continuous() =>
231 {
232 RangeIter::Exclusive::<_, _, T> {
233 ranges: s.iter_ranges(),
234 min: T::ordered_values().next().unwrap(),
235 max: T::ordered_values().next_back().unwrap(),
236 done: false,
237 }
238 }
239 (Membership::Exclusive(s), false) | (Membership::Inclusive(s), true) => {
240 RangeIter::ExclusiveDiscontinuous::<_, _, T> {
241 all_values: Some(T::ordered_values()),
242 set: s,
243 next_value: None,
244 }
245 }
246 };
247
248 u32_iter.map(|r| T::from_u32(InDomain(*r.start()))..=T::from_u32(InDomain(*r.end())))
249 }
250
251 pub fn insert(&mut self, val: T) -> bool {
255 let val = val.to_u32();
256 match &mut self.0 {
257 Membership::Inclusive(s) => s.insert(val),
258 Membership::Exclusive(s) => s.remove(val),
259 }
260 }
261
262 pub fn insert_range(&mut self, range: RangeInclusive<T>) {
264 if T::is_continuous() {
265 let range = range.start().to_u32()..=range.end().to_u32();
266 match &mut self.0 {
267 Membership::Inclusive(s) => s.insert_range(range),
268 Membership::Exclusive(s) => s.remove_range(range),
269 }
270 } else {
271 let range = T::ordered_values_range(range);
272 match &mut self.0 {
273 Membership::Inclusive(s) => s.extend(range),
274 Membership::Exclusive(s) => s.remove_all(range),
275 }
276 }
277 }
278
279 pub fn extend_unsorted<U: IntoIterator<Item = T>>(&mut self, iter: U) {
283 let iter = iter.into_iter().map(|v| v.to_u32());
284 match &mut self.0 {
285 Membership::Inclusive(s) => s.extend_unsorted(iter),
286 Membership::Exclusive(s) => s.remove_all(iter),
287 }
288 }
289
290 pub fn remove(&mut self, val: T) -> bool {
292 let val = val.to_u32();
293 match &mut self.0 {
294 Membership::Inclusive(s) => s.remove(val),
295 Membership::Exclusive(s) => s.insert(val),
296 }
297 }
298
299 pub fn remove_all<U: IntoIterator<Item = T>>(&mut self, iter: U) {
301 let iter = iter.into_iter().map(|v| v.to_u32());
302 match &mut self.0 {
303 Membership::Inclusive(s) => s.remove_all(iter),
304 Membership::Exclusive(s) => s.extend(iter),
305 }
306 }
307
308 pub fn remove_range(&mut self, range: RangeInclusive<T>) {
310 if T::is_continuous() {
311 let range = range.start().to_u32()..=range.end().to_u32();
312 match &mut self.0 {
313 Membership::Inclusive(s) => s.remove_range(range),
314 Membership::Exclusive(s) => s.insert_range(range),
315 }
316 } else {
317 let range = T::ordered_values_range(range);
318 match &mut self.0 {
319 Membership::Inclusive(s) => s.remove_all(range),
320 Membership::Exclusive(s) => s.extend(range),
321 }
322 }
323 }
324
325 pub fn union(&mut self, other: &IntSet<T>) {
327 match (&mut self.0, &other.0) {
328 (Membership::Inclusive(a), Membership::Inclusive(b)) => a.union(b),
329 (Membership::Inclusive(a), Membership::Exclusive(b)) => {
330 a.reversed_subtract(b);
331 self.invert();
332 }
333 (Membership::Exclusive(a), Membership::Inclusive(b)) => a.subtract(b),
334 (Membership::Exclusive(a), Membership::Exclusive(b)) => a.intersect(b),
335 }
336 }
337
338 pub fn intersect(&mut self, other: &IntSet<T>) {
340 match (&mut self.0, &other.0) {
341 (Membership::Inclusive(a), Membership::Inclusive(b)) => a.intersect(b),
342 (Membership::Inclusive(a), Membership::Exclusive(b)) => a.subtract(b),
343 (Membership::Exclusive(a), Membership::Inclusive(b)) => {
344 a.reversed_subtract(b);
345 self.invert();
346 }
347 (Membership::Exclusive(a), Membership::Exclusive(b)) => a.union(b),
348 }
349 }
350
351 pub fn subtract(&mut self, other: &IntSet<T>) {
353 match (&mut self.0, &other.0) {
354 (Membership::Inclusive(a), Membership::Inclusive(b)) => a.subtract(b),
355 (Membership::Inclusive(a), Membership::Exclusive(b)) => a.intersect(b),
356 (Membership::Exclusive(a), Membership::Inclusive(b)) => a.union(b),
357 (Membership::Exclusive(a), Membership::Exclusive(b)) => {
358 a.reversed_subtract(b);
359 self.invert();
360 }
361 }
362 }
363
364 pub fn intersects_range(&self, range: RangeInclusive<T>) -> bool {
366 self.range(range).next().is_some()
367 }
368
369 pub fn intersects_set(&self, other: &IntSet<T>) -> bool {
371 let (a, b) = match (&self.0, &other.0) {
374 (Membership::Inclusive(us), Membership::Inclusive(them)) => {
375 return us.intersects_set(them);
377 }
378
379 (
380 Membership::Inclusive(us) | Membership::Exclusive(us),
381 Membership::Inclusive(them) | Membership::Exclusive(them),
382 ) => {
383 if us.num_pages() > them.num_pages() {
384 (self, other)
385 } else {
386 (other, self)
387 }
388 }
389 };
390
391 for range in b.iter_ranges() {
392 if a.intersects_range(range) {
393 return true;
394 }
395 }
396 false
397 }
398
399 pub fn is_subset(&self, other: &IntSet<T>) -> bool {
401 if self.len() > other.len() {
402 return false;
403 }
404
405 match (&self.0, &other.0) {
406 (Membership::Inclusive(a), Membership::Inclusive(b)) => a.is_subset(b),
407 (Membership::Inclusive(a), Membership::Exclusive(b)) => !a.intersects_set(b),
408 (Membership::Exclusive(a), Membership::Inclusive(b)) => {
409 a.len() + b.len() - a.intersection_len(b) == T::count()
414 }
415 (Membership::Exclusive(a), Membership::Exclusive(b)) => b.is_subset(a),
416 }
417 }
418
419 pub fn first(&self) -> Option<T> {
421 return self.iter().next();
422 }
423
424 pub fn last(&self) -> Option<T> {
426 return self.iter().next_back();
427 }
428
429 pub fn contains(&self, val: T) -> bool {
431 let val = val.to_u32();
432 match &self.0 {
433 Membership::Inclusive(s) => s.contains(val),
434 Membership::Exclusive(s) => !s.contains(val),
435 }
436 }
437
438 pub fn len(&self) -> u64 {
440 match &self.0 {
441 Membership::Inclusive(s) => s.len(),
442 Membership::Exclusive(s) => T::count() - s.len(),
443 }
444 }
445
446 pub fn is_empty(&self) -> bool {
448 self.len() == 0
449 }
450}
451
452impl IntSet<u32> {
453 pub(crate) fn from_bitset(set: U32Set) -> IntSet<u32> {
454 IntSet(Membership::Inclusive(set), PhantomData::<u32>)
455 }
456}
457
458impl<T> IntSet<T> {
459 pub const fn new() -> Self {
463 Self::empty()
464 }
465
466 pub const fn empty() -> Self {
468 IntSet(Membership::Inclusive(U32Set::empty()), PhantomData::<T>)
469 }
470
471 pub const fn all() -> Self {
473 IntSet(Membership::Exclusive(U32Set::empty()), PhantomData::<T>)
474 }
475
476 pub fn is_inverted(&self) -> bool {
478 match &self.0 {
479 Membership::Inclusive(_) => false,
480 Membership::Exclusive(_) => true,
481 }
482 }
483
484 pub fn invert(&mut self) {
486 let reuse_storage = match &mut self.0 {
487 Membership::Inclusive(s) | Membership::Exclusive(s) => {
490 std::mem::replace(s, U32Set::empty())
491 }
492 };
493
494 self.0 = match &mut self.0 {
496 Membership::Inclusive(_) => Membership::Exclusive(reuse_storage),
497 Membership::Exclusive(_) => Membership::Inclusive(reuse_storage),
498 };
499 }
500
501 pub fn clear(&mut self) {
503 let mut reuse_storage = match &mut self.0 {
504 Membership::Inclusive(s) => {
506 s.clear();
507 return;
508 }
509 Membership::Exclusive(s) => std::mem::replace(s, U32Set::empty()),
512 };
513 reuse_storage.clear();
515 self.0 = Membership::Inclusive(reuse_storage);
516 }
517}
518
519impl<T: Domain> FromIterator<T> for IntSet<T> {
520 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
521 let mut s = IntSet::empty();
522 s.extend(iter);
523 s
524 }
525}
526
527impl<T: Domain> Extend<T> for IntSet<T> {
528 fn extend<U: IntoIterator<Item = T>>(&mut self, iter: U) {
535 let iter = iter.into_iter().map(|v| v.to_u32());
536 match &mut self.0 {
537 Membership::Inclusive(s) => s.extend(iter),
538 Membership::Exclusive(s) => s.remove_all(iter),
539 }
540 }
541}
542
543impl<T: Domain> PartialEq for IntSet<T> {
544 fn eq(&self, other: &Self) -> bool {
545 match (&self.0, &other.0) {
546 (Membership::Inclusive(a), Membership::Inclusive(b)) => a == b,
547 (Membership::Exclusive(a), Membership::Exclusive(b)) => a == b,
548 (Membership::Inclusive(_), Membership::Exclusive(_))
549 | (Membership::Exclusive(_), Membership::Inclusive(_)) => {
550 if self.len() == other.len() {
555 let r = self
556 .iter_ranges()
557 .map(|r| r.start().to_u32()..=r.end().to_u32())
558 .eq(other
559 .iter_ranges()
560 .map(|r| r.start().to_u32()..=r.end().to_u32()));
561 r
562 } else {
563 false
565 }
566 }
567 }
568 }
569}
570
571impl<T: Domain> Hash for IntSet<T> {
572 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
573 self.iter_ranges()
578 .map(|r| r.start().to_u32()..=r.end().to_u32())
579 .for_each(|r| r.hash(state));
580 }
581}
582
583impl<T: Domain + Ord> Ord for IntSet<T> {
584 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
585 match (&self.0, &other.0) {
586 (Membership::Inclusive(a), Membership::Inclusive(b)) => a.cmp(b),
587 _ => {
588 let mut this = self
589 .iter_ranges()
590 .map(|r| r.start().to_u32()..=r.end().to_u32());
591 let mut other = other
592 .iter_ranges()
593 .map(|r| r.start().to_u32()..=r.end().to_u32());
594 loop {
595 match (this.next(), other.next()) {
596 (Some(a), Some(b)) => {
597 let cmp = a.start().cmp(b.start());
598 if cmp != Ordering::Equal {
599 return cmp;
600 }
601
602 match a.end().cmp(b.end()) {
603 Ordering::Equal => continue,
604 Ordering::Less => {
611 return if this.next().is_some() {
612 Ordering::Greater
613 } else {
614 Ordering::Less
615 };
616 }
617 Ordering::Greater => {
618 return if other.next().is_some() {
619 Ordering::Less
620 } else {
621 Ordering::Greater
622 };
623 }
624 }
625 }
626 (None, None) => return Ordering::Equal,
627 (None, Some(_)) => return Ordering::Less,
628 (Some(_), None) => return Ordering::Greater,
629 }
630 }
631 }
632 }
633 }
634}
635
636impl<T: Domain + Ord> PartialOrd for IntSet<T> {
637 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
638 Some(self.cmp(other))
639 }
640}
641
642impl<T: Domain> Eq for IntSet<T> {}
643
644impl<T: Domain, const N: usize> From<[T; N]> for IntSet<T> {
645 fn from(value: [T; N]) -> Self {
646 value.into_iter().collect()
647 }
648}
649
650impl<T: Domain + Debug> Debug for IntSet<T> {
651 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
652 f.debug_set().entries(self.iter()).finish()
653 }
654}
655
656impl<T> Display for IntSet<T>
657where
658 T: Domain + Display,
659{
660 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
661 write!(f, "{{ ")?;
662 let mut first = true;
663 for range in self.iter_ranges() {
664 if !first {
665 write!(f, ", ")?;
666 }
667 first = false;
668 write!(f, "{}..={}", range.start(), range.end())?;
669 }
670 write!(f, "}}")
671 }
672}
673
674#[cfg(feature = "serde")]
675impl<T: Domain> serde::Serialize for IntSet<T> {
676 fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
677 self.0.serialize(serializer)
678 }
679}
680
681#[cfg(feature = "serde")]
682impl<'de, T: Domain> serde::Deserialize<'de> for IntSet<T> {
683 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
684 where
685 D: serde::Deserializer<'de>,
686 {
687 let members = Membership::deserialize(deserializer)?;
688 let bits = match &members {
689 Membership::Inclusive(bit_set) => bit_set,
690 Membership::Exclusive(bit_set) => bit_set,
691 };
692
693 if let Some(bad) = bits.iter().find(|val| !T::contains(*val)) {
694 return Err(serde::de::Error::custom(format!(
695 "value '{bad}' out of range for domain {}",
696 std::any::type_name::<T>(),
697 )));
698 }
699 Ok(IntSet(members, PhantomData))
700 }
701}
702
703struct Iter<SetIter, AllValuesIter> {
704 set_values: SetIter,
705 all_values: Option<AllValuesIter>,
706 next_skipped_forward: Option<u32>,
707 next_skipped_backward: Option<u32>,
708}
709
710impl<SetIter, AllValuesIter> Iter<SetIter, AllValuesIter>
711where
712 SetIter: Iterator<Item = u32>,
713 AllValuesIter: Iterator<Item = u32>,
714{
715 fn new(
716 mut set_values: SetIter,
717 all_values: Option<AllValuesIter>,
718 ) -> Iter<SetIter, AllValuesIter> {
719 match all_values {
720 Some(_) => Iter {
721 next_skipped_forward: set_values.next(),
722 next_skipped_backward: None,
723 set_values,
724 all_values,
725 },
726 None => Iter {
727 next_skipped_forward: None,
728 next_skipped_backward: None,
729 set_values,
730 all_values,
731 },
732 }
733 }
734}
735
736impl<SetIter, AllValuesIter> Iter<SetIter, AllValuesIter>
737where
738 SetIter: DoubleEndedIterator<Item = u32>,
739 AllValuesIter: DoubleEndedIterator<Item = u32>,
740{
741 fn new_bidirectional(
742 mut set_values: SetIter,
743 all_values: Option<AllValuesIter>,
744 ) -> Iter<SetIter, AllValuesIter> {
745 match all_values {
746 Some(_) => Iter {
747 next_skipped_forward: set_values.next(),
748 next_skipped_backward: set_values.next_back(),
749 set_values,
750 all_values,
751 },
752 None => Iter {
753 set_values,
754 all_values,
755 next_skipped_forward: None,
756 next_skipped_backward: None,
757 },
758 }
759 }
760}
761
762impl<SetIter, AllValuesIter> Iterator for Iter<SetIter, AllValuesIter>
763where
764 SetIter: Iterator<Item = u32>,
765 AllValuesIter: Iterator<Item = u32>,
766{
767 type Item = u32;
768
769 fn next(&mut self) -> Option<u32> {
770 let Some(all_values_it) = &mut self.all_values else {
771 return self.set_values.next();
772 };
773
774 for index in all_values_it.by_ref() {
775 let index = index.to_u32();
776 loop {
777 let Some(skip) = self.next_skipped_forward else {
778 if let Some(skip) = self.next_skipped_backward {
781 if skip == index {
782 break;
784 }
785 }
786 return Some(index);
788 };
789
790 if index < skip {
791 return Some(index);
793 }
794
795 self.next_skipped_forward = self.set_values.next();
796 if index > skip {
797 continue;
799 }
800
801 break;
803 }
804 }
805 None
806 }
807}
808
809impl<SetIter, AllValuesIter> DoubleEndedIterator for Iter<SetIter, AllValuesIter>
810where
811 SetIter: DoubleEndedIterator<Item = u32>,
812 AllValuesIter: DoubleEndedIterator<Item = u32>,
813{
814 fn next_back(&mut self) -> Option<Self::Item> {
815 let Some(all_values_it) = &mut self.all_values else {
816 return self.set_values.next_back();
817 };
818
819 for index in all_values_it.by_ref().rev() {
820 let index = index.to_u32();
821 loop {
822 let Some(skip) = self.next_skipped_backward else {
823 if let Some(skip) = self.next_skipped_forward {
826 if skip == index {
827 break;
829 }
830 }
831 return Some(index);
833 };
834
835 if index > skip {
836 return Some(index);
838 }
839
840 self.next_skipped_backward = self.set_values.next_back();
841 if index < skip {
842 continue;
844 }
845
846 break;
848 }
849 }
850 None
851 }
852}
853
854enum RangeIter<'a, InclusiveRangeIter, AllValuesIter, T>
855where
856 InclusiveRangeIter: Iterator<Item = RangeInclusive<u32>>,
857 AllValuesIter: Iterator<Item = u32>,
858 T: Domain,
859{
860 Inclusive {
861 ranges: InclusiveRangeIter,
862 },
863 InclusiveDiscontinuous {
864 ranges: InclusiveRangeIter,
865 current_range: Option<RangeInclusive<u32>>,
866 phantom: PhantomData<T>,
867 },
868 Exclusive {
869 ranges: InclusiveRangeIter,
870 min: u32,
871 max: u32,
872 done: bool,
873 },
874 ExclusiveDiscontinuous {
875 all_values: Option<AllValuesIter>,
876 set: &'a U32Set,
877 next_value: Option<u32>,
878 },
879}
880
881impl<InclusiveRangeIter, AllValuesIter, T> Iterator
882 for RangeIter<'_, InclusiveRangeIter, AllValuesIter, T>
883where
884 InclusiveRangeIter: Iterator<Item = RangeInclusive<u32>>,
885 AllValuesIter: Iterator<Item = u32>,
886 T: Domain,
887{
888 type Item = RangeInclusive<u32>;
889
890 fn next(&mut self) -> Option<Self::Item> {
891 match self {
892 RangeIter::Inclusive { ranges } => ranges.next(),
893 RangeIter::InclusiveDiscontinuous {
894 ranges,
895 current_range,
896 phantom: _,
897 } => loop {
898 let Some(next_range) = ranges.next() else {
903 return current_range.take();
905 };
906
907 let Some(range) = current_range.clone() else {
908 *current_range = Some(next_range);
910 continue;
911 };
912
913 if RangeIter::<InclusiveRangeIter, AllValuesIter, T>::are_values_adjacent(
915 *range.end(),
916 *next_range.start(),
917 ) {
918 *current_range = Some(*range.start()..=*next_range.end());
920 continue;
921 }
922
923 *current_range = Some(next_range);
925 return Some(range);
926 },
927 RangeIter::Exclusive {
928 ranges,
929 min,
930 max,
931 done,
932 } => RangeIter::<InclusiveRangeIter, AllValuesIter, T>::next_exclusive(
933 ranges, min, max, done,
934 ),
935 RangeIter::ExclusiveDiscontinuous {
936 all_values,
937 set,
938 next_value,
939 } => RangeIter::<InclusiveRangeIter, AllValuesIter, T>::next_discontinuous(
940 all_values, set, next_value,
941 ),
942 }
943 }
944}
945
946impl<'a, InclusiveRangeIter, AllValuesIter, T> RangeIter<'a, InclusiveRangeIter, AllValuesIter, T>
947where
948 InclusiveRangeIter: Iterator<Item = RangeInclusive<u32>>,
949 AllValuesIter: Iterator<Item = u32>,
950 T: Domain,
951{
952 fn next_exclusive(
954 ranges: &mut InclusiveRangeIter,
955 min: &mut u32,
956 max: &mut u32,
957 done: &mut bool,
958 ) -> Option<RangeInclusive<u32>> {
959 if *done {
960 return None;
961 }
962
963 loop {
964 let next_range = ranges.next();
965
966 let Some(next_range) = next_range else {
967 *done = true;
968 return Some(*min..=*max);
969 };
970
971 if next_range.contains(min) {
972 if *next_range.end() >= *max {
973 break;
974 }
975 *min = next_range.end() + 1;
976 continue;
977 }
978
979 let result = *min..=(next_range.start() - 1);
980 if *next_range.end() < *max {
981 *min = next_range.end() + 1;
982 } else {
983 *done = true;
984 }
985 return Some(result);
986 }
987
988 *done = true;
989 None
990 }
991
992 fn next_discontinuous(
994 all_values: &mut Option<AllValuesIter>,
995 set: &'a U32Set,
996 next_value: &mut Option<u32>,
997 ) -> Option<RangeInclusive<u32>> {
998 let all_values_iter = all_values.as_mut().unwrap();
999
1000 let mut current_range: Option<RangeInclusive<u32>> = None;
1001 loop {
1002 let next = next_value.take().or_else(|| all_values_iter.next());
1003 let Some(next) = next else {
1004 return current_range;
1006 };
1007
1008 if set.contains(next) {
1009 if let Some(range) = current_range {
1010 return Some(range);
1012 }
1013 continue;
1014 }
1015
1016 let Some(range) = current_range.as_ref() else {
1017 current_range = Some(next..=next);
1018 continue;
1019 };
1020
1021 current_range = Some(*range.start()..=next);
1022 }
1023 }
1024
1025 fn are_values_adjacent(a: u32, b: u32) -> bool {
1026 let mut it = T::ordered_values_range(T::from_u32(InDomain(a))..=T::from_u32(InDomain(b)));
1027 it.next(); if let Some(second) = it.next() {
1029 return second.to_u32() == b.to_u32();
1031 }
1032 false
1033 }
1034}
1035
1036impl Domain for u32 {
1037 fn to_u32(&self) -> u32 {
1038 *self
1039 }
1040
1041 fn from_u32(member: InDomain) -> u32 {
1042 member.value()
1043 }
1044
1045 fn contains(_value: u32) -> bool {
1046 true
1047 }
1048
1049 fn is_continuous() -> bool {
1050 true
1051 }
1052
1053 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1054 u32::MIN..=u32::MAX
1055 }
1056
1057 fn ordered_values_range(range: RangeInclusive<u32>) -> impl DoubleEndedIterator<Item = u32> {
1058 range
1059 }
1060
1061 fn count() -> u64 {
1062 (u32::MAX as u64) - (u32::MIN as u64) + 1
1063 }
1064}
1065
1066impl Domain for u16 {
1067 fn to_u32(&self) -> u32 {
1068 *self as u32
1069 }
1070
1071 fn from_u32(member: InDomain) -> u16 {
1072 member.value() as u16
1073 }
1074
1075 fn contains(value: u32) -> bool {
1076 (u16::MIN as u32..=u16::MAX as _).contains(&value)
1077 }
1078
1079 fn is_continuous() -> bool {
1080 true
1081 }
1082
1083 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1084 (u16::MIN as u32)..=(u16::MAX as u32)
1085 }
1086
1087 fn ordered_values_range(range: RangeInclusive<u16>) -> impl DoubleEndedIterator<Item = u32> {
1088 (*range.start() as u32)..=(*range.end() as u32)
1089 }
1090
1091 fn count() -> u64 {
1092 (u16::MAX as u64) - (u16::MIN as u64) + 1
1093 }
1094}
1095
1096impl Domain for u8 {
1097 fn to_u32(&self) -> u32 {
1098 *self as u32
1099 }
1100
1101 fn from_u32(member: InDomain) -> u8 {
1102 member.value() as u8
1103 }
1104
1105 fn contains(value: u32) -> bool {
1106 (u8::MIN as u32..=u8::MAX as _).contains(&value)
1107 }
1108
1109 fn is_continuous() -> bool {
1110 true
1111 }
1112
1113 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1114 (u8::MIN as u32)..=(u8::MAX as u32)
1115 }
1116
1117 fn ordered_values_range(range: RangeInclusive<u8>) -> impl DoubleEndedIterator<Item = u32> {
1118 (*range.start() as u32)..=(*range.end() as u32)
1119 }
1120
1121 fn count() -> u64 {
1122 (u8::MAX as u64) - (u8::MIN as u64) + 1
1123 }
1124}
1125
1126impl Domain for GlyphId16 {
1127 fn to_u32(&self) -> u32 {
1128 self.to_u16() as u32
1129 }
1130
1131 fn from_u32(member: InDomain) -> GlyphId16 {
1132 GlyphId16::new(member.value() as u16)
1133 }
1134
1135 fn contains(value: u32) -> bool {
1136 (u16::MIN as u32..=u16::MAX as _).contains(&value)
1137 }
1138
1139 fn is_continuous() -> bool {
1140 true
1141 }
1142
1143 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1144 (u16::MIN as u32)..=(u16::MAX as u32)
1145 }
1146
1147 fn ordered_values_range(
1148 range: RangeInclusive<GlyphId16>,
1149 ) -> impl DoubleEndedIterator<Item = u32> {
1150 range.start().to_u32()..=range.end().to_u32()
1151 }
1152
1153 fn count() -> u64 {
1154 (u16::MAX as u64) - (u16::MIN as u64) + 1
1155 }
1156}
1157
1158impl Domain for GlyphId {
1159 fn to_u32(&self) -> u32 {
1160 GlyphId::to_u32(*self)
1161 }
1162
1163 fn from_u32(member: InDomain) -> GlyphId {
1164 GlyphId::from(member.value())
1165 }
1166
1167 fn contains(_value: u32) -> bool {
1168 true
1169 }
1170
1171 fn is_continuous() -> bool {
1172 true
1173 }
1174
1175 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1176 u32::MIN..=u32::MAX
1177 }
1178
1179 fn ordered_values_range(
1180 range: RangeInclusive<GlyphId>,
1181 ) -> impl DoubleEndedIterator<Item = u32> {
1182 range.start().to_u32()..=range.end().to_u32()
1183 }
1184
1185 fn count() -> u64 {
1186 (u32::MAX as u64) - (u32::MIN as u64) + 1
1187 }
1188}
1189
1190impl Domain for Tag {
1191 fn to_u32(&self) -> u32 {
1192 u32::from_be_bytes(self.to_be_bytes())
1193 }
1194
1195 fn from_u32(member: InDomain) -> Tag {
1196 Tag::from_u32(member.value())
1197 }
1198
1199 fn contains(_value: u32) -> bool {
1200 true
1201 }
1202
1203 fn is_continuous() -> bool {
1204 true
1205 }
1206
1207 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1208 u32::MIN..=u32::MAX
1209 }
1210
1211 fn ordered_values_range(range: RangeInclusive<Tag>) -> impl DoubleEndedIterator<Item = u32> {
1212 range.start().to_u32()..=range.end().to_u32()
1213 }
1214
1215 fn count() -> u64 {
1216 (u32::MAX as u64) - (u32::MIN as u64) + 1
1217 }
1218}
1219
1220impl Domain for NameId {
1221 fn to_u32(&self) -> u32 {
1222 self.to_u16() as u32
1223 }
1224
1225 fn from_u32(member: InDomain) -> NameId {
1226 NameId::new(member.value() as u16)
1227 }
1228
1229 fn contains(value: u32) -> bool {
1230 (u16::MIN as u32..=u16::MAX as u32).contains(&value)
1231 }
1232
1233 fn is_continuous() -> bool {
1234 true
1235 }
1236
1237 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1238 (u16::MIN as u32)..=(u16::MAX as u32)
1239 }
1240
1241 fn ordered_values_range(range: RangeInclusive<NameId>) -> impl DoubleEndedIterator<Item = u32> {
1242 (range.start().to_u16() as u32)..=(range.end().to_u16() as u32)
1243 }
1244
1245 fn count() -> u64 {
1246 (u16::MAX as u64) - (u16::MIN as u64) + 1
1247 }
1248}
1249
1250#[cfg(test)]
1251mod test {
1252 use core::cmp::Ordering;
1253 use std::{collections::HashSet, hash::Hash};
1254
1255 use super::*;
1256
1257 #[derive(PartialEq, Eq, Debug, PartialOrd, Ord, Clone, Copy)]
1258 struct EvenInts(u16);
1259
1260 impl Domain for EvenInts {
1261 fn to_u32(&self) -> u32 {
1262 self.0 as u32
1263 }
1264
1265 fn contains(value: u32) -> bool {
1266 (value % 2) == 0
1267 }
1268
1269 fn from_u32(member: InDomain) -> EvenInts {
1270 EvenInts(member.0 as u16)
1271 }
1272
1273 fn is_continuous() -> bool {
1274 false
1275 }
1276
1277 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1278 (u16::MIN..=u16::MAX)
1279 .filter(|v| v % 2 == 0)
1280 .map(|v| v as u32)
1281 }
1282
1283 fn ordered_values_range(
1284 range: RangeInclusive<EvenInts>,
1285 ) -> impl DoubleEndedIterator<Item = u32> {
1286 Self::ordered_values()
1287 .filter(move |v| *v >= range.start().to_u32() && *v <= range.end().to_u32())
1288 }
1289
1290 fn count() -> u64 {
1291 ((u32::MAX as u64) - (u32::MIN as u64)).div_ceil(2)
1292 }
1293 }
1294
1295 #[derive(PartialEq, Eq, Debug, PartialOrd, Ord, Hash, Clone, Copy)]
1296 struct TwoParts(u16);
1297
1298 impl Domain for TwoParts {
1299 fn to_u32(&self) -> u32 {
1300 self.0 as u32
1301 }
1302
1303 fn contains(value: u32) -> bool {
1304 (2..=5).contains(&value) || (8..=16).contains(&value)
1305 }
1306
1307 fn from_u32(member: InDomain) -> TwoParts {
1308 TwoParts(member.0 as u16)
1309 }
1310
1311 fn is_continuous() -> bool {
1312 false
1313 }
1314
1315 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1316 [2..=5, 8..=16].into_iter().flat_map(|it| it.into_iter())
1317 }
1318
1319 fn ordered_values_range(
1320 range: RangeInclusive<TwoParts>,
1321 ) -> impl DoubleEndedIterator<Item = u32> {
1322 Self::ordered_values()
1323 .filter(move |v| *v >= range.start().to_u32() && *v <= range.end().to_u32())
1324 }
1325
1326 fn count() -> u64 {
1327 4 + 9
1328 }
1329 }
1330
1331 #[derive(PartialEq, Eq, Debug, PartialOrd, Ord, Clone, Copy)]
1332 struct TwoPartsBounds(u32);
1333
1334 impl Domain for TwoPartsBounds {
1335 fn to_u32(&self) -> u32 {
1336 self.0
1337 }
1338
1339 fn contains(value: u32) -> bool {
1340 (0..=1).contains(&value) || (u32::MAX - 1..=u32::MAX).contains(&value)
1341 }
1342
1343 fn from_u32(member: InDomain) -> TwoPartsBounds {
1344 TwoPartsBounds(member.0)
1345 }
1346
1347 fn is_continuous() -> bool {
1348 false
1349 }
1350
1351 fn ordered_values() -> impl DoubleEndedIterator<Item = u32> {
1352 [0..=1, u32::MAX - 1..=u32::MAX]
1353 .into_iter()
1354 .flat_map(|it| it.into_iter())
1355 }
1356
1357 fn ordered_values_range(
1358 range: RangeInclusive<TwoPartsBounds>,
1359 ) -> impl DoubleEndedIterator<Item = u32> {
1360 Self::ordered_values()
1361 .filter(move |v| *v >= range.start().to_u32() && *v <= range.end().to_u32())
1362 }
1363
1364 fn count() -> u64 {
1365 4
1366 }
1367 }
1368
1369 #[test]
1370 fn from_sparse_set() {
1371 let bytes = [0b00001101, 0b00000011, 0b00110001];
1372
1373 let set = IntSet::<u32>::from_sparse_bit_set(&bytes).unwrap();
1374
1375 let mut expected: IntSet<u32> = IntSet::<u32>::empty();
1376 expected.insert_range(0..=17);
1377
1378 assert_eq!(set, expected);
1379 }
1380
1381 #[test]
1382 fn insert() {
1383 let mut empty = IntSet::<u32>::empty();
1384 let mut all = IntSet::<u32>::all();
1385
1386 assert!(!empty.contains(10));
1387 assert!(empty.insert(10));
1388 assert!(empty.contains(10));
1389 assert!(!empty.insert(10));
1390
1391 assert!(all.contains(10));
1392 assert!(!all.insert(10));
1393 assert!(all.contains(10));
1394 assert!(!all.insert(10));
1395 }
1396
1397 #[test]
1398 fn remove() {
1399 let mut empty = IntSet::<u32>::empty();
1400 empty.insert(10);
1401 let mut all = IntSet::<u32>::all();
1402
1403 assert!(empty.contains(10));
1404 assert!(empty.remove(10));
1405 assert!(!empty.contains(10));
1406 assert!(!empty.remove(10));
1407
1408 assert!(all.contains(10));
1409 assert!(all.remove(10));
1410 assert!(!all.contains(10));
1411 assert!(!all.remove(10));
1412 }
1413
1414 #[test]
1415 fn is_empty() {
1416 let mut set = IntSet::<u32>::empty();
1417
1418 assert!(set.is_empty());
1419 set.insert(13);
1420 set.insert(800);
1421 assert!(!set.is_empty());
1422
1423 set.invert();
1424 assert!(!set.is_empty());
1425
1426 let mut empty = IntSet::<u32>::empty();
1427 assert!(empty.is_empty());
1428 empty.invert();
1429 assert!(!empty.is_empty());
1430 }
1431
1432 #[test]
1433 fn first() {
1434 let set = IntSet::<u16>::empty();
1435 assert_eq!(set.first(), None);
1436
1437 let set = IntSet::<u16>::all();
1438 assert_eq!(set.first(), Some(0));
1439
1440 let mut set = IntSet::<u16>::empty();
1441 set.extend([0]);
1442 assert_eq!(set.first(), Some(0));
1443
1444 let mut set = IntSet::<u16>::empty();
1445 set.extend([u16::MAX]);
1446 assert_eq!(set.first(), Some(u16::MAX));
1447
1448 let mut set = IntSet::<u16>::empty();
1449 set.extend([100, 1000, 10000]);
1450 assert_eq!(set.first(), Some(100));
1451
1452 set.invert();
1453 assert_eq!(set.first(), Some(0));
1454
1455 set.remove_range(0..=100);
1456 assert_eq!(set.first(), Some(101));
1457 }
1458
1459 #[test]
1460 fn last() {
1461 let set = IntSet::<u16>::empty();
1462 assert_eq!(set.last(), None);
1463
1464 let set = IntSet::<u16>::all();
1465 assert_eq!(set.last(), Some(u16::MAX));
1466
1467 let mut set = IntSet::<u16>::empty();
1468 set.extend([0]);
1469 assert_eq!(set.last(), Some(0));
1470
1471 let mut set = IntSet::<u16>::empty();
1472 set.extend([u16::MAX]);
1473 assert_eq!(set.last(), Some(u16::MAX));
1474
1475 let mut set = IntSet::<u16>::empty();
1476 set.extend([5, 7, 8]);
1477 assert_eq!(set.last(), Some(8));
1478
1479 let mut set = IntSet::<u16>::empty();
1480 set.extend([100, 1000, 10000]);
1481 assert_eq!(set.last(), Some(10000));
1482
1483 set.invert();
1484 assert_eq!(set.last(), Some(u16::MAX));
1485
1486 set.remove_range(u16::MAX - 10..=u16::MAX);
1487 assert_eq!(set.last(), Some(u16::MAX - 11));
1488 }
1489
1490 #[test]
1491 fn clear() {
1492 let mut set = IntSet::<u32>::empty();
1493 set.insert(13);
1494 set.insert(800);
1495
1496 let mut set_inverted = IntSet::<u32>::empty();
1497 set_inverted.insert(13);
1498 set_inverted.insert(800);
1499 set_inverted.invert();
1500
1501 set.clear();
1502 assert!(set.is_empty());
1503 set_inverted.clear();
1504 assert!(set_inverted.is_empty());
1505 }
1506
1507 #[allow(deprecated)] fn hash<T>(set: &IntSet<T>) -> u64
1509 where
1510 T: Domain,
1511 {
1512 use std::hash::Hasher;
1513 let mut h = std::hash::SipHasher::new();
1514 set.hash(&mut h);
1515 h.finish()
1516 }
1517
1518 #[test]
1519 fn equal_and_hash() {
1520 let mut inc1 = IntSet::<u32>::empty();
1521 inc1.insert(14);
1522 inc1.insert(670);
1523
1524 let mut inc2 = IntSet::<u32>::empty();
1525 inc2.insert(670);
1526 inc2.insert(14);
1527
1528 let mut inc3 = inc1.clone();
1529 inc3.insert(5);
1530
1531 let mut exc = inc1.clone();
1532 exc.invert();
1533
1534 assert_eq!(inc1, inc2);
1535 assert_ne!(inc1, inc3);
1536 assert_ne!(inc1, exc);
1537
1538 let set = HashSet::from([inc1.clone(), inc3.clone(), exc.clone()]);
1539 assert!(set.contains(&inc1));
1540 assert!(set.contains(&inc3));
1541 assert!(set.contains(&exc));
1542
1543 assert_ne!(hash(&inc1), hash(&exc));
1544 assert_eq!(hash(&inc1), hash(&inc2));
1545 }
1546
1547 #[test]
1548 fn equal_and_hash_mixed_membership_types() {
1549 let mut inverted_all = IntSet::<TwoParts>::all();
1550 let mut all = IntSet::<TwoParts>::empty();
1551 for v in TwoParts::ordered_values() {
1552 all.insert(TwoParts(v as u16));
1553 }
1554
1555 assert_eq!(inverted_all, all);
1556 assert_eq!(hash(&all), hash(&inverted_all));
1557
1558 inverted_all.remove(TwoParts(5));
1559 assert_ne!(inverted_all, all);
1560
1561 all.remove(TwoParts(5));
1562 assert_eq!(inverted_all, all);
1563 assert_eq!(hash(&all), hash(&inverted_all));
1564 }
1565
1566 #[test]
1567 fn iter() {
1568 let mut set = IntSet::<u32>::empty();
1569 set.insert(3);
1570 set.insert(8);
1571 set.insert(534);
1572 set.insert(700);
1573 set.insert(10000);
1574 set.insert(10001);
1575 set.insert(10002);
1576
1577 let v: Vec<u32> = set.iter().collect();
1578 assert_eq!(v, vec![3, 8, 534, 700, 10000, 10001, 10002]);
1579
1580 let v: Vec<u32> = set.inclusive_iter().unwrap().collect();
1581 assert_eq!(v, vec![3, 8, 534, 700, 10000, 10001, 10002]);
1582 }
1583
1584 #[test]
1585 fn iter_backwards() {
1586 let mut set = IntSet::<u32>::empty();
1587 set.insert_range(1..=6);
1588 {
1589 let mut it = set.iter();
1590 assert_eq!(Some(1), it.next());
1591 assert_eq!(Some(6), it.next_back());
1592 assert_eq!(Some(5), it.next_back());
1593 assert_eq!(Some(2), it.next());
1594 assert_eq!(Some(3), it.next());
1595 assert_eq!(Some(4), it.next());
1596 assert_eq!(None, it.next());
1597 assert_eq!(None, it.next_back());
1598 }
1599
1600 let mut set = IntSet::<u8>::empty();
1601 set.invert();
1602 set.remove_range(10..=255);
1603 set.remove(4);
1604 set.remove(8);
1605 {
1606 let mut it = set.iter();
1607 assert_eq!(Some(0), it.next());
1608 assert_eq!(Some(1), it.next());
1609 assert_eq!(Some(2), it.next());
1610 assert_eq!(Some(3), it.next());
1611
1612 assert_eq!(Some(9), it.next_back());
1613 assert_eq!(Some(7), it.next_back());
1614 assert_eq!(Some(6), it.next_back());
1615 assert_eq!(Some(5), it.next_back());
1616 assert_eq!(None, it.next_back());
1617
1618 assert_eq!(None, it.next());
1619 }
1620
1621 let mut set = IntSet::<u8>::empty();
1622 set.invert();
1623 set.remove_range(10..=255);
1624 set.remove(4);
1625 set.remove(8);
1626 {
1627 let mut it = set.iter();
1628 assert_eq!(Some(0), it.next());
1629 assert_eq!(Some(1), it.next());
1630 assert_eq!(Some(2), it.next());
1631 assert_eq!(Some(3), it.next());
1632 assert_eq!(Some(5), it.next());
1633
1634 assert_eq!(Some(9), it.next_back());
1635 assert_eq!(Some(7), it.next_back());
1636 assert_eq!(Some(6), it.next_back());
1637 assert_eq!(None, it.next_back());
1638
1639 assert_eq!(None, it.next());
1640 }
1641 }
1642
1643 #[test]
1644 fn exclusive_iter() {
1645 let mut set = IntSet::<u32>::all();
1646 set.remove(3);
1647 set.remove(7);
1648 set.remove(8);
1649
1650 let mut iter = set.iter();
1651
1652 assert_eq!(iter.next(), Some(0));
1653 assert_eq!(iter.next(), Some(1));
1654 assert_eq!(iter.next(), Some(2));
1655 assert_eq!(iter.next(), Some(4));
1656 assert_eq!(iter.next(), Some(5));
1657 assert_eq!(iter.next(), Some(6));
1658 assert_eq!(iter.next(), Some(9));
1659 assert_eq!(iter.next(), Some(10));
1660
1661 assert!(set.inclusive_iter().is_none());
1662
1663 let mut set = IntSet::<u32>::all();
1665 set.remove_range(0..=200);
1666
1667 let mut iter = set.iter();
1668 assert_eq!(iter.next(), Some(201));
1669
1670 let mut set = IntSet::<u8>::all();
1672 set.remove_range(200..=255);
1673
1674 let mut iter = set.iter();
1675 assert_eq!(iter.next_back(), Some(199));
1676 }
1677
1678 #[test]
1679 fn iter_ranges_inclusive() {
1680 let mut set = IntSet::<u32>::empty();
1681 let items: Vec<_> = set.iter_ranges().collect();
1682 assert_eq!(items, vec![]);
1683
1684 set.insert_range(200..=700);
1685 set.insert(5);
1686 let items: Vec<_> = set.iter_ranges().collect();
1687 assert_eq!(items, vec![5..=5, 200..=700]);
1688
1689 let mut set = IntSet::<u32>::empty();
1690 set.insert_range(0..=0);
1691 set.insert_range(u32::MAX..=u32::MAX);
1692 let items: Vec<_> = set.iter_ranges().collect();
1693 assert_eq!(items, vec![0..=0, u32::MAX..=u32::MAX]);
1694
1695 let mut set = IntSet::<u32>::empty();
1696 set.insert_range(0..=5);
1697 set.insert_range(u32::MAX - 5..=u32::MAX);
1698 let items: Vec<_> = set.iter_ranges().collect();
1699 assert_eq!(items, vec![0..=5, u32::MAX - 5..=u32::MAX]);
1700
1701 let mut inverted = set.clone();
1702 inverted.invert();
1703 assert_eq!(
1704 set.iter_ranges().collect::<Vec<_>>(),
1705 inverted.iter_excluded_ranges().collect::<Vec<_>>()
1706 );
1707 }
1708
1709 #[test]
1710 fn iter_ranges_inclusive_discontinuous() {
1711 let mut set = IntSet::<EvenInts>::empty();
1712 let items: Vec<_> = set.iter_ranges().collect();
1713 assert_eq!(items, vec![]);
1714
1715 set.insert_range(EvenInts(4)..=EvenInts(12));
1716 set.insert(EvenInts(16));
1717
1718 let items: Vec<_> = set.iter_ranges().collect();
1719 assert_eq!(
1720 items,
1721 vec![EvenInts(4)..=EvenInts(12), EvenInts(16)..=EvenInts(16)]
1722 );
1723
1724 let mut inverted = set.clone();
1725 inverted.invert();
1726 assert_eq!(
1727 set.iter_ranges().collect::<Vec<_>>(),
1728 inverted.iter_excluded_ranges().collect::<Vec<_>>()
1729 );
1730 }
1731
1732 #[test]
1733 fn iter_ranges_exclusive() {
1734 let mut set = IntSet::<u32>::all();
1735 set.remove_range(200..=700);
1736 set.remove(5);
1737 let items: Vec<_> = set.iter_ranges().collect();
1738 assert_eq!(items, vec![0..=4, 6..=199, 701..=u32::MAX]);
1739
1740 let mut set = IntSet::<u32>::all();
1741 set.remove_range(0..=700);
1742 let items: Vec<_> = set.iter_ranges().collect();
1743 assert_eq!(items, vec![701..=u32::MAX]);
1744
1745 let mut inverted = set.clone();
1746 inverted.invert();
1747 assert_eq!(
1748 set.iter_ranges().collect::<Vec<_>>(),
1749 inverted.iter_excluded_ranges().collect::<Vec<_>>()
1750 );
1751
1752 let mut set = IntSet::<u32>::all();
1753 set.remove_range(u32::MAX - 10..=u32::MAX);
1754 let items: Vec<_> = set.iter_ranges().collect();
1755 assert_eq!(items, vec![0..=u32::MAX - 11]);
1756
1757 let mut set = IntSet::<u16>::all();
1758 set.remove_range(0..=u16::MAX);
1759 let items: Vec<_> = set.iter_ranges().collect();
1760 assert_eq!(items, vec![]);
1761
1762 let mut set = IntSet::<u16>::all();
1763 set.remove_range(0..=u16::MAX - 1);
1764 let items: Vec<_> = set.iter_ranges().collect();
1765 assert_eq!(items, vec![u16::MAX..=u16::MAX]);
1766
1767 let mut set = IntSet::<u16>::all();
1768 set.remove_range(1..=u16::MAX);
1769 let items: Vec<_> = set.iter_ranges().collect();
1770 assert_eq!(items, vec![0..=0]);
1771
1772 let set = IntSet::<u32>::all();
1773 let items: Vec<_> = set.iter_ranges().collect();
1774 assert_eq!(items, vec![0..=u32::MAX]);
1775 }
1776
1777 #[test]
1778 fn iter_ranges_exclusive_discontinuous() {
1779 let mut set = IntSet::<EvenInts>::all();
1780 set.remove_range(EvenInts(0)..=EvenInts(8));
1781 set.remove_range(EvenInts(16)..=EvenInts(u16::MAX - 1));
1782 let items: Vec<_> = set.iter_ranges().collect();
1783 assert_eq!(items, vec![EvenInts(10)..=EvenInts(14),]);
1784
1785 let mut set = IntSet::<TwoParts>::all();
1786 set.remove_range(TwoParts(11)..=TwoParts(13));
1787 let items: Vec<_> = set.iter_ranges().collect();
1788 assert_eq!(
1789 items,
1790 vec![TwoParts(2)..=TwoParts(10), TwoParts(14)..=TwoParts(16),]
1791 );
1792
1793 let mut inverted = set.clone();
1794 inverted.invert();
1795 assert_eq!(
1796 set.iter_ranges().collect::<Vec<_>>(),
1797 inverted.iter_excluded_ranges().collect::<Vec<_>>()
1798 );
1799
1800 let mut set = IntSet::<TwoParts>::all();
1801 set.remove_range(TwoParts(2)..=TwoParts(16));
1802 let items: Vec<_> = set.iter_ranges().collect();
1803 assert_eq!(items, vec![]);
1804
1805 let mut set = IntSet::<TwoParts>::all();
1806 set.remove_range(TwoParts(2)..=TwoParts(5));
1807 let items: Vec<_> = set.iter_ranges().collect();
1808 assert_eq!(items, vec![TwoParts(8)..=TwoParts(16),]);
1809
1810 let mut set = IntSet::<TwoParts>::all();
1811 set.remove_range(TwoParts(6)..=TwoParts(16));
1812 let items: Vec<_> = set.iter_ranges().collect();
1813 assert_eq!(items, vec![TwoParts(2)..=TwoParts(5),]);
1814
1815 let set = IntSet::<TwoPartsBounds>::all();
1817 let items: Vec<_> = set.iter_ranges().collect();
1818 assert_eq!(items, vec![TwoPartsBounds(0)..=TwoPartsBounds(u32::MAX),]);
1819 }
1820
1821 #[test]
1822 fn iter_range() {
1823 let mut set = IntSet::<u32>::empty();
1824 assert_eq!(set.iter_after(0).count(), 0);
1825
1826 set.extend([5, 7, 10, 1250, 1300, 3001]);
1827
1828 assert_eq!(
1829 set.iter_after(0).collect::<Vec<u32>>(),
1830 vec![5, 7, 10, 1250, 1300, 3001]
1831 );
1832 assert_eq!(
1833 set.range(0..).collect::<Vec<u32>>(),
1834 vec![5, 7, 10, 1250, 1300, 3001]
1835 );
1836
1837 assert_eq!(
1838 set.iter_after(5).collect::<Vec<u32>>(),
1839 vec![7, 10, 1250, 1300, 3001]
1840 );
1841 assert_eq!(
1842 set.range(5..).collect::<Vec<u32>>(),
1843 vec![5, 7, 10, 1250, 1300, 3001]
1844 );
1845
1846 assert_eq!(
1847 set.iter_after(700).collect::<Vec<u32>>(),
1848 vec![1250, 1300, 3001]
1849 );
1850 assert_eq!(
1851 set.range(700..).collect::<Vec<u32>>(),
1852 vec![1250, 1300, 3001]
1853 );
1854 }
1855
1856 #[test]
1857 fn iter_after_from_exclusive() {
1858 let mut set = IntSet::<u32>::empty();
1859 set.extend([5, 7, 10, 1250, 1300, 3001]);
1860 set.invert();
1861
1862 assert_eq!(
1863 set.iter_after(3).take(5).collect::<Vec<u32>>(),
1864 vec![4, 6, 8, 9, 11]
1865 );
1866 assert_eq!(
1867 set.range(3..).take(5).collect::<Vec<u32>>(),
1868 vec![3, 4, 6, 8, 9]
1869 );
1870
1871 assert_eq!(
1872 set.iter_after(0).take(5).collect::<Vec<u32>>(),
1873 vec![1, 2, 3, 4, 6]
1874 );
1875 assert_eq!(
1876 set.range(0..).take(5).collect::<Vec<u32>>(),
1877 vec![0, 1, 2, 3, 4]
1878 );
1879
1880 assert_eq!(
1881 set.iter_after(u32::MAX - 1).take(1).collect::<Vec<u32>>(),
1882 vec![u32::MAX]
1883 );
1884 assert_eq!(
1885 set.range(u32::MAX - 1..).take(2).collect::<Vec<u32>>(),
1886 vec![u32::MAX - 1, u32::MAX]
1887 );
1888
1889 assert_eq!(set.iter_after(u32::MAX).take(1).count(), 0);
1890 set.remove(u32::MAX);
1891 assert_eq!(set.range(u32::MAX..).take(1).count(), 0);
1892 assert_eq!(set.iter_after(u32::MAX - 1).take(1).count(), 0);
1893 }
1894
1895 #[test]
1896 fn iter_after_discontinuous() {
1897 let mut set = IntSet::<EvenInts>::empty();
1898 set.extend([EvenInts(6), EvenInts(10)]);
1899 set.invert();
1900
1901 assert_eq!(
1902 set.iter_after(EvenInts(2))
1903 .take(5)
1904 .collect::<Vec<EvenInts>>(),
1905 vec![
1906 EvenInts(4),
1907 EvenInts(8),
1908 EvenInts(12),
1909 EvenInts(14),
1910 EvenInts(16)
1911 ]
1912 );
1913 assert_eq!(
1914 set.range(EvenInts(2)..).take(5).collect::<Vec<EvenInts>>(),
1915 vec![
1916 EvenInts(2),
1917 EvenInts(4),
1918 EvenInts(8),
1919 EvenInts(12),
1920 EvenInts(14)
1921 ]
1922 );
1923
1924 assert_eq!(
1925 set.iter_after(EvenInts(4))
1926 .take(5)
1927 .collect::<Vec<EvenInts>>(),
1928 vec![
1929 EvenInts(8),
1930 EvenInts(12),
1931 EvenInts(14),
1932 EvenInts(16),
1933 EvenInts(18)
1934 ]
1935 );
1936
1937 assert_eq!(
1938 set.iter_after(EvenInts(u16::MAX - 1))
1939 .collect::<Vec<EvenInts>>(),
1940 vec![]
1941 );
1942 assert_eq!(
1943 set.range(EvenInts(u16::MAX - 1)..)
1944 .collect::<Vec<EvenInts>>(),
1945 vec![EvenInts(u16::MAX - 1)]
1946 );
1947
1948 assert_eq!(
1949 set.iter_after(EvenInts(u16::MAX - 5))
1950 .collect::<Vec<EvenInts>>(),
1951 vec![EvenInts(u16::MAX - 3), EvenInts(u16::MAX - 1)]
1952 );
1953
1954 set.remove(EvenInts(u16::MAX - 1));
1955 assert_eq!(
1956 set.iter_after(EvenInts(u16::MAX - 5))
1957 .collect::<Vec<EvenInts>>(),
1958 vec![EvenInts(u16::MAX - 3),]
1959 );
1960 assert_eq!(
1961 set.range(EvenInts(u16::MAX - 5)..)
1962 .collect::<Vec<EvenInts>>(),
1963 vec![EvenInts(u16::MAX - 5), EvenInts(u16::MAX - 3),]
1964 );
1965 }
1966
1967 #[test]
1968 #[allow(clippy::reversed_empty_ranges)]
1969 fn range() {
1970 let mut set = IntSet::<u32>::empty();
1971 assert_eq!(set.range(0..=5).count(), 0);
1972
1973 set.extend([5, 7, 10, 1250, 1300, 3001]);
1974
1975 assert_eq!(set.range(0..=5).collect::<Vec<u32>>(), vec![5]);
1976 assert_eq!(set.range(5..=11).collect::<Vec<u32>>(), vec![5, 7, 10]);
1977 assert_eq!(set.range(5..10).collect::<Vec<u32>>(), vec![5, 7]);
1978 assert_eq!(set.range(..10).collect::<Vec<u32>>(), vec![5, 7]);
1979 assert_eq!(set.range(..=10).collect::<Vec<u32>>(), vec![5, 7, 10]);
1980 assert_eq!(set.range(6..=11).collect::<Vec<u32>>(), vec![7, 10]);
1981
1982 assert!(set.range(7..6).collect::<Vec<u32>>().is_empty());
1983 assert!(set.range(7..7).collect::<Vec<u32>>().is_empty());
1984 assert_eq!(set.range(7..=7).collect::<Vec<u32>>(), vec![7]);
1985
1986 assert!(set.range(5..=0).collect::<Vec<u32>>().is_empty());
1987 }
1988
1989 #[test]
1990 fn from_iterator() {
1991 let s: IntSet<u32> = [3, 8, 12, 589].into_iter().collect();
1992 let mut expected = IntSet::<u32>::empty();
1993 expected.insert(3);
1994 expected.insert(8);
1995 expected.insert(12);
1996 expected.insert(589);
1997
1998 assert_eq!(s, expected);
1999 }
2000
2001 #[test]
2002 fn from_int_set_iterator() {
2003 let s1: IntSet<u32> = [3, 8, 12, 589].into_iter().collect();
2004 let s2: IntSet<u32> = s1.iter().collect();
2005 assert_eq!(s1, s2);
2006 }
2007
2008 #[test]
2009 fn extend() {
2010 let mut s = IntSet::<u32>::empty();
2011 s.extend([3, 12]);
2012 s.extend([8, 10, 589]);
2013
2014 let mut expected = IntSet::<u32>::empty();
2015 expected.insert(3);
2016 expected.insert(8);
2017 expected.insert(10);
2018 expected.insert(12);
2019 expected.insert(589);
2020
2021 assert_eq!(s, expected);
2022 }
2023
2024 #[test]
2025 fn extend_on_inverted() {
2026 let mut s = IntSet::<u32>::all();
2027 for i in 10..=20 {
2028 s.remove(i);
2029 }
2030
2031 s.extend([12, 17, 18]);
2032
2033 assert!(!s.contains(11));
2034 assert!(s.contains(12));
2035 assert!(!s.contains(13));
2036
2037 assert!(!s.contains(16));
2038 assert!(s.contains(17));
2039 assert!(s.contains(18));
2040 assert!(!s.contains(19));
2041 assert!(s.contains(100));
2042 }
2043
2044 #[test]
2045 fn remove_all() {
2046 let mut empty = IntSet::<u32>::empty();
2047 let mut all = IntSet::<u32>::all();
2048
2049 empty.extend([1, 2, 3, 4]);
2050
2051 empty.remove_all([2, 3]);
2052 all.remove_all([2, 3]);
2053
2054 assert!(empty.contains(1));
2055 assert!(!empty.contains(2));
2056 assert!(!empty.contains(3));
2057 assert!(empty.contains(4));
2058
2059 assert!(all.contains(1));
2060 assert!(!all.contains(2));
2061 assert!(!all.contains(3));
2062 assert!(all.contains(4));
2063 }
2064
2065 #[test]
2066 fn remove_range() {
2067 let mut empty = IntSet::<u32>::empty();
2068 let mut all = IntSet::<u32>::all();
2069
2070 empty.extend([1, 2, 3, 4]);
2071
2072 empty.remove_range(2..=3);
2073 all.remove_range(2..=3);
2074
2075 assert!(empty.contains(1));
2076 assert!(!empty.contains(2));
2077 assert!(!empty.contains(3));
2078 assert!(empty.contains(4));
2079
2080 assert!(all.contains(1));
2081 assert!(!all.contains(2));
2082 assert!(!all.contains(3));
2083 assert!(all.contains(4));
2084 }
2085
2086 #[test]
2087 fn insert_remove_range_boundary() {
2088 let mut set = IntSet::<u32>::empty();
2089
2090 set.remove_range(u32::MAX - 10..=u32::MAX);
2091 assert!(!set.contains(u32::MAX));
2092 set.insert_range(u32::MAX - 10..=u32::MAX);
2093 assert!(set.contains(u32::MAX));
2094 set.remove_range(u32::MAX - 10..=u32::MAX);
2095 assert!(!set.contains(u32::MAX));
2096
2097 set.remove_range(0..=10);
2098 assert!(!set.contains(0));
2099 set.insert_range(0..=10);
2100 assert!(set.contains(0));
2101 set.remove_range(0..=10);
2102 assert!(!set.contains(0));
2103 }
2104
2105 #[test]
2106 fn insert_remove_range_exclusive_boundary() {
2107 let mut set = IntSet::<u32>::all();
2108
2109 set.remove_range(u32::MAX - 10..=u32::MAX);
2110 assert!(!set.contains(u32::MAX));
2111 set.insert_range(u32::MAX - 10..=u32::MAX);
2112 assert!(set.contains(u32::MAX));
2113 set.remove_range(u32::MAX - 10..=u32::MAX);
2114 assert!(!set.contains(u32::MAX));
2115
2116 set.remove_range(0..=10);
2117 assert!(!set.contains(0));
2118 set.insert_range(0..=10);
2119 assert!(set.contains(0));
2120 set.remove_range(0..=10);
2121 assert!(!set.contains(0));
2122 }
2123
2124 struct SetOpInput {
2125 has_x: bool,
2126 inverted: bool,
2127 has_page: bool,
2128 }
2129
2130 impl SetOpInput {
2131 fn get_all_inputs() -> Vec<SetOpInput> {
2132 let mut result: Vec<SetOpInput> = vec![];
2133 for has_x in [true, false] {
2134 for inverted in [true, false] {
2135 result.push(SetOpInput {
2136 has_x,
2137 inverted,
2138 has_page: false,
2139 });
2140 let can_have_empty_page = has_x == inverted;
2141 if can_have_empty_page {
2142 result.push(SetOpInput {
2143 has_x,
2144 inverted,
2145 has_page: true,
2146 });
2147 }
2148 }
2149 }
2150 result
2151 }
2152
2153 fn to_set(&self, x: u32) -> IntSet<u32> {
2154 let mut s = IntSet::<u32>::empty();
2155 if self.inverted {
2156 s.invert();
2157 }
2158 if self.has_page {
2159 if self.inverted {
2161 s.remove(x);
2162 } else {
2163 s.insert(x);
2164 }
2165 }
2166 if self.has_x {
2167 s.insert(x);
2168 } else {
2169 s.remove(x);
2170 }
2171 s
2172 }
2173 }
2174
2175 fn set_operation_test_message(
2176 a: &SetOpInput,
2177 b: &SetOpInput,
2178 op_name: &str,
2179 should_contain_x: bool,
2180 ) -> String {
2181 format!(
2182 "{}{}{} {} {}{}{} failed. {}",
2183 if a.inverted { "i" } else { "" },
2184 if a.has_page { "p" } else { "" },
2185 if a.has_x { "13" } else { "" },
2186 op_name,
2187 if b.inverted { "i" } else { "" },
2188 if b.has_page { "p" } else { "" },
2189 if b.has_x { "13" } else { "" },
2190 if should_contain_x {
2191 "Result did not have 13."
2192 } else {
2193 "Result should not have 13."
2194 }
2195 )
2196 }
2197
2198 fn check_union(a: &SetOpInput, b: &SetOpInput) {
2199 let x = 13;
2200 let mut set_a = a.to_set(x);
2201 let set_b = b.to_set(x);
2202
2203 let should_contain_x = a.has_x || b.has_x;
2204 set_a.union(&set_b);
2205
2206 assert_eq!(
2207 set_a.contains(x),
2208 should_contain_x,
2209 "{}",
2210 set_operation_test_message(a, b, "union", should_contain_x)
2211 );
2212 }
2213
2214 fn check_intersect(a: &SetOpInput, b: &SetOpInput) {
2215 let x = 13;
2216 let mut set_a = a.to_set(x);
2217 let set_b = b.to_set(x);
2218
2219 let should_contain_x = a.has_x && b.has_x;
2220 set_a.intersect(&set_b);
2221
2222 assert_eq!(
2223 set_a.contains(x),
2224 should_contain_x,
2225 "{}",
2226 set_operation_test_message(a, b, "intersect", should_contain_x)
2227 );
2228 }
2229
2230 fn check_subtract(a: &SetOpInput, b: &SetOpInput) {
2231 let x = 13;
2232 let mut set_a = a.to_set(x);
2233 let set_b = b.to_set(x);
2234
2235 let should_contain_x = a.has_x && (!b.has_x);
2236 set_a.subtract(&set_b);
2237
2238 assert_eq!(
2239 set_a.contains(x),
2240 should_contain_x,
2241 "{}",
2242 set_operation_test_message(a, b, "subtract", should_contain_x)
2243 );
2244 }
2245
2246 #[test]
2247 fn set_operations() {
2248 for a in SetOpInput::get_all_inputs() {
2249 for b in SetOpInput::get_all_inputs() {
2250 check_union(&a, &b);
2251 check_intersect(&a, &b);
2252 check_subtract(&a, &b);
2253 }
2254 }
2255 }
2256
2257 #[test]
2258 fn inverted() {
2259 let mut set = IntSet::<u32>::empty();
2260
2261 set.insert(13);
2262 set.insert(800);
2263 assert!(set.contains(13));
2264 assert!(set.contains(800));
2265 assert_eq!(set.len(), 2);
2266 assert!(!set.is_inverted());
2267
2268 set.invert();
2269 assert_eq!(set.len(), u32::MAX as u64 - 1);
2270 assert!(!set.contains(13));
2271 assert!(set.contains(80));
2272 assert!(!set.contains(800));
2273 assert!(set.is_inverted());
2274
2275 set.remove(80);
2276 assert!(!set.contains(80));
2277
2278 set.insert(13);
2279 assert!(set.contains(13));
2280
2281 set.invert();
2282 assert!(set.contains(80));
2283 assert!(set.contains(800));
2284 }
2285
2286 #[test]
2287 fn limited_domain_type() {
2288 let mut set = IntSet::<EvenInts>::empty();
2289
2290 set.insert(EvenInts(2));
2291 set.insert(EvenInts(8));
2292 set.insert(EvenInts(12));
2293 set.insert_range(EvenInts(20)..=EvenInts(34));
2294 set.remove_range(EvenInts(30)..=EvenInts(34));
2295
2296 assert!(set.contains(EvenInts(2)));
2297 assert!(!set.contains(EvenInts(4)));
2298
2299 assert!(!set.contains(EvenInts(18)));
2300 assert!(!set.contains(EvenInts(19)));
2301 assert!(set.contains(EvenInts(20)));
2302 assert!(!set.contains(EvenInts(21)));
2303 assert!(set.contains(EvenInts(28)));
2304 assert!(!set.contains(EvenInts(29)));
2305 assert!(!set.contains(EvenInts(30)));
2306
2307 let copy: IntSet<EvenInts> = set.iter().collect();
2308 assert_eq!(set, copy);
2309
2310 set.invert();
2311
2312 assert!(!set.contains(EvenInts(2)));
2313 assert!(set.contains(EvenInts(4)));
2314
2315 let Some(max) = set.iter().max() else {
2316 panic!("should have a max");
2317 };
2318
2319 assert_eq!(max.0, u16::MAX - 1);
2320
2321 {
2322 let mut it = set.iter();
2323 assert_eq!(it.next(), Some(EvenInts(0)));
2324 assert_eq!(it.next(), Some(EvenInts(4)));
2325 assert_eq!(it.next(), Some(EvenInts(6)));
2326 assert_eq!(it.next(), Some(EvenInts(10)));
2327 assert_eq!(it.next(), Some(EvenInts(14)));
2328 }
2329
2330 set.insert_range(EvenInts(6)..=EvenInts(10));
2331 {
2332 let mut it = set.iter();
2333 assert_eq!(it.next(), Some(EvenInts(0)));
2334 assert_eq!(it.next(), Some(EvenInts(4)));
2335 assert_eq!(it.next(), Some(EvenInts(6)));
2336 assert_eq!(it.next(), Some(EvenInts(8)));
2337 assert_eq!(it.next(), Some(EvenInts(10)));
2338 assert_eq!(it.next(), Some(EvenInts(14)));
2339 }
2340
2341 set.remove_range(EvenInts(6)..=EvenInts(10));
2342 {
2343 let mut it = set.iter();
2344 assert_eq!(it.next(), Some(EvenInts(0)));
2345 assert_eq!(it.next(), Some(EvenInts(4)));
2346 assert_eq!(it.next(), Some(EvenInts(14)));
2347 }
2348 }
2349
2350 #[test]
2351 fn with_u16() {
2352 let mut set = IntSet::<u16>::empty();
2353
2354 set.insert(5);
2355 set.insert(8);
2356 set.insert(12);
2357 set.insert_range(200..=210);
2358
2359 assert!(set.contains(5));
2360 assert!(!set.contains(6));
2361 assert!(!set.contains(199));
2362 assert!(set.contains(200));
2363 assert!(set.contains(210));
2364 assert!(!set.contains(211));
2365
2366 let copy: IntSet<u16> = set.iter().collect();
2367 assert_eq!(set, copy);
2368
2369 set.invert();
2370
2371 assert!(!set.contains(5));
2372 assert!(set.contains(6));
2373
2374 let Some(max) = set.iter().max() else {
2375 panic!("should have a max");
2376 };
2377
2378 assert_eq!(max, u16::MAX);
2379
2380 let mut it = set.iter();
2381 assert_eq!(it.next(), Some(0));
2382 assert_eq!(it.next(), Some(1));
2383 assert_eq!(it.next(), Some(2));
2384 assert_eq!(it.next(), Some(3));
2385 assert_eq!(it.next(), Some(4));
2386 assert_eq!(it.next(), Some(6));
2387 }
2388
2389 #[test]
2390 fn with_glyph_id_16() {
2391 let mut set = IntSet::<font_types::GlyphId16>::empty();
2392
2393 set.insert(GlyphId16::new(5));
2394 set.insert(GlyphId16::new(8));
2395 set.insert(GlyphId16::new(12));
2396 set.insert_range(GlyphId16::new(200)..=GlyphId16::new(210));
2397
2398 assert!(set.contains(GlyphId16::new(5)));
2399 assert!(!set.contains(GlyphId16::new(6)));
2400 assert!(!set.contains(GlyphId16::new(199)));
2401 assert!(set.contains(GlyphId16::new(200)));
2402 assert!(set.contains(GlyphId16::new(210)));
2403 assert!(!set.contains(GlyphId16::new(211)));
2404
2405 let copy: IntSet<GlyphId16> = set.iter().collect();
2406 assert_eq!(set, copy);
2407
2408 set.invert();
2409
2410 assert!(!set.contains(GlyphId16::new(5)));
2411 assert!(set.contains(GlyphId16::new(6)));
2412
2413 let Some(max) = set.iter().max() else {
2414 panic!("should have a max");
2415 };
2416
2417 assert_eq!(max, GlyphId16::new(u16::MAX));
2418
2419 let mut it = set.iter();
2420 assert_eq!(it.next(), Some(GlyphId16::new(0)));
2421 assert_eq!(it.next(), Some(GlyphId16::new(1)));
2422 assert_eq!(it.next(), Some(GlyphId16::new(2)));
2423 assert_eq!(it.next(), Some(GlyphId16::new(3)));
2424 assert_eq!(it.next(), Some(GlyphId16::new(4)));
2425 assert_eq!(it.next(), Some(GlyphId16::new(6)));
2426 }
2427
2428 #[test]
2429 fn with_glyph_id() {
2430 let mut set = IntSet::<font_types::GlyphId>::empty();
2431
2432 set.insert(GlyphId::new(5));
2433 set.insert(GlyphId::new(8));
2434 set.insert(GlyphId::new(12));
2435 set.insert_range(GlyphId::new(200)..=GlyphId::new(210));
2436
2437 assert!(set.contains(GlyphId::new(5)));
2438 assert!(!set.contains(GlyphId::new(6)));
2439 assert!(!set.contains(GlyphId::new(199)));
2440 assert!(set.contains(GlyphId::new(200)));
2441 assert!(set.contains(GlyphId::new(210)));
2442 assert!(!set.contains(GlyphId::new(211)));
2443
2444 let copy: IntSet<GlyphId> = set.iter().collect();
2445 assert_eq!(set, copy);
2446
2447 set.invert();
2448
2449 assert!(!set.contains(GlyphId::new(5)));
2450 assert!(set.contains(GlyphId::new(6)));
2451
2452 let mut it = set.iter();
2453 assert_eq!(it.next(), Some(GlyphId::new(0)));
2454 assert_eq!(it.next(), Some(GlyphId::new(1)));
2455 assert_eq!(it.next(), Some(GlyphId::new(2)));
2456 assert_eq!(it.next(), Some(GlyphId::new(3)));
2457 assert_eq!(it.next(), Some(GlyphId::new(4)));
2458 assert_eq!(it.next(), Some(GlyphId::new(6)));
2459 }
2460
2461 #[test]
2462 fn with_tag() {
2463 let mut set = IntSet::<Tag>::empty();
2464
2465 set.insert(Tag::new(b"GSUB"));
2466 set.insert(Tag::new(b"CFF "));
2467 set.insert(Tag::new(b"OS/2"));
2468
2469 assert!(set.contains(Tag::new(b"GSUB")));
2470 assert!(!set.contains(Tag::new(b"GSU ")));
2471 assert!(set.contains(Tag::new(b"CFF ")));
2472 assert!(set.contains(Tag::new(b"OS/2")));
2473
2474 let copy: IntSet<Tag> = set.iter().collect();
2475 assert_eq!(set, copy);
2476
2477 set.invert();
2478
2479 assert!(!set.contains(Tag::new(b"GSUB")));
2480 assert!(set.contains(Tag::new(b"GSU ")));
2481 assert!(!set.contains(Tag::new(b"CFF ")));
2482 assert!(!set.contains(Tag::new(b"OS/2")));
2483 }
2484
2485 #[test]
2486 fn intersects_range() {
2487 let mut set = IntSet::<u32>::empty();
2488 assert!(!set.intersects_range(0..=0));
2489 assert!(!set.intersects_range(0..=100));
2490 assert!(!set.intersects_range(0..=u32::MAX));
2491 assert!(!set.intersects_range(u32::MAX..=u32::MAX));
2492
2493 set.insert(1234);
2494 assert!(!set.intersects_range(0..=1233));
2495 assert!(!set.intersects_range(1235..=1240));
2496
2497 assert!(set.intersects_range(1234..=1234));
2498 assert!(set.intersects_range(1230..=1240));
2499 assert!(set.intersects_range(0..=1234));
2500 assert!(set.intersects_range(1234..=u32::MAX));
2501
2502 set.insert(0);
2503 assert!(set.intersects_range(0..=0));
2504 assert!(!set.intersects_range(1..=1));
2505 }
2506
2507 #[test]
2508 fn intersects_set() {
2509 macro_rules! assert_intersects {
2510 ($lhs:path, $rhs:path, $expected:expr) => {
2511 assert_eq!($lhs.intersects_set(&$rhs), $expected);
2512 assert_eq!($rhs.intersects_set(&$lhs), $expected);
2513 };
2514 }
2515
2516 assert!(!IntSet::<u32>::empty().intersects_set(&IntSet::<u32>::empty()));
2517
2518 let empty = IntSet::<u32>::empty();
2519 let a = IntSet::from([1u32, 5, 6, 7, 8, 12]);
2520 let b = IntSet::from([2u32, 13]);
2521 let c = IntSet::from([8u32, 14]);
2522 let mut d = IntSet::all();
2523 d.remove_range(0u32..=13);
2524 let mut e = IntSet::all();
2525 e.remove_range(0u32..=100);
2526
2527 assert_intersects!(a, b, false);
2528 assert_intersects!(a, c, true);
2529 assert_intersects!(a, d, false);
2530
2531 assert_intersects!(b, c, false);
2532 assert_intersects!(b, d, false);
2533 assert_intersects!(b, e, false);
2534
2535 assert_intersects!(c, d, true);
2536 assert_intersects!(c, e, false);
2537
2538 assert_intersects!(d, e, true);
2539
2540 assert_intersects!(a, empty, false);
2541 assert_intersects!(b, empty, false);
2542 assert_intersects!(c, empty, false);
2543 assert_intersects!(d, empty, false);
2544 assert_intersects!(e, empty, false);
2545 }
2546
2547 #[test]
2548 fn is_subset() {
2549 let empty = IntSet::<u32>::empty();
2550 let a = IntSet::from([1u32, 5, 6, 7, 8, 12]);
2551 let b = IntSet::from([1u32, 5, 6, 7, 8, 12, 15]);
2552 let c = IntSet::from([1u32, 5, 6, 7, 8, 13]);
2553
2554 assert!(empty.is_subset(&empty));
2556 assert!(empty.is_subset(&a));
2557 assert!(!a.is_subset(&empty));
2558
2559 assert!(a.is_subset(&a));
2560
2561 assert!(a.is_subset(&b));
2562 assert!(!b.is_subset(&a)); assert!(!a.is_subset(&c)); assert!(!c.is_subset(&a));
2566
2567 let mut all_but_13 = IntSet::<u32>::all();
2569 all_but_13.remove(13);
2570
2571 let mut all_but_5 = IntSet::<u32>::all();
2572 all_but_5.remove(5);
2573
2574 assert!(a.is_subset(&all_but_13)); assert!(!a.is_subset(&all_but_5)); assert!(empty.is_subset(&all_but_13));
2577
2578 let mut all_but_1 = IntSet::<u8>::all();
2580 all_but_1.remove(1u8);
2581
2582 let mut all_but_1_2 = IntSet::<u8>::all();
2583 all_but_1_2.remove(1u8);
2584 all_but_1_2.remove(2u8);
2585
2586 let mut incl_all_but_1 = IntSet::<u8>::empty();
2587 incl_all_but_1.insert_range(0u8..=255);
2588 incl_all_but_1.remove(1u8);
2589
2590 let mut incl_all_but_3 = IntSet::<u8>::empty();
2591 incl_all_but_3.insert_range(0u8..=255);
2592 incl_all_but_3.remove(3u8);
2593
2594 let mut incl_all = IntSet::<u8>::empty();
2595 incl_all.insert_range(0u8..=255);
2596
2597 assert!(all_but_1.is_subset(&incl_all));
2598 assert!(all_but_1.is_subset(&incl_all_but_1));
2599 assert!(all_but_1_2.is_subset(&incl_all_but_1));
2600 assert!(!all_but_1.is_subset(&IntSet::<u8>::from([0u8, 2, 3]))); assert!(!all_but_1_2.is_subset(&incl_all_but_3)); let mut all_but_2_3 = IntSet::<u8>::all();
2605 all_but_2_3.remove(2u8);
2606 all_but_2_3.remove(3u8);
2607
2608 assert!(all_but_1_2.is_subset(&all_but_1));
2609 assert!(!all_but_1.is_subset(&all_but_1_2)); assert!(!all_but_1_2.is_subset(&all_but_2_3)); assert!(IntSet::<u32>::all().is_subset(&IntSet::<u32>::all()));
2612
2613 let even_empty = IntSet::<EvenInts>::empty();
2615 let even_a = IntSet::from([EvenInts(2), EvenInts(4)]);
2616 let even_b = IntSet::from([EvenInts(2), EvenInts(4), EvenInts(6)]);
2617 let even_c = IntSet::from([EvenInts(2), EvenInts(6)]);
2618 assert!(even_empty.is_subset(&even_a));
2619 assert!(even_a.is_subset(&even_b));
2620 assert!(!even_b.is_subset(&even_a)); assert!(!even_c.is_subset(&even_a)); }
2623
2624 #[test]
2625 fn intersects_range_discontinuous() {
2626 let mut set = IntSet::<EvenInts>::empty();
2627 assert!(!set.intersects_range(EvenInts(0)..=EvenInts(0)));
2628 assert!(!set.intersects_range(EvenInts(0)..=EvenInts(100)));
2629 assert!(!set.intersects_range(EvenInts(0)..=EvenInts(u16::MAX - 1)));
2630 assert!(!set.intersects_range(EvenInts(u16::MAX - 1)..=EvenInts(u16::MAX - 1)));
2631
2632 set.insert(EvenInts(1234));
2633 assert!(!set.intersects_range(EvenInts(0)..=EvenInts(1232)));
2634 assert!(!set.intersects_range(EvenInts(1236)..=EvenInts(1240)));
2635
2636 assert!(set.intersects_range(EvenInts(1234)..=EvenInts(1234)));
2637 assert!(set.intersects_range(EvenInts(1230)..=EvenInts(1240)));
2638 assert!(set.intersects_range(EvenInts(0)..=EvenInts(1234)));
2639 assert!(set.intersects_range(EvenInts(1234)..=EvenInts(u16::MAX - 1)));
2640
2641 set.insert(EvenInts(0));
2642 assert!(set.intersects_range(EvenInts(0)..=EvenInts(0)));
2643 assert!(!set.intersects_range(EvenInts(2)..=EvenInts(2)));
2644 }
2645
2646 #[test]
2647 fn intersects_range_exclusive() {
2648 let mut set = IntSet::<u32>::all();
2649 assert!(set.intersects_range(0..=0));
2650 assert!(set.intersects_range(0..=100));
2651 assert!(set.intersects_range(0..=u32::MAX));
2652 assert!(set.intersects_range(u32::MAX..=u32::MAX));
2653
2654 set.remove(1234);
2655 assert!(set.intersects_range(0..=1233));
2656 assert!(set.intersects_range(1235..=1240));
2657
2658 assert!(!set.intersects_range(1234..=1234));
2659 assert!(set.intersects_range(1230..=1240));
2660 assert!(set.intersects_range(0..=1234));
2661 assert!(set.intersects_range(1234..=u32::MAX));
2662
2663 set.remove(0);
2664 assert!(!set.intersects_range(0..=0));
2665 assert!(set.intersects_range(1..=1));
2666
2667 set.remove_range(5000..=5200);
2668 assert!(!set.intersects_range(5000..=5200));
2669 assert!(!set.intersects_range(5100..=5150));
2670 assert!(set.intersects_range(4999..=5200));
2671 assert!(set.intersects_range(5000..=5201));
2672 }
2673
2674 #[test]
2675 fn intersects_range_exclusive_discontinuous() {
2676 let mut set = IntSet::<EvenInts>::all();
2677 assert!(set.intersects_range(EvenInts(0)..=EvenInts(0)));
2678 assert!(set.intersects_range(EvenInts(0)..=EvenInts(100)));
2679 assert!(set.intersects_range(EvenInts(0)..=EvenInts(u16::MAX - 1)));
2680 assert!(set.intersects_range(EvenInts(u16::MAX - 1)..=EvenInts(u16::MAX - 1)));
2681
2682 set.remove(EvenInts(1234));
2683 assert!(set.intersects_range(EvenInts(0)..=EvenInts(1232)));
2684 assert!(set.intersects_range(EvenInts(1236)..=EvenInts(1240)));
2685
2686 assert!(!set.intersects_range(EvenInts(1234)..=EvenInts(1234)));
2687 assert!(set.intersects_range(EvenInts(1230)..=EvenInts(1240)));
2688 assert!(set.intersects_range(EvenInts(0)..=EvenInts(1234)));
2689 assert!(set.intersects_range(EvenInts(1234)..=EvenInts(u16::MAX - 1)));
2690
2691 set.remove(EvenInts(0));
2692 assert!(!set.intersects_range(EvenInts(0)..=EvenInts(0)));
2693 assert!(set.intersects_range(EvenInts(2)..=EvenInts(2)));
2694
2695 set.remove_range(EvenInts(5000)..=EvenInts(5200));
2696 assert!(!set.intersects_range(EvenInts(5000)..=EvenInts(5200)));
2697 assert!(!set.intersects_range(EvenInts(5100)..=EvenInts(5150)));
2698 assert!(set.intersects_range(EvenInts(4998)..=EvenInts(5200)));
2699 assert!(set.intersects_range(EvenInts(5000)..=EvenInts(5202)));
2700 }
2701
2702 #[test]
2703 fn length() {
2704 let mut s = IntSet::<u32>::empty();
2705 assert_eq!(s.len(), 0);
2706 s.insert(5);
2707 s.insert(5);
2708 s.insert(100);
2709 assert_eq!(s.len(), 2);
2710
2711 s.invert();
2712 assert_eq!(s.len(), (u32::MAX - 1) as u64);
2713
2714 assert_eq!(IntSet::<u32>::all().len(), (u32::MAX as u64) + 1);
2715
2716 let mut s = IntSet::<TwoParts>::all();
2717 assert_eq!(s.len(), 13);
2718 s.remove(TwoParts::from_u32(InDomain(5)));
2719 assert_eq!(s.len(), 12);
2720
2721 for v in TwoParts::ordered_values() {
2722 s.remove(TwoParts::from_u32(InDomain(v)));
2723 }
2724 assert_eq!(s.len(), 0);
2725 }
2726
2727 #[test]
2728 fn ordering() {
2729 macro_rules! assert_ord {
2730 ($lhs:expr, $rhs:expr, $ord:path) => {
2731 assert_eq!(
2732 IntSet::from($lhs.clone()).cmp(&IntSet::from($rhs.clone())),
2733 $ord,
2734 "{:?}, {:?}",
2735 $lhs,
2736 $rhs
2737 )
2738 };
2739 }
2740
2741 const EMPTY: [u16; 0] = [];
2742 assert_ord!(EMPTY, EMPTY, Ordering::Equal);
2743 assert_ord!(EMPTY, [0], Ordering::Less);
2744 assert_ord!([0u16], [0], Ordering::Equal);
2745 assert_ord!([0u16, 1, 2], [1, 2, 3], Ordering::Less);
2746 assert_ord!([0u16, 1, 4], [1, 2, 3], Ordering::Less);
2747 assert_ord!([1u16, 2, 3], [0, 2, 4], Ordering::Greater);
2748 assert_ord!([5u16, 4, 0], [1, 2, 3], Ordering::Less); assert_ord!([1u16, 2, 3], [1, 2, 3, 4], Ordering::Less); assert_ord!([2u16, 3, 4], [1, 2, 3, 4, 5], Ordering::Greater); let all = IntSet::<u16>::all();
2754 let mut all_but_0 = all.clone();
2755 all_but_0.remove(0);
2756 let mut all_but_5 = all.clone();
2757 all_but_5.remove(5);
2758
2759 assert_eq!(all.cmp(&all), Ordering::Equal);
2760 assert_eq!(all.cmp(&all_but_0), Ordering::Less);
2761 assert_eq!(all_but_0.cmp(&all), Ordering::Greater);
2762
2763 let mut a = IntSet::<u16>::all();
2764 a.remove_range(0..=5);
2765 a.remove_range(221..=1693);
2766 let mut b = IntSet::<u16>::all();
2767 b.remove_range(0..=1693);
2768 assert_eq!(a.cmp(&b), Ordering::Less);
2769
2770 let mut inc_all_but_0 = IntSet::<u16>::empty();
2772 inc_all_but_0.insert_range(1..=u16::MAX);
2773 let mut inc_all_but_5 = IntSet::<u16>::empty();
2774 inc_all_but_5.insert_range(0..=4);
2775 inc_all_but_5.insert_range(6..=u16::MAX);
2776
2777 assert_eq!(all.cmp(&all), Ordering::Equal);
2778 assert_eq!(all.cmp(&inc_all_but_0), Ordering::Less);
2779 assert_eq!(inc_all_but_0.cmp(&all), Ordering::Greater);
2780 assert_eq!(inc_all_but_5.cmp(&all_but_0), Ordering::Less);
2781
2782 let mut a = IntSet::<u16>::all();
2783 a.remove_range(8..=1160);
2784 let mut b = IntSet::<u16>::empty();
2785 b.insert_range(0..=259);
2786
2787 assert_eq!(a.cmp(&b), Ordering::Greater);
2788
2789 let mut a = IntSet::<u16>::all();
2790 a.remove_range(8..=u16::MAX);
2791 let mut b = IntSet::<u16>::empty();
2792 b.insert_range(0..=259);
2793
2794 assert_eq!(a.cmp(&b), Ordering::Less);
2795 }
2796
2797 #[cfg(feature = "serde")]
2798 fn roundtrip_json<T: Domain>(set: &IntSet<T>) -> Result<IntSet<T>, serde_json::Error> {
2799 let json = serde_json::to_vec(&set).unwrap();
2800 serde_json::from_slice(&json)
2801 }
2802
2803 #[test]
2804 #[cfg(feature = "serde")]
2805 fn simple_serde() {
2806 let mut set = IntSet::empty();
2807 set.insert(0u32);
2808 set.insert(u32::MAX);
2809 assert_eq!(roundtrip_json(&set).unwrap(), set);
2810 }
2811
2812 #[test]
2813 #[cfg(feature = "serde")]
2814 fn serde_non_contiguous() {
2815 fn ev(val: u16) -> EvenInts {
2816 assert!(val % 2 == 0);
2817 EvenInts(val)
2818 }
2819 let set = IntSet::<EvenInts>::from([ev(2), ev(166), ev(u16::MAX - 1)]);
2820 assert_eq!(roundtrip_json(&set).unwrap(), set);
2821 }
2822
2823 #[test]
2824 #[cfg(feature = "serde")]
2825 #[should_panic(expected = "out of range for domain")]
2826 fn serde_non_contiguous_out_of_domain() {
2827 let set = IntSet::from([1u16, 2, 3, 4, 5, 6, 7]);
2828 let bytes = serde_json::to_vec(&set).unwrap();
2829 serde_json::from_slice::<IntSet<EvenInts>>(&bytes).unwrap();
2830 }
2831
2832 #[test]
2833 #[cfg(feature = "serde")]
2834 fn non_contiguous_inverted() {
2835 let all = IntSet::<u16>::all();
2836 let bytes = serde_json::to_vec(&all).unwrap();
2837 let readback: IntSet<EvenInts> = serde_json::from_slice(&bytes).unwrap();
2838 let mut iter = readback.iter().map(|v| v.0);
2839 let mut values = (&mut iter).take(5).collect::<Vec<_>>();
2840 values.extend(iter.rev().take(5));
2841
2842 assert_eq!(values, [0, 2, 4, 6, 8, 65534, 65532, 65530, 65528, 65526])
2843 }
2844
2845 #[test]
2846 #[cfg(feature = "serde")]
2847 fn serde_inverted() {
2848 let mut set = IntSet::all();
2849 set.remove_range(0u16..=420);
2850 let bytes = serde_json::to_string(&set).unwrap();
2851 assert!(bytes.len() < 5000, "sanity check serialization");
2852 assert_eq!(roundtrip_json(&set).unwrap(), set)
2853 }
2854
2855 #[test]
2856 #[cfg(feature = "serde")]
2857 fn serde_inverted_out_of_domain() {
2858 let mut set = IntSet::all();
2859 set.remove_range(0u16..=250);
2860 let bytes = serde_json::to_string(&set).unwrap();
2861 let readback: IntSet<u8> = serde_json::from_str(&bytes).unwrap();
2862 assert_eq!(readback.len(), 5);
2863 assert_eq!(
2864 readback.iter().collect::<Vec<_>>(),
2865 [251, 252, 253, 254, 255]
2866 );
2867 }
2868
2869 #[test]
2870 #[cfg(feature = "serde")]
2871 #[should_panic(expected = "out of range for domain")]
2872 fn serde_out_of_domain() {
2873 let set = IntSet::from([u32::MAX]);
2874 let json = serde_json::to_vec(&set).unwrap();
2875 serde_json::from_slice::<IntSet<GlyphId16>>(&json).unwrap();
2876 }
2877}