// This is a utility class for FindRank
class intPair {
  public int i, v;
  
  public intPair( int i, int v ){
    this.i = i;
    this.v = v;
  }

}

/**
  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: FindRank.java,v 1.6 1999/02/16 21:37:38 danielr Exp $<P>

  Determine if a biased pick will work and if so find the correct index
  to partition around.

  */
public class FindRank extends Object {

  //-- METHODS --

  /**

    Based on where the single rank we are looking for in the range p
    to r it might make sense to bias the partition towards one end.

    @param S the array of numbers to use for value comparisons
    @param p the begin point of the range to consider
    @param r the end point of the range to consider
    @param K the array equal to length S marking the ranks to find
    
    @return the index who's value we should partition around; -1 if biasing won't work.

    */
  public static int biasedPartition( int[] S, int p, int r, int[] ks ){
    
    int n = r - p + 1;
    int rank = p;
    while ( ks[ rank ] != 1 )
      rank++;

    /* THIS GENERALLY ONLY ELIMINATES 1/7 MORE THAN MEDIAN;
       THIS COSTS 11 COMPARISON (WORST CASE);
       WE'LL SKIP ALL OF THIS IF N >= 77;
       THIS IS ACTUALLY PROBABLY BETTER THAN THAT 
       ( SINCE 1/7 OF THE TIME IT ELIMINATES 2/7, AND SOMETIMES
       TAKES LESS THAN 11 COMPARISONS )

       BUT WE'LL USE 77 AS THE CUT OFF POINT FOR NOW.
       */

    if ( n <= 77 )
      return -1 ;


    pl( "n = " + n );
    pl( "rank = " + rank );

    //-- FIGURE OUT WHICH 1/14 WE ARE IN

    int dist = Math.abs( rank - p );

    double chunksize = n / 14.0;
    int chunk = 1;
    pl( "dist = " + dist );
    pl( "chunksize = " + chunksize );

    while ( ( chunk * chunksize ) < dist )
      chunk++;
    
    if ( chunk > 14 ) chunk = 14; 
    //just in case of weird things with
    //doubles and actually being the LAST rank


    //INVARIANT: chunk should now be between 1..14

    pl( "chunk = " + chunk );

    //-- GET SEVEN RANDOM INDEXES


    // the size of the section
    int size = ( r - p ) + 1;

    // 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 seven[] = new int[ 7 ];

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

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

      seven[ i ] = temp;
      range[ temp - p ] = true;
    }

    //-- CHOOSE WHICH OF THE SEVEN RANDOM ELEMENTS TO PARTITION AROUND --

    int whichseven = 0;
    switch ( chunk ){
    case 1: {
      whichseven = 2;
      break;}
    case 2:
    case 3:{
      whichseven = 3;
      break;}
    case 12:
    case 13:{
      whichseven = 5;
      break;}
    case 14:{
      whichseven = 6;
      break;}
    default:
      whichseven = -1; //MARKER FOR ``BAD'' BREAK -- NO BIAS USED
    }

    int returnIndex  = -1;//MARKER FOR ``BAD'' BREAK -- NO BIAS USED

    //we have a "good" break -- bias it!
    if ( whichseven > 0 ) {
      
      //--MAKE INTPAIRS --
      
      intPair[] sevenpairs = new intPair[ seven.length ];
      intPair t = null;
      for ( int i = 0; i < seven.length; i++ ){
	t = new intPair( seven[ i ]  , S[ seven[i] ] );
	sevenpairs[ i ] = t;
      }

      returnIndex = selectRank( sevenpairs, whichseven );

    }//if whichseven > 0
      
