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;
  }
}