/* An instance of this Java class can partition an "affiliated" array of type
** int[] (or a specified segment thereof) with respect to a specified pivot 
** value, meaning that it rearranges the array elements so that elements less
** than the pivot are placed in lower-numbered locations than elements equal 
** to the pivot, which are placed into lower-numbered locations than elements 
** greater than the pivot.  The three array sub-segments just described are 
** called the <-pivot, =-pivot, and >-pivot segments, respectively.
**
** Following a call to the partition() method, the client can use observer
** methods to ascertain the locations of the boundaries between adjacent 
** sub-segments in the array segment that was partitioned.  Also accessible
** via observer methods are the number of array element swaps and comparisons
** between pivot values and array elements since the last time the counters
** were reset to zero.
**
** Author: R. McCloskey
** Date: Oct. 2018
*/

public class PivotPartitionerOfInt {

   // instance variables
   // ------------------

   private int[] a;   // the "affiliated" array (i.e., the one in which
                      // partitioning occurs

   // These two variables indicate where the boundaries between the three 
   // array sub-segments (the <-pivot, =-pivot, and >-pivot sub-segments) 
   // lie with respect to the most recent call to a partition() method.  
   private int eqStartLoc;  // starting location of the =-pivot segment
   private int gtStartLoc;  // starting location of the >-pivot segment

   private int swapCntr;    // # swaps and # comparisons to have occurred during
   private int compareCntr; // calls to partition() since the last time the 
                            // counters were reset

   // constructor
   // -----------

   /* Establishes the given array as being this object's "affiliated" array
   ** (i.e., the one in which it can perform partitioning).
   */
   public PivotPartitionerOfInt(int[] ary) { 
      a = ary; 
      swapCntr = 0;  compareCntr = 0;  // these initializations not necessary
   }


   // observers
   // ---------

   /* Indicates the location of the boundary between the <-pivot and =-pivot
   ** sub-segments of the array segment most recently partitioned.
   ** Specifically, it returns the starting location of the =-pivot segment.
   ** (If that segment is empty, this is the same as the starting location of
   ** the >-pivot segment.)
   */
   public int getEqStartLoc() { return eqStartLoc; }

   /* Indicates the location of the boundary between the =-pivot and >-pivot
   ** sub-segments of the array segment most recently partitioned.  
   ** Specifically, it returns the starting location of the >-pivot segment.
   ** (If that segment is empty, this is the same as the ending location of 
   ** the segment that was partitioned.)
   */
   public int getGtStartLoc() { return gtStartLoc; }

   /* Returns the number of times that a pair of array elements was swapped
   ** since the last time the counter was reset to zero.
   */
   public int getSwapCount() { return swapCntr; }

   /* Returns the number of times that the pivot was compared to an array
   ** element since the last time the counter was reset to zero.
   */
   public int getCompareCount() { return compareCntr; }


   // mutators
   // --------

   /* Resets the swap and compare counters to zero.
   */
   public void resetCounters() { swapCntr = 0;  compareCntr = 0; }


   /* Partitions the affiliated array with respect to the specified pivot.
   */
   public void partition(int pivot) { partition(0, a.length, pivot); }
   
   /* Partitions the specified segment of the affiliated array with respect
   ** to the specified pivot.  That is, it rearranges the elements of the 
   ** array segment a[low..high) (where a[] is the affiliated array) so that it
   ** contains three sub-segments, which, respectively, contain the elements 
   ** less than, equal to, and greater than the pivot.  It also increases the
   ** swap counter and compare counter, respectively, in accord with the number
   ** of times that two array elements were swapped and the number of 
   ** comparisons that were made between the pivot and array elements.
   **
   ** pre: 0 <= low <= high <= a.length
   ** post: low <= getEqStartLoc() <= getGtStartLoc() <= high &&
   **   Every element in a[low..getEqStartLoc(]) is < pivot &&
   **   Every element in a[getEqStartLoc()..getGtStartLoc()) is = pivot &&
   **   Every element in a[getGtStartLoc()..high)] is > pivot.
   */
   public void partition(int low, int high, int pivot) {
      
      int j = low, k = high, m = high;

      /* Loop invariant: low <= j <= k <= m <= high
      **    Every element in a[low..j) is < pivot &&
      **    Every element in a[k..m) is = pivot.
      **    Every element in a[m..high) is > pivot.
      */
      while (j != k) {
         if (a[k-1] < pivot) 
            { swap(j,k-1); j = j+1; swapCntr++; compareCntr++; }
         else if (a[k-1] == pivot) 
            { k = k-1; compareCntr = compareCntr + 2; }
         else {  // a[k-1] > pivot
            swap(k-1,m-1); k = k-1; m = m-1; 
            swapCntr++; compareCntr = compareCntr + 2;
         }
      }
      eqStartLoc = k;
      gtStartLoc = m;
   }


   // private
   // -------

   /* Swaps the values in the two specified locations of the affiliated array.
   */
   private void swap(int p, int q) {
      int temp = a[p];
      a[p] = a[q];
      a[q] = temp;
   }

}