Struct aatree::AATreeSet

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

A set based on an AA-Tree.

See AATreeMap’s documentation for a detailed discussion of this collection’s performance benefits and drawbacks.

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Example

This example is adopted from BTreeSet’s documentation:

use aatree::AATreeSet;

let mut books = AATreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

// Check for a specific one
if !books.contains("The Winds of Winter") {
	println!("We have {} books, but The Winds of Winter ain't one.", books.len());
}

// Remove a book.
books.remove("The Odyssey");

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

Implementations

impl<T> AATreeSet<T>

pub const fn new() -> Self

Construct a new, empty AA-Tree based set.

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn clear(&mut self)

Clears the set, removing all elements.

Example

let mut set = AATreeSet::new();
set.insert(1);
set.clear();
assert!(set.is_empty());

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

Creates an iterator over this set that visits the values in ascending order.

impl<T: Ord> AATreeSet<T>

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

Adds a value to the set.

If the set did already contain this value, the entry is not updated, and false is returned.

Example

let mut set = AATreeSet::new();
set.insert(42);
set.insert(42);
assert_eq!(set.len(), 1);

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

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

Examples

use aatree::AATreeSet;

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

let mut b = AATreeSet::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 first(&self) -> Option<&T>

Returns the first/smallest element of the set.

Example

let mut set = AATreeSet::new();
assert!(set.first().is_none());
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.first(), Some(&40));

pub fn last(&self) -> Option<&T>

Returns the last/largest element of the set.

Example

let mut set = AATreeSet::new();
assert!(set.last().is_none());
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.last(), Some(&44));

pub fn pop_first(&mut self) -> Option<T>

Remove and return the first/smallest element of the set.

Example

let mut set = AATreeSet::new();
assert_eq!(set.pop_first(), None);
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.pop_first(), Some(40));
assert_eq!(set.pop_first(), Some(42));
assert_eq!(set.pop_first(), Some(44));
assert_eq!(set.pop_first(), None);

pub fn pop_last(&mut self) -> Option<T>

Remove and return the last/largest element of the set.

Example

let mut set = AATreeSet::new();
assert_eq!(set.pop_last(), None);
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.pop_last(), Some(44));
assert_eq!(set.pop_last(), Some(42));
assert_eq!(set.pop_last(), Some(40));
assert_eq!(set.pop_last(), None);

pub fn contains<Q>(&self, value: &Q) -> boolwhere
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns true if the set contains an element with the given value.

Example

let mut set = AATreeSet::new();
set.insert(43);
assert_eq!(set.contains(&42), false);
set.insert(42);
assert_eq!(set.contains(&42), true);

pub fn first_at_or_after<Q>(&self, value: &Q) -> Option<&T>where
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns the first/smallest element of the set that is greater or equal to x.

Example

let mut set = AATreeSet::new();
assert!(set.first_at_or_after(&41).is_none());
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.first_at_or_after(&41), Some(&42));

pub fn last_at_or_before<Q>(&self, value: &Q) -> Option<&T>where
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Returns the last/largest element of the set that is smaller or equal to x.

Example

let mut set = AATreeSet::new();
assert!(set.last_at_or_before(&43).is_none());
set.insert(42);
set.insert(44);
set.insert(40);
assert_eq!(set.last_at_or_before(&43), Some(&42));

pub fn remove<Q>(&mut self, x: &Q) -> boolwhere
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Removes a value from the set, and returns true if it was removed.

pub fn take<Q>(&mut self, x: &Q) -> Option<T>where
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

Removes a value from the set, and returns the value that was removed.

Trait Implementations

impl<T: Clone> Clone for AATreeSet<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for AATreeSet<T>

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

Formats the value using the given formatter.

impl<T> Default for AATreeSet<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T: Ord + Copy + 'a> Extend<&'a T> for AATreeSet<T>

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord> Extend<T> for AATreeSet<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord, const N: usize> From<[T; N]> for AATreeSet<T>

fn from(array: [T; N]) -> Self

Converts to this type from the input type.

impl<T: Ord> From<Vec<T, Global>> for AATreeSet<T>

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

Converts to this type from the input type.

impl<T: Ord> FromIterator<T> for AATreeSet<T>

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a AATreeSet<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = AAIter<'a, T, &'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 AATreeSet<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = AAIntoIter<T, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Ord> Ord for AATreeSet<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: PartialOrd<Self>,

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<AATreeSet<T>> for AATreeSet<T>

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialOrd> PartialOrd<AATreeSet<T>> for AATreeSet<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Eq> Eq for AATreeSet<T>