[−][src]Trait treers::SedgewickMap

pub trait SedgewickMap<K: Ord, V> {
    fn new() -> Self;

    fn size(&self) -> usize;

    fn get(&self, key: &K) -> Option<&V>;

    fn put(&mut self, key: K, value: V);

    fn height(&self) -> Option<usize>;

    fn min(&self) -> Option<&K>;

    fn max(&self) -> Option<&K>;

    fn is_empty(&self) -> bool { ... }

    fn contains(&self, key: &K) -> bool { ... }
}

Required methods

fn new() -> Self

fn size(&self) -> usize

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

fn put(&mut self, key: K, value: V)

fn height(&self) -> Option<usize>

fn min(&self) -> Option<&K>

fn max(&self) -> Option<&K>

Loading content...

Provided methods

fn is_empty(&self) -> bool

fn contains(&self, key: &K) -> bool

Checks if key exists in Tree

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;
use treers::rbtree::RedBlackTree;
use treers::btree::BalancedTree;

let mut bst: BST<char, u32> = BST::new();
let mut rbtree: RedBlackTree<char, u32> = RedBlackTree::new();
let mut btree: BalancedTree<char, u32> = BalancedTree::new();

bst.put('a', 2);
rbtree.put('a', 2);
btree.put('a', 2);

assert_eq!(bst.contains(&'a'), true);
assert_eq!(bst.contains(&'b'), false);

assert_eq!(rbtree.contains(&'a'), true);
assert_eq!(rbtree.contains(&'b'), false);

assert_eq!(btree.contains(&'a'), true);
assert_eq!(btree.contains(&'b'), false);
Loading content...

Implementors

impl<K: Ord + Clone, V: Clone> SedgewickMap<K, V> for RedBlackTree<K, V>[src]

fn new() -> Self[src]

Inits a new instance of Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);

fn size(&self) -> usize[src]

Returns a size of elements in Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.size(), 4_usize);

fn get(&self, key: &K) -> Option<&V>[src]

Returns a reference to optional reference to value.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
assert_eq!(rbtree.get(&'a'), Some(&1));
assert_eq!(rbtree[&'a'], 1);
assert_eq!(rbtree.get(&'b'), None);

fn put(&mut self, key: K, value: V)[src]

Insert a key-value pair into the Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);

rbtree.put('a', 1_i32);
assert_eq!(rbtree.is_empty(), false);
assert_eq!(rbtree.get(&'a'), Some(&1_i32));
assert_eq!(rbtree[&'a'], 1_i32);

fn height(&self) -> Option<usize>[src]

Get height of Red-Black Tree.

Red-Black Tree is a balanced tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
//   b         <-- height: 0
//  / \
// a   d       <-- height: 1
//    / \
//   c         <-- height: 2
// Note -The Height of red-black tree with single node is taken as zero.
assert_eq!(rbtree.get(&'a'), Some(&1_i32));
assert_eq!(rbtree.height(), Some(2_usize));
assert_eq!(rbtree.size(), 4_usize);

fn is_empty(&self) -> bool[src]

Checks if Red-Black Tree node is empty.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);
rbtree.put('a', 2);
assert_eq!(rbtree.is_empty(), false);

fn min(&self) -> Option<&K>[src]

Returns a optional reference to minimal key

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.min(), None);
rbtree.put('c', 1);
rbtree.put('a', 2);
rbtree.put('b', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.min(), Some(&'a'));

fn max(&self) -> Option<&K>[src]

Returns a optional reference to maximum key

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.max(), None);
rbtree.put('c', 1);
rbtree.put('a', 2);
rbtree.put('b', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.max(), Some(&'d'));

impl<K: Ord + Clone, V: Clone> SedgewickMap<K, V> for BalancedTree<K, V>[src]

fn new() -> Self[src]

Inits a new instance of Balanced Tree.

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let btree: BalancedTree<char, i32> = BalancedTree::new();
assert_eq!(btree.is_empty(), true);

fn size(&self) -> usize[src]

Returns a size of elements in BST.

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
btree.put('a', 1);
btree.put('b', 2);
btree.put('c', 3);
btree.put('d', 4);
assert_eq!(btree.size(), 4_usize);

fn get(&self, key: &K) -> Option<&V>[src]

Returns a reference to optional reference to value.

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
btree.put('a', 1);
assert_eq!(btree.get(&'a'), Some(&1));
assert_eq!(btree.get(&'b'), None);
assert_eq!(btree[&'a'], 1);

fn put(&mut self, key: K, value: V)[src]

Insert a key-value pair into the BTree.

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
assert_eq!(btree.is_empty(), true);

