/* An instance of this Java class has methods by which to rearrange the
** elements of an array into RED, WHITE, and BLUE segments, respectively.
** Afterwards, it can report how many comparisons and how many swaps were
** performed in carrying out this task.
** To keep things simple, the array to be partitioned is of type char[]
** and each of its elements is assumed to have as its value one of 'R',
** 'W', or 'B' (standing for RED, WHITE, and BLUE, respectively.)
**
** Authors: R. McCloskey and <STUDENTS' NAMES>
** Known Defects: ...
*/

public class RWB_Partitioner {

   // class constants
   // ---------------

   private final char RED = 'R';
   private final char WHITE = 'W';
   private final char BLUE = 'B';

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

   // The array that this object most recently partitioned.
   private char[] ary;   

   // The values of these variables indicate the locations of the RED/WHITE 
   // and WHITE/BLUE boundaries, respectively, in the array most recently
   // partitioned.  Specifically, 'rw' indicates the location at which the
   // WHITE segment begins and 'wb' indicates the location at which the BLUE
   // segment begins.
   private int rw, wb;

   // # of comparisons and swaps performed, respectively, during the 
   // most recent execution of a method that does partitioning.
   private int compareCntr;
   private int swapCntr;   


   // constructors
   // ------------

   // No constructor needed


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

   /* Returns (a reference to) the array that this object most recently 
   ** partitioned.
   */
   public char[] array() { return ary; }

   /* Returns, with respect to the array most recently partitioned,
   ** the location at which the WHITE segment begins.
   */
   public int whiteStart() { return rw; }

   /* Returns, with respect to the array most recently partitioned,
   ** the location at which the BLUE segment begins.
   */
   public int blueStart() { return wb; }

   /* Returns the # of comparisons performed during the most recent 
   ** execution of a method that does partitioning.
   */
   public int numComparisons() { return compareCntr; }

   /* Returns the # of swaps performed during the most recent 
   ** execution of a method that does partitioning.
   */
   public int numSwaps() { return swapCntr; }


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

   /* Rearranges the elements of b[] (the given array) so that all RED 
   ** values come before any WHITE values, which come before any BLUE values.
   ** Code is consistent with a loop invariant specifying that the ?-segment
   ** lies between the WHITE and BLUE segments.  In diagram form, the loop
   ** invariant is
   **      0           rw            wq            wb           N
   **     +-----------+-------------+-------------+------------+
   **   b |  all RED  |  all WHITE  |      ?      |  all BLUE  |
   **     +-----------+-------------+-------------+------------+
   */
   public void partition1(char[] b) {
      // Place in instance variable 'ary' a reference to the array about 
      // to be partitioned and reset to zero the variables that keep track 
      // of # comparisons and swaps.
      ary = b;  
      compareCntr = 0;  swapCntr = 0;

      // Initialize variables so as to truthify the loop invariant by making
      // each of the Red, White, and Blue segments empty.  (Which means that
      // the ?-segment covers the whole array).
      rw = -99;          // RED/WHITE boundary (instance variable)
      int wq = -99;      // WHITE/? boundary   (local variable)
      wb = -99;          // ?/BLUE boundary    (instance variable)

      //WARNING: The -99's above are not correct, of course.

      /* loop invariant:
      ** 0 <= rw <= wq <= wb <= b.length && segmentIsRed(b,0,rw) && 
      ** segmentIsWhite(b,rw,wq) && segmentIsBlue(b,wb,b.length)
      */

      // Verify that the loop invariant is true before the 1st loop iteration.
      assert loopInvariant1(b,wq);

      while (true) {  
         if (isRed(b[-99])) {
            // ?? 
         }
         else if (isWhite(b[-99])) {
            // ??
         }
         else if (isBlue(b[-99])) {
            // ??
         }
         else { 
            System.out.println("ERROR: Array element of unknown color!");
         }
         // Verify that the loop invariant is true at the end of each iteration
         assert loopInvariant1(b,wq);
      }
   }


   /* Returns the result (either true or false) of evaluating the 
   ** loop invariant of partition1().
   */
   private boolean loopInvariant1(char[] b, int wq) {
      return 0 <= rw  &&  rw <= wq  &&  wq <= wb  &&  wb <= b.length  &&
             segmentIsRed(b,0,rw)  &&  
             segmentIsWhite(b,rw,wq)  &&  
             segmentIsBlue(b,wb,b.length);
   }


