Struct algorithm::RBTree

pub struct RBTree<K: Ord, V> { /* private fields */ }

A red black tree implemented with Rust It is required that the keys implement the Ord traits.

Examples

use algorithm::RBTree;
// type inference lets us omit an explicit type signature (which
// would be `RBTree<&str, &str>` in this example).
let mut book_reviews = RBTree::new();

// review some books.
book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book.");
book_reviews.insert("Grimms' Fairy Tales", "Masterpiece.");
book_reviews.insert("Pride and Prejudice", "Very enjoyable.");
book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");

// check for a specific one.
if !book_reviews.contains_key(&"Les Misérables") {
    println!(
        "We've got {} reviews, but Les Misérables ain't one.",
        book_reviews.len()
    );
}

// oops, this review has a lot of spelling mistakes, let's delete it.
book_reviews.remove(&"The Adventures of Sherlock Holmes");

// look up the values associated with some keys.
let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
for book in &to_find {
    match book_reviews.get(book) {
        Some(review) => println!("{}: {}", book, review),
        None => println!("{} is unreviewed.", book),
    }
}

// iterate over everything.
for (book, review) in book_reviews.iter() {
    println!("{}: \"{}\"", book, review);
}

book_reviews.print_tree();

// A RBTree with fixed list of elements can be initialized from an array:

use algorithm::RBTree;
let timber_resources: RBTree<&str, i32> =
[("Norway", 100),
 ("Denmark", 50),
 ("Iceland", 10)]
 .iter().cloned().collect();
// use the values stored in rbtree

Implementations

impl<K: Ord + Debug, V: Debug> RBTree<K, V>

This is a method to help us to get inner struct.

pub fn print_tree(&self)

impl<K: Ord, V> RBTree<K, V>

pub fn new() -> RBTree<K, V>

Creates an empty RBTree.

pub fn len(&self) -> usize

Returns the len of RBTree.

pub fn is_empty(&self) -> bool

Returns true if the RBTree is empty.

pub fn replace_or_insert(&mut self, k: K, v: V) -> Option<V>

replace value if key exist, if not exist insert it.

Examples

use algorithm::RBTree;
let mut m = RBTree::new();
assert_eq!(m.len(), 0);
m.insert(2, 4);
assert_eq!(m.len(), 1);
assert_eq!(m.replace_or_insert(2, 6).unwrap(), 4);
assert_eq!(m.len(), 1);
assert_eq!(*m.get(&2).unwrap(), 6);

pub fn insert(&mut self, k: K, v: V)

pub fn get_first(&self) -> Option<(&K, &V)>

pub fn get_last(&self) -> Option<(&K, &V)>

pub fn pop_first(&mut self) -> Option<(K, V)>

pub fn pop_last(&mut self) -> Option<(K, V)>

pub fn get_first_mut(&mut self) -> Option<(&K, &mut V)>

pub fn get_last_mut(&mut self) -> Option<(&K, &mut V)>

pub fn get(&self, k: &K) -> Option<&V>

pub fn get_mut(&mut self, k: &K) -> Option<&mut V>

pub fn contains_key(&self, k: &K) -> bool

pub fn clear(&mut self)

clear all red back tree elements.

Examples

use algorithm::RBTree;
let mut m = RBTree::new();
for i in 0..6 {
    m.insert(i, i);
}
assert_eq!(m.len(), 6);
m.clear();
assert_eq!(m.len(), 0);

pub fn remove(&mut self, k: &K) -> Option<V>

pub fn keys(&self) -> Keys<'_, K, V>

Return the keys iter

pub fn values(&self) -> Values<'_, K, V>

Return the value iter

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Return the value iter mut

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

Return the key and value iter

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Return the key and mut value iter

pub fn drain(&mut self) -> Drain<'_, K, V>

Trait Implementations

impl<K: Ord + Clone, V: Clone> Clone for RBTree<K, V>

If key and value are both impl Clone, we can call clone to get a copy.

fn clone(&self) -> RBTree<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for RBTree<K, V>

where K: Ord + Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K: Ord, V> Drop for RBTree<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: Ord, V> Extend<(K, V)> for RBTree<K, V>

RBTree into iter

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

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<K: Ord, V> FromIterator<(K, V)> for RBTree<K, V>

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> RBTree<K, V>

Creates a value from an iterator.

impl<'a, K, V> Index<&'a K> for RBTree<K, V>

where K: Ord,

type Output = V

The returned type after indexing.

fn index(&self, index: &K) -> &V

Performs the indexing (container[index]) operation.

impl<K: Ord, V> IntoIterator for RBTree<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.

impl<K, V> PartialEq for RBTree<K, V>

where K: Eq + Ord, V: PartialEq,

all key be same, but it has multi key, if has multi key, it perhaps no correct

fn eq(&self, other: &RBTree<K, V>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<K, V> Eq for RBTree<K, V>

where K: Eq + Ord, V: Eq,

impl<K: Ord, V> Send for RBTree<K, V>

impl<K: Ord, V> Sync for RBTree<K, V>