rb_tree

此crate包含红黑树数据结构的实现以及构建在此实现之上的几个数据结构。当前包括RBTree、RBMap和RBQueue。

数据结构

RBTree

此数据结构可以用作集合，并具有支持其作为集合使用的方法。此数据结构特有的方法包括并集、差集等集合操作。值按照其PartialOrd排序存储。

RBMap

此数据结构提供了将RBTree用作映射的接口。映射中的值按照其键的PartialOrd排序。

RBQueue

此数据结构允许将底层红黑树用作优先队列。在实例化时提供了一个比较函数（使用RBQueue::new(Fn(&T, &T) -> std::cmp::Ordering)或new_c_queue!(Fn(&T, &T) -> i8)）。它用于排序条目。

功能

上述数据结构可以可选地排除（默认情况下全部包含）。如果您只使用一种或两种类型，可以排除其他类型以帮助最小化二进制文件大小。但是，因为RBMap是RBTree的包装类型，包括前者将始终包括后者。为此，请将以下内容添加到您的依赖项中

[dependencies]
rb_tree = { version = "*", default-features = false, features = ["map" | "set" | "queue"]}

这将分别向您的二进制文件添加RBMap、RBTree和RBQueue类型。将default-features设置为false很重要，因为默认情况下已启用所有功能。

此外，还可以通过 serde 功能添加对上述类型的序列化支持。

有关 cargo 功能系统的更多信息，请参见此处。

示例

use rb_tree::RBTree;

// uses an rbtree to sort data
fn sort<T: PartialOrd>(to_order: Vec<T>) -> Vec<T> {
    let mut tree = RBTree::new();
    let mut ordered = Vec::new();
    for v in to_order {
        tree.insert(v);
    }
    while let Some(v) = tree.pop() {
        ordered.push(v);
    }
    ordered
}

fn main() {
    let eg1 = vec!(3, 6, 1, 2, 0, 4, -1, 5, 10, 11, -13);
    assert_eq!(sort(eg1), vec!(-13, -1, 0, 1, 2, 3, 4, 5, 6, 10, 11));

    let eg2 = vec!("Is", "this", "the", "real", "life");
    assert_eq!(sort(eg2), vec!("Is", "life", "real", "the", "this"))
}

use rb_tree::RBMap;

fn main() {
    let mut squares = RBMap::new();
    for i in 0..10 {
        squares.insert(i, i);
    }

    squares.values_mut().for_each(|v| *v = (*v as f64).powi(2) as u32);

    for i in 0..10 {
        assert_eq!(*squares.get(&i).unwrap(), (i as f64).powi(2) as u32);
    }
}

#[macro_use(new_c_queue)]
extern crate rb_tree;

use rb_tree::RBQueue;

fn main() {
    
    // use the default comarator
    let mut q1 = RBQueue::new(|l: &i64, r| {
        l.cmp(r)
    });

    // compare in the reverse order
    let mut q2 = new_c_queue!(|l: &i64, r| (r - l));

    q1.insert(1);
    q1.insert(2);
    q1.insert(3);
    q2.insert(1);
    q2.insert(2);
    q2.insert(3);

    assert_eq!(q1.ordered(), [&1, &2, &3]);
    assert_eq!(q2.ordered(), [&3, &2, &1]);
}

许可证

本项目的许可协议为 MIT 许可证，具体请参见此处。