btree.put('a', 1_i32);
assert_eq!(btree.is_empty(), false);
assert_eq!(btree.get(&'a'), Some(&1_i32));
assert_eq!(btree[&'a'], 1_i32);

fn height(&self) -> Option<usize>[src]

Get height of BTree.

BTree is balanced tree. TODO: add more text

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
assert_eq!(btree.height(), Some(0_usize));
btree.put('a', 1);
btree.put('b', 2);
btree.put('c', 3);
btree.put('d', 4);
btree.put('e', 5);
btree.put('f', 6);
btree.put('g', 7);
//    |a|c|e|         <-- height: 0
//    /  |  \
// |b|  |d|  |f|g|    <-- height: 1
//
// Note -The Height of balanced tree with single node is taken as zero,
//       but empty BTree is 0, not None.
assert_eq!(btree.height(), Some(1_usize));
assert_eq!(btree.get(&'g'), Some(&7_i32));
assert_eq!(btree[&'g'], 7_i32);
assert_eq!(btree.size(), 7_usize);

fn min(&self) -> Option<&K>[src]

Returns a optional reference to minimal key

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
assert_eq!(btree.min(), None);
btree.put('c', 1);
btree.put('a', 2);
btree.put('b', 3);
btree.put('d', 4);
assert_eq!(btree.min(), Some(&'a'));

fn max(&self) -> Option<&K>[src]

Returns a optional reference to maximum key

Examples

Basic usage:

use treers::btree::BalancedTree;
use treers::SedgewickMap;

let mut btree: BalancedTree<char, i32> = BalancedTree::new();
assert_eq!(btree.max(), None);
btree.put('c', 1);
btree.put('a', 2);
btree.put('b', 3);
btree.put('d', 4);
assert_eq!(btree.max(), Some(&'d'));

impl<K: Ord, V> SedgewickMap<K, V> for BST<K, V>[src]

fn new() -> Self[src]

Inits a new instance of Binary Search Tree.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let bst: BST<char, i32> = BST::new();
assert_eq!(bst.is_empty(), true);

fn size(&self) -> usize[src]

Returns a size of elements in BST.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
bst.put('a', 1);
bst.put('b', 2);
bst.put('c', 3);
bst.put('d', 4);
assert_eq!(bst.size(), 4_usize);

fn get(&self, key: &K) -> Option<&V>[src]

Returns a reference to optional reference to value.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
bst.put('a', 1);
assert_eq!(bst.get(&'a'), Some(&1));
assert_eq!(bst.get(&'b'), None);
assert_eq!(bst[&'a'], 1);

fn put(&mut self, key: K, value: V)[src]

Insert a key-value pair into the BST.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
assert_eq!(bst.is_empty(), true);

bst.put('a', 1_i32);
assert_eq!(bst.is_empty(), false);
assert_eq!(bst.get(&'a'), Some(&1_i32));
assert_eq!(bst[&'a'], 1_i32);

fn height(&self) -> Option<usize>[src]

Get height of BST.

BST is not balanced tree, so in worst-case scenario, height will be same as size, like a Linked-List.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
bst.put('a', 1);
bst.put('b', 2);
bst.put('c', 3);
bst.put('d', 4);
//  a         <-- height: 0
// / \
//    b       <-- height: 1
//   / \
//      c     <-- height: 2
//     / \
//        d   <-- height: 3
// Note -The Height of binary tree with single node is taken as zero.
assert_eq!(bst.get(&'a'), Some(&1_i32));
assert_eq!(bst.height(), Some(3_usize));
assert_eq!(bst.size(), 4_usize);

fn is_empty(&self) -> bool[src]

Checks if BST node is empty.

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
assert_eq!(bst.is_empty(), true);
bst.put('a', 2);
assert_eq!(bst.is_empty(), false);

fn min(&self) -> Option<&K>[src]

Returns a optional reference to minimal key

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
assert_eq!(bst.min(), None);
bst.put('c', 1);
bst.put('a', 2);
bst.put('b', 3);
bst.put('d', 4);
assert_eq!(bst.min(), Some(&'a'));

fn max(&self) -> Option<&K>[src]

Returns a optional reference to maximum key

Examples

Basic usage:

use treers::bst::BST;
use treers::SedgewickMap;

let mut bst: BST<char, i32> = BST::new();
assert_eq!(bst.max(), None);
bst.put('c', 1);
bst.put('a', 2);
bst.put('b', 3);
bst.put('d', 4);
assert_eq!(bst.max(), Some(&'d'));
Loading content...