Struct rtrees::rbtree::RBTree

pub struct RBTree<K: Ord + Copy, A: Copy, V>(_);

A left-leaning red–black (LLRB) Tree, optimized for safety, simplicity of implementation, and augmentation. This tree is mimicking the behavior of a 2-3 tree. Full desciption of the tree design and complexity analysis is available in the paper titled Left-leaning Red-Black Trees by Robert Sedgewick. If you just need a normal non-augmentable tree-baesed map check std::collections::BTreeMap instead.

Methods

impl<K: Ord + Copy, A: Copy, V> RBTree<K, A, V> where
    RBTree<K, A, V>: Augment<A>, 

pub fn is_node(&self) -> bool

Return True if the current node is not null node.

pub fn key(&self) -> K

Returns copy of key of the current Tree node

Panics

panics if current subtree is not a node

pub fn set_aug_data(&mut self, aug_data: A)

Changes the aug_data stored in the current Tree node.

Panics

panics if current subtree is not a node.

pub fn aug_data(&self) -> A

Returns aug_data stored in the current Tree node.

Panics

panics if current subtree is not a node

pub fn set_data(&mut self, data: V)

Changes the data stored in the current Tree node.

Panics

panics if current subtree is not a node.

pub fn data(self) -> V

Returns data stored in the current Tree node.

Panics

panics if current subtree is not a node

pub fn mut_me(&mut self) -> LeftRightDataTuple<K, A, V>

Returns a tuple of tree elements: a mutable reference to left node, mutable right node and mutable referent to the value stored inside the current node. The reason such functionality might be desired, is when user wants to keep mutual reference of at least any 2 of either left node, right node or data. left_mut(), right_mut() and data_mut() will not work because rust does not support partial borrowing yet.

pub fn data_ref(&self) -> &V

Returns non-mutable reference to data stored in the current Tree node

Panics

panics if current subtree is not a node

pub fn data_mut(&mut self) -> &mut V

Returns mutable reference to data stored in the current Tree node

Panics

panics if current subtree is not a node

pub fn set_left(&mut self, subtree: RBTree<K, A, V>)

Set the left subtree of the current Node.

Panics

panics if current subtree is not a node.

pub fn left(&mut self) -> RBTree<K, A, V>

Returns the left subtree after ripping it from the current node.

Panics

panics if current subtree is not a node

pub fn left_ref(&self) -> &RBTree<K, A, V>

Returns a non-mutable reference to left subtree.

Panics

panics if current subtree is not a node

pub fn left_mut(&mut self) -> &mut RBTree<K, A, V>

Returns a mutable reference to left subtree.

Panics

panics if current subtree is not a node

pub fn set_right(&mut self, subtree: RBTree<K, A, V>)

Set the right subtree of the current Node.

Panics

panics if current subtree is not a node.

pub fn right(&mut self) -> RBTree<K, A, V>

Returns the right subtree after ripping it from the current node.

Panics

panics if current subtree is not a node

pub fn right_ref(&self) -> &RBTree<K, A, V>

Returns a non-mutable reference to right subtree.

Panics

panics if current subtree is not a node

pub fn right_mut(&mut self) -> &mut RBTree<K, A, V>

Returns a mutable reference to right subtree.

Panics

panics if current subtree is not a node

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

Returns new Red Black Tree

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let my_tree = Tree::new();

pub fn size(&self) -> u64

Returns the number of elements in the tree

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let mut rbtree = Tree::new();
assert_eq!(rbtree.size(), 0);
rbtree.insert(0, PlaceHolder(), "Zero");
assert_eq!(rbtree.size(), 1);
rbtree.insert(1, PlaceHolder(), "One");
assert_eq!(rbtree.size(), 2);
rbtree.insert(2, PlaceHolder(), "Two");
assert_eq!(rbtree.size(), 3);

pub fn get_level(&self) -> u64

0 will be returned in case of empty tree. If tree has nodes, then get_level returns 1 + the number of connections between root and the farthest node from it.

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let mut rbtree = Tree::new();
assert_eq!(rbtree.get_level(), 0);
for i in 0..1024 {
    rbtree.insert(i, PlaceHolder(), "Random Value");
}
assert!(rbtree.get_level() >= 10 && rbtree.get_level() <= 20);

pub fn delete_min(&mut self) -> Option<V>

