FlexOr.container
Class OrderedBinaryTree

java.lang.Object
  FlexOr.container.BinaryTree
      FlexOr.container.OrderedBinaryTree

All Implemented Interfaces:

Container, java.lang.Cloneable

public class OrderedBinaryTree
extends BinaryTree

Version:

1.0 1999 Jan 15

Author:

Gunnar Gotshalks

Constructor Summary

OrderedBinaryTree(BinaryPredicate orderComparison, BinaryPredicate equalComparison)
Define an empty binary tree.

Method Summary

void	add(java.lang.Object obj) Adds obj at the leaf level such that comparison.execute(obj, node.datum) = true means go down the left subtree else go down the right subtree.
java.lang.Object	clone() Return a copy of the container that points to the same objects as in the original container.
boolean	contains(java.lang.Object obj) Determines whether an element is in the tree.
boolean	remove(java.lang.Object obj) Remove the specified element.

Methods inherited from class FlexOr.container.BinaryTree

elements, equals, inOrderLRtraversal, inOrderRLtraversal, isEmpty, isFull, levelOrderLRtraversal, levelOrderRLtraversal, postOrderLRtraversal, postOrderRLtraversal, preOrderLRtraversal, preOrderRLtraversal, remove, removeAll, size, toString

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

OrderedBinaryTree

public OrderedBinaryTree(BinaryPredicate orderComparison,
                         BinaryPredicate equalComparison)

Define an empty binary tree.

Parameters:

orderComparison - defines how nodes are compared when deciding which branch to take.

equalComparison - defines how nodes are checked for equality.

Method Detail

add

public void add(java.lang.Object obj)

Adds obj at the leaf level such that
comparison.execute(obj, node.datum) = true
means go down the left subtree else go down the right subtree. An inorder traversal of the tree will give the elements from low to high or high to low, depending upon whether the comparison is lessThan or greaterThan. If obj is already in the tree based upon equalTo (which could be partiol equality) then datum is replaced with obj.

Requires: True
Ensures: contains(obj) = true
            old contains(obj) = false => size = old size + 1
            old contains(obj) = true => size = old size

Specified by:

add in interface Container

Specified by:

add in class BinaryTree

remove

public boolean remove(java.lang.Object obj)

Remove the specified element.

Requires: size >= 0
Ensures: 
    old binaryTree.contains(obj) =>
        binaryTree = old binaryTree / obj and result = true 
not old binaryTree.contains(obj) =>
        binaryTree = old binaryTree and result = false

Specified by:

remove in class BinaryTree

Throws:

ContainerEmptyException - when removing from an empty container.

contains

public boolean contains(java.lang.Object obj)

Determines whether an element is in the tree.

Requires: True
Ensures: contains(obj) => result = true
            not contains(obj) => result = false

Specified by:

contains in interface Container

Overrides:

contains in class BinaryTree

clone

public java.lang.Object clone()

Return a copy of the container that points to the same objects as in the original container. Part way between a shallow and deep copy. This is equivalent to how a Vector is cloned.

Requires: True
Ensures: result = copy of BinaryTree

Specified by:

clone in interface Container

Specified by:

clone in class BinaryTree