import java.util.Scanner;
import java.util.Arrays;

public class PartitionTwoColor {

   private static final char RED = 'R';
   private static final char BLUE = 'B';

   /* Rearranges the elements in the given array so that all the RED ones
   ** are in a[0..m) and all the BLUE ones are in a[m..N), where N is an
   ** abbreviation for a.length, m is the value returned (corresponding to 
   ** the number of RED elements in the array).  The loop's invariant is 
   ** intended to be as depicted by this diagram:
   **
   **    0            k            m             N
   **   +------------+------------+-------------+
   ** a |     ?      |  all RED   |  all BLUE   |
   **   +------------+------------+-------------+
   **
   ** In words, the loop invariant is 0 <= k <= m <= N &&
   ** all elements in a[k..m) are RED && 
   ** all elements in a[m..N) are BLUE
   */
   public static int partition(char[] a) {
      int k, m;
      k = ??;  m = ??;   // missing initializations
      assert loopInvariant(a, k, m);
      while ( ?? ) {  // missing loop guard

         // missing loop body

         assert loopInvariant(a, k, m);
      }
      return m;
   }

   // main() method
   public static void main(String[] args) {
      System.out.println("Welcome to PartitionTwoColor\n");

      // If no command line arguments are provided, use a set of
      // hard-coded strings:
      if (args.length == 0) {
         args = new String[] 
             { "RRBRBBRBBR", "BBBRRBBRRRBR", "BRBRRBRBBRB", "RRRR", "BB" };
      }
 
      for (int i=0; i != args.length; i++) {
         char[] c = args[i].toCharArray();
         System.out.print("Array to be partitioned: ");
         printAry(c);
         int m = partition(c);
         System.out.println("\nAfter partitioning:");
         System.out.print("RED segment:  ");
         printArySeg(c, 0, m);
         System.out.print("\nBLUE segment: ");
         printArySeg(c, m, c.length);
         System.out.println("\n");
      }
            
   }



   // utilities
   // ---------

   private static void printAry(char[] b) { printArySeg(b, 0, b.length); }

   private static void printArySeg(char[] b, int low, int high) {
      for (int i = low; i != high; i++) {
         System.out.print(b[i]);
      }
   }

   /* Swaps the values in locations i and j of array ary[].
   */
   private static void swap(char[] ary, int i, int j) {
      char temp = ary[i];
      ary[i] = ary[j];
      ary[j] = temp;
   }

   /* Reports whether or not the following condition is true:
   ** 0 <= k <= m <= a.length &&
   ** all elements in a[k..m) are RED &&
   ** all elements in a[m..a.length) are BLUE 
   */
   private static boolean loopInvariant(char[] a, int k, int m) {
      return 0 <= k && k <= m && m <= a.length &&
             allRed(a,k,m) && allBlue(a,m,a.length);
   }

   private static boolean isRed(char ch) { return ch == RED; }
   private static boolean isBlue(char ch) { return ch == BLUE; }

   /* Reports whether or not every element in a[low..high) is RED.
   */
   private static boolean allRed(char[] a, int low, int high) {
      return allEqualTo(a, low, high, RED);
   }

   /* Reports whether or not every element in a[low..high) is BLUE
   */
   private static boolean allBlue(char[] a, int low, int high) {
      return allEqualTo(a, low, high, BLUE);
   }

   /* Reports whether or not every element in a[low..high) is equal to ch.
   */
   private static boolean allEqualTo(char[] a, int low, int high, char ch) {
      int i = low;
      while (i != high && a[i] == ch) { i = i+1; }
      return i == high;
   }

}