Skip to main content

read_fonts/collections/int_set/
mod.rs

1//! A fast, efficient, sparse, & ordered unsigned integer (u32) bit set which is invertible.
2//!
3//! The bitset is implemented using fixed size pages which allows it to compactly
4//! represent sparse membership. However, the set excels when set members are typically
5//! clustered together. For example when representing glyph id or unicode codepoint values
6//! in a font.
7//!
8//! The set can have inclusive (the set of integers which are members) or
9//! exclusive (the set of integers which are not members) membership. The
10//! exclusive/inverted version of the set is useful for patterns such as
11//! "keep all codepoints except for {x, y, z, ...}".
12//!
13//! When constructing a new [`IntSet`] from an existing lists of integer values the most efficient
14//! way to create the set is to initialize it from a sorted (ascending) iterator of the values.
15//!
16//! For a type to be stored in the [`IntSet`] it must implement the [`Domain`] trait, and all
17//! unique values of that type must be able to be mapped to and from a unique `u32` value.
18//! See the [`Domain`] trait for more information.
19
20mod 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/// A fast & efficient invertible ordered set for small (up to 32-bit) unsigned integer types.
38#[derive(Clone)]
39pub struct IntSet<T>(Membership, PhantomData<T>);
40
41/// Defines the domain of `IntSet` member types.
42///
43/// Members of `IntSet` must implement this trait. Members of `IntSet`'s must meet the following
44/// conditions to be used in an `IntSet`:
45///
46/// 1. Every possible unique value of `T` must be able map to and from a unique `u32`
47///    integer.
48///
49/// 2. The mapped `u32` values must retain the same ordering as the values in `T`.
50///
51/// 3. `ordered_values`() must iterate over all values in `T` in sorted order (ascending).
52///
53/// `from_u32`() will only ever be called with u32 values that are part of the domain of T as defined
54/// by an implementation of this trait. So it doesn't need to correctly handle values
55/// that are outside the domain of `T`.
56pub trait Domain: Sized + Copy {
57    /// Converts this value of `T` to a value in u32.
58    ///
59    /// The mapped value must maintain the same ordering as `T`.
60    fn to_u32(&self) -> u32;
61
62    /// Returns `true` if the value is part of this domain.
63    fn contains(value: u32) -> bool;
64
65    /// Converts a mapped u32 value back to T.
66    ///
67    /// Will only ever be called with values produced by `to_u32`.
68    fn from_u32(member: InDomain) -> Self;
69
70    /// Returns true if all u32 values between the mapped u32 min and mapped u32 max value of T are used.
71    fn is_continuous() -> bool;
72
73    /// Returns an iterator which iterates over all values in the domain of `T`
74    ///
75    /// Values should be converted to `u32`'s according to the mapping defined in
76    /// `to_u32`/`from_u32`.
77    fn ordered_values() -> impl DoubleEndedIterator<Item = u32>;
78
79    /// Return an iterator which iterates over all values of T in the given range.
80    ///
81    /// Values should be converted to `u32`'s according to the mapping defined in
82    /// `to_u32`/`from_u32`.
83    fn ordered_values_range(range: RangeInclusive<Self>) -> impl DoubleEndedIterator<Item = u32>;
84
85    /// Returns the number of members in the domain.
86    fn count() -> u64;
87}
88
89/// Marks a mapped value as being in the domain of `T` for [`Domain`].
90///
91/// See [`Domain`] for more information.
92pub struct InDomain(u32);
93
94#[derive(Clone, Debug, Hash, PartialEq, Eq)]
95#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
96enum Membership {
97    /// Records a set of integers which are members of the set.
98    Inclusive(U32Set),
99
100    /// Records the set of integers which are not members of the set.
101    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    /// Returns an iterator over all members of the set in sorted ascending order.
118    ///
119    /// Note: iteration of inverted sets can be extremely slow due to the very large number of members in the set
120    /// care should be taken when using `.iter()` in combination with an inverted set.
121    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    /// If this is an inclusive membership set then returns an iterator over the members, otherwise returns `None`.
132    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                    // either min or max doesn't exist, so just return an iterator that has no values.
157                    let mut it = Iter::new(s.iter_from(u32::MAX), None);
158                    it.next();
159                    it
160                }
161            }
162        }
163    }
164
165    /// Returns an iterator over the members of this set that are after `value` in ascending order.
166    ///
167    /// Note: iteration of inverted sets can be extremely slow due to the very large number of members in the set
168    /// care should be taken when using `.iter()` in combination with an inverted set.
169    pub fn iter_after(&self, value: T) -> impl Iterator<Item = T> + '_ {
170        self.range((Bound::Excluded(value), Bound::Unbounded))
171    }
172
173    /// Returns an iterator over members of this set that are in `range`.
174    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    /// Returns an iterator over all disjoint ranges of values within the set in sorted ascending order.
201    pub fn iter_ranges(&self) -> impl Iterator<Item = RangeInclusive<T>> + '_ {
202        self.iter_ranges_invertible(false)
203    }
204
205    /// Returns an iterator over all disjoint ranges of values not within the set in sorted ascending order.
206    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    /// Adds a value to the set.
252    ///
253    /// Returns `true` if the value was newly inserted.
254    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    /// Add all values in range as members of this set.
263    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    /// An alternate version of [`extend()`] which is optimized for inserting an unsorted iterator of values.
280    ///
281    /// [`extend()`]: Self::extend
282    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    /// Removes a value from the set. Returns whether the value was present in the set.
291    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    // Removes all values in iter from the set.
300    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    /// Removes all values in range as members of this set.
309    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    /// Sets the members of this set to the union of self and other.
326    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    /// Sets the members of this set to the intersection of self and other.
339    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    /// Sets the members of this set to self - other.
352    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    /// Returns true if this set contains at least one element in 'range'.
365    pub fn intersects_range(&self, range: RangeInclusive<T>) -> bool {
366        self.range(range).next().is_some()
367    }
368
369    /// Returns true if this set contains at least one element in 'other'.
370    pub fn intersects_set(&self, other: &IntSet<T>) -> bool {
371        // Iterate the smaller set and check for member ship in the larger set
372        // Estimate the true size as the number of pages.
373        let (a, b) = match (&self.0, &other.0) {
374            (Membership::Inclusive(us), Membership::Inclusive(them)) => {
375                // Can utilize the bitset intersects method.
376                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    /// Returns `true` if this set is a subset of `other`.
400    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                // For this (A) to be a subset of other (B):
410                // - All members of the domain T must be in either A, B, or both
411                // - So we check that A U B = T, which we can do by checking |A U B| = |T|
412                // - |A U B| is given by |A| + |B| - |A n B| (inclusion exclusion principle)
413                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    /// Returns first element in the set, if any. This element is always the minimum of all elements in the set.
420    pub fn first(&self) -> Option<T> {
421        return self.iter().next();
422    }
423
424    /// Returns the last element in the set, if any. This element is always the maximum of all elements in the set.
425    pub fn last(&self) -> Option<T> {
426        return self.iter().next_back();
427    }
428
429    /// Returns `true` if the set contains a value.
430    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    /// Returns the number of members in this set.
439    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    /// Return true if there are no members in this set.
447    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    /// Create a new, (empty) `IntSet`.
460    ///
461    /// You can create a new full set with [`IntSet::all`].
462    pub const fn new() -> Self {
463        Self::empty()
464    }
465
466    /// Create a new empty set (inclusive).
467    pub const fn empty() -> Self {
468        IntSet(Membership::Inclusive(U32Set::empty()), PhantomData::<T>)
469    }
470
471    /// Create a new set which contains all integers (exclusive).
472    pub const fn all() -> Self {
473        IntSet(Membership::Exclusive(U32Set::empty()), PhantomData::<T>)
474    }
475
476    /// Returns true if this set is inverted (has exclusive membership).
477    pub fn is_inverted(&self) -> bool {
478        match &self.0 {
479            Membership::Inclusive(_) => false,
480            Membership::Exclusive(_) => true,
481        }
482    }
483
484    /// Return the inverted version of this set.
485    pub fn invert(&mut self) {
486        let reuse_storage = match &mut self.0 {
487            // take the existing storage to reuse in a new set of the opposite
488            // type.
489            Membership::Inclusive(s) | Membership::Exclusive(s) => {
490                std::mem::replace(s, U32Set::empty())
491            }
492        };
493
494        // reuse the storage with a membership of the opposite type.
495        self.0 = match &mut self.0 {
496            Membership::Inclusive(_) => Membership::Exclusive(reuse_storage),
497            Membership::Exclusive(_) => Membership::Inclusive(reuse_storage),
498        };
499    }
500
501    /// Clears the set, removing all values.
502    pub fn clear(&mut self) {
503        let mut reuse_storage = match &mut self.0 {
504            // if we're inclusive, we just clear the storage
505            Membership::Inclusive(s) => {
506                s.clear();
507                return;
508            }
509            // otherwise take the existing storage to reuse in a new
510            // inclusive set:
511            Membership::Exclusive(s) => std::mem::replace(s, U32Set::empty()),
512        };
513        // reuse the now empty storage and mark us as inclusive
514        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    /// Extends a collection with the contents of an iterator.
529    ///
530    /// This implementation is optimized to provide the best performance when the iterator contains sorted values.
531    /// Consider using [`extend_unsorted()`] if the iterator is known to contain unsorted values.
532    ///
533    /// [`extend_unsorted()`]: IntSet::extend_unsorted
534    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                // while these sets have different membership modes, they can still be equal if they happen to have
551                // the same effective set of members. In this case fallback to checking via iterator equality.
552                // iter_ranges() is used instead of iter() because for exclusive sets it's likely to be significantly
553                // faster and have far less items.
554                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                    // Shortcut iteration equality check if lengths aren't the same.
564                    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        // Because equality considers two sets with the same effective members (but different membership modes) as
574        // equal, hash must be based on the effective member set as well. Exclusive sets may have extremely large numbers
575        // of effective members, so here we use iter_ranges() to produce the hash, which should typically produce a more
576        // reasonable numbers elements.
577        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                                // If a range isn't equal then there are two possible scenarios:
605                                // 1. The set with the shorter range has at least one more range.
606                                //    In this case the set with the shorter range's next element will always be bigger
607                                //    then the other set's next element and should be considered greater.
608                                // 2. The set with the shorter range does not have anymore ranges, in that case we
609                                //    know the other set has at least one more element and thus should be considered greater.
610                                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                    // There are no skips left in the iterator, but there may still be a skipped
779                    // number on the backwards iteration, so check that.
780                    if let Some(skip) = self.next_skipped_backward {
781                        if skip == index {
782                            // this index should be skipped, go to the next one.
783                            break;
784                        }
785                    }
786                    // No-longer any values to skip, can freely return index
787                    return Some(index);
788                };
789
790                if index < skip {
791                    // Not a skipped value
792                    return Some(index);
793                }
794
795                self.next_skipped_forward = self.set_values.next();
796                if index > skip {
797                    // We've passed the skip value, need to check the next one.
798                    continue;
799                }
800
801                // index == skip, so we need to skip this index.
802                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                    // There are no skips left in the iterator, but there may still be a skipped
824                    // number on the backwards iteration, so check that.
825                    if let Some(skip) = self.next_skipped_forward {
826                        if skip == index {
827                            // this index should be skipped, go to the next one.
828                            break;
829                        }
830                    }
831                    // No-longer any values to skip, can freely return index
832                    return Some(index);
833                };
834
835                if index > skip {
836                    // Not a skipped value
837                    return Some(index);
838                }
839
840                self.next_skipped_backward = self.set_values.next_back();
841                if index < skip {
842                    // We've passed the skip value, need to check the next one.
843                    continue;
844                }
845
846                // index == skip, so we need to skip this index.
847                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                // Discontinuous domains need special handling since members of the domain may be adjacent
899                // while their u32 representations may not be. So this iterator implementation compares successive
900                // ranges from the underlying u32 range iterator and merges any ranges that are found to be adjacent
901                // in the domain of type T.
902                let Some(next_range) = ranges.next() else {
903                    // No more ranges, commit the one we've got.
904                    return current_range.take();
905                };
906
907                let Some(range) = current_range.clone() else {
908                    // Populate current range, then move to the next so we can check if it's adjacent.
909                    *current_range = Some(next_range);
910                    continue;
911                };
912
913                // Check if next_range can merge into current_range
914                if RangeIter::<InclusiveRangeIter, AllValuesIter, T>::are_values_adjacent(
915                    *range.end(),
916                    *next_range.start(),
917                ) {
918                    // Do the merge, and check next
919                    *current_range = Some(*range.start()..=*next_range.end());
920                    continue;
921                }
922
923                // No merge is possible, return current range and replace it with next
924                *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    /// Iterate the ranges of an exclusive set where the domain is continuous.
953    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    /// Iterate the ranges of an exclusive set where the domain is discontinuous.
993    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                // No more values, so the current range is over, return it.
1005                return current_range;
1006            };
1007
1008            if set.contains(next) {
1009                if let Some(range) = current_range {
1010                    // current range has ended, return it. No need to save 'next' as it's not in the set.
1011                    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(); // skip 'a'
1028        if let Some(second) = it.next() {
1029            // if a and b are adject then the second value in the iterator should be 'b'
1030            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)] // SipHasher required because of MSRV
1508    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        // Forward skip first
1664        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        // Backward skip first
1671        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        // Check we can safely iterate to the limits of u32.
1816        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                // Ensure a page exists for x.
2160                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        // Inclusive - Inclusive
2555        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)); // Rejection via length check (7 > 6)
2563
2564        assert!(!a.is_subset(&c)); // Rejection via member check (6 <= 6)
2565        assert!(!c.is_subset(&a));
2566
2567        // Inclusive - Exclusive
2568        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)); // a doesn't contain 13
2575        assert!(!a.is_subset(&all_but_5)); // a contains 5 which is excluded in excl_5
2576        assert!(empty.is_subset(&all_but_13));
2577
2578        // Exclusive - Inclusive
2579        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]))); // Rejection via length check (255 > 3)
2601        assert!(!all_but_1_2.is_subset(&incl_all_but_3)); // Rejection via member check (254 <= 255)
2602
2603        // Exclusive - Exclusive
2604        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)); // Rejection via length check (255 > 254)
2610        assert!(!all_but_1_2.is_subset(&all_but_2_3)); // Rejection via member (254 <= 254)
2611        assert!(IntSet::<u32>::all().is_subset(&IntSet::<u32>::all()));
2612
2613        // Discontinuous Domain
2614        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)); // Rejection via length check (3 > 2)
2621        assert!(!even_c.is_subset(&even_a)); // Rejection via member check (2 <= 2)
2622    }
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); // out of order
2749        assert_ord!([1u16, 2, 3], [1, 2, 3, 4], Ordering::Less); // out of order
2750        assert_ord!([2u16, 3, 4], [1, 2, 3, 4, 5], Ordering::Greater); // out of order
2751
2752        // Exclusive - Exclusive
2753        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        // Mixed
2771        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}