/**
 * A collection of methods related to int[].
 */
public class ArrayStuffSolution {

  /**
   * Print list[0..i-1] on one line, separated by spaces and surrounded by
   * [ and ].
   * @param list the sorted array.
   * @param i the number of items in list to print.
   */
  public static void print(int[] list, int i) {
    System.out.print("[");

    // Print the first only if there are any.
    if (i > 0) {
      System.out.print(list[0]);

      // Print list[1..i] --all but the first.
      int j= 1;
      while(j != i) {
        System.out.print(", " + list[j]);
        j++;
      }
    }

    // There is no ',' after the last item.
    System.out.println("]");
  }

  /**
   * Return whether k is in list[i..j].
   * Precondition: list[i..j] is sorted.
   * @param list the sorted array.
   * @param i the index of the start of the range to be searched.
   * @param j the index of the end of the range to be searched.
   * @param k the number to search for.
   */
  public static boolean contains(int[] list, int i, int j, int k) {

    // Seach list[i..j]. We've looked at list[i..t-1].
    int t= i;
    while (t != j+1 && list[t] != k) {
      t++;
    }

    return t != j+1;
  }

  /**
   * Insert k into list where it belongs.
   * Precondition: list[0..i-1] is sorted, and list[i] is unused.
   * @param list the sorted array.
   * @param i the number of items in list.
   * @param k the number to add to list.
   */
  public static void insert(int[] list, int i, int k) {

    // Shift all items in list[0..i-1] that are > k.

    // Before every iteration, we've moved list[t+1..i-1].
    // t is the next candidate to shift.
    int t= i-1;
    while(t != -1 && list[t] > k) {
      list[t+1]= list[t];
      t--;
    }

    list[t+1]= k;
  }

  /**
   * Remove k from list[0..i-1].
   * Precondition: list[0..i-1] is sorted, and k is an element of list[0..i-1].
   * @param list the sorted array.
   * @param i the number of items in list.
   * @param k the number to remove from list.
   */
  public static void remove(int[] list, int i, int k) {

    // Find the location of k. We've looked at list[0..j-1].
    int j= 0;
    while (list[j] != k) {
      j++;
    }

    // Remove k by shifting the remainder. We've moved at list[t..j-1].
    int t= j;
    while(j != i) {
      list[j]= list[j+1];
      j++;
    }
  }

  /**
   * Return whether k is in list[rowI..rowJ][colI..colJ].
   * (That describes a rectangular portion of a two-dimensional array.)
   * @param list the array to be searched.
   * @param rowI the index of the start of the horizontal range to be searched.
   * @param rowJ the index of the end of the horizontal range to be searched.
   * @param colI the index of the start of the vertical range to be searched.
   * @param colJ the index of the end of the vertical range to be searched.
   * @param k the number to search for.
   */
  public static boolean contains(
    int[][] list, int rowI, int rowJ, int colI, int colJ, int k) {

    boolean contains= false;

    // Search [rowI..rowJ]. We've looked at rows rowI..row-1.
    for (int row= rowI; row != rowJ+1; row++) {

      // Search [colI..colJ]. We've looked at columns colI..col-1.
      for (int col= colI; col != colJ+1; col++) {
        contains= contains || list[row][col] == k;
      }
    }

    return contains;
  }

  /**
   * If b is false, print a stack trace.
   */
  public static void assertTrue(boolean b) {
    if (!b) {
      new Exception().printStackTrace();
    }
  }

  /**
   * If a[0..i-1] and b[0..i-1] are not equal, print a stack trace.
   */
  public static void arraysEqual(int[] a, int[] b, int i) {
    boolean same= true;

    // Compare a[0..i]. t is the next item to compare. a[0..t-1] are all
    // equal.
    int t= 0;
    while (t != i && same) {
      same= a[t] == b[t];
      ++t;
    }

    if (!same) {
      new Exception().printStackTrace();
      print(a, i);
      print(b, i);
    }
  }

  /**
   * Test the various methods in this class, except for method print.
   */
  public static void main(String[] args) {

    /*
     * The following line creates an int[] object of length 2 with 11 and
     * 13 in it. Cool, huh? It's called an "array initializer".
     */
    int[] a= new int[] {11, 13};

    print(a, 2); // Result: [11 13]
    print(a, 1); // Result: [11]
    print(a, 0); // Result: []

    assertTrue(contains(a, 0, 1, 11)); // Result: true
    assertTrue(!contains(a, 1, 1, 11)); // Result: false
    assertTrue(!contains(a, 2, 1, 11)); // Result: false

    a= new int[10];
    a[0]= 1;
    a[1]= 3;
    a[2]= 5;

    print(a, 3); // Result: [1 3 5]
    insert(a, 3, 2);
    print(a, 4); // Result: [1 2 3 5]
    arraysEqual(a, new int[] {1, 2, 3, 5}, 4);
    insert(a, 4, 0);
    arraysEqual(a, new int[] {0, 1, 2, 3, 5}, 5);
    print(a, 5); // Result: [0 1 2 3 5]
    insert(a, 5, 7);
    arraysEqual(a, new int[] {0, 1, 2, 3, 5, 7}, 6);
    print(a, 6); // Result: [0 1 2 3 5 7]

    remove(a, 6, 7);
    print(a, 5); // Result: [0 1 2 3 5]
    remove(a, 5, 0);
    print(a, 4); // Result: [1 2 3 5]
    remove(a, 4, 2);
    print(a, 3); // Result: [1 3 5]

    a= new int[10];
    a[0]= 1;
    remove(a, 1, 1);
    print(a, 0); // Result: []

    /*
     * The following line creates an int[][] that looks like this:
     *    8 11 13
     *    1  2  3
     */
    int[][] b= new int[][] { {8, 11, 13}, {1, 2, 3} };
    assertTrue(contains(b, 0, 1, 1, 2, 3)); // Should be true.
    assertTrue(!contains(b, 0, 1, 0, 1, 3)); // Should be false.

    int[] c= new int[] {1, -4, 10, 2};
    print(c, 4);
    insertionSort1(c);
    print(c, 4);

    int[] d= new int[0];
    print(d, 0);
    insertionSort1(c);

    int[] e= new int[] {1, -4, 10, 2};
    print(e, 4);
    insertionSort2(e);
    print(e, 4);

    int[] f= new int[0];
    print(f, 0);
    insertionSort2(f);
  }

  /** Sort a. */
  public static void insertionSort1(int[] a) {
    int i= 0;
    while (i != a.length) {

      // Find where a[i] belongs in a[0..i].
      int j= i-1;
      while (j != -1 && a[j] > a[i]) {
        j--;
      }

      //move a[j+1..i] over by 1 and put a[i] in a[j + i]
      int t= a[i];
      System.arraycopy(a, j+1, a, j+2, i-j-1);
      a[j+1]= t;

      i++;
    }
  }

  /** Sort a. */
  public static void insertionSort2(int[] a) {
    int i= 0;
    while (i != a.length) {

      int t= a[i];

      // Find where a[i] belongs in a[0..i].
      int j= i-1;
      while (j != -1 && a[j] > t) {
        a[j+1]= a[j];
        j--;
      }

      a[j+1]= t;

      i++;
    }
  }
}