import java.util.Arrays;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

/* Java application that includes a method to "compress" each plateau
** in an array to a plateau of length one.  The remaining methods are
** for the purpose of testing that method.
**
** Authors: R. McCloskey and < STUDENT's NAMES(s) >
** Known Defects: 
*/

public class PlateauCompressApp {

   /* This method expects a single run (i.e., command line) argument that
   ** names a data file.  That file is expected to contain test data by
   ** which to construct arrays to be fed to the compressPlateaus()
   ** method.  Each line of the file is expected to contain a sequence of
   ** integer numerals that is used to populate an array.  Each such array
   ** is passed to the method (which "compresses" each of its plateaus into
   ** a plateau of length one).
   */
   public static void main(String[] args) throws FileNotFoundException {
      Scanner input = new Scanner(new File(args[0]));
      while (input.hasNextLine()) {
         int[] ary = readArray(input);
         System.out.println("Array:");
         System.out.println(Arrays.toString(ary));
         System.out.println("Compressing the array ...");
         int n = compressPlateaus(ary);
         System.out.print("Result: ");
         printPrefix(ary, n);
         System.out.println();
      } 
      System.out.println("Goodbye");
   }

   /* Prints the elements of b[0..high).
   */
   private static void printPrefix(int[] b, int high) {
      for (int i=0; i != high; i++) {
         System.out.print(b[i] + " ");
      }
      System.out.println();
   }


   /* "Compresses" the given array (a[]) so that the plateaus in a[0..k)
   ** match those of its original contents, but each one is now of length one.
   ** Example: Suppose that a[] was originally 
   ** a: [5,5,2,7,7,7,4,4,5,5,5,8].  Then, upon completion, the method will
   ** return 6 (corresponding to the number of plateaus in a[]) and the
   ** first six elements of a[] will be a[0..6): [5,2,7,4,5,8].
   ** pre: a.length != 0
   ** post: The value returned, k, is the number of plateaus in a[], and
   **   a[0..k) contains one "representative" of each of those k plateaus,
   **   in the same order as they originally appeared in the array.  To 
   **   state it another way, a[0..k) is the sequence obtained by removing
   **   from a[0..a.length] any element equal to its predecessor.
   */
   public static int compressPlateaus(int[] a) {
      int k = ?;
      int n = ?;
      int[] aOrig = a.clone();
      // loop invariant: 
      //    1 <= k <= n <= a.length  && 
      //    the plateaus in a[0..k) are of length one and match
      //    one-to-one with the plateaus in aOrig(0 .. n). 
      assert loopInvariant(aOrig, a, k, n);
      while ( ?? ) {

         // MISSING LOOP BODY

         assert loopInvariant(aOrig, a, k, n);
      }
      // postcondition:
      //   The plateaus in a[0..k) are of length one and match one-to-one
      //   with the plateaus in aOrig(0 .. n) and n == a.length.
      return k;
   }

   /* Reports the truth or falsity of the loop invariant of the method above.
   ** If not, the program aborts.
   */
   private static boolean loopInvariant(int[] aOrig, int[] a, int k, int n) {
      boolean goodSoFar = true;
      if (!(1 <= k && k <= n && n <= a.length)) {
         goodSoFar = false;
         System.out.printf("WARNING: 1 <= k(%d) <= n(%d) <= a.length(%d) is false\n\n",
                           k, n, a.length);
      }
      // Check a[0..k) for adjacent duplicates
      boolean adjDupFound = false;
      for (int i=1; i < k && !adjDupFound; i++) {
         if (a[i-1] == a[i]) {
            adjDupFound = true;
         }
      }
      if (adjDupFound) {
         goodSoFar = false;
         System.out.printf("WARNING: Adjacent duplicates found in a[0..%d):\n", k);
         printArySeg(a, 0, k);
      } 

      
      if (!plateausMatch(aOrig, n, a, k)) {
         goodSoFar = false;
      }

      return goodSoFar;
   }

   /* Determines whether ary1[0..high1) and ary2[0..high2) match each
   ** other in terms of plateaus.  That is, would they compress to the
   ** same result.
   */
   private static boolean plateausMatch(int[] ary1, int high1, int[] ary2, int high2) {
      boolean goodSoFar = true;
      int i = 0, j = 0;
      // loop invariant: 
      //   (i == high1 || a plateau begins at location i of ary1[])  &&
      //   (j == high2 || a plateau begins at location j of ary2[])
      while (i != high1  &&  j != high2) {
         // Verify that the current plateaus in ary1 and ary2 contain the same value.
         if (ary1[i] != ary2[j]) 
            { goodSoFar = false; }
         else { 
            // set i to the location where the next plateau in ary1[] begins
            i = i+1;
            while (i != high1  &&  ary1[i] == ary1[i-1]) { i = i+1; }

            // set j to the location where the next plateau in ary2[] begins
            j = j+1;
            while (j != high2  &&  ary2[j] == ary2[j-1]) { j = j+1; }
         }
      }
      // Verify that both i and j have moved past the last plateaus in
      // their respective array segments.  (If not, one array segment
      // has more plateaus than the other.)
      if (i != high1  ||  j != high2) {
         goodSoFar = false;
      }
      return goodSoFar;
   }

   /* Prints the elements of b[low..high) and skips to next line.
   */
   private static void printArySeg(int[] b, int low, int high) {
      System.out.println("  ");
      for (int i=low; i != high; i++) {
         System.out.printf("%d ", b[i]);
      }
      System.out.println();
   }


   /* Reads a line from the source to which the given Scanner is bound,
   ** under the assumption that the tokens on that line (separated by
   ** whitespace) are integer numerals.  An array containing the
   ** corresponding numbers is returned.
   */
   private static int[] readArray(Scanner input) {
      // Read a line of input.
      String line = input.nextLine();
      // Place the tokens on that line into an array of Strings
      String[] items = line.split("\\s+");
      // Convert the Strings into int's and place them into an array
      int[] result = new int[items.length];
      for (int i=0; i != items.length; i++) {
         result[i] = Integer.parseInt(items[i]);
      }
      return result;   // Return the resultant array.
   }
         
}