import java.util.Vector;
import java.util.Hashtable;
import java.util.Enumeration;

// This is a utility class for MergeInsertion that keeps track of the
// relationship between an A and B and their rank in the list
class MergeInsertionPair {
  public int low;
  public int high;
  public int rank;

  MergeInsertionPair( int low, int high, int rank ) {
    this.low = low;
    this.high = high;
    this.rank = rank;
  }
}

/**
  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: MergeInsertion.java,v 1.3 1999/02/16 05:23:47 danielr Exp $<P>

  Sort N elements via MergeInsertion. As explained on page 186 on
  Knuth vol. 3.

  */
public class MergeInsertion {

  /**
    Sort the range from p to r inclusive in the array S.
    
    @param S the array to sort
    @param p the begin point of the range to consider
    @param r the end point of the range to consider
    
    */
  public static void sort( int[] S, int p, int r ) {

    // convert the range into our MIP class
    Vector elements = new Vector( r - p + 1);
    for ( int i = p; i <= r; i++ ) {
      elements.addElement( new MergeInsertionPair( 0, S[ i ], 0 ) );
    }
    
    mergeInsertion( elements );
    
    // convert back to an array of ints
    int i = p;
    Enumeration values = elements.elements();
    while( values.hasMoreElements() ) {
      S[ i ] = ( ( MergeInsertionPair )values.nextElement() ).high;
      i++;
    }
  }

  /**

    A utility function to make the code for sorting 3 numbers easier
    to read below.
    
    @param sets the Vector of MIPs to reorder
    @param a the MIP that goes at position 0 in the Vector
    @param b the MIP that goes at position 1 in the Vector
    @param c the MIP that goes at position 2 in the Vector 

    */
  private static void order3( Vector sets, MergeInsertionPair a, 
			      MergeInsertionPair b, MergeInsertionPair c ) {
    a.rank = 1;
    b.rank = 2;
    c.rank = 3;

    sets.setElementAt( a, 0 );
    sets.setElementAt( b, 1 );
    sets.setElementAt( c, 2 );
  }

