Struct coll::persistent::RbTree

pub struct RbTree<T: PartialEq + PartialOrd> { /* fields omitted */ }

Methods

impl<T: PartialEq + PartialOrd> RbTree<T>

fn new() -> RbTree<T>

Creates a new, empty, red-black tree.

fn insert(&self, item: T) -> RbTree<T>

Inserts an item into a new copy of the existing Tree.

Examples

use coll::persistent::RbTree;
let tree_one = RbTree::new();
let tree_two = tree_one.insert(1);
let tree_three = tree_two.insert(2);
assert!(tree_one != tree_two);
assert!(tree_two != tree_three);
assert!(tree_three != tree_one);

fn len(&self) -> usize

Gets the length of the current tree.

Examples

use coll::persistent::RbTree;
let tree = RbTree::new().insert(4).insert(2).insert(3).insert(1);
assert_eq!(tree.len(), 4);

fn contains(&self, item: T) -> bool where T: PartialEq + PartialOrd

Checks the tree for the presence of a given T.

Examples

use coll::persistent::RbTree;
let tree = RbTree::new().insert(1).insert(2).insert(3);
assert!(tree.contains(1));
assert!(tree.contains(2));
assert!(tree.contains(3));
assert_eq!(tree.contains(4), false);

fn is_empty(&self) -> bool

Returns true if the collection is empty.

Examples

use coll::persistent::RbTree;
let tree: RbTree<i32> = RbTree::new();
assert!(tree.is_empty());

let tree = tree.insert(1);
assert!(tree.is_empty() == false);

fn iter(&self) -> Iter<T>

Returns an in-order iterator over the nodes in the tree.

The iterator uses O(log n) space for node traversal.

Examples

use coll::persistent::RbTree;
let tree = RbTree::new().insert(4).insert(2).insert(1).insert(3)
                        .insert(8).insert(6).insert(5).insert(7);
let mut iter = tree.iter();
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&4));
assert_eq!(iter.next(), Some(&5));
assert_eq!(iter.next(), Some(&6));
assert_eq!(iter.next(), Some(&7));
assert_eq!(iter.next(), Some(&8));
assert_eq!(iter.next(), None);

Trait Implementations

impl<T: Debug + PartialEq + PartialOrd> Debug for RbTree<T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: PartialEq + PartialEq + PartialOrd> PartialEq for RbTree<T>

fn eq(&self, __arg_0: &RbTree<T>) -> bool

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

fn ne(&self, __arg_0: &RbTree<T>) -> bool

This method tests for !=.

impl<T: Clone + PartialEq + PartialOrd> Clone for RbTree<T>

fn clone(&self) -> RbTree<T>

Returns a copy of the value.

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

Performs copy-assignment from source.