/**
  John P. Cataldo &lt;cataldoj@ccs.neu.edu&gt;<br>
  Daniel Rinehart &lt;danielr@ccs.neu.edu&gt;<br>
  Aris Yannopoulos &lt;aris@ccs.neu.edu&gt;<br>
  COM1390 Programming Assignment #1<P>

  $Id: Median.java,v 1.4 1999/02/16 07:10:02 danielr Exp $<P>

  Find the median by various methods.

  */
public class Median {


  /** 

    This will select the median based on three random numbers picked
    from the range p to r inclusive.

    @param S the array to use for value comparison
    @param p the begin point of the range to consider
    @param r the end point of the range to consider

    @return the index to partition around
    */
  public static int medianOf3Random( int S[], int p, int r ) {
    // how big is the range 
    int size = r - p + 1;
    
    // this will loop forever on less than 3 items
    if ( size < 3 ) {
      return( p );
    }

    // get three random elements between p and r inclusive
    int a = p + ( int )( Math.random() * ( double )size );

    int b = p + ( int )( Math.random() * ( double )size );
    while( b == a ) {
      b = p + ( int )( Math.random() * ( double )size );
    }

    int c = p + ( int )( Math.random() * ( double )size );
    while( c == a || c == b ) {
      c = p + ( int )( Math.random() * ( double )size );
    }
    
    return( medianOf3( S, a, b, c ) );
  }

  /** 

    This will select nine random numbers between the range p to r inclusive. It then finds the median of each group of three, then finding the median of those three medians.

    @param S the array to use for value comparison
    @param p the begin point of the range to consider
    @param r the end point of the range to consider

    @return the index to partition around
    */
  public static int medianOf9Random( int S[], int p, int r ) {

    // how big is the range
    int size = r - p + 1;

    // this would loop forever on less than 9 items
    if ( size < 9 ) {
      return( medianOf3Random( S, p, r ) );
    }

    // for checking to see if we have picked this index before
    boolean range[] = new boolean[ size ];
    
    // mark each number as not used
    for( int i = 0; i < size; i++ ) {
      range[ i ] = false;
    }
    
    // how many numbers are we finding
    int indexes[] = new int[ 9 ];

    // find the 9 indexes
    for( int i = 0; i < 9; i++ ) {
      int temp = p + ( int )( Math.random() * ( double )size );

      while( range[ temp - p ] ) {
	temp = p + ( int )( Math.random() * ( double )size );
      }

      indexes[ i ] = temp;
      range[ temp - p ] = true;
    }
    
    // get the median of each index
    int a = medianOf3( S, indexes[ 0 ], indexes[ 1 ], indexes[ 2 ] );
    int b = medianOf3( S, indexes[ 3 ], indexes[ 4 ], indexes[ 5 ] );
    int c = medianOf3( S, indexes[ 6 ], indexes[ 7 ], indexes[ 8 ] );

    // find the median of those 3 indexes
    return( medianOf3( S, a, b, c ) );
  }
  
  /** 

    Find the median of three numbers.

    @param S the array to use for value comparison
    @param indexA the first index to consider
    @param indexB the second index to consider
    @param indexC the third index to consider

    @return the index to partition around
    */
  public static int medianOf3( int S[], int indexA, int indexB, int indexC ) {
    
    if ( S[ indexA ] <= S[ indexB ] ) {
      if ( S[ indexB ] <= S[ indexC ] ) {
	FindQuantiles.incComp( 2 );
	return( indexB );
      }
      if ( S[ indexA ] <= S[ indexC ] ) {
	FindQuantiles.incComp( 3 );
	return( indexC );
      } else {
	FindQuantiles.incComp( 3 );
	return( indexA );
      }
    }
    if ( S[ indexA ] <= S[ indexC ] ) {
      FindQuantiles.incComp( 2 );
      return( indexA );
    }
    if ( S[ indexB ] <= S[ indexC ] ) {
      FindQuantiles.incComp( 3 );
      return( indexC );
    } else {
      FindQuantiles.incComp( 3 );
      return( indexB );
    }
  }
}