Struct RotatedArraySet

Source

pub struct RotatedArraySet<T> { /* private fields */ }

Expand description

An ordered set based on a 2-level rotated array.

§Examples

use rotated_array_set::RotatedArraySet;

// Type inference lets us omit an explicit type signature (which
// would be `RotatedArraySet<i32>` in this example).
let mut ints = RotatedArraySet::new();

// Add some integers.
ints.insert(-1);
ints.insert(6);
ints.insert(1729);
ints.insert(24);

// Check for a specific one.
if !ints.contains(&42) {
    println!("We don't have the answer to Life, the Universe, and Everything :-(");
}

// Remove an integer.
ints.remove(&6);

// Iterate over everything.
for int in &ints {
    println!("{}", int);
}

Implementations§

Source §

impl<T> RotatedArraySet<T>
where T: Ord + Copy + Default + Debug,

Source

pub fn new() -> Self

Makes a new RotatedArraySet without any heap allocations.

This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut set: RotatedArraySet<i32> = RotatedArraySet::new();

Source

pub fn with_capacity(capacity: usize) -> RotatedArraySet<T>

Constructs a new, empty RotatedArraySet<T> with the specified capacity.

The set will be able to hold exactly capacity elements without reallocating. If capacity is 0, the set will not allocate.

It is important to note that although the returned set has the capacity specified, the set will have a zero length.

§Examples

use rotated_array_set::RotatedArraySet;

let mut set = RotatedArraySet::with_capacity(10);

// The set contains no items, even though it has capacity for more
assert_eq!(set.len(), 0);

// These are all done without reallocating...
for i in 0..10 {
    set.insert(i);
}

// ...but this may make the set reallocate
set.insert(11);

Source

pub fn clear(&mut self)

Clears the set, removing all values.

This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut v = RotatedArraySet::new();
v.insert(1);
v.clear();
assert!(v.is_empty());

Source

pub fn contains(&self, value: &T) -> bool

Returns true if the set contains a value.

This is an O(lg n) operation.

§Examples

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<_> = vec![1, 2, 3].into();
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);

Source

pub fn is_disjoint(&self, other: &RotatedArraySet<T>) -> bool

Returns true if self has no elements in common with other. This is equivalent to checking for an empty intersection.

§Examples

use rotated_array_set::RotatedArraySet;

let a: RotatedArraySet<_> = vec![1, 2, 3].into();
let mut b = RotatedArraySet::new();

assert_eq!(a.is_disjoint(&b), true);
b.insert(4);
assert_eq!(a.is_disjoint(&b), true);
b.insert(1);
assert_eq!(a.is_disjoint(&b), false);

Source

pub fn is_subset(&self, other: &RotatedArraySet<T>) -> bool

Returns true if the set is a subset of another, i.e., other contains at least all the values in self.

§Examples

use rotated_array_set::RotatedArraySet;

let sup: RotatedArraySet<_> = vec![1, 2, 3].into();
let mut set = RotatedArraySet::new();

assert_eq!(set.is_subset(&sup), true);
set.insert(2);
assert_eq!(set.is_subset(&sup), true);
set.insert(4);
assert_eq!(set.is_subset(&sup), false);

Source

pub fn is_superset(&self, other: &RotatedArraySet<T>) -> bool

Returns true if the set is a superset of another, i.e., self contains at least all the values in other.

§Examples

use rotated_array_set::RotatedArraySet;

let sub: RotatedArraySet<_> = vec![1, 2].into();
let mut set = RotatedArraySet::new();

assert_eq!(set.is_superset(&sub), false);

set.insert(0);
set.insert(1);
assert_eq!(set.is_superset(&sub), false);

set.insert(2);
assert_eq!(set.is_superset(&sub), true);

Source

pub fn get(&self, value: &T) -> Option<&T>

Returns a reference to the value in the set, if any, that is equal to the given value.

This is an O(lg n) operation.

§Examples

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<_> = vec![1, 2, 3].into();
assert_eq!(set.get(&2), Some(&2));
assert_eq!(set.get(&4), None);

Source

pub fn rank(&self, value: &T) -> Result<usize, usize>

Returns the rank of the value in the set if it exists (as Result::Ok), or the rank of its largest predecessor plus one, if it does not exist (as Result::Err). This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<_> = vec![1, 2, 3].into();
assert_eq!(set.rank(&1), Ok(0));
assert_eq!(set.rank(&4), Err(3));

Source

pub fn select(&self, rank: usize) -> Option<&T>

Returns a reference to the value in the set, if any, with the given rank.

This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<_> = vec![1, 2, 3].into();
assert_eq!(set.select(0), Some(&1));
assert_eq!(set.select(3), None);

Source

pub fn insert(&mut self, value: T) -> bool

Adds a value to the set.

This is an O(√n) operation.

If the set did not have this value present, true is returned.

If the set did have this value present, false is returned, and the entry is not updated.

§Examples

use rotated_array_set::RotatedArraySet;

let mut set = RotatedArraySet::new();

assert_eq!(set.insert(2), true);
assert_eq!(set.insert(2), false);
assert_eq!(set.len(), 1);

Source

pub fn remove(&mut self, value: &T) -> bool

Removes a value from the set. Returns whether the value was present in the set.

This is an O(√n) operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut set = RotatedArraySet::new();

set.insert(2);
assert_eq!(set.remove(&2), true);
assert_eq!(set.remove(&2), false);

Source

pub fn take(&mut self, value: &T) -> Option<T>

