rb_tree 0.5.0

A Red Black Tree implementation in Rust
Documentation 
1
2
3
4
5
6
7
8
9
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

use crate::node::Node;
use crate::node::Node::{Internal, Leaf};
use std::fmt::Debug;

pub fn write_to_level<T: Debug>(
    cur: &Node<T>,
    from_str: String,
    level: usize,
    levels: &mut Vec<String>,
) {
    if levels.len() <= level {
        match cur {
            Internal(n) => levels.push(format!("{}{}:{:?}", from_str, n.colour(), n.value())),
            Leaf(_) => levels.push(format!("{}___", from_str)),
        }
    } else {
        match cur {
            Internal(n) => levels[level] += &format!(" {}{}:{:?}", from_str, n.colour(), n.value()),
            Leaf(_) => levels[level] += &format!(" {}___", from_str),
        }
    }
    if !cur.is_leaf() {
        write_to_level(
            cur.get_left(),
            format!("{:?}->", cur.value().unwrap()),
            level + 1,
            levels,
        );
        write_to_level(
            cur.get_right(),
            format!("{:?}->", cur.value().unwrap()),
            level + 1,
            levels,
        );
    }
}

pub fn ordered_insertion<'a, T>(cur: &'a Node<T>, order: &mut Vec<&'a T>) {
    if cur.is_leaf() {
        return;
    }
    ordered_insertion(cur.get_left(), order);
    if let Some(v) = cur.value() {
        order.push(v);
    }
    ordered_insertion(cur.get_right(), order);
}

// inserts into stack start and all left children
// of start down to the leaf
#[cfg(feature = "set")]
pub fn insert_left_down<'a, T>(start: &'a Node<T>, stack: &mut Vec<&'a Node<T>>) {
    let mut cur = start;
    while !cur.is_leaf() {
        stack.push(cur);
        cur = cur.get_left();
    }
}