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.rec <int>; Creates a simple balanced input tree for the web driver. Uses recursion. the input number is rounded to the nearest power of 2

Program: gentree.pl.loop <int>; Creates 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

page and content copyright 2003 Zack Ramjan