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}