Struct rbtree::RBTree

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

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

Examples

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

Methods

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

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

fn print_tree(&self)

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

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

Creates an empty RBTree.

fn len(&self) -> usize

Returns the len of RBTree.

fn is_empty(&self) -> bool

Returns true if the RBTree is empty.

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

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

Examples

use rbtree::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);

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

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

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

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

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

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

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

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

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

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

fn clear(&mut self)

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

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

Return the keys iter

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

Return the value iter

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

Return the value iter mut

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

Return the key and value iter

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

Return the key and mut value iter

Trait Implementations

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

fn drop(&mut self)

Executes the destructor for this type.

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, 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

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 !=.

impl<K, V> Eq for RBTree<K, V> where
    K: Eq + Ord,
    V: Eq, 

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

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.