Struct rb_tree::RBTree

pub struct RBTree<T: PartialOrd> { /* fields omitted */ }

A red black tree that can be used to store elements sorted by their PartialOrd provided ordering.

Implementations

impl<T: PartialOrd> RBTree<T>

pub fn new() -> RBTree<T>

Creates and returns a new RBTree.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(3);
t.insert(2);
assert_eq!(t.take(&2).unwrap(), 2);

pub fn into_queue<P>(self, comp: P) -> RBQueue<T, P> where
    P: Copy + Fn(&T, &T) -> Ordering, 

Turns this tree into a queue with the given the comparison method.

Example:

use rb_tree::{RBTree, RBQueue};
use std::cmp::Ordering::{Equal, Less, Greater};

let mut t = RBTree::new();
t.insert(3);
t.insert(2);
t.insert(1);

// reverse order queue
let mut q = t.into_queue(|l, r| {
    match l - r {
        i32::MIN..=-1_i32 => Greater,
        0 => Equal,
        1_i32..=i32::MAX => Less
    }
});
assert_eq!(q.pop().unwrap(), 3);
assert_eq!(q.pop().unwrap(), 2);
assert_eq!(q.pop().unwrap(), 1);
assert_eq!(q.pop(), None);

pub fn clear(&mut self)

Clears all entries from the tree.

Example:

use rb_tree::RBTree;

let mut tree = RBTree::new();
tree.insert(2);
tree.insert(5);
tree.clear();
assert_eq!(tree.len(), 0);
assert!(!tree.contains(&2));

pub fn drain(&mut self) -> Drain<T>

Clears the tree and returns all values as an iterator in their PartialOrd order.

Example:

use rb_tree::RBTree;

let mut tree = RBTree::new();
tree.insert(2);
tree.insert(5);
assert_eq!(tree.len(), 2);
let mut drain = tree.drain();
assert_eq!(drain.next().unwrap(), 2);
assert_eq!(drain.next().unwrap(), 5);
assert!(drain.next().is_none());
assert_eq!(tree.len(), 0);

pub fn ordered(&self) -> Vec<&T>

Returns a vector presenting the contained elements of the RBTree in the order by which they are prioritised (that is, in the in-order tree traversal order).

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(3);
t.insert(1);
t.insert(2);
let order = t.ordered();
assert_eq!(*order[1], 2);

pub fn len(&self) -> usize

Returns the number of elements contained in the tree.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(3);
t.insert(1);
t.insert(2);
assert_eq!(t.len(), 3);
t.remove(&2);
assert_eq!(t.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if there are no items present in the tree, false otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
assert!(t.is_empty());
t.insert(3);
assert!(!t.is_empty());

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

Inserts a new element into the RBTree. Returns true if this item was not already in the tree, and false otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
assert_eq!(t.insert("Hello".to_string()), true);
assert_eq!(t.insert("Hello".to_string()), false);

pub fn replace(&mut self, val: T) -> Option<T>

Inserts a new element into the RBTree. Returns None if this item was not already in the tree, and the previously contained item otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
assert_eq!(t.replace("Hello".to_string()), None);
assert_eq!(t.replace("Hello".to_string()), Some("Hello".to_string()));

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

Returns true if the tree contains the specified item, false otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(2);
assert!(!t.contains(&3));
assert!(t.contains(&2));

pub fn get<K: PartialOrd<T>>(&self, val: &K) -> Option<&T>

Returns the item specified if contained, None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(1);
assert_eq!(*t.get(&1).unwrap(), 1);
assert_eq!(t.get(&2), None);

pub fn take<K: PartialOrd<T>>(&mut self, val: &K) -> Option<T>

Removes an item the tree. Returns the matching item if it was contained in the tree, None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(4);
t.insert(2);
assert_eq!(t.take(&2).unwrap(), 2);
assert_eq!(t.len(), 1);
assert_eq!(t.take(&2), None);

pub fn remove<K: PartialOrd<T>>(&mut self, val: &K) -> bool

Removes an item the tree. Returns true if it was contained in the tree, false otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(4);
t.insert(2);
assert_eq!(t.remove(&2), true);
assert_eq!(t.len(), 1);
assert_eq!(t.remove(&2), false);

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

Removes the item at the front of the priority queue that the RBTree represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(t.pop().unwrap(), 1);

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

Peeks the item at the front of the priority queue that the RBTree represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(*t.peek().unwrap(), 1);

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

Removes the item at the back of the priority queue that the RBTree represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(t.pop_back().unwrap(), 3);

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

Peeks the item at the back of the priority queue that the RBTree represents if any elements are present, or None otherwise.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(2);
t.insert(1);
t.insert(3);
assert_eq!(*t.peek_back().unwrap(), 3);

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

Returns an iterator over the elements contained in this RBTree.

Example:

use rb_tree::RBTree;

let mut t = RBTree::new();
t.insert(3);
t.insert(1);
t.insert(5);
assert_eq!(t.iter().collect::<Vec<&usize>>(), vec!(&1, &3, &5));

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

Returns an iterator representing the difference between the items in this RBTree and those in another RBTree, i.e. the values in self but not in other.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..5).for_each(|v| {t2.insert(v);});
assert_eq!(
    t1.difference(&t2).collect::<Vec<&usize>>(),
    vec!(&0, &1)
);
assert_eq!(
    t2.difference(&t1).collect::<Vec<&usize>>(),
    vec!(&3, &4)
);

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

