[−][src]Trait outils::tree::bst::OrderedTree

pub trait OrderedTree<Ix = DefaultIndexType> where
    Ix: IndexType, {
    fn sub_predecessor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn sub_successor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn predecessor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn successor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn first(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn last(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn is_smaller(&self, node_u: NodeIndex<Ix>, node_v: NodeIndex<Ix>) -> bool;
}

This trait defines operations for navigating the binary tree with respect to its in-order.

Required methods

fn sub_predecessor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the biggest node of the left subtree of the tree node indexed by node.

fn sub_successor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the smallest node of the right subtree of the tree node indexed by node.

fn predecessor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

fn successor(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

fn first(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the smallest node of the left subtree of the tree node indexed by node.

fn last(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the biggest node of the right subtree of the tree node indexed by node.

fn is_smaller(&self, node_u: NodeIndex<Ix>, node_v: NodeIndex<Ix>) -> bool

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, false is returned.

Loading content...

Implementors

impl<K, V> OrderedTree<usize> for AaTree<K, V> where
    K: KeyType,
    V: ValueType, [src]

fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;            // The resulting tree is shown below:
                                   //
let mut aatree = AaTree::new(10);  //       -- (3) --
                                   //      /         \
for i in 0..7 {                    //    (1)         (5)
    aatree.insert(i, i);           //   /   \       /   \
}                                  // (0)   (2)    (4)   (6)

let n2 = aatree.index(2).expect("Key '2' should be present");
let n3 = aatree.index(3).expect("Key '3' should be present");
let n4 = aatree.index(4).expect("Key '4' should be present");

assert_eq!(aatree.sub_predecessor(n3), Some(n2)); // 2 is biggest key in left subtree of 3.
assert_eq!(aatree.sub_predecessor(n4), None);     // 4 is a leaf and thus has no subtrees.'

fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the right subtree of the tree node indexed by node.

Usage is analogous to sub_predecessor

fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

use outils::prelude::*;            // The resulting tree is shown below:
                                   //
let mut aatree = AaTree::new(10);  //       -- (3) --
                                   //      /         \
for i in 0..7 {                    //    (1)         (5)
    aatree.insert(i, i);           //   /   \       /   \
}                                  // (0)   (2)    (4)   (6)

let n0 = aatree.index(0).expect("Key '0' should be present");
let n3 = aatree.index(3).expect("Key '3' should be present");
let n4 = aatree.index(4).expect("Key '4' should be present");

assert_eq!(aatree.predecessor(n4), Some(n3)); // 3 is the biggest key of the whole tree
                                              // smaller than 4.
assert_eq!(aatree.predecessor(n0), None);     // 0 is globally the smallest key of the
                                              // whole tree and thus has no predecessor.

fn successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

Usage is analogous to predecessor

fn first(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;            // The resulting tree is shown below:
                                   //
let mut aatree = AaTree::new(10);  //       -- (3) --
                                   //      /         \
for i in 0..7 {                    //    (1)         (5)
    aatree.insert(i, i);           //   /   \       /   \
}                                  // (0)   (2)    (4)   (6)

let n0 = aatree.index(0).expect("Key '0' should be present");
let n1 = aatree.index(1).expect("Key '1' should be present");
let n3 = aatree.index(3).expect("Key '3' should be present");

assert_eq!(aatree.first(n3), Some(n0));  // 0 is the smallest key of the left subtree of 3
assert_eq!(aatree.first(n1), Some(n0));  // 0 is the smallest key of the left subtree of 1

fn last(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the right subtree of the tree node indexed by node.

Usage is analogous to first

fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool[src]

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, false is returned.

Panics if the path to the root from either of the tree nodes to be compared contains more than 64 nodes. This is because the directions (i.e. left or right) on the path are encoded in a bitmap of type u64. In practice it is next to impossible for this method to panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.

use outils::prelude::*;            // The resulting tree is shown below:
                                   //
let mut aatree = AaTree::new(10);  //       -- (3) --
                                   //      /         \
for i in 0..7 {                    //    (1)         (5)
    aatree.insert(i, i);           //   /   \       /   \
}                                  // (0)   (2)    (4)   (6)

let n0 = aatree.index(0).expect("Key '0' should be present");
let n1 = aatree.index(1).expect("Key '1' should be present");
let n3 = aatree.index(3).expect("Key '3' should be present");

assert!(aatree.is_smaller(n0, n3));
assert!(!aatree.is_smaller(n3, n1));

impl<K, V, W> OrderedTree<usize> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, [src]

fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n2 = waatree.index(2).expect("Key '2' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");
let n4 = waatree.index(4).expect("Key '4' should be present");

assert_eq!(waatree.sub_predecessor(n3), Some(n2)); // 2 is biggest key in left subtree of 3.
assert_eq!(waatree.sub_predecessor(n4), None);     // 4 is a leaf and thus has no subtrees.'

fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the right subtree of the tree node indexed by node.

Usage is analogous to sub_predecessor

fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");
let n4 = waatree.index(4).expect("Key '4' should be present");

assert_eq!(waatree.predecessor(n4), Some(n3)); // 3 is the biggest key of the whole tree
                                              // smaller than 4.
assert_eq!(waatree.predecessor(n0), None);     // 0 is globally the smallest key of the
                                              // whole tree and thus has no predecessor.

fn successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

Usage is analogous to predecessor

fn first(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n1 = waatree.index(1).expect("Key '1' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");

assert_eq!(waatree.first(n3), Some(n0));  // 0 is the smallest key of the left subtree of 3
assert_eq!(waatree.first(n1), Some(n0));  // 0 is the smallest key of the left subtree of 1

fn last(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the right subtree of the tree node indexed by node.

Usage is analogous to first

fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool[src]

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, false is returned.

Panics if the path to the root from either of the tree nodes to be compared contains more than 64 nodes. This is because the directions (i.e. left or right) on the path are encoded in a bitmap of type u64. In practice it is next to impossible for this method to panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n1 = waatree.index(1).expect("Key '1' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");

assert!(waatree.is_smaller(n0, n3));
assert!(!waatree.is_smaller(n3, n1));

impl<V> OrderedTree<usize> for AaForest<V> where
    V: ValueType, [src]

fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                // The resulting tree is shown below:
                                       //
let mut aaforest = AaForest::new(10);  //       -- (3) --
                                       //      /         \
let mut indices = Vec::new();          //    (1)         (5)
indices.push(aaforest.insert(0));      //   /   \       /   \
                                       // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

// 2 is biggest key in left subtree of 3.
assert_eq!(aaforest.sub_predecessor(indices[3]), Some(indices[2]));
// 4 is a leaf and thus has no subtrees.
assert_eq!(aaforest.sub_predecessor(indices[4]), None);

fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the right subtree of the tree node indexed by node.

Usage is analogous to sub_predecessor

fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

use outils::prelude::*;                // The resulting tree is shown below:
                                       //
let mut aaforest = AaForest::new(10);  //       -- (3) --
                                       //      /         \
let mut indices = Vec::new();          //    (1)         (5)
indices.push(aaforest.insert(0));      //   /   \       /   \
                                       // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

// 3 is the biggest key of the whole tree smaller than 4.
assert_eq!(aaforest.predecessor(indices[4]), Some(indices[3]));
// 0 is globally the smallest key of the whole tree and thus has no predecessor.
assert_eq!(aaforest.predecessor(indices[0]), None);

fn successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

Usage is analogous to predecessor

fn first(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                // The resulting tree is shown below:
                                       //
let mut aaforest = AaForest::new(10);  //       -- (3) --
                                       //      /         \
let mut indices = Vec::new();          //    (1)         (5)
indices.push(aaforest.insert(0));      //   /   \       /   \
                                       // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

// 0 is the smallest key of the left subtree of 3
assert_eq!(aaforest.first(indices[3]), Some(indices[0]));
// 0 is the smallest key of the left subtree of 1
assert_eq!(aaforest.first(indices[1]), Some(indices[0]));

fn last(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the right subtree of the tree node indexed by node.

Usage is analogous to first

fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool[src]

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, or if the nodes do not belong to the same forest tree, false is returned.

Panics if the path to the root from either of the tree nodes to be compared contains more than 64 nodes. This is because the directions (i.e. left or right) on the path are encoded in a bitmap of type u64. In practice it is next to impossible for this method to panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.

use outils::prelude::*;                // The resulting tree is shown below:
                                       //
let mut aaforest = AaForest::new(10);  //       -- (3) --
                                       //      /         \
let mut indices = Vec::new();          //    (1)         (5)
indices.push(aaforest.insert(0));      //   /   \       /   \
                                       // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

assert!(aaforest.is_smaller(indices[0], indices[3]));
assert!(!aaforest.is_smaller(indices[3], indices[1]));

impl<V, W> OrderedTree<usize> for WeightedAaForest<V, W> where
    V: ValueType,
    W: WeightType, [src]

fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                         // The resulting tree is shown below:
                                                //
let mut waaforest = WeightedAaForest::new(10);  //       -- (3) --
                                                //      /         \
let mut indices = Vec::new();                   //    (1)         (5)
indices.push(waaforest.insert_weighted(0, 1));  //   /   \       /   \
                                                // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(waaforest.insert_weighted(i, 1));
    waaforest.append(indices[i-1], indices[i]);
}

// 2 is biggest key in left subtree of 3.
assert_eq!(waaforest.sub_predecessor(indices[3]), Some(indices[2]));
// 4 is a leaf and thus has no subtrees.
assert_eq!(waaforest.sub_predecessor(indices[4]), None);

fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the right subtree of the tree node indexed by node.

Usage is analogous to sub_predecessor

fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

use outils::prelude::*;                         // The resulting tree is shown below:
                                                //
let mut waaforest = WeightedAaForest::new(10);  //       -- (3) --
                                                //      /         \
let mut indices = Vec::new();                   //    (1)         (5)
indices.push(waaforest.insert_weighted(0, 1));  //   /   \       /   \
                                                // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(waaforest.insert_weighted(i, 1));
    waaforest.append(indices[i-1], indices[i]);
}

// 3 is the biggest key of the whole tree smaller than 4.
assert_eq!(waaforest.predecessor(indices[4]), Some(indices[3]));
// 0 is globally the smallest key of the whole tree and thus has no predecessor.
assert_eq!(waaforest.predecessor(indices[0]), None);

fn successor(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

Usage is analogous to predecessor

fn first(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the smallest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                         // The resulting tree is shown below:
                                                //
let mut waaforest = WeightedAaForest::new(10);  //       -- (3) --
                                                //      /         \
let mut indices = Vec::new();                   //    (1)         (5)
indices.push(waaforest.insert_weighted(0, 1));  //   /   \       /   \
                                                // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(waaforest.insert_weighted(i, 1));
    waaforest.append(indices[i-1], indices[i]);
}

// 0 is the smallest key of the left subtree of 3
assert_eq!(waaforest.first(indices[3]), Some(indices[0]));
// 0 is the smallest key of the left subtree of 1
assert_eq!(waaforest.first(indices[1]), Some(indices[0]));

fn last(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the biggest node of the right subtree of the tree node indexed by node.

Usage is analogous to first

fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool[src]

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, or if the nodes do not belong to the same forest tree, false is returned.

Panics if the path to the root from either of the tree nodes to be compared contains more than 64 nodes. This is because the directions (i.e. left or right) on the path are encoded in a bitmap of type u64. In practice it is next to impossible for this method to panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.

use outils::prelude::*;                         // The resulting tree is shown below:
                                                //
let mut waaforest = WeightedAaForest::new(10);  //       -- (3) --
                                                //      /         \
let mut indices = Vec::new();                   //    (1)         (5)
indices.push(waaforest.insert_weighted(0, 1));  //   /   \       /   \
                                                // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(waaforest.insert(i));
    waaforest.append(indices[i-1], indices[i]);
}

assert!(waaforest.is_smaller(indices[0], indices[3]));
assert!(!waaforest.is_smaller(indices[3], indices[1]));
Loading content...