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

/**
* Utilities to manipulate 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; 

  // Most of the functions in this file operate either on full
  // arrays, or on subarrays. Generally speaking the full array
  // version will simply call the subarray version with the
  // appropriate parameters for the left (0) and right (a.length)
  // endpoints.


  // Insert a value at position index. Remaining values are pushed to
  // the right, with the final value of the array or subarray being
  // lost. This would be used mostly in a context where the array is
  // thought of as storing 'real' information in some initial part,
  // and the remainder is junk, or spare space.

  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;
  }

  // Delete an element at position index. Move remaining elements of
  // the subarray leftward to fill the hole, marking the hole left at
  // the right hand end as a GAP

  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;

  }

  // Search for a value in an unsorted array. The search simply
  // proceeds from left to right and returns the position where the
  // value is first found. If the value is not found, -1 is returned.

  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;
  }

  // Search for a value in a *sorted* array. The search works by
  // comparing the midpoint of the current subarray against the value
  // being sought. If it matches, we return the value, otherwise we
  // search in a new subarray which is half the size. The behaviour
  // of this search in an unsorted array is completely unpredictable
  // (but it will generally return NOT_FOUND, whether or not the item
  // is actually present.)

  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);
  }

}