rotated_array_set/
lib.rs

1//! An ordered set based on a 2-level rotated array.
2//!
3//! See <a href="https://github.com/senderista/rotated-array-set/blob/master/README.md">the repository README</a> for a detailed discussion of this collection's performance
4//! benefits and drawbacks.
5
6#![doc(html_root_url = "https://docs.rs/rotated-array-set/0.1.0/rotated_array_set/")]
7#![doc(
8    html_logo_url = "https://raw.githubusercontent.com/senderista/rotated-array-set/master/img/cells.png"
9)]
10
11use std::cmp::Ordering::{self, Equal, Greater, Less};
12use std::cmp::{max, min};
13use std::fmt::Debug;
14use std::hash::{Hash, Hasher};
15use std::iter::{DoubleEndedIterator, ExactSizeIterator, FromIterator, FusedIterator, Peekable};
16use std::mem;
17use std::ops::Bound::{Excluded, Included, Unbounded};
18use std::ops::RangeBounds;
19// remove when Iterator::is_sorted is stabilized
20use is_sorted::IsSorted;
21
22/// An ordered set based on a 2-level rotated array.
23///
24/// # Examples
25///
26/// ```
27/// use rotated_array_set::RotatedArraySet;
28///
29/// // Type inference lets us omit an explicit type signature (which
30/// // would be `RotatedArraySet<i32>` in this example).
31/// let mut ints = RotatedArraySet::new();
32///
33/// // Add some integers.
34/// ints.insert(-1);
35/// ints.insert(6);
36/// ints.insert(1729);
37/// ints.insert(24);
38///
39/// // Check for a specific one.
40/// if !ints.contains(&42) {
41///     println!("We don't have the answer to Life, the Universe, and Everything :-(");
42/// }
43///
44/// // Remove an integer.
45/// ints.remove(&6);
46///
47/// // Iterate over everything.
48/// for int in &ints {
49///     println!("{}", int);
50/// }
51/// ```
52#[derive(Debug, Clone)]
53pub struct RotatedArraySet<T> {
54    data: Vec<T>,
55    min_indexes: Vec<usize>,
56    min_data: Vec<T>,
57}
58
59// Internal encapsulation of container + bounds
60#[derive(Debug, Copy, Clone)]
61struct Range<'a, T: 'a> {
62    container: &'a RotatedArraySet<T>,
63    start_index_inclusive: usize,
64    end_index_exclusive: usize,
65}
66
67impl<'a, T> Range<'a, T>
68where
69    T: Ord + Copy + Default + Debug,
70{
71    fn with_bounds(
72        container: &'a RotatedArraySet<T>,
73        start_index_inclusive: usize,
74        end_index_exclusive: usize,
75    ) -> Range<'a, T> {
76        assert!(end_index_exclusive >= start_index_inclusive);
77        assert!(end_index_exclusive <= container.len());
78        Range {
79            container,
80            start_index_inclusive,
81            end_index_exclusive,
82        }
83    }
84
85    fn new(container: &'a RotatedArraySet<T>) -> Range<'a, T> {
86        Range::with_bounds(container, 0, container.len())
87    }
88
89    fn at(&self, index: usize) -> Option<&'a T> {
90        let container_idx = index + self.start_index_inclusive;
91        self.container.select(container_idx)
92    }
93
94    fn len(&self) -> usize {
95        self.end_index_exclusive - self.start_index_inclusive
96    }
97}
98
99/// An iterator over the items of a `RotatedArraySet`.
100///
101/// This `struct` is created by the [`iter`] method on [`RotatedArraySet`][`RotatedArraySet`].
102/// See its documentation for more.
103///
104/// [`RotatedArraySet`]: struct.RotatedArraySet.html
105/// [`iter`]: struct.RotatedArraySet.html#method.iter
106#[derive(Debug, Copy, Clone)]
107pub struct Iter<'a, T: 'a> {
108    range: Range<'a, T>,
109    next_index: usize,
110    next_rev_index: usize,
111}
112
113impl<'a, T> Iter<'a, T>
114where
115    T: Ord + Copy + Default + Debug,
116{
117    fn new(range: Range<'a, T>) -> Iter<'a, T> {
118        let next_index = 0;
119        let next_rev_index = if range.len() == 0 { 0 } else { range.len() - 1 };
120        Iter {
121            range,
122            next_index,
123            next_rev_index,
124        }
125    }
126
127    #[inline(always)]
128    fn assert_invariants(&self) -> bool {
129        assert!(self.next_index <= self.range.len());
130        assert!(self.next_rev_index <= self.range.len());
131        if self.next_rev_index < self.next_index {
132            assert!(self.next_index - self.next_rev_index == 1);
133        }
134        true
135    }
136}
137
138/// An owning iterator over the items of a `RotatedArraySet`.
139///
140/// This `struct` is created by the [`into_iter`] method on [`RotatedArraySet`][`RotatedArraySet`]
141/// (provided by the `IntoIterator` trait). See its documentation for more.
142///
143/// [`RotatedArraySet`]: struct.RotatedArraySet.html
144/// [`into_iter`]: struct.RotatedArraySet.html#method.into_iter
145#[derive(Debug, Clone)]
146pub struct IntoIter<T> {
147    vec: Vec<T>,
148    next_index: usize,
149}
150
151/// A lazy iterator producing elements in the difference of `RotatedArraySet`s.
152///
153/// This `struct` is created by the [`difference`] method on [`RotatedArraySet`].
154/// See its documentation for more.
155///
156/// [`RotatedArraySet`]: struct.RotatedArraySet.html
157/// [`difference`]: struct.RotatedArraySet.html#method.difference
158#[derive(Debug, Clone)]
159pub struct Difference<'a, T: 'a> {
160    self_iter: Iter<'a, T>,
161    other_set: &'a RotatedArraySet<T>,
162}
163
164/// A lazy iterator producing elements in the symmetric difference of `RotatedArraySet`s.
165///
166/// This `struct` is created by the [`symmetric_difference`] method on
167/// [`RotatedArraySet`]. See its documentation for more.
168///
169/// [`RotatedArraySet`]: struct.RotatedArraySet.html
170/// [`symmetric_difference`]: struct.RotatedArraySet.html#method.symmetric_difference
171#[derive(Debug, Clone)]
172pub struct SymmetricDifference<'a, T: 'a>
173where
174    T: Ord + Copy + Default + Debug,
175{
176    a: Peekable<Iter<'a, T>>,
177    b: Peekable<Iter<'a, T>>,
178}
179
180/// A lazy iterator producing elements in the intersection of `RotatedArraySet`s.
181///
182/// This `struct` is created by the [`intersection`] method on [`RotatedArraySet`].
183/// See its documentation for more.
184///
185/// [`RotatedArraySet`]: struct.RotatedArraySet.html
186/// [`intersection`]: struct.RotatedArraySet.html#method.intersection
187#[derive(Debug, Clone)]
188pub struct Intersection<'a, T: 'a> {
189    small_iter: Iter<'a, T>,
190    large_set: &'a RotatedArraySet<T>,
191}
192
193/// A lazy iterator producing elements in the union of `RotatedArraySet`s.
194///
195/// This `struct` is created by the [`union`] method on [`RotatedArraySet`].
196/// See its documentation for more.
197///
198/// [`RotatedArraySet`]: struct.RotatedArraySet.html
199/// [`union`]: struct.RotatedArraySet.html#method.union
200#[derive(Debug, Clone)]
201pub struct Union<'a, T: 'a>
202where
203    T: Ord + Copy + Default + Debug,
204{
205    a: Peekable<Iter<'a, T>>,
206    b: Peekable<Iter<'a, T>>,
207}
208
209impl<T> RotatedArraySet<T>
210where
211    T: Ord + Copy + Default + Debug,
212{
213    /// Makes a new `RotatedArraySet` without any heap allocations.
214    ///
215    /// This is a constant-time operation.
216    ///
217    /// # Examples
218    ///
219    /// ```
220    /// # #![allow(unused_mut)]
221    /// use rotated_array_set::RotatedArraySet;
222    ///
223    /// let mut set: RotatedArraySet<i32> = RotatedArraySet::new();
224    /// ```
225    pub fn new() -> Self {
226        RotatedArraySet {
227            data: Vec::new(),
228            min_indexes: Vec::new(),
229            min_data: Vec::new(),
230        }
231    }
232
233    /// Constructs a new, empty `RotatedArraySet<T>` with the specified capacity.
234    ///
235    /// The set will be able to hold exactly `capacity` elements without
236    /// reallocating. If `capacity` is 0, the set will not allocate.
237    ///
238    /// It is important to note that although the returned set has the
239    /// *capacity* specified, the set will have a zero *length*.
240    ///
241    /// # Examples
242    ///
243    /// ```
244    /// use rotated_array_set::RotatedArraySet;
245    ///
246    /// let mut set = RotatedArraySet::with_capacity(10);
247    ///
248    /// // The set contains no items, even though it has capacity for more
249    /// assert_eq!(set.len(), 0);
250    ///
251    /// // These are all done without reallocating...
252    /// for i in 0..10 {
253    ///     set.insert(i);
254    /// }
255    ///
256    /// // ...but this may make the set reallocate
257    /// set.insert(11);
258    /// ```
259    pub fn with_capacity(capacity: usize) -> RotatedArraySet<T> {
260        let min_indexes_capacity = if capacity > 0 {
261            Self::get_subarray_idx_from_array_idx(capacity - 1) + 1
262        } else {
263            0
264        };
265        RotatedArraySet {
266            data: Vec::with_capacity(capacity),
267            min_indexes: Vec::with_capacity(min_indexes_capacity),
268            min_data: Vec::with_capacity(min_indexes_capacity),
269        }
270    }
271
272    /// Clears the set, removing all values.
273    ///
274    /// This is a constant-time operation.
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// use rotated_array_set::RotatedArraySet;
280    ///
281    /// let mut v = RotatedArraySet::new();
282    /// v.insert(1);
283    /// v.clear();
284    /// assert!(v.is_empty());
285    /// ```
286    pub fn clear(&mut self) {
287        self.data.clear();
288        self.min_indexes.clear();
289        self.min_data.clear();
290    }
291
292    /// Returns `true` if the set contains a value.
293    ///
294    /// This is an `O(lg n)` operation.
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// use rotated_array_set::RotatedArraySet;
300    ///
301    /// let set: RotatedArraySet<_> = vec![1, 2, 3].into();
302    /// assert_eq!(set.contains(&1), true);
303    /// assert_eq!(set.contains(&4), false);
304    /// ```
305    pub fn contains(&self, value: &T) -> bool {
306        self.get(value).is_some()
307    }
308
309    /// Returns `true` if `self` has no elements in common with `other`.
310    /// This is equivalent to checking for an empty intersection.
311    ///
312    /// # Examples
313    ///
314    /// ```
315    /// use rotated_array_set::RotatedArraySet;
316    ///
317    /// let a: RotatedArraySet<_> = vec![1, 2, 3].into();
318    /// let mut b = RotatedArraySet::new();
319    ///
320    /// assert_eq!(a.is_disjoint(&b), true);
321    /// b.insert(4);
322    /// assert_eq!(a.is_disjoint(&b), true);
323    /// b.insert(1);
324    /// assert_eq!(a.is_disjoint(&b), false);
325    /// ```
326    pub fn is_disjoint(&self, other: &RotatedArraySet<T>) -> bool {
327        self.intersection(other).next().is_none()
328    }
329
330    /// Returns `true` if the set is a subset of another,
331    /// i.e., `other` contains at least all the values in `self`.
332    ///
333    /// # Examples
334    ///
335    /// ```
336    /// use rotated_array_set::RotatedArraySet;
337    ///
338    /// let sup: RotatedArraySet<_> = vec![1, 2, 3].into();
339    /// let mut set = RotatedArraySet::new();
340    ///
341    /// assert_eq!(set.is_subset(&sup), true);
342    /// set.insert(2);
343    /// assert_eq!(set.is_subset(&sup), true);
344    /// set.insert(4);
345    /// assert_eq!(set.is_subset(&sup), false);
346    /// ```
347    pub fn is_subset(&self, other: &RotatedArraySet<T>) -> bool {
348        // Same result as self.difference(other).next().is_none()
349        // but much faster.
350        if self.len() > other.len() {
351            false
352        } else {
353            // Iterate `self`, searching for matches in `other`.
354            for next in self {
355                if !other.contains(next) {
356                    return false;
357                }
358            }
359            true
360        }
361    }
362
363    /// Returns `true` if the set is a superset of another,
364    /// i.e., `self` contains at least all the values in `other`.
365    ///
366    /// # Examples
367    ///
368    /// ```
369    /// use rotated_array_set::RotatedArraySet;
370    ///
371    /// let sub: RotatedArraySet<_> = vec![1, 2].into();
372    /// let mut set = RotatedArraySet::new();
373    ///
374    /// assert_eq!(set.is_superset(&sub), false);
375    ///
376    /// set.insert(0);
377    /// set.insert(1);
378    /// assert_eq!(set.is_superset(&sub), false);
379    ///
380    /// set.insert(2);
381    /// assert_eq!(set.is_superset(&sub), true);
382    /// ```
383    pub fn is_superset(&self, other: &RotatedArraySet<T>) -> bool {
384        other.is_subset(self)
385    }
386
387    /// Returns a reference to the value in the set, if any, that is equal to the given value.
388    ///
389    /// This is an `O(lg n)` operation.
390    ///
391    /// # Examples
392    ///
393    /// ```
394    /// use rotated_array_set::RotatedArraySet;
395    ///
396    /// let set: RotatedArraySet<_> = vec![1, 2, 3].into();
397    /// assert_eq!(set.get(&2), Some(&2));
398    /// assert_eq!(set.get(&4), None);
399    /// ```
400    pub fn get(&self, value: &T) -> Option<&T> {
401        let raw_idx = self.find_raw_index(value).ok()?;
402        Some(&self.data[raw_idx])
403    }
404
405    /// Returns the rank of the value in the set if it exists (as `Result::Ok`),
406    /// or the rank of its largest predecessor plus one, if it does not exist (as `Result::Err`).
407    /// This is a constant-time operation.
408    ///
409    /// # Examples
410    ///
411    /// ```
412    /// use rotated_array_set::RotatedArraySet;
413    ///
414    /// let set: RotatedArraySet<_> = vec![1, 2, 3].into();
415    /// assert_eq!(set.rank(&1), Ok(0));
416    /// assert_eq!(set.rank(&4), Err(3));
417    /// ```
418    pub fn rank(&self, value: &T) -> Result<usize, usize> {
419        let (raw_index, exists) = match self.find_raw_index(value) {
420            Ok(index) => (index, true),
421            Err(index) => (index, false),
422        };
423        if raw_index == self.data.len() {
424            return Err(raw_index);
425        }
426        debug_assert!(raw_index < self.data.len());
427        let subarray_idx = Self::get_subarray_idx_from_array_idx(raw_index);
428        let subarray_start_idx = Self::get_array_idx_from_subarray_idx(subarray_idx);
429        let subarray_len = if subarray_idx == self.min_indexes.len() - 1 {
430            self.data.len() - subarray_start_idx
431        } else {
432            subarray_idx + 1
433        };
434        let pivot_idx = subarray_start_idx + self.min_indexes[subarray_idx];
435        let logical_index = if raw_index >= pivot_idx {
436            subarray_start_idx + raw_index - pivot_idx
437        } else {
438            subarray_start_idx + subarray_len - (pivot_idx - raw_index)
439        };
440        if exists {
441            Ok(logical_index)
442        } else {
443            Err(logical_index)
444        }
445    }
446
447    /// Returns a reference to the value in the set, if any, with the given rank.
448    ///
449    /// This is a constant-time operation.
450    ///
451    /// # Examples
452    ///
453    /// ```
454    /// use rotated_array_set::RotatedArraySet;
455    ///
456    /// let set: RotatedArraySet<_> = vec![1, 2, 3].into();
457    /// assert_eq!(set.select(0), Some(&1));
458    /// assert_eq!(set.select(3), None);
459    /// ```
460    pub fn select(&self, rank: usize) -> Option<&T> {
461        if rank >= self.data.len() {
462            return None;
463        }
464        let subarray_idx = Self::get_subarray_idx_from_array_idx(rank);
465        let subarray_start_idx = Self::get_array_idx_from_subarray_idx(subarray_idx);
466        let subarray_len = if subarray_idx == self.min_indexes.len() - 1 {
467            self.data.len() - subarray_start_idx
468        } else {
469            subarray_idx + 1
470        };
471        debug_assert!(rank >= subarray_start_idx);
472        let idx_offset = rank - subarray_start_idx;
473        let pivot_offset = self.min_indexes[subarray_idx];
474        let rotated_offset = (pivot_offset + idx_offset) % subarray_len;
475        debug_assert!(rotated_offset < subarray_len);
476        let raw_idx = subarray_start_idx + rotated_offset;
477        Some(&self.data[raw_idx])
478    }
479
480    /// Adds a value to the set.
481    ///
482    /// This is an `O(√n)` operation.
483    ///
484    /// If the set did not have this value present, `true` is returned.
485    ///
486    /// If the set did have this value present, `false` is returned, and the
487    /// entry is not updated.
488    ///
489    /// # Examples
490    ///
491    /// ```
492    /// use rotated_array_set::RotatedArraySet;
493    ///
494    /// let mut set = RotatedArraySet::new();
495    ///
496    /// assert_eq!(set.insert(2), true);
497    /// assert_eq!(set.insert(2), false);
498    /// assert_eq!(set.len(), 1);
499    /// ```
500    pub fn insert(&mut self, value: T) -> bool {
501        let insert_idx = match self.find_raw_index(&value).err() {
502            None => return false,
503            Some(idx) => idx,
504        };
505        // find subarray containing this insertion point
506        let subarray_idx = Self::get_subarray_idx_from_array_idx(insert_idx);
507        // inserted element could be in a new subarray
508        debug_assert!(subarray_idx <= self.min_indexes.len());
509        // create a new subarray if necessary
510        if subarray_idx == self.min_indexes.len() {
511            self.min_indexes.push(0);
512            self.min_data.push(T::default());
513        }
514        debug_assert_eq!(self.min_indexes.len(), self.min_data.len());
515        let subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx);
516        // if insertion point is in last subarray and last subarray isn't full, just insert the new element
517        if subarray_idx == self.min_indexes.len() - 1 && !self.is_last_subarray_full() {
518            // Since we always insert into a partially full subarray in sorted order,
519            // there is no need to update the pivot location, but we do have to update
520            // the pivot value.
521            debug_assert!(self.min_indexes[subarray_idx] == 0);
522            self.data.insert(insert_idx, value);
523            // These writes are redundant unless the minimum has changed, but avoiding a branch may be worth it,
524            // given that the end of the data arrays should be in cache.
525            self.min_data[subarray_idx] = self.data[subarray_offset];
526            debug_assert!(self.assert_invariants());
527            return true;
528        }
529        // From now on, we can assume that the subarray we're inserting into is always full.
530        let next_subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx + 1);
531        let subarray = &mut self.data[subarray_offset..next_subarray_offset];
532        let pivot_offset = self.min_indexes[subarray_idx];
533        let insert_offset = insert_idx - subarray_offset;
534        let max_offset = if pivot_offset == 0 {
535            subarray.len() - 1
536        } else {
537            pivot_offset - 1
538        };
539        let mut prev_max = subarray[max_offset];
540        // this logic is best understood with a diagram of a rotated array, e.g.:
541        //
542        // ------------------------------------------------------------------------
543        // | 12 | 13 | 14 | 15 | 16 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
544        // ------------------------------------------------------------------------
545        //
546        if max_offset < pivot_offset && insert_offset >= pivot_offset {
547            subarray.copy_within(pivot_offset..insert_offset, max_offset);
548            subarray[insert_offset - 1] = value;
549            self.min_indexes[subarray_idx] = max_offset;
550            self.min_data[subarray_idx] = subarray[max_offset];
551        } else {
552            subarray.copy_within(insert_offset..max_offset, insert_offset + 1);
553            subarray[insert_offset] = value;
554            if insert_offset == pivot_offset {
555                // inserted value is new minimum for subarray
556                self.min_data[subarray_idx] = value;
557            }
558        }
559        debug_assert!(self.assert_invariants());
560        let max_subarray_idx = self.min_indexes.len() - 1;
561        let next_subarray_idx = subarray_idx + 1;
562        let last_subarray_full = self.is_last_subarray_full();
563        // now loop over all remaining subarrays, setting the min (pivot) of each to the max of its predecessor
564        for (i, pivot_offset_ref) in self.min_indexes[next_subarray_idx..].iter_mut().enumerate() {
565            let cur_subarray_idx = next_subarray_idx + i;
566            // if the last subarray isn't full, skip it
567            if cur_subarray_idx == max_subarray_idx && !last_subarray_full {
568                break;
569            }
570            let max_offset = if *pivot_offset_ref == 0 {
571                cur_subarray_idx
572            } else {
573                *pivot_offset_ref - 1
574            };
575            let max_idx = max_offset + Self::get_array_idx_from_subarray_idx(cur_subarray_idx);
576            let next_max = self.data[max_idx];
577            self.data[max_idx] = prev_max;
578            *pivot_offset_ref = max_offset;
579            self.min_data[cur_subarray_idx] = prev_max;
580            prev_max = next_max;
581        }
582        // if the last subarray was full, append current max to a new subarray, otherwise insert max in sorted order
583        if last_subarray_full {
584            self.data.push(prev_max);
585            self.min_indexes.push(0);
586            self.min_data.push(prev_max);
587        } else {
588            let max_subarray_offset = Self::get_array_idx_from_subarray_idx(max_subarray_idx);
589            // since `max` is guaranteed to be <= the pivot value, we always insert it at the pivot location
590            debug_assert!(prev_max <= self.data[max_subarray_offset]);
591            self.data.insert(max_subarray_offset, prev_max);
592            self.min_data[max_subarray_idx] = prev_max;
593        }
594        debug_assert!(self.find_raw_index(&value).is_ok());
595        debug_assert!(self.assert_invariants());
596        true
597    }
598
599    /// Removes a value from the set. Returns whether the value was
600    /// present in the set.
601    ///
602    /// This is an `O(√n)` operation.
603    ///
604    /// # Examples
605    ///
606    /// ```
607    /// use rotated_array_set::RotatedArraySet;
608    ///
609    /// let mut set = RotatedArraySet::new();
610    ///
611    /// set.insert(2);
612    /// assert_eq!(set.remove(&2), true);
613    /// assert_eq!(set.remove(&2), false);
614    /// ```
615    pub fn remove(&mut self, value: &T) -> bool {
616        let mut remove_idx = match self.find_raw_index(&value).ok() {
617            Some(idx) => idx,
618            None => return false,
619        };
620        let max_subarray_idx = self.min_indexes.len() - 1;
621        let max_subarray_offset = Self::get_array_idx_from_subarray_idx(max_subarray_idx);
622        // find subarray containing the element to remove
623        let subarray_idx = Self::get_subarray_idx_from_array_idx(remove_idx);
624        debug_assert!(subarray_idx <= max_subarray_idx);
625        let subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx);
626        // if we're not removing an element in the last subarray, then we end up deleting its minimum,
627        // which is always at the first offset since it's sorted
628        let mut max_subarray_remove_idx = if subarray_idx == max_subarray_idx {
629            remove_idx
630        } else {
631            max_subarray_offset
632        };
633        // if the last subarray was rotated, sort it to maintain insert invariant
634        if self.is_last_subarray_full() {
635            let last_min_offset = self.min_indexes[max_subarray_idx];
636            // rotate left by the min offset instead of sorting
637            self.data[max_subarray_offset..].rotate_left(last_min_offset);
638            self.min_indexes[max_subarray_idx] = 0;
639            // the remove index might change after sorting the last subarray
640            if subarray_idx == max_subarray_idx {
641                remove_idx = self
642                    .find_raw_index(&value)
643                    .expect("recalculating remove index after sorting");
644                max_subarray_remove_idx = remove_idx;
645            }
646        }
647        // if insertion point is not in last subarray, perform a "hard exchange"
648        if subarray_idx < max_subarray_idx {
649            // From now on, we can assume that the subarray we're removing from is full.
650            let next_subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx + 1);
651            let subarray = &mut self.data[subarray_offset..next_subarray_offset];
652            let pivot_offset = self.min_indexes[subarray_idx];
653            let remove_offset = remove_idx - subarray_offset;
654            let max_offset = if pivot_offset == 0 {
655                subarray.len() - 1
656            } else {
657                pivot_offset - 1
658            };
659            // this logic is best understood with a diagram of a rotated array, e.g.:
660            //
661            // ------------------------------------------------------------------------
662            // | 12 | 13 | 14 | 15 | 16 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
663            // ------------------------------------------------------------------------
664            //
665            let mut prev_max_offset = if max_offset < pivot_offset && remove_offset >= pivot_offset
666            {
667                subarray.copy_within(pivot_offset..remove_offset, pivot_offset + 1);
668                let new_pivot_offset = if pivot_offset == subarray.len() - 1 {
669                    0
670                } else {
671                    pivot_offset + 1
672                };
673                self.min_indexes[subarray_idx] = new_pivot_offset;
674                self.min_data[subarray_idx] = subarray[new_pivot_offset];
675                pivot_offset
676            } else {
677                subarray.copy_within(remove_offset + 1..=max_offset, remove_offset);
678                if remove_offset == pivot_offset {
679                    self.min_data[subarray_idx] = subarray[pivot_offset];
680                }
681                max_offset
682            };
683            let next_subarray_idx = min(max_subarray_idx, subarray_idx + 1);
684            // now perform an "easy exchange" in all remaining subarrays except the last,
685            // setting the max of each to the min of its successor.
686            for (i, pivot_offset_ref) in self.min_indexes[next_subarray_idx..max_subarray_idx]
687                .iter_mut()
688                .enumerate()
689            {
690                let cur_subarray_idx = next_subarray_idx + i;
691                let cur_subarray_offset = Self::get_array_idx_from_subarray_idx(cur_subarray_idx);
692                let prev_max_idx =
693                    prev_max_offset + Self::get_array_idx_from_subarray_idx(cur_subarray_idx - 1);
694                self.data[prev_max_idx] = self.data[cur_subarray_offset + *pivot_offset_ref];
695                // the min_data array needs to be updated when the previous subarray's max offset
696                // coincides with its min offset, i.e., when it is subarray 0
697                if cur_subarray_idx == 1 {
698                    self.min_data[0] = self.data[0];
699                    debug_assert!(IsSorted::is_sorted(&mut self.min_data.iter()));
700                }
701                prev_max_offset = *pivot_offset_ref;
702                let new_min_offset = if *pivot_offset_ref == cur_subarray_idx {
703                    0
704                } else {
705                    *pivot_offset_ref + 1
706                };
707                *pivot_offset_ref = new_min_offset;
708                self.min_data[cur_subarray_idx] = self.data[cur_subarray_offset + new_min_offset];
709                debug_assert!(IsSorted::is_sorted(&mut self.min_data.iter()));
710            }
711            // now we fix up the last subarray. if it was initially full, we need to sort it to maintain the insert invariant.
712            // if the removed element is in the last subarray, we just sort and remove() on the vec, updating auxiliary arrays.
713            // otherwise, we copy the minimum to the max position of the previous subarray, then remove it and fix up
714            // auxiliary arrays.
715            let prev_max_idx =
716                prev_max_offset + Self::get_array_idx_from_subarray_idx(max_subarray_idx - 1);
717            // since the last subarray is always sorted, its minimum element is always on the first offset
718            self.data[prev_max_idx] = self.data[max_subarray_offset];
719            // the min_data array needs to be updated when the previous subarray's max offset
720            // coincides with its min offset, i.e., when it is subarray 0
721            if max_subarray_idx == 1 {
722                self.min_data[0] = self.data[0];
723                debug_assert!(IsSorted::is_sorted(&mut self.min_data.iter()));
724            }
725        }
726        self.data.remove(max_subarray_remove_idx);
727        // if last subarray is now empty, trim the auxiliary arrays
728        if max_subarray_offset == self.data.len() {
729            self.min_indexes.pop();
730            self.min_data.pop();
731        } else {
732            // since the last subarray is always sorted, its minimum is always on the first offset
733            self.min_data[max_subarray_idx] = self.data[max_subarray_offset];
734            debug_assert!(IsSorted::is_sorted(&mut self.min_data.iter()));
735        }
736        debug_assert!(self.find_raw_index(&value).is_err());
737        debug_assert!(self.assert_invariants());
738        true
739    }
740
741    /// Removes and returns the value in the set, if any, that is equal to the given one.
742    ///
743    /// This is an `O(√n)` operation.
744    ///
745    /// # Examples
746    ///
747    /// ```
748    /// use rotated_array_set::RotatedArraySet;
749    ///
750    /// let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
751    /// assert_eq!(set.take(&2), Some(2));
752    /// assert_eq!(set.take(&2), None);
753    /// ```
754    pub fn take(&mut self, value: &T) -> Option<T> {
755        let ret = self.get(value).copied();
756        if ret.is_some() {
757            self.remove(value);
758        }
759        ret
760    }
761
762    /// Moves all elements from `other` into `Self`, leaving `other` empty.
763    ///
764    /// # Examples
765    ///
766    /// ```
767    /// use rotated_array_set::RotatedArraySet;
768    ///
769    /// let mut a = RotatedArraySet::new();
770    /// a.insert(1);
771    /// a.insert(2);
772    /// a.insert(3);
773    ///
774    /// let mut b = RotatedArraySet::new();
775    /// b.insert(3);
776    /// b.insert(4);
777    /// b.insert(5);
778    ///
779    /// a.append(&mut b);
780    ///
781    /// assert_eq!(a.len(), 5);
782    /// assert_eq!(b.len(), 0);
783    ///
784    /// assert!(a.contains(&1));
785    /// assert!(a.contains(&2));
786    /// assert!(a.contains(&3));
787    /// assert!(a.contains(&4));
788    /// assert!(a.contains(&5));
789    /// ```
790    pub fn append(&mut self, other: &mut Self) {
791        // allocate new set and copy union into it
792        let mut union: Self = self.union(other).cloned().collect();
793        // empty `other`
794        other.clear();
795        // steal data from new set and drop data from old set
796        mem::swap(self, &mut union);
797    }
798
799    /// Splits the collection into two at `value`. Returns everything after `value`,
800    /// including `value` itself.
801    ///
802    /// # Examples
803    ///
804    /// Basic usage:
805    ///
806    /// ```
807    /// use rotated_array_set::RotatedArraySet;
808    ///
809    /// let mut a = RotatedArraySet::new();
810    /// a.insert(1);
811    /// a.insert(2);
812    /// a.insert(3);
813    /// a.insert(17);
814    /// a.insert(41);
815    ///
816    /// let b = a.split_off(&3);
817    ///
818    /// assert_eq!(a.len(), 2);
819    /// assert_eq!(b.len(), 3);
820    ///
821    /// assert!(a.contains(&1));
822    /// assert!(a.contains(&2));
823    ///
824    /// assert!(b.contains(&3));
825    /// assert!(b.contains(&17));
826    /// assert!(b.contains(&41));
827    /// ```
828    pub fn split_off(&mut self, value: &T) -> Self {
829        let tail = self.range((Included(value), Unbounded));
830        if tail.len() == 0 {
831            // if key follows everything in set, just return empty set
832            Self::default()
833        } else if tail.len() == self.len() {
834            // if key precedes everything in set, just return moved self
835            mem::replace(self, Self::default())
836        } else {
837            // return tail and truncate self
838            let new_len = self.len() - tail.len();
839            let tail_set: Self = tail.cloned().collect();
840            self.truncate(new_len);
841            tail_set
842        }
843    }
844
845    /// Truncates the sorted sequence, keeping the first `len` elements and dropping
846    /// the rest.
847    ///
848    /// If `len` is greater than the set's current length, this has no
849    /// effect.
850    ///
851    /// # Examples
852    ///
853    /// Truncating a five-element set to two elements:
854    ///
855    /// ```
856    /// use rotated_array_set::RotatedArraySet;
857    ///
858    /// let mut set: RotatedArraySet<_> = vec![1, 2, 3, 4, 5].into();
859    /// set.truncate(2);
860    /// assert_eq!(set, vec![1, 2].into());
861    /// ```
862    ///
863    /// No truncation occurs when `len` is greater than the vector's current
864    /// length:
865    ///
866    /// ```
867    /// use rotated_array_set::RotatedArraySet;
868    ///
869    /// let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
870    /// set.truncate(8);
871    /// assert_eq!(set, vec![1, 2, 3].into());
872    /// ```
873    ///
874    /// Truncating when `len == 0` is equivalent to calling the [`clear`]
875    /// method.
876    ///
877    /// ```
878    /// use rotated_array_set::RotatedArraySet;
879    ///
880    /// let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
881    /// set.truncate(0);
882    /// assert_eq!(set, vec![].into());
883    /// ```
884    pub fn truncate(&mut self, len: usize) {
885        if len == 0 {
886            self.clear();
887        // if len >= self.len(), do nothing
888        } else if len < self.len() {
889            // logical index corresponding to truncated length
890            let index = len - 1;
891            // find subarray containing logical index (we don't need to translate to raw index for this)
892            let subarray_idx = Self::get_subarray_idx_from_array_idx(index);
893            let subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx);
894            let next_subarray_offset = if subarray_idx == self.min_indexes.len() - 1 {
895                self.data.len()
896            } else {
897                Self::get_array_idx_from_subarray_idx(subarray_idx + 1)
898            };
899            let subarray = &mut self.data[subarray_offset..next_subarray_offset];
900            // sort subarray and update auxiliary arrays
901            let min_offset = self.min_indexes[subarray_idx];
902            subarray.rotate_left(min_offset);
903            self.min_indexes[subarray_idx] = 0;
904            // now we can truncate the whole data array at the logical index
905            self.data.truncate(len);
906            // trim auxiliary arrays
907            self.min_indexes.truncate(subarray_idx + 1);
908            self.min_data.truncate(subarray_idx + 1);
909        }
910        debug_assert!(self.assert_invariants());
911    }
912
913    /// Returns the number of elements in the set.
914    ///
915    /// This is a constant-time operation.
916    ///
917    /// # Examples
918    ///
919    /// ```
920    /// use rotated_array_set::RotatedArraySet;
921    ///
922    /// let mut v = RotatedArraySet::new();
923    /// assert_eq!(v.len(), 0);
924    /// v.insert(1);
925    /// assert_eq!(v.len(), 1);
926    /// ```
927    pub fn len(&self) -> usize {
928        self.data.len()
929    }
930
931    /// Returns `true` if the set contains no elements.
932    ///
933    /// This is a constant-time operation.
934    ///
935    /// # Examples
936    ///
937    /// ```
938    /// use rotated_array_set::RotatedArraySet;
939    ///
940    /// let mut v = RotatedArraySet::new();
941    /// assert!(v.is_empty());
942    /// v.insert(1);
943    /// assert!(!v.is_empty());
944    /// ```
945    pub fn is_empty(&self) -> bool {
946        self.data.is_empty()
947    }
948
949    /// Gets a double-ended iterator that visits the values in the `RotatedArraySet` in ascending (descending) order.
950    ///
951    /// # Examples
952    ///
953    /// ```
954    /// use rotated_array_set::RotatedArraySet;
955    ///
956    /// let set: RotatedArraySet<usize> = RotatedArraySet::new();
957    /// let mut set_iter = set.iter();
958    /// assert_eq!(set_iter.next(), None);
959    /// ```
960    ///
961    /// ```
962    /// use rotated_array_set::RotatedArraySet;
963    ///
964    /// let set: RotatedArraySet<usize> = vec![1, 2, 3].into();
965    /// let mut set_iter = set.iter();
966    /// assert_eq!(set_iter.next(), Some(&1));
967    /// assert_eq!(set_iter.next(), Some(&2));
968    /// assert_eq!(set_iter.next(), Some(&3));
969    /// assert_eq!(set_iter.next(), None);
970    /// ```
971    ///
972    /// Values returned by the iterator are returned in ascending order:
973    ///
974    /// ```
975    /// use rotated_array_set::RotatedArraySet;
976    ///
977    /// let set: RotatedArraySet<usize> = vec![3, 1, 2].into();
978    /// let mut set_iter = set.iter();
979    /// assert_eq!(set_iter.next(), Some(&1));
980    /// assert_eq!(set_iter.next(), Some(&2));
981    /// assert_eq!(set_iter.next(), Some(&3));
982    /// assert_eq!(set_iter.next(), None);
983    /// ```
984    pub fn iter(&self) -> Iter<'_, T> {
985        Iter::new(Range::new(self))
986    }
987
988    /// Constructs a double-ended iterator over a sub-range of elements in the set.
989    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
990    /// yield elements from `min` (inclusive) to `max` (exclusive).
991    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
992    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
993    /// range from 4 to 10.
994    ///
995    /// # Examples
996    ///
997    /// ```
998    /// use rotated_array_set::RotatedArraySet;
999    /// use std::ops::Bound::Included;
1000    ///
1001    /// let mut set = RotatedArraySet::new();
1002    /// set.insert(3);
1003    /// set.insert(5);
1004    /// set.insert(8);
1005    /// for &elem in set.range((Included(&4), Included(&8))) {
1006    ///     println!("{}", elem);
1007    /// }
1008    /// assert_eq!(Some(&5), set.range(4..).next());
1009    /// ```
1010    ///
1011    /// ```
1012    /// use rotated_array_set::RotatedArraySet;
1013    /// use std::ops::Bound::{Included, Excluded};
1014    ///
1015    /// let mut set: RotatedArraySet<_> = (1..10).collect();
1016    /// let range: Vec<_> = set.range((Included(&4), Excluded(&8))).cloned().collect();
1017    /// assert_eq!(range, vec![4, 5, 6, 7]);
1018    /// ```
1019    pub fn range<R>(&self, range: R) -> Iter<'_, T>
1020    where
1021        R: RangeBounds<T>,
1022    {
1023        let range = self.get_range(range);
1024        Iter::new(range)
1025    }
1026
1027    fn get_range<R>(&self, range: R) -> Range<'_, T>
1028    where
1029        R: RangeBounds<T>,
1030    {
1031        match (range.start_bound(), range.end_bound()) {
1032            (Excluded(s), Excluded(e)) if s == e => {
1033                panic!("range start and end are equal and excluded in RotatedArraySet")
1034            }
1035            (Included(s), Included(e))
1036            | (Included(s), Excluded(e))
1037            | (Excluded(s), Included(e))
1038            | (Excluded(s), Excluded(e))
1039                if s > e =>
1040            {
1041                panic!("range start is greater than range end in RotatedArraySet")
1042            }
1043            _ => {}
1044        };
1045        let start_index_inclusive = match range.start_bound() {
1046            Unbounded => 0,
1047            Included(s) => match self.find_raw_index(s) {
1048                Ok(index) => index,
1049                Err(index) => index,
1050            },
1051            Excluded(s) => match self.find_raw_index(s) {
1052                Ok(index) => index + 1,
1053                Err(index) => index,
1054            },
1055        };
1056        let end_index_exclusive = match range.end_bound() {
1057            Unbounded => self.len(),
1058            Included(e) => match self.find_raw_index(e) {
1059                Ok(index) => index + 1,
1060                Err(index) => index,
1061            },
1062            Excluded(e) => match self.find_raw_index(e) {
1063                Ok(index) => index,
1064                Err(index) => index,
1065            },
1066        };
1067        Range::with_bounds(self, start_index_inclusive, end_index_exclusive)
1068    }
1069
1070    /// Visits the values representing the difference,
1071    /// i.e., the values that are in `self` but not in `other`,
1072    /// in ascending order.
1073    ///
1074    /// # Examples
1075    ///
1076    /// ```
1077    /// use rotated_array_set::RotatedArraySet;
1078    ///
1079    /// let mut a = RotatedArraySet::new();
1080    /// a.insert(1);
1081    /// a.insert(2);
1082    ///
1083    /// let mut b = RotatedArraySet::new();
1084    /// b.insert(2);
1085    /// b.insert(3);
1086    ///
1087    /// let diff: Vec<_> = a.difference(&b).cloned().collect();
1088    /// assert_eq!(diff, [1]);
1089    /// ```
1090    pub fn difference<'a>(&'a self, other: &'a RotatedArraySet<T>) -> Difference<'a, T> {
1091        Difference {
1092            self_iter: self.iter(),
1093            other_set: other,
1094        }
1095    }
1096
1097    /// Visits the values representing the symmetric difference,
1098    /// i.e., the values that are in `self` or in `other` but not in both,
1099    /// in ascending order.
1100    ///
1101    /// # Examples
1102    ///
1103    /// ```
1104    /// use rotated_array_set::RotatedArraySet;
1105    ///
1106    /// let mut a = RotatedArraySet::new();
1107    /// a.insert(1);
1108    /// a.insert(2);
1109    ///
1110    /// let mut b = RotatedArraySet::new();
1111    /// b.insert(2);
1112    /// b.insert(3);
1113    ///
1114    /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
1115    /// assert_eq!(sym_diff, [1, 3]);
1116    /// ```
1117    pub fn symmetric_difference<'a>(
1118        &'a self,
1119        other: &'a RotatedArraySet<T>,
1120    ) -> SymmetricDifference<'a, T> {
1121        SymmetricDifference {
1122            a: self.iter().peekable(),
1123            b: other.iter().peekable(),
1124        }
1125    }
1126
1127    /// Visits the values representing the intersection,
1128    /// i.e., the values that are both in `self` and `other`,
1129    /// in ascending order.
1130    ///
1131    /// # Examples
1132    ///
1133    /// ```
1134    /// use rotated_array_set::RotatedArraySet;
1135    ///
1136    /// let mut a = RotatedArraySet::new();
1137    /// a.insert(1);
1138    /// a.insert(2);
1139    ///
1140    /// let mut b = RotatedArraySet::new();
1141    /// b.insert(2);
1142    /// b.insert(3);
1143    ///
1144    /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
1145    /// assert_eq!(intersection, [2]);
1146    /// ```
1147    pub fn intersection<'a>(&'a self, other: &'a RotatedArraySet<T>) -> Intersection<'a, T> {
1148        let (small, other) = if self.len() <= other.len() {
1149            (self, other)
1150        } else {
1151            (other, self)
1152        };
1153        // Iterate the small set, searching for matches in the large set.
1154        Intersection {
1155            small_iter: small.iter(),
1156            large_set: other,
1157        }
1158    }
1159
1160    /// Visits the values representing the union,
1161    /// i.e., all the values in `self` or `other`, without duplicates,
1162    /// in ascending order.
1163    ///
1164    /// # Examples
1165    ///
1166    /// ```
1167    /// use rotated_array_set::RotatedArraySet;
1168    ///
1169    /// let mut a = RotatedArraySet::new();
1170    /// a.insert(1);
1171    /// a.insert(2);
1172    ///
1173    /// let mut b = RotatedArraySet::new();
1174    /// b.insert(2);
1175    /// b.insert(3);
1176    ///
1177    /// let union: Vec<_> = a.union(&b).cloned().collect();
1178    /// assert_eq!(union, [1, 2, 3]);
1179    /// ```
1180    pub fn union<'a>(&'a self, other: &'a RotatedArraySet<T>) -> Union<'a, T> {
1181        Union {
1182            a: self.iter().peekable(),
1183            b: other.iter().peekable(),
1184        }
1185    }
1186
1187    fn integer_sum(n: usize) -> usize {
1188        // I learned this from a 10-year-old named Gauss
1189        (n * (n + 1)) / 2
1190    }
1191
1192    fn integer_sum_inverse(n: usize) -> usize {
1193        // y = (x * (x + 1)) / 2
1194        // x = (sqrt(8 * y + 1) - 1) / 2
1195        ((f64::from((n * 8 + 1) as u32).sqrt() as usize) - 1) / 2
1196    }
1197
1198    fn get_subarray_idx_from_array_idx(idx: usize) -> usize {
1199        if idx == 0 {
1200            0
1201        } else {
1202            Self::integer_sum_inverse(idx)
1203        }
1204    }
1205
1206    fn get_array_idx_from_subarray_idx(idx: usize) -> usize {
1207        if idx == 0 {
1208            0
1209        } else {
1210            Self::integer_sum(idx)
1211        }
1212    }
1213
1214    fn is_last_subarray_full(&self) -> bool {
1215        self.data.len() == Self::get_array_idx_from_subarray_idx(self.min_indexes.len())
1216    }
1217
1218    // Returns either (raw) index of element if it exists, or (raw) insertion point if it doesn't exist.
1219    fn find_raw_index(&self, value: &T) -> Result<usize, usize> {
1220        if self.data.is_empty() {
1221            return Err(0);
1222        }
1223        // find two candidate subarrays by binary searching self.min_data,
1224        // then compare value to max value of first subarray, if it's smaller
1225        // then binary search first subarray, otherwise second subarray
1226        // TODO: actually we only need to binary search first subarray, max
1227        // comparison is just to determine insertion point (to preserve invariant
1228        // that we never insert element into a subarray greater than its current max).
1229        // if element greater than max of first subarray but less than min of
1230        // second subarray, just return insertion point on min index of second subarray.
1231        debug_assert!(self.assert_invariants());
1232        match self.min_data.binary_search(value) {
1233            Ok(idx) => {
1234                // `value` is located directly on a pivot index
1235                let found_idx = Self::get_array_idx_from_subarray_idx(idx) + self.min_indexes[idx];
1236                debug_assert!(found_idx < self.len());
1237                Ok(found_idx)
1238            }
1239            Err(idx) => {
1240                // The element might be in either the subarray corresponding to the insertion point,
1241                // or in its predecessor; compare to max value of predecessor to decide.
1242                // A special case is when the insertion point is after the last subarray and the last subarray isn't full.
1243                // In that case, we want to insert into the existing last subarray, not create a new one.
1244                let subarray_idx = if idx == 0 {
1245                    0
1246                } else if idx == self.min_indexes.len() && !self.is_last_subarray_full() {
1247                    // partially full final subarray
1248                    idx - 1
1249                } else {
1250                    // we can assume the predecessor subarray is full
1251                    let prev_max_idx = if self.min_indexes[idx - 1] == 0 {
1252                        Self::get_array_idx_from_subarray_idx(idx) - 1
1253                    } else {
1254                        Self::get_array_idx_from_subarray_idx(idx - 1) + self.min_indexes[idx - 1]
1255                            - 1
1256                    };
1257                    if *value <= self.data[prev_max_idx] {
1258                        idx - 1
1259                    } else {
1260                        idx
1261                    }
1262                };
1263                let subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx);
1264                // we may need to create a new subarray to insert this element
1265                debug_assert!(subarray_offset <= self.data.len());
1266                if subarray_offset == self.data.len() {
1267                    return Err(subarray_offset);
1268                }
1269                // if our last subarray is truncated, then account for that
1270                let next_subarray_offset = if subarray_idx == self.min_indexes.len() - 1 {
1271                    self.data.len()
1272                } else {
1273                    Self::get_array_idx_from_subarray_idx(subarray_idx + 1)
1274                };
1275                // split subarray into two slices separated by pivot,
1276                // and search both separately.
1277                let subarray = &self.data[subarray_offset..next_subarray_offset];
1278                let pivot_offset = self.min_indexes[subarray_idx];
1279                let subarray_pivot = subarray_offset + pivot_offset;
1280                let (left, right) = subarray.split_at(pivot_offset);
1281                debug_assert!(
1282                    IsSorted::is_sorted(&mut left.iter()) && IsSorted::is_sorted(&mut right.iter())
1283                );
1284                match (left.binary_search(value), right.binary_search(value)) {
1285                    (Ok(idx), _) => Ok(subarray_offset + idx),
1286                    (_, Ok(idx)) => Ok(subarray_pivot + idx),
1287                    // if right insertion point is past right subarray, and left subarray is not empty, then true insertion point must be on left
1288                    (Err(left_idx), Err(right_idx))
1289                        if right_idx == right.len() && !left.is_empty() =>
1290                    {
1291                        Err(subarray_offset + left_idx)
1292                    }
1293                    // if right insertion point is within right subarray, or left subarray is empty, then true insertion point must be on right
1294                    (Err(_left_idx), Err(right_idx))
1295                        if right_idx < right.len() || left.is_empty() =>
1296                    {
1297                        Err(subarray_pivot + right_idx)
1298                    }
1299                    (Err(_), Err(_)) => unreachable!(),
1300                }
1301            }
1302        }
1303    }
1304
1305    #[inline(always)]
1306    fn assert_invariants(&self) -> bool {
1307        // assert order
1308        assert!(IsSorted::is_sorted(&mut self.min_data.iter()));
1309        let mut min_data_dedup = self.min_data.clone();
1310        min_data_dedup.dedup();
1311        // assert uniqueness
1312        assert!(self.min_data[..] == min_data_dedup[..]);
1313        // assert index of each subarray's minimum lies within the subarray
1314        assert!(self
1315            .min_indexes
1316            .iter()
1317            .enumerate()
1318            .all(|(idx, &offset)| offset <= idx));
1319        // assert min_data is properly synchronized with min_indexes and self.data
1320        assert!(self
1321            .min_indexes
1322            .iter()
1323            .enumerate()
1324            .all(|(idx, &offset)| self.min_data[idx]
1325                == self.data[Self::get_array_idx_from_subarray_idx(idx) + offset]));
1326        // assert min_indexes holds the index of the actual minimum of each subarray
1327        for i in 0..self.min_indexes.len() {
1328            let subarray_begin_idx = Self::get_array_idx_from_subarray_idx(i);
1329            let subarray_end_idx = min(
1330                self.data.len(),
1331                Self::get_array_idx_from_subarray_idx(i + 1),
1332            );
1333            let subarray = &self.data[subarray_begin_idx..subarray_end_idx];
1334            let min_idx = subarray
1335                .iter()
1336                .enumerate()
1337                .min_by(|&(_, v1), &(_, v2)| v1.cmp(v2))
1338                .unwrap()
1339                .0;
1340            assert!(min_idx == self.min_indexes[i]);
1341        }
1342        true
1343    }
1344
1345    // given data array, initialize auxiliary arrays
1346    fn init(&mut self) {
1347        debug_assert!(self.min_indexes.is_empty() && self.min_data.is_empty());
1348        if !self.data.is_empty() {
1349            self.data.sort_unstable(); // don't want to allocate
1350            let last_subarray_idx = Self::get_subarray_idx_from_array_idx(self.data.len() - 1);
1351            self.min_indexes = vec![0; last_subarray_idx + 1];
1352            for subarray_idx in 0..=last_subarray_idx {
1353                let subarray_offset = Self::get_array_idx_from_subarray_idx(subarray_idx);
1354                self.min_data.push(self.data[subarray_offset]);
1355            }
1356        }
1357    }
1358}
1359
1360impl<T> PartialEq for RotatedArraySet<T>
1361where
1362    T: Ord + Copy + Default + Debug,
1363{
1364    fn eq(&self, other: &Self) -> bool {
1365        if self.len() != other.len() {
1366            return false;
1367        }
1368        for i in 0..self.len() {
1369            if self.select(i).unwrap() != other.select(i).unwrap() {
1370                return false;
1371            }
1372        }
1373        true
1374    }
1375}
1376
1377impl<T> Eq for RotatedArraySet<T> where T: Ord + Copy + Default + Debug {}
1378
1379impl<T> Hash for RotatedArraySet<T>
1380where
1381    T: Ord + Copy + Default + Debug + Hash,
1382{
1383    fn hash<H: Hasher>(&self, state: &mut H) {
1384        for i in 0..self.len() {
1385            self.select(i).hash(state);
1386        }
1387    }
1388}
1389
1390impl<'a, T> Iterator for Iter<'a, T>
1391where
1392    T: Ord + Copy + Default + Debug,
1393{
1394    type Item = &'a T;
1395
1396    fn next(&mut self) -> Option<Self::Item> {
1397        if self.len() == 0 || self.next_index > self.next_rev_index {
1398            None
1399        } else {
1400            let current = self.range.at(self.next_index);
1401            self.next_index += 1;
1402            debug_assert!(self.assert_invariants());
1403            current
1404        }
1405    }
1406
1407    fn nth(&mut self, n: usize) -> Option<Self::Item> {
1408        self.next_index = min(self.next_index + n, self.len());
1409        let ret = if self.len() == 0 || self.next_index > self.next_rev_index {
1410            None
1411        } else {
1412            let nth = self.range.at(self.next_index);
1413            self.next_index += 1;
1414            nth
1415        };
1416        debug_assert!(self.assert_invariants());
1417        ret
1418    }
1419
1420    fn count(self) -> usize {
1421        self.len() - self.next_index
1422    }
1423
1424    fn last(self) -> Option<Self::Item> {
1425        if self.len() == 0 {
1426            None
1427        } else {
1428            self.range.at(self.len() - 1)
1429        }
1430    }
1431
1432    fn max(self) -> Option<Self::Item> {
1433        if self.len() == 0 {
1434            None
1435        } else {
1436            self.range.at(self.len() - 1)
1437        }
1438    }
1439
1440    fn min(self) -> Option<Self::Item> {
1441        self.range.at(0)
1442    }
1443
1444    // FIXME: uncomment when Iterator::is_sorted is stabilized
1445    // fn is_sorted(self) -> bool {
1446    //     true
1447    // }
1448
1449    fn size_hint(&self) -> (usize, Option<usize>) {
1450        let remaining_count = self.len() - self.next_index;
1451        (remaining_count, Some(remaining_count))
1452    }
1453}
1454
1455impl<'a, T> DoubleEndedIterator for Iter<'a, T>
1456where
1457    T: Ord + Copy + Default + Debug,
1458{
1459    fn next_back(&mut self) -> Option<Self::Item> {
1460        if self.len() == 0 || self.next_rev_index < self.next_index {
1461            None
1462        } else {
1463            let current = self.range.at(self.next_rev_index);
1464            // We can't decrement next_rev_index past 0, so we cheat and move next_index
1465            // ahead instead. That works since next() must return None once next_rev_index
1466            // has crossed next_index.
1467            if self.next_rev_index == 0 {
1468                self.next_index += 1;
1469            } else {
1470                self.next_rev_index -= 1;
1471            }
1472            debug_assert!(self.assert_invariants());
1473            current
1474        }
1475    }
1476
1477    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1478        self.next_rev_index = self.next_rev_index.saturating_sub(n);
1479        let ret = if self.len() == 0 || self.next_rev_index < self.next_index {
1480            None
1481        } else {
1482            let nth = self.range.at(self.next_rev_index);
1483            // We can't decrement next_rev_index past 0, so we cheat and move next_index
1484            // ahead instead. That works since next() must return None once next_rev_index
1485            // has crossed next_index.
1486            if self.next_rev_index == 0 {
1487                self.next_index += 1;
1488            } else {
1489                self.next_rev_index -= 1;
1490            }
1491            nth
1492        };
1493        debug_assert!(self.assert_invariants());
1494        ret
1495    }
1496}
1497
1498impl<T> ExactSizeIterator for Iter<'_, T>
1499where
1500    T: Ord + Copy + Default + Debug,
1501{
1502    fn len(&self) -> usize {
1503        self.range.len()
1504    }
1505}
1506
1507impl<T> FusedIterator for Iter<'_, T> where T: Ord + Copy + Default + Debug {}
1508
1509impl<'a, T> IntoIterator for &'a RotatedArraySet<T>
1510where
1511    T: Ord + Copy + Default + Debug,
1512{
1513    type Item = &'a T;
1514    type IntoIter = Iter<'a, T>;
1515
1516    fn into_iter(self) -> Self::IntoIter {
1517        self.iter()
1518    }
1519}
1520
1521impl<T> IntoIterator for RotatedArraySet<T>
1522where
1523    T: Ord + Copy + Default + Debug,
1524{
1525    type Item = T;
1526    type IntoIter = IntoIter<T>;
1527
1528    fn into_iter(self) -> Self::IntoIter {
1529        IntoIter {
1530            vec: self.into(),
1531            next_index: 0,
1532        }
1533    }
1534}
1535
1536impl<'a, T> Iterator for IntoIter<T>
1537where
1538    T: Ord + Copy + Default + Debug,
1539{
1540    type Item = T;
1541
1542    fn next(&mut self) -> Option<Self::Item> {
1543        if self.next_index == self.vec.len() {
1544            None
1545        } else {
1546            let current = self.vec[self.next_index];
1547            self.next_index += 1;
1548            debug_assert!(self.next_index <= self.vec.len());
1549            Some(current)
1550        }
1551    }
1552}
1553
1554/// From https://doc.rust-lang.org/src/alloc/collections/btree/set.rs.html
1555/// Compares `x` and `y`, but return `short` if x is None and `long` if y is None
1556fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering {
1557    match (x, y) {
1558        (None, _) => short,
1559        (_, None) => long,
1560        (Some(x1), Some(y1)) => x1.cmp(y1),
1561    }
1562}
1563
1564impl<'a, T> Iterator for Difference<'a, T>
1565where
1566    T: Ord + Copy + Default + Debug,
1567{
1568    type Item = &'a T;
1569
1570    fn next(&mut self) -> Option<&'a T> {
1571        // Just use a simple lookup from `self_iter` to `other_set` for now,
1572        // later add a proper linear merge for size ratios close to 1 if benchmarks warrant.
1573        // (A point lookup has much better worst-case performance than linear merge.)
1574        // NB: For a single algorithm optimal over all size ratios, see
1575        // "A simple algorithm for merging two disjoint linearly-ordered sets".
1576        loop {
1577            let self_next = self.self_iter.next()?;
1578            if !self.other_set.contains(&self_next) {
1579                return Some(self_next);
1580            }
1581        }
1582    }
1583
1584    fn size_hint(&self) -> (usize, Option<usize>) {
1585        let (self_len, other_len) = (self.self_iter.len(), self.other_set.len());
1586        (self_len.saturating_sub(other_len), Some(self_len))
1587    }
1588}
1589
1590impl<T> FusedIterator for Difference<'_, T> where T: Ord + Copy + Default + Debug {}
1591
1592impl<'a, T> Iterator for SymmetricDifference<'a, T>
1593where
1594    T: Ord + Copy + Default + Debug,
1595{
1596    type Item = &'a T;
1597
1598    fn next(&mut self) -> Option<&'a T> {
1599        loop {
1600            match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
1601                Less => return self.a.next(),
1602                Equal => {
1603                    self.a.next();
1604                    self.b.next();
1605                }
1606                Greater => return self.b.next(),
1607            }
1608        }
1609    }
1610
1611    fn size_hint(&self) -> (usize, Option<usize>) {
1612        (0, Some(self.a.len() + self.b.len()))
1613    }
1614}
1615
1616impl<T> FusedIterator for SymmetricDifference<'_, T> where T: Ord + Copy + Default + Debug {}
1617
1618impl<'a, T> Iterator for Intersection<'a, T>
1619where
1620    T: Ord + Copy + Default + Debug,
1621{
1622    type Item = &'a T;
1623
1624    fn next(&mut self) -> Option<&'a T> {
1625        // Just use a simple lookup from `self_iter` to `other_set` for now,
1626        // later add a proper linear merge for size ratios close to 1 if benchmarks warrant.
1627        // (A point lookup has much better worst-case performance than linear merge.)
1628        // NB: For a single algorithm optimal over all size ratios, see
1629        // "A simple algorithm for merging two disjoint linearly-ordered sets".
1630        loop {
1631            let small_next = self.small_iter.next()?;
1632            if self.large_set.contains(&small_next) {
1633                return Some(small_next);
1634            }
1635        }
1636    }
1637
1638    fn size_hint(&self) -> (usize, Option<usize>) {
1639        let min_len = self.small_iter.len();
1640        (0, Some(min_len))
1641    }
1642}
1643
1644impl<T> FusedIterator for Intersection<'_, T> where T: Ord + Copy + Default + Debug {}
1645
1646impl<'a, T> Iterator for Union<'a, T>
1647where
1648    T: Ord + Copy + Default + Debug,
1649{
1650    type Item = &'a T;
1651
1652    fn next(&mut self) -> Option<&'a T> {
1653        match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
1654            Less => self.a.next(),
1655            Equal => {
1656                self.b.next();
1657                self.a.next()
1658            }
1659            Greater => self.b.next(),
1660        }
1661    }
1662
1663    fn size_hint(&self) -> (usize, Option<usize>) {
1664        let a_len = self.a.len();
1665        let b_len = self.b.len();
1666        (max(a_len, b_len), Some(a_len + b_len))
1667    }
1668}
1669
1670impl<T> FusedIterator for Union<'_, T> where T: Ord + Copy + Default + Debug {}
1671
1672impl<'a, T> From<&'a [T]> for RotatedArraySet<T>
1673where
1674    T: Ord + Copy + Default + Debug,
1675{
1676    fn from(slice: &[T]) -> Self {
1677        let mut this = RotatedArraySet {
1678            data: slice.to_vec(),
1679            min_indexes: Vec::new(),
1680            min_data: Vec::new(),
1681        };
1682        this.init();
1683        this
1684    }
1685}
1686
1687impl<T> From<Vec<T>> for RotatedArraySet<T>
1688where
1689    T: Ord + Copy + Default + Debug,
1690{
1691    fn from(vec: Vec<T>) -> Self {
1692        let mut this = RotatedArraySet {
1693            data: vec,
1694            min_indexes: Vec::new(),
1695            min_data: Vec::new(),
1696        };
1697        this.init();
1698        this
1699    }
1700}
1701
1702impl<T> Into<Vec<T>> for RotatedArraySet<T>
1703where
1704    T: Ord + Copy + Default + Debug,
1705{
1706    fn into(mut self) -> Vec<T> {
1707        // sort the data array in-place and steal it from self
1708        for (i, &pivot_offset) in self.min_indexes.iter().enumerate() {
1709            let subarray_start_idx = Self::get_array_idx_from_subarray_idx(i);
1710            let subarray_len = if i == self.min_indexes.len() - 1 {
1711                self.data.len() - subarray_start_idx
1712            } else {
1713                i + 1
1714            };
1715            let subarray_end_idx = subarray_start_idx + subarray_len;
1716            let subarray = &mut self.data[subarray_start_idx..subarray_end_idx];
1717            // sort subarray in-place
1718            subarray.rotate_left(pivot_offset);
1719        }
1720        // steal data array
1721        self.data
1722    }
1723}
1724
1725impl<T> FromIterator<T> for RotatedArraySet<T>
1726where
1727    T: Ord + Copy + Default + Debug,
1728{
1729    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1730        let mut this = RotatedArraySet {
1731            data: Vec::from_iter(iter.into_iter()),
1732            min_indexes: Vec::new(),
1733            min_data: Vec::new(),
1734        };
1735        this.init();
1736        this
1737    }
1738}
1739
1740impl<T> Default for RotatedArraySet<T>
1741where
1742    T: Ord + Copy + Default + Debug,
1743{
1744    fn default() -> RotatedArraySet<T> {
1745        RotatedArraySet::new()
1746    }
1747}