[−][src]Struct rotated_array_set::RotatedArraySet
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,
[src]
T: Ord + Copy + Default + Debug,
pub fn new() -> Self
[src]
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>
[src]
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)
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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>
[src]
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>
[src]
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>
[src]
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
[src]
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
[src]
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>
[src]
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)
[src]
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
[src]
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)
[src]
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
[src]
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
[src]
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>pub fn iter(&self) -> Iter<T>
[src]
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>pub fn range<R>(&self, range: R) -> Iter<T> where
R: RangeBounds<T>,
[src]
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>pub fn difference<'a>(
&'a self,
other: &'a RotatedArraySet<T>
) -> Difference<'a, T>
[src]
&'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>pub fn symmetric_difference<'a>(
&'a self,
other: &'a RotatedArraySet<T>
) -> SymmetricDifference<'a, T>
[src]
&'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>pub fn intersection<'a>(
&'a self,
other: &'a RotatedArraySet<T>
) -> Intersection<'a, T>
[src]
&'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>pub fn union<'a>(&'a self, other: &'a RotatedArraySet<T>) -> Union<'a, T>
[src]
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>
[src]
fn clone(&self) -> RotatedArraySet<T>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T: Debug> Debug for RotatedArraySet<T>
[src]
impl<T> Default for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
fn default() -> RotatedArraySet<T>
[src]
impl<T> Eq for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
impl<'a, T> From<&'a [T]> for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
impl<T> From<Vec<T>> for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
impl<T> FromIterator<T> for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
impl<T> Hash for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug + Hash,
[src]
T: Ord + Copy + Default + Debug + Hash,
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl<T> Into<Vec<T>> for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
impl<'a, T> IntoIterator for &'a RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
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
[src]
impl<T> IntoIterator for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
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
[src]
impl<T> PartialEq<RotatedArraySet<T>> for RotatedArraySet<T> where
T: Ord + Copy + Default + Debug,
[src]
T: Ord + Copy + Default + Debug,
Auto Trait Implementations
impl<T> RefUnwindSafe for RotatedArraySet<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> Send for RotatedArraySet<T> where
T: Send,
T: Send,
impl<T> Sync for RotatedArraySet<T> where
T: Sync,
T: Sync,
impl<T> Unpin for RotatedArraySet<T> where
T: Unpin,
T: Unpin,
impl<T> UnwindSafe for RotatedArraySet<T> where
T: UnwindSafe,
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,