COSTA: COSt and Termination Analyzer for Java Bytecode

package memory.jolden.bisort;

/**
* A class that represents a value to be sorted by the <tt>BiSort</tt>
* algorithm.  We represents a values as a node in a binary tree.
**/
class Value
{
private int value;
private Value left;
private Value right;

static final boolean FORWARD = false;
static final boolean BACKWARD = true;

// These are used by the Olden benchmark random no. generator
private static final int CONST_m1 = 10000;
private static final int CONST_b = 31415821;
static final int RANGE = 100;

/**
* Constructor for a node representing a value in the bitonic sort tree.
* @param v the integer value which is the sort key
**/
Value(int v)
{
value = v;
left = right = null;
}

/**
* Create a random tree of value to be sorted using the bitonic sorting algorithm.
*
* @param size the number of values to create.
* @param seed a random number generator seed value
* @return the root of the (sub) tree.
**/
static Value createTree(int size, int seed)
{
if (size > 1) {
seed = random(seed);
int next_val = seed % RANGE;

Value retval = new Value(next_val);
retval.left = createTree(size/2, seed);
retval.right = createTree(size/2, skiprand(seed, size+1));
return retval;
} else {
return null;
}
}

/**
* Perform a bitonic sort based upon the Bilardi and Nicolau algorithm.
*
* @param spr_val the "spare" value in the algorithm.
* @param direction the direction of the sort (forward or backward)
* @return the new "spare" value.
**/
int bisort(int spr_val, boolean direction)
{
if (left == null) {
if ((value > spr_val) ^ direction) {
int tmpval = spr_val;
spr_val = value;
value = tmpval;
}
} else {
int val = value;
value = left.bisort(val, direction);
boolean ndir = !direction;
spr_val = right.bisort(spr_val, ndir);
spr_val = bimerge(spr_val, direction);
}
return spr_val;
}

/**
* Perform the merge part of the bitonic sort.  The merge part does
* the actualy sorting.
* @param spr_val the "spare" value in the algorithm.
* @param direction the direction of the sort (forward or backward)
* @return the new "spare" value
**/
int bimerge(int spr_val, boolean direction)
{
int   rv = value;
Value pl = left;
Value pr = right;

boolean rightexchange = (rv > spr_val) ^ direction;
if (rightexchange) {
value = spr_val;
spr_val = rv;
}

while (pl != null) {
int   lv  = pl.value;
Value pll = pl.left;
Value plr = pl.right;
rv        = pr.value;
Value prl = pr.left;
Value prr = pr.right;

boolean elementexchange = (lv > rv) ^ direction;
if (rightexchange) {
if (elementexchange) {
pl.swapValRight(pr);
pl = pll;
pr = prl;
} else {
pl = plr;
pr = prr;
}
} else {
if (elementexchange) {
pl.swapValLeft(pr);
pl = plr;
pr = prr;
} else {
pl = pll;
pr = prl;
}
}
}

if (left != null) {
value = left.bimerge(value, direction);
spr_val = right.bimerge(spr_val, direction);
}
return spr_val;
}

/**
* Swap the values and the right subtrees.
* @param n the other subtree involved in the swap.
**/
void swapValRight(Value n)
{
int   tmpv = n.value;
Value tmpr = n.right;

n.value = value;
n.right = right;

value = tmpv;
right = tmpr;
}

/**
* Swap the values and the left subtrees.
* @param n the other subtree involved in the swap.
**/
void swapValLeft(Value n)
{
int   tmpv = n.value;
Value tmpl = n.left;

n.value = value;
n.left  = left;

value = tmpv;
left  = tmpl;
}

/**
* Print out the nodes in the binary tree in infix order.
**/
void inOrder()
{
if (left != null)
left.inOrder();
System.out.println(value + " " + hashCode());
if (right != null)
right.inOrder();
}

/**
* A random generator.  The original Olden benchmark uses its
* own random generator.  We use the same one in the Java version.
* @return the next random number in the sequence.
**/
private static int mult(int p, int q)
{
int p1 = p/CONST_m1;
int p0 = p%CONST_m1;
int q1 = q/CONST_m1;
int q0 = q%CONST_m1;
return (((p0*q1+p1*q0) % CONST_m1) * CONST_m1+p0*q0);
}

/**
* A routine to skip the next <i>n</i> random numbers.
* @param seed the current random no. seed
* @param n the number of numbers to skip
**/
private static int skiprand(int seed, int n)
{
for (; n > 0; n--) seed = random(seed);
return seed;
}

/**
* Return a random number based upon the seed value.
* @param seed the random number seed value
* @return a random number based upon the seed value.
**/
static int random(int seed)
{
int tmp = mult(seed, CONST_b) + 1;
return tmp;
}
}