Bender and Farach-Colton's Method:
Perl Routines Created:

stgGen( @array )Creates an ST Matrix from an array of Euler Tour Heights (or any valid list of numbers). Each Row corresponds to a distance of 2^i, each column is the minimum element in that distance. The last line of the matrix is the actual value at the given index.

Input: eulerTourHeights array, a corresponding index array (optional).

Returns: STMatrix (array of arrays)

logn( $number, $number )takes the log of a number using specified bases.

Input: a number, a base

Returns: log[b](N)

round( $number )Rounds a number to the nearest integer.

Input: a number

Returns: an integer

partitionBlocks( @array )Partitions the EulerTour Heights into chunks of size logn/2. It then find the minimum of each block, and the position of that minimum. This may add values to the incoming array. Next, the blocks are normalized and each unique block identifier is tied to a specific array for intra-block lookups. In array B, the position is the global index.

Input: eulerTourHeights array.

Returns: an array of arrays

Output[0] = array, A, where A[i] is the minima element of a block

Output[1] = array B, where B[i] is the position of the element

Output[2] = array C, the block-based normalized eulertour.

Output[3] = array D, where D[i] is block i's matrix type.

Output[4] = matrix E, D[i]'s matrix-type storage, at i-1

Example: block i's matrix is located at E[D[i]-1]

Output[5] = scalar, the partition size (AKA block size).

eulerTour( @array of arrays )performs a eulorTour on a given tree, and calculates the heights of the nodes with respect to the root.

Input: a Tree stored in a 3 x N matrix, where each row has the form: { $NODE_NAME $LEFT_CHILD $RIGHT_CHILD } passed by typeGlob

Returns: an array of arrays

Ouput[0] = array, which is a list representing the EulerTour of the nodes

Output[1] = array, which corresponds to the aboves distance from the root.

Output[2] = hash, key is a unique node name, value is its 1st occurrence in the Euler Tour.

LCAquery(array,array,array,number,number)calculate LCA queries by RMQ. All incoming data (except numbers) must be passed by typeGlob for calculations.

Input: eulerMatrix, STmatrix, partitionBlocks Matrix, NODE1, NODE2

Output: {LCA_NODE3, time taken}

Program: gentree.pl.recCreates a simple balanced input tree for the web driver. Uses recursion. the input number is rounded to the nearest power of 2<int>;

Program: gentree.pl.loopCreates a simple balanced input tree for the web driver. no recursion, so supports larger trees. the input number is rounded to the nearest power of 2<int>;

*page and content copyright 2003
Zack
Ramjan *