Struct rbtree::RBTree

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

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

Implementations§

source§

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

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

source

pub fn print_tree(&self)

source§

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

source

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

Creates an empty RBTree.

Examples found in repository?
examples/bench.rs (line 26)
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

fn test_insert(repeat: u64, insert: u64) {
    let mut sum = 0;
    let mut max = 0;
    let mut min = ::std::u64::MAX;

    let mut get_sum = 0;
    let mut get_max = 0;
    let mut get_min = ::std::u64::MAX;

    let mut remove_sum = 0;
    let mut remove_max = 0;
    let mut remove_min = ::std::u64::MAX;


    for _ in 0..repeat {
        let now = Instant::now();
        let mut a = RBTree::new();
        for i in 0..insert {
            a.insert(i, i * 2);
        }
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        sum += cost;
        max = cmp::max(cost, max);
        min = cmp::min(cost, min);


        let now = Instant::now();
        assert_eq!(a.get(&20).unwrap(), &40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        get_sum += cost;
        get_max = cmp::max(cost, get_max);
        get_min = cmp::min(cost, get_min);


        let now = Instant::now();
        assert_eq!(a.remove(&20).unwrap(), 40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        remove_sum += cost;
        remove_max = cmp::max(cost, remove_max);
        remove_min = cmp::min(cost, remove_min);
    }

    println!("-----------All Test Repeat: {}, All Tree Num: {}-------------------", repeat, insert);
    println!("Insert Test,           Max Cost: {}us, Min Cost: {}us, Aver Cost: {}us", 
            max / 1000,
            min / 1000,
            sum / 1000 / repeat);

    println!("Get data by key=20,    Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            get_max,
            get_min,
            get_sum / repeat);

    println!("Remove data by key=20, Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            remove_max,
            remove_min,
            remove_sum / repeat);

    println!("-----------End Tree Test----------------------------------------------\n");

}
source

pub fn len(&self) -> usize

Returns the len of RBTree.

source

pub fn is_empty(&self) -> bool

Returns true if the RBTree is empty.

source

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 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);
source

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

Examples found in repository?
examples/bench.rs (line 28)
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

fn test_insert(repeat: u64, insert: u64) {
    let mut sum = 0;
    let mut max = 0;
    let mut min = ::std::u64::MAX;

    let mut get_sum = 0;
    let mut get_max = 0;
    let mut get_min = ::std::u64::MAX;

    let mut remove_sum = 0;
    let mut remove_max = 0;
    let mut remove_min = ::std::u64::MAX;


    for _ in 0..repeat {
        let now = Instant::now();
        let mut a = RBTree::new();
        for i in 0..insert {
            a.insert(i, i * 2);
        }
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        sum += cost;
        max = cmp::max(cost, max);
        min = cmp::min(cost, min);


        let now = Instant::now();
        assert_eq!(a.get(&20).unwrap(), &40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        get_sum += cost;
        get_max = cmp::max(cost, get_max);
        get_min = cmp::min(cost, get_min);


        let now = Instant::now();
        assert_eq!(a.remove(&20).unwrap(), 40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        remove_sum += cost;
        remove_max = cmp::max(cost, remove_max);
        remove_min = cmp::min(cost, remove_min);
    }

    println!("-----------All Test Repeat: {}, All Tree Num: {}-------------------", repeat, insert);
    println!("Insert Test,           Max Cost: {}us, Min Cost: {}us, Aver Cost: {}us", 
            max / 1000,
            min / 1000,
            sum / 1000 / repeat);

    println!("Get data by key=20,    Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            get_max,
            get_min,
            get_sum / repeat);

    println!("Remove data by key=20, Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            remove_max,
            remove_min,
            remove_sum / repeat);

    println!("-----------End Tree Test----------------------------------------------\n");

}
source

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

source

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

source

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

source

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

source

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

source

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

source

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

Examples found in repository?
examples/bench.rs (line 38)
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

fn test_insert(repeat: u64, insert: u64) {
    let mut sum = 0;
    let mut max = 0;
    let mut min = ::std::u64::MAX;

    let mut get_sum = 0;
    let mut get_max = 0;
    let mut get_min = ::std::u64::MAX;

    let mut remove_sum = 0;
    let mut remove_max = 0;
    let mut remove_min = ::std::u64::MAX;


    for _ in 0..repeat {
        let now = Instant::now();
        let mut a = RBTree::new();
        for i in 0..insert {
            a.insert(i, i * 2);
        }
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        sum += cost;
        max = cmp::max(cost, max);
        min = cmp::min(cost, min);


        let now = Instant::now();
        assert_eq!(a.get(&20).unwrap(), &40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        get_sum += cost;
        get_max = cmp::max(cost, get_max);
        get_min = cmp::min(cost, get_min);


        let now = Instant::now();
        assert_eq!(a.remove(&20).unwrap(), 40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        remove_sum += cost;
        remove_max = cmp::max(cost, remove_max);
        remove_min = cmp::min(cost, remove_min);
    }

    println!("-----------All Test Repeat: {}, All Tree Num: {}-------------------", repeat, insert);
    println!("Insert Test,           Max Cost: {}us, Min Cost: {}us, Aver Cost: {}us", 
            max / 1000,
            min / 1000,
            sum / 1000 / repeat);

    println!("Get data by key=20,    Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            get_max,
            get_min,
            get_sum / repeat);

    println!("Remove data by key=20, Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            remove_max,
            remove_min,
            remove_sum / repeat);

    println!("-----------End Tree Test----------------------------------------------\n");

}
source

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

source

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

source

pub fn clear(&mut self)

clear all red back tree elements.

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

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

Examples found in repository?
examples/bench.rs (line 47)
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

fn test_insert(repeat: u64, insert: u64) {
    let mut sum = 0;
    let mut max = 0;
    let mut min = ::std::u64::MAX;

    let mut get_sum = 0;
    let mut get_max = 0;
    let mut get_min = ::std::u64::MAX;

    let mut remove_sum = 0;
    let mut remove_max = 0;
    let mut remove_min = ::std::u64::MAX;


    for _ in 0..repeat {
        let now = Instant::now();
        let mut a = RBTree::new();
        for i in 0..insert {
            a.insert(i, i * 2);
        }
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        sum += cost;
        max = cmp::max(cost, max);
        min = cmp::min(cost, min);


        let now = Instant::now();
        assert_eq!(a.get(&20).unwrap(), &40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        get_sum += cost;
        get_max = cmp::max(cost, get_max);
        get_min = cmp::min(cost, get_min);


        let now = Instant::now();
        assert_eq!(a.remove(&20).unwrap(), 40);
        let new_now = Instant::now();
        let cost = duration_to_num(new_now.duration_since(now));
        remove_sum += cost;
        remove_max = cmp::max(cost, remove_max);
        remove_min = cmp::min(cost, remove_min);
    }

    println!("-----------All Test Repeat: {}, All Tree Num: {}-------------------", repeat, insert);
    println!("Insert Test,           Max Cost: {}us, Min Cost: {}us, Aver Cost: {}us", 
            max / 1000,
            min / 1000,
            sum / 1000 / repeat);

    println!("Get data by key=20,    Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            get_max,
            get_min,
            get_sum / repeat);

    println!("Remove data by key=20, Max Cost: {}ns, Min Cost: {}ns, Aver Cost: {}ns", 
            remove_max,
            remove_min,
            remove_sum / repeat);

    println!("-----------End Tree Test----------------------------------------------\n");

}
source

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

Return the keys iter

source

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

Return the value iter

source

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

Return the value iter mut

source

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

Return the key and value iter

source

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

Return the key and mut value iter

Trait Implementations§

source§

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.

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn drop(&mut self)

Executes the destructor for this type. Read more
source§

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

RBTree into iter

source§

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

Extends a collection with the contents of an iterator. Read more
source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
source§

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. Read more
source§

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

source§

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

Creates a value from an iterator. Read more
source§

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

§

type Output = V

The returned type after indexing.
source§

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

Performs the indexing (container[index]) operation. Read more
source§

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?
source§

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

Creates an iterator from a value. Read more
source§

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

source§

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

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

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

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

source§

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

source§

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

Auto Trait Implementations§

§

impl<K, V> RefUnwindSafe for RBTree<K, V>
where K: RefUnwindSafe, V: RefUnwindSafe,

§

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

§

impl<K, V> UnwindSafe for RBTree<K, V>
where K: RefUnwindSafe, V: RefUnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.