Struct rotated_array_set::RotatedArraySet

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

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);
}

Methods

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

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();

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);

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());

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);

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);

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);

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);

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);

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));

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);

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);

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);

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);

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));

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));

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());

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);

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());

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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);

Important traits for Iter<'a, T>

impl<'a, T> Iterator for Iter<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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]);

Important traits for Difference<'a, T>

impl<'a, T> Iterator for Difference<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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]);

Important traits for SymmetricDifference<'a, T>

impl<'a, T> Iterator for SymmetricDifference<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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]);

Important traits for Intersection<'a, T>

impl<'a, T> Iterator for Intersection<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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]);

Important traits for Union<'a, T>

impl<'a, T> Iterator for Union<'a, T> where
    T: Ord + Copy + Default + Debug,  type Item = &'a T;

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]);

Trait Implementations

impl<T: Clone> Clone for RotatedArraySet<T>

fn clone(&self) -> RotatedArraySet<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for RotatedArraySet<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

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

fn default() -> RotatedArraySet<T>

Returns the "default value" for a type.

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

impl<'a, T> From<&'a [T]> for RotatedArraySet<T> where
    T: Ord + Copy + Default + Debug, 

fn from(slice: &[T]) -> Self

Performs the conversion.

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

fn from(vec: Vec<T>) -> Self

Performs the conversion.

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

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

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

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

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

fn into(self) -> Vec<T>

Performs the conversion.

impl<'a, T> IntoIterator for &'a RotatedArraySet<T> where
    T: Ord + Copy + Default + Debug, 

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.