   /* Rearranges the elements of b[] (the given array) so that all RED 
   ** values come before any WHITE values, which come before any BLUE values.
   ** Code is consistent with a loop invariant specifying that the ?-segment
   ** lies after the BLUE segment.  In diagram form, the loop invariant is
   **      0           rw            wb           bq           N
   **     +-----------+-------------+------------+------------+
   **   b |  all RED  |  all WHITE  |  all BLUE  |     ?      | 
   **     +-----------+-------------+------------+------------+
   */
   public void partition2(char[] b) {
      // Place in instance variable 'ary' a reference to the array about 
      // to be partitioned and reset to zero the variables that keep track 
      // of # comparisons and swaps.
      ary = b;  
      compareCntr = 0;  swapCntr = 0;

      // Initialize variables so as to truthify the loop invariant by making
      // each of the Red, White, and Blue segments empty.  (Which means that
      // the ?-segment covers the whole array).
      rw = 0;         // RED/WHITE boundary (instance variable)
      wb = 0;          // WHITE/BLUE boundary (instance variable)
      int bq = 0;      // BLUE/? boundary   (local variable)

      /* loop invariant:
      ** 0 <= rw <= wb <= bq <= b.length && segmentIsRed(b,0,rw) && 
      ** segmentIsWhite(b,rw,wb) && segmentIsBlue(b,wb,bq)
      */

      // Verify that the loop invariant is true before the 1st loop iteration.
      assert loopInvariant2(b,bq);

      while (false) {  // ???


         // ?? (MISSING CODE HERE)


         // Verify that the loop invariant is true at the end of each iteration
         assert loopInvariant2(b,bq);
      }
   }

   /* Returns the result (either true or false) of evaluating the 
   ** loop invariant of partition2().
   */
   private boolean loopInvariant2(char[] b, int bq) {
      return false;  // STUB!!
   } 


   // ------------------------------------------------------------

   // utility methods
   // ---------------

   /* Methods that classify a character as being either RED, WHITE, or BLUE.
   ** They also update the comparison counter.
   */
   private boolean isRed(char ch) { 
      compareCntr++;
      return ch == RED;
   }

   private boolean isWhite(char ch) { 
      compareCntr++;
      return ch == WHITE;
   }
   private boolean isBlue(char ch) { 
      compareCntr++;
      return ch == BLUE;
   }


   /* Swaps the values at the specified locations (i and j) in the
   ** specified array (a).  (Also increments the swap counter.)
   ** pre: 0 <= i < a.length  &&  0 <= j < a.length
   */
   private void swap(char[] a, int i, int j) { 
      swapCntr++;
      char temp = a[i]; a[i] = a[j]; a[j] = temp;
   }


   /* Returns true iff every element in the specified array segment
   ** (namely, a[lower..upper)) is equal to the specified value (ch).
   */
   private boolean allEqualTo(char[] a, int lower, int upper, char ch) {
      int i = lower;
      // loop invariant: 0<=lower<=i<=upper<=a.length  &&
      //                 every element in a[lower..i) is equal to ch
      while (i != upper  &&  a[i] == ch) {
         i = i+1;
      }
      return i == upper;
   }


   /** Returns true iff every element in the specified array segment
   **  (namely, a[lower..upper)) is RED.
   **  pre: 0 <= lower <= upper <= a.length
   */
   private boolean segmentIsRed(char[] a, int lower, int upper) {
      return allEqualTo(a, lower, upper, RED);
   }


   /** Returns true iff every element in the specified array segment
   **  (namely, a[lower..upper)) is WHITE.
   **  pre: 0 <= lower <= upper <= a.length
   */
   private boolean segmentIsWhite(char[] a, int lower, int upper) {
      return allEqualTo(a, lower, upper, WHITE);
   }


   /** Returns true iff every element in the specified array segment
   **  (namely, a[lower..upper)) is BLUE.
   **  pre: 0 <= lower <= upper <= a.length
   */
   private boolean segmentIsBlue(char[] a, int lower, int upper) {
      return allEqualTo(a, lower, upper, BLUE);
   }

}