  /**
    The heart of the algorithm which takes in a Vector of MIPs and
    sorts them.
    
    @param sets the Vector of MIPs to sort.
    */
  private static void mergeInsertion( Vector sets ) {
    int size = sets.size();

    if ( size == 0 || size == 1 )
      return;
    
    if ( size == 2 ) {
      MergeInsertionPair a = ( MergeInsertionPair )sets.elementAt( 0 );
      MergeInsertionPair b = ( MergeInsertionPair )sets.elementAt( 1 );
      
      if ( a.high > b.high ) {
	a.rank = 2;
	b.rank = 1;
	sets.setElementAt( b, 0 );
	sets.setElementAt( a, 1 );
      } else {
	a.rank = 1;
	b.rank = 2;
      }
      FindQuantiles.incComp( 1 );
      return;
    } // size == 2
    
    if ( size == 3 ) {
      MergeInsertionPair a = ( MergeInsertionPair )sets.elementAt( 0 );
      MergeInsertionPair b = ( MergeInsertionPair )sets.elementAt( 1 );
      MergeInsertionPair c = ( MergeInsertionPair )sets.elementAt( 2 );
      
      if ( a.high < b.high ) {
	if ( b.high < c.high ) {
	  order3( sets, a, b, c );
	  FindQuantiles.incComp( 2 );
	  return;
	} else {
	  if ( a.high < c.high ) {
	    order3( sets, a, c, b );
	    FindQuantiles.incComp( 3 );
	    return;
	  } else {
	    order3( sets, c, a, b );
	    FindQuantiles.incComp( 3 );
	    return;
	  }
	}
      } else {
	if ( a.high < c.high ) {
	  order3( sets, b, a, c );
	  FindQuantiles.incComp( 2 );
	  return;
	} else {
	  if ( b.high < c.high ) {
	    order3( sets, b, c, a );
	    FindQuantiles.incComp( 3 );
	    return;
	  } else {
	    order3( sets, c, b, a );
	    FindQuantiles.incComp( 3 );
	    return;
	  }
	}
      }
    } // size == 3
    
    // for the loops
    int comp = 0;
    
    // the number of pairs that we have to compare
    int halfSize = ( size - ( size % 2 ) ) / 2;
    
    // use a lookup table to find the original MIP that
    // an element refers to
    Vector setPairs = new Vector( halfSize );
    Hashtable lookup = new Hashtable( size );
      
    // compare each pair and find the large of the two
    // create a new MIP for each pair so we can recursively call
    // mergeInsertion
    for( int i = 0; i < ( size - ( size % 2 ) ); i += 2 ) {
      MergeInsertionPair a = ( MergeInsertionPair )sets.elementAt( i );
      lookup.put( new Integer( a.high ), a );
      
      MergeInsertionPair b = ( MergeInsertionPair )sets.elementAt( i + 1 );
      lookup.put( new Integer( b.high ), b );
      
      comp++;
      if ( a.high > b.high ) {
	setPairs.addElement( new MergeInsertionPair( b.high, a.high, 0 ) );
      } else {
	setPairs.addElement( new MergeInsertionPair( a.high, b.high, 0 ) );
      }
    }

    // add the odd element to the lookup table
    if ( ( size % 2 ) == 1 ) {
      MergeInsertionPair a = ( MergeInsertionPair )sets.elementAt( size - 1 );
      lookup.put( new Integer( a.high ), a );
    }

    // recursively call mergeInsertion to sort the pairs of numbers
    mergeInsertion( setPairs );

    // create a vector for storing the final set of sorted numbers
    Vector result = new Vector( size );

    // add the lowest b at the head of the list as a dummy MIP
    MergeInsertionPair lowest = 
      ( MergeInsertionPair )setPairs.elementAt( 0 );
    result.addElement( new MergeInsertionPair( 0, lowest.low, 0 ) );

    // add all of the A's in their sorted order
    Enumeration pairs = setPairs.elements();
    while( pairs.hasMoreElements() ) {
      result.addElement( pairs.nextElement() );
    }
      
    // keep track of powers for easier power raising
    int powerTwo = 4;
    int powerNegOne = -1;
    
    // the last t sub k we started at
    int lastStart = 1;

    // are we dealing with an odd lengthed n
    boolean oddN = ( size % 2 ) == 1 ? true : false;
      
    // repeat until a break happenes
    while( true ) {
      // increase to the next value of k
      powerTwo *= 2;
      powerNegOne *= -1;

      // the b sub t we will start inserting with
      int start = ( powerTwo + powerNegOne ) / 3;

      // loop over this ranges values for b sub t
      for ( int t = start; t > lastStart; t-- ) {
	
	// this is a valid b sub t to insert
	if ( t <= ( halfSize + ( size % 2 ) ) ) {

	  int lastPos = 1;
	  if ( oddN && ( t == ( halfSize + ( size % 2 ) ) ) ) {
	    lastPos = result.size();
	  } else {
	    // find where the current a sub t is in the sorted list
	    while( ( ( MergeInsertionPair )result.elementAt( lastPos ) ).rank != t ) {
	      lastPos++;
	    }
	  }

	  // get the value of b we are trying to insert
	  int valueOfB;
	  if ( oddN && ( t == ( halfSize + ( size % 2 ) ) ) ) {
	    valueOfB = 
	      ( ( MergeInsertionPair )sets.elementAt( size - 1 ) ).high;
	  } else {
	    valueOfB = 
	      ( ( MergeInsertionPair )result.elementAt( lastPos ) ).low;
	  }

	  // create the MIP we will put into the sorted list
	  MergeInsertionPair MIPOfB = 
	    new MergeInsertionPair( 0, valueOfB, 0 );
	  
	  // we know that b sub t can not be higher in the list than 
	  // a sub t so only consider the porition of the list
	  // 0 .. lastPos-1
	  // we will do a binary insertion so start looking at 

	  // Convert to an array so we can call binaryInsert
	  int bI[] = new int[ lastPos ];
	  for( int i = 0; i < lastPos; i++ ) {
	    bI[ i ] = ( ( MergeInsertionPair )result.elementAt( i ) ).high;
	  }
	  
	  int insertAt = BinaryInsert.binaryInsert( bI, valueOfB );

	  // just add it to the end
	  if ( insertAt == result.size() ) {
	    result.addElement( MIPOfB );
	  } else {
	    result.insertElementAt( MIPOfB, insertAt );
	  }
	} // valid t
      } // for( t )
      
      lastStart = start;
      // if we have inserted all the valid b sub t's stop
      if ( lastStart >= ( halfSize + ( size % 2 ) ) )
	break;
    }
    
    // order the original Vector based on the ranks that we now have
    for ( int i = 0; i < size; i++ ) {
      MergeInsertionPair temp = ( MergeInsertionPair )result.elementAt( i );
      Integer lookupKey = new Integer( temp.high );
      MergeInsertionPair item = 
	( MergeInsertionPair )lookup.get( lookupKey );
      
      item.rank = i + 1;
      sets.setElementAt( item, i );
    }
    
    FindQuantiles.incComp( comp );
  }
}