Removes and returns the value in the set, if any, that is equal to the given one.

This is an O(√n) operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
assert_eq!(set.take(&2), Some(2));
assert_eq!(set.take(&2), None);

Source

pub fn append(&mut self, other: &mut Self)

Moves all elements from other into Self, leaving other empty.

§Examples

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);
a.insert(3);

let mut b = RotatedArraySet::new();
b.insert(3);
b.insert(4);
b.insert(5);

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert!(a.contains(&1));
assert!(a.contains(&2));
assert!(a.contains(&3));
assert!(a.contains(&4));
assert!(a.contains(&5));

Source

pub fn split_off(&mut self, value: &T) -> Self

Splits the collection into two at value. Returns everything after value, including value itself.

§Examples

Basic usage:

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);
a.insert(3);
a.insert(17);
a.insert(41);

let b = a.split_off(&3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);

assert!(a.contains(&1));
assert!(a.contains(&2));

assert!(b.contains(&3));
assert!(b.contains(&17));
assert!(b.contains(&41));

Source

pub fn truncate(&mut self, len: usize)

Truncates the sorted sequence, keeping the first len elements and dropping the rest.

If len is greater than the set’s current length, this has no effect.

§Examples

Truncating a five-element set to two elements:

use rotated_array_set::RotatedArraySet;

let mut set: RotatedArraySet<_> = vec![1, 2, 3, 4, 5].into();
set.truncate(2);
assert_eq!(set, vec![1, 2].into());

No truncation occurs when len is greater than the vector’s current length:

use rotated_array_set::RotatedArraySet;

let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
set.truncate(8);
assert_eq!(set, vec![1, 2, 3].into());

Truncating when len == 0 is equivalent to calling the [clear] method.

use rotated_array_set::RotatedArraySet;

let mut set: RotatedArraySet<_> = vec![1, 2, 3].into();
set.truncate(0);
assert_eq!(set, vec![].into());

Source

pub fn len(&self) -> usize

Returns the number of elements in the set.

This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut v = RotatedArraySet::new();
assert_eq!(v.len(), 0);
v.insert(1);
assert_eq!(v.len(), 1);

Source

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

This is a constant-time operation.

§Examples

use rotated_array_set::RotatedArraySet;

let mut v = RotatedArraySet::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());

Source

pub fn iter(&self) -> Iter<'_, T> ⓘ

Gets a double-ended iterator that visits the values in the RotatedArraySet in ascending (descending) order.

§Examples

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<usize> = RotatedArraySet::new();
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), None);

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<usize> = vec![1, 2, 3].into();
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

Values returned by the iterator are returned in ascending order:

use rotated_array_set::RotatedArraySet;

let set: RotatedArraySet<usize> = vec![3, 1, 2].into();
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

Source

pub fn range<R>(&self, range: R) -> Iter<'_, T> ⓘ
where R: RangeBounds<T>,

Constructs a double-ended iterator over a sub-range of elements in the set. The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

§Examples

use rotated_array_set::RotatedArraySet;
use std::ops::Bound::Included;

let mut set = RotatedArraySet::new();
set.insert(3);
set.insert(5);
set.insert(8);
for &elem in set.range((Included(&4), Included(&8))) {
    println!("{}", elem);
}
assert_eq!(Some(&5), set.range(4..).next());

use rotated_array_set::RotatedArraySet;
use std::ops::Bound::{Included, Excluded};

let mut set: RotatedArraySet<_> = (1..10).collect();
let range: Vec<_> = set.range((Included(&4), Excluded(&8))).cloned().collect();
assert_eq!(range, vec![4, 5, 6, 7]);

Source

pub fn difference<'a>( &'a self, other: &'a RotatedArraySet<T>, ) -> Difference<'a, T> ⓘ

Visits the values representing the difference, i.e., the values that are in self but not in other, in ascending order.

§Examples

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);

let mut b = RotatedArraySet::new();
b.insert(2);
b.insert(3);

let diff: Vec<_> = a.difference(&b).cloned().collect();
assert_eq!(diff, [1]);

Source

pub fn symmetric_difference<'a>( &'a self, other: &'a RotatedArraySet<T>, ) -> SymmetricDifference<'a, T> ⓘ

Visits the values representing the symmetric difference, i.e., the values that are in self or in other but not in both, in ascending order.

§Examples

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);

let mut b = RotatedArraySet::new();
b.insert(2);
b.insert(3);

let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
assert_eq!(sym_diff, [1, 3]);

Source

pub fn intersection<'a>( &'a self, other: &'a RotatedArraySet<T>, ) -> Intersection<'a, T> ⓘ

Visits the values representing the intersection, i.e., the values that are both in self and other, in ascending order.

§Examples

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);

let mut b = RotatedArraySet::new();
b.insert(2);
b.insert(3);

let intersection: Vec<_> = a.intersection(&b).cloned().collect();
assert_eq!(intersection, [2]);

Source

pub fn union<'a>(&'a self, other: &'a RotatedArraySet<T>) -> Union<'a, T> ⓘ

Visits the values representing the union, i.e., all the values in self or other, without duplicates, in ascending order.

§Examples

use rotated_array_set::RotatedArraySet;

let mut a = RotatedArraySet::new();
a.insert(1);
a.insert(2);

let mut b = RotatedArraySet::new();
b.insert(2);
b.insert(3);

let union: Vec<_> = a.union(&b).cloned().collect();
assert_eq!(union, [1, 2, 3]);