/* File: ArrayManipulation.java - March 2011 */
package l08;

/**
 * Demonstrate manipulation of arrays and subarrays
 *
 * @author Michael Albert
 *
 */

public class ArrayManipulation{

   public static final int GAP = Integer.MIN_VALUE; // Just a decision
   public static final int NOT_FOUND = -1; 

   public static void insert(int[] a, int index, int value) {
      insert(a, index, 0, a.length, value);
   }

   public static void insert(int[] a, int index, int left, int right, 
                             int value) {
      for(int dest = right-1; dest > index; dest--) {
         a[dest] = a[dest-1];
      }
      a[index] = value;
   }

   public static void delete(int[] a, int index) {
      delete(a, index, 0, a.length);
   }

   public static void delete(int[] a, int index, int left, int right) {
      if (index < left || right <= index) return; // Out of range
      
      for(int i = index+1; i < right; i++) {
         a[i-1] = a[i];
      }
      a[right-1] = GAP;
   }

   public static int search(int[] a, int value) {
      return search(a, 0, a.length, value);
   }

   public static int search(int[] a, int left, int right, int value) {
      for(int i = left; i < right; i++) {
         if (a[i] == value) return i;
      }
      return NOT_FOUND;
   }

   public static int binarySearch(int[] a, int value) {
      return binarySearch(a, 0, a.length, value);
   }

   public static int binarySearch(int[] a, int left, int right, int value) {
      if (right <= left) return NOT_FOUND;
      int mid = (right + left)/2;
      if (a[mid] == value) return mid;
      if (a[mid] > value) return binarySearch(a, left, mid, value);
      return binarySearch(a, mid+1, right, value);
   }

   public static void reverse(int[] a) {
      reverse(a, 0, a.length);
   }

   public static void reverse(int[] a, int left, int right) {
      int low = left;
      int high = right-1;
      while (low < high) {
         int t = a[low]; a[low] = a[high]; a[high] = t;
         low++; high--;
      }
   }

   public static void rotate(int[] a, int k) {
      k = k % a.length;
      reverse(a,a.length-k, a.length);
      reverse(a,0,a.length-k);
      reverse(a);
   }
}