com.ibm.etools.mft.builder.internal
Class BinaryTree

java.lang.Object
  |
  +--com.ibm.etools.mft.builder.internal.BinaryTree

public class BinaryTree
extends java.lang.Object

A binary tree stored in an integer array

Intended use is as an index structure for storing ITable Row indices. This data-structure supports collisions (duplicate keys), unlike the java.util Collections classes.

It is expected (especially in the case of the reference table) that there may be very many rows that have the same reference symbol. So scalable performance in the presence of duplicates is very important.

The tree is accessed using handles, which are integer values indicating the tree node in the array. The actual value of the handle returned can be used to index into the array, for the number of integers specified when allocating the tree node. The sizeof(int handle) method can be used to determine the amount of space allocated in a given tree node.

An example of a binary tree is depicted below.

The binary tree data structure is:

Implementer notes:


Constructor Summary
BinaryTree()
          Default constructor
 
Method Summary
 int allocTreeNode(int size)
          Allocate an empty, balanced tree node
 void clear()
           
 int getTreeNodeCount(int index)
           
 void insertTreeNode(int handle, com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
          Insert a node in the tree
 void removeTreeNode(int handle)
          Remove an element from the tree
 int[] searchTree(com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
          Search the tree for matches
 int sizeof(int handle)
          Return the amount of user space allocated in a tree node
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BinaryTree

public BinaryTree()
Default constructor

Method Detail

clear

public final void clear()

removeTreeNode

public final void removeTreeNode(int handle)
Remove an element from the tree

Parameters:
handle -

searchTree

public final int[] searchTree(com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
Search the tree for matches

First, search for the "lowest common parent" (LCP). In an in-order sorted tree, all the matching tree nodes will be children of this lowest common parent. Split the LCP subtree in 2 (the left and right subtrees of the LCP).

Second, count the number of matches for a search. Since the tree supports multiple nodes with the same value, any such duplicate nodes will be left or right children of the LCP. Further, there is a 'first' node on the left of the LCP such that all nodes in-order between it and the parent must also match, conversely, there is a 'last' node in the right of the LCP such that all nodes between the LCP and the last node are also matches.

Consider the left subtree. The tree being sorted in-order, no nodes will compare greater than the LCP. If any node TN compares equal to the search, all right branches must also compare equal; the first node must either be TN or in the left subtree of TN. If TN node compares less than the search, then TN and all its left children are less than the search and the first node, if it is a child of TN, must be in the right subtree. The converse is true for the right branch.

So the in-order property lets us count the number of matches by counting matching nodes and their right children (for the left subtree) or left children (for the right subtree) from the LCP.


insertTreeNode

public final void insertTreeNode(int handle,
                                 com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
Insert a node in the tree


sizeof

public final int sizeof(int handle)
Return the amount of user space allocated in a tree node

This may actually be greater than the amount of space requested, depending on the size of the memory block allocated.

Parameters:
handle -
Returns:
the amount of user space (not the full memory allocation)

allocTreeNode

public final int allocTreeNode(int size)
Allocate an empty, balanced tree node

Parameters:
size -
Returns:
handle of newly allocated node in the tree

getTreeNodeCount

public final int getTreeNodeCount(int index)