    return returnIndex;
  }

  /**
    For debugging output.
    */
  private static void pl( String args ){
    // System.out.println( args );
  }

  //ARIS'S CODE:

  /**
    
    Given 7 numbers pick a certain rank using very few compares.
    
    @param pairs the numbers to compare
    @param neededRank the rank we are trying to find

    @return the index in the original array for the specified rank

    */
  private static int selectRank( intPair[] pairs, int neededRank ){
    intPair ip=null; //used in 3,5

    switch(neededRank){
    case 6: { 
      HiBuildHeap(pairs);

      FindQuantiles.incComp( 1 );
      if( pairs[1].v > pairs[2].v ){
	return pairs[1].i;
      } else {
	return pairs[2].i;
      }
      //      break;
    }
    case 5: { 
      HiBuildHeap(pairs);

      //      pl( ip2s( pairs ) );
      
      //GET THIRD LARGEST IN HEAP
      int next = 0;
      boolean last = false;

      FindQuantiles.incComp( 1 );
      last = ( pairs[1].v > pairs[2].v ) ;
      ip = ( last ) ? pairs[2] : pairs[1];
      next = ( last ) ? 3 : 5; //children of the OTHER node

      //children of above
      FindQuantiles.incComp( 1 );
      FindQuantiles.incComp( 1 );
      ip = ( ip.v > pairs[ next ].v ) ? ip : pairs[ next ];
      ip = ( ip.v > pairs[ next + 1 ].v ) ? ip : pairs[ next + 1];

      return ip.i;
      //      break;
    }
    case 3: {
      LoBuildHeap(pairs);
      //      pl( "Inverted: ");
      //      pl( ip2s( pairs ) );

      int next = 0;
      boolean last;
      FindQuantiles.incComp( 1 );
      last=(pairs[1].v < pairs[2].v);
      ip = ( last ) ? pairs[2] : pairs[1];
      next = ( last ) ? 3 : 5; //children of the OTHER node

      //children of above
      FindQuantiles.incComp( 1 );
      FindQuantiles.incComp( 1 );
      ip = ( ip.v < pairs[ next ].v ) ? ip : pairs[ next ];
      ip = ( ip.v < pairs[ next + 1 ].v ) ? ip : pairs[ next + 1];

      return ip.i;
      //      break;
    }
    case 2: {
      LoBuildHeap(pairs);
      FindQuantiles.incComp( 1 );
      if( pairs[1].v > pairs[2].v){
	return pairs[2].i;
      }
      else{
	return pairs[1].i;
      }
      
      //      break;
    }
    default:     // This should never happen
      // RunTimeException( "ERROR DEEP IN FINDRANK 
      // (selectRank called with " + neededRank + " )");
      return(-1);
    
    }
    //    return -1;
  }    
  
  /**

    Swap the data at two different indexes in the array.

    @param pairs the array to swap values in
    @param a the index to swap b with
    @param b the index to swap a with

    */
  private static void SwapIndex(intPair[] pairs, int a, int b){
    intPair t=pairs[a];
    pairs[a]=pairs[b];
    pairs[b]=t;
  }
    
  // This is almost directly from the book 

  /**

    Heapify an array of numbers based around index i.

    @param pairs the array to heapify
    @param i the index to heapify around

    */
  private static void Heapify( intPair[] pairs, int i ){
    int largest=i;
    if(2*i+1 < pairs.length){

      FindQuantiles.incComp( 1 );
      if( pairs[i].v < pairs[2*i].v ){
	largest=2*i;
      }
	
      FindQuantiles.incComp( 1 );
      if(pairs[largest].v < pairs[2*i+1].v){
	largest=2*i+1;
      }
	
      if(i != largest){
	SwapIndex(pairs,i,largest);
	Heapify(pairs,largest);
      }
    }
  }
    
  /**

    Heapify placing the smallest value at the top.

    @param pairs the array to inverse heapify
    @param i the index to reverse heapify around

    */
  private static void InverseHeapify( intPair[] pairs, int i ){
    int smallest=i;
    if(2*i+1 < pairs.length){

      FindQuantiles.incComp( 1 );
      if( pairs[i].v > pairs[2*i].v ){
	smallest=2*i;
      }
	
      FindQuantiles.incComp( 1 );
      if(pairs[smallest].v > pairs[2*i+1].v){
	smallest=2*i+1;
      }
	
      if(i != smallest){
	SwapIndex(pairs,i,smallest);
	Heapify(pairs,smallest);
      }
    }
  }
    
  /**

    Build a heap with the smallest value on top.

    @param pairs the array to build into a heap

    */
  private static void LoBuildHeap( intPair[] pairs ){
    int i=0,j=0;
    intPair[] NewPairs= new intPair[pairs.length+1];
    
    for(j=0 ; j<pairs.length ; j++){
      NewPairs[j+1]=pairs[j];
    }
    for(i=NewPairs.length/2 ; i>=1 ; i--){
      InverseHeapify(NewPairs,i);
    }
    for(j=0 ; j<pairs.length ; j++){
      pairs[j]=NewPairs[j+1];
    }
  }
    
  /**

    Build a heap with the largest value on top.

    @param pairs the array to build a heap from

    */
  private static void HiBuildHeap( intPair[] pairs ){
    int i=0,j=0;
    intPair[] NewPairs= new intPair[pairs.length+1];
    
    for(j=0 ; j<pairs.length ; j++){
      NewPairs[j+1]=pairs[j];
    }
    for(i=NewPairs.length/2 ; i>=1 ; i--){
      Heapify(NewPairs,i);
    }
    for(j=0 ; j<pairs.length ; j++){
      pairs[j]=NewPairs[j+1];
    }
  }
}