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 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 smallest(&self) -> Option<&T>

Returns the smallest element of the set.

Example

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

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

Returns the largest element of the set.

Example

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

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

Remove and return the smallest element of the set.

Example

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

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

Remove and return the largest element of the set.

Example

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

pub fn contains<Q>(&self, x: &Q) -> bool where
    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 smallest_geq_than<Q>(&self, x: &Q) -> Option<&T> where
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized, 

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

Example

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

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

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

Example

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

pub fn remove<Q>(&mut self, x: &Q) -> bool where
    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<T: Ord> FromIterator<T> for AATreeSet<T>

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

Creates a value from an iterator.

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<'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.