Deletes the minimum value in the tree and returns the data stored in that node.

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let mut rbtree = RBTree::new();
rbtree.insert(0, PlaceHolder(), "First Insertion");
rbtree.insert(5, PlaceHolder(), "Second Insertion");
rbtree.insert(10, PlaceHolder(), "Third Insertion");
assert_eq!(rbtree.delete_min().unwrap(), "First Insertion");
assert_eq!(rbtree.delete_min().unwrap(), "Second Insertion");
assert_eq!(rbtree.delete_min().unwrap(), "Third Insertion");
assert_eq!(rbtree.delete_min(), None);

pub fn insert(&mut self, key: K, aug_data: A, data: V)

Inserts data associated with key into tree. insert does not support duplicated key. In case of inserting into an already existing key, the old data will silently be repalced by the new data.

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, u64> {}
type Tree = RBTree<u64, PlaceHolder, u64>;
let mut rbtree = Tree::new();
rbtree.insert(0, PlaceHolder(), 0);
rbtree.insert(1, PlaceHolder(), 1);
rbtree.insert(2, PlaceHolder(), 2);
assert_eq!(rbtree.search(0).unwrap(), &0);
assert_eq!(rbtree.search(1).unwrap(), &1);
assert_eq!(rbtree.search(2).unwrap(), &2);

pub fn force_sync_aug(&mut self, key: K)

Force recalculating all agumented data from node matching key up to the root node.

pub fn search(&self, key: K) -> Option<&V>

Returns a non mutable references of the data stored at key #example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let mut rbtree = Tree::new();
rbtree.insert(0, PlaceHolder(), "First Insertion");
rbtree.insert(5, PlaceHolder(), "Second Insertion");
assert_eq!(rbtree.search(0).unwrap(), &"First Insertion");
assert_eq!(rbtree.search(5).unwrap(), &"Second Insertion");
assert_eq!(rbtree.search(21), None);

pub fn search_mut(&mut self, key: K) -> Option<&mut V>

Returns a mutable references of the data stored at key. We assume that in mutable search caller might modify augmented data, #example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, String> {}
type Tree = RBTree<u64, PlaceHolder,  String>;
let mut rbtree = RBTree::new();
rbtree.insert(0, PlaceHolder(), String::from("First Insertion"));
rbtree.search_mut(0).unwrap().push_str(" Modified");
assert_eq!(rbtree.search(0).unwrap(), &"First Insertion Modified");

pub fn delete(&mut self, key: K) -> Option<V>

Deletes tree node represented by key. The return value is data stored there.

Example

use rtrees::rbtree::*;
#[derive(Copy, Clone)]
struct PlaceHolder();
impl Augment<PlaceHolder> for RBTree<u64, PlaceHolder, &'static str> {}
type Tree = RBTree<u64, PlaceHolder,  &'static str>;
let mut rbtree = Tree::new();
rbtree.insert(10, PlaceHolder(), "First Insertion");
rbtree.insert(15, PlaceHolder(), "Second Insertion");
assert_eq!(rbtree.delete(10).unwrap(), "First Insertion");
assert_eq!(rbtree.delete(15).unwrap(), "Second Insertion");

Trait Implementations

impl<K: Default + Ord + Copy, A: Default + Copy, V: Default> Default for RBTree<K, A, V>

fn default() -> RBTree<K, A, V>

Returns the "default value" for a type.

impl<K: Ord + Copy, A: Copy, V> IntoIterator for RBTree<K, A, V> where
    RBTree<K, A, V>: Augment<A>, 

type Item = (K, A, V)

The type of the elements being iterated over.

type IntoIter = TreeIterator<K, A, V>

Which kind of iterator are we turning this into?

Important traits for TreeIterator<K, A, V>

impl<K: Ord + Copy, A: Copy, V> Iterator for TreeIterator<K, A, V> where
    RBTree<K, A, V>: Augment<A>,  type Item = (K, A, V);

fn into_iter(self) -> TreeIterator<K, A, V>

Creates an iterator from a value.

impl<'a, K: Ord + Copy, A: Copy, V> IntoIterator for &'a RBTree<K, A, V> where
    RBTree<K, A, V>: Augment<A>, 

type Item = (K, A, &'a V)

The type of the elements being iterated over.

type IntoIter = TreeRefIterator<'a, K, A, V>

Which kind of iterator are we turning this into?

Important traits for TreeRefIterator<'a, K, A, V>

impl<'a, K: Ord + Copy, A: Copy, V> Iterator for TreeRefIterator<'a, K, A, V> where
    RBTree<K, A, V>: Augment<A>,  type Item = (K, A, &'a V);

fn into_iter(self) -> TreeRefIterator<'a, K, A, V>

Creates an iterator from a value.