Returns an iterator representing the symmetric difference between the items in this RBTree and those in another, i.e. the values in self or other but not in both.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..5).for_each(|v| {t2.insert(v);});
assert_eq!(
    t1.symmetric_difference(&t2).collect::<Vec<&usize>>(),
    vec!(&0, &1, &3, &4)
);
assert_eq!(
    t2.symmetric_difference(&t1).collect::<Vec<&usize>>(),
    vec!(&0, &1, &3, &4)
);

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

Returns an iterator representing the intersection of this RBTree and another, i.e. the values that appear in both self and other.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..5).for_each(|v| {t2.insert(v);});
assert_eq!(
    t1.intersection(&t2).collect::<Vec<&usize>>(),
    vec!(&2)
);

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

Returns an iterator representing the union of this RBTree and another, i.e. the values that appear in at least one of the RBTrees.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..5).for_each(|v| {t2.insert(v);});
assert_eq!(
    t1.union(&t2).collect::<Vec<&usize>>(),
    vec!(&0, &1, &2, &3, &4)
);

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

Returns true if this RBTree and another are disjoint, i.e. there are no values in self that appear in other and vice versa, false otherwise.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..5).for_each(|v| {t2.insert(v);});
assert!(!t1.is_disjoint(&t2));
t2.pop(); // remove '2' from t2
assert!(t1.is_disjoint(&t2));

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

Returns true if this RBTree is a subset of another, i.e. at least all values in self also appear in other, false otherwise.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
let mut t3 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..10).for_each(|v| {t2.insert(v);});
(3..7).for_each(|v| {t3.insert(v);});
assert!(!t1.is_subset(&t2));
assert!(t3.is_subset(&t2));

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

Returns true if this RBTree is a superset of another, i.e. at least all values in other also appear in self, false otherwise.

Example:

use rb_tree::RBTree;

let mut t1 = RBTree::new();
let mut t2 = RBTree::new();
let mut t3 = RBTree::new();
(0..3).for_each(|v| {t1.insert(v);});
(2..10).for_each(|v| {t2.insert(v);});
(3..7).for_each(|v| {t3.insert(v);});
assert!(!t2.is_superset(&t1));
assert!(t2.is_superset(&t3));

pub fn retain<F: FnMut(&T) -> bool>(&mut self, f: F)

Retains in this RBTree only those values for which the passed closure returns true.

Example:

use rb_tree::RBTree;

let mut t: RBTree<usize> = (0..10).collect();
t.retain(|v| v % 2 == 0);
assert_eq!(t.iter().collect::<Vec<&usize>>(), vec!(&0, &2, &4, &6, &8));

Trait Implementations

impl<T: Clone + PartialOrd> Clone for RBTree<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: PartialOrd + Debug> Debug for RBTree<T>

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

Formats the value using the given formatter.

impl<T: PartialOrd> Default for RBTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: PartialOrd + Debug> Display for RBTree<T>

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

Formats the value using the given formatter.

impl<'a, T: PartialOrd + Copy + 'a> Extend<&'a T> for RBTree<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: PartialOrd> Extend<T> for RBTree<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, P> From<RBQueue<T, P>> for RBTree<T> where
    T: PartialOrd,
    P: Copy + Fn(&T, &T) -> Ordering, 

fn from(q: RBQueue<T, P>) -> Self

Performs the conversion.

impl<T: PartialOrd> FromIterator<T> for RBTree<T>

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

Creates a value from an iterator.

impl<T: PartialOrd> IntoIterator for RBTree<T>

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) -> IntoIter<T>

Creates an iterator from a value.