package rebelsky.util;

import java.util.Random;		// We'll be generating random numbers

/**
 * A collection of algorithms appropriate for arrays of integers.  While
 * this class was originally designed to support an exercise in 
 * algorithm measurement, it is hoped that it has other uses.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of February 1998
 */
public class IntegerArrayAlgorithms 
{
  /**
   * Search a sorted array of integers for a particular value.
   * <br>pre: The array is sorted in increasing order.
   * <br>pre: The array is nonempty.
   * <br>post: The array is not affected.
   * 
   * @return true if the value is in the array; false otherwise.
   */
  public static boolean binarySearch(int[] iarr, int key)
  {
    // We'll maintain the condition that "if key is in the array,
    // then it is between positions lb and ub, inclusive."
    // The lower bound
    int lb = 0;
    // The upper bound
    int ub = iarr.length - 1;
    // The middle (used for splitting).
    int mid;

    // Keep going until we find the element (in which case we stop
    // because of a "return") or decide that it's not there.
    while (lb <= ub) {
      mid = (lb + ub) / 2;
      if (iarr[mid] == key) {
        return true;
      }
      else if (iarr[mid] < key) {
        lb = mid + 1;
      }
      else { // if (iarr[mid] > key)
        ub = mid - 1;
      }
    } // while

    // Didn't find it, so it's not there.
    return false;
  } // binarySearch

  /**
   * Sort an array of integers by "bubbling" values up the array.
   * <br>pre: (none)
   * <br>post: the original array is unmodified.
   * <br>post: for 0 <= i < length-1, sorted[i] <= sorted[i+1]
   * <br>post: if element x appears n times in the original array,
   *     it also appears n times in the sorted array
   * <br>post: the sorted array has the same length as the original
   *     array.
   *
   * @return a sorted version of the original array. 
   */
  public static int[] bubbleSort(int[] iarr) 
  {
    // Make a copy of the array.
    int[] sorted = (int[]) iarr.clone();

    // Step through each position, swapping as necessary.
    for (int i = 0; i < sorted.length; ++i) {
      for (int j = 0; j < (sorted.length-1-i); ++j) {
        if (sorted[j] > sorted[j+1]) {
          swap(sorted, j, j+1);
        }
      } // for j
    } // for i      
   
    // That's it
    return sorted;
  } // bubbleSort(int[])

  /**
   * Find the position of the smallest element in an array
   * of integers.
   *
   * <br>pre: The array is nonempty.
   * <br>post: The array is unaffected.
   * <br>post: The index smallest element is returned.
   *
   * @return x s.t. iarr[x] <= iarr[i] for all 0 <= i < iarr.length
   */
  public static int indexOfSmallest(int iarr[])
  {
    return indexOfSmallest(iarr, 0, iarr.length-1);
  } // indexOfSmallest

  /**
   * Find the position of the smallest element in a subrange
   * of an array of integers.
   *
   * <br>pre: The subrange is nonempty.
   * <br>post: The array is unaffected.
   * <br>post: The index smallest element is returned.
   *
   * @return x s.t. iarr[x] <= iarr[i] for all lb <= i < iarr.length
   */
  public static int indexOfSmallest(int iarr[], int lb) 
  {
    return indexOfSmallest(iarr, lb, iarr.length-1);
  } // indexOfSmallest
   
  /**
   * Find the position of the smallest element in a subrange
   * of an array of integers.
   *
   * <br>pre: The subrange is nonempty.
   * <br>post: The array is unaffected.
   * <br>post: The index smallest element is returned.
   *
   * @return x s.t. iarr[x] <= iarr[i] for all lb <= i <= ub
   */
  public static int indexOfSmallest(int[] iarr, int lb, int ub)
  {
    // The index of the smallest element found so far.
    int guess = lb;
    // Step through the remaining elements, updating as necessary.
    for (int i = lb; i <= ub; ++i) {
      if (iarr[i] < iarr[guess]) 
        guess = i;
    } // for
    return guess;
  } // indexOfSmallest

  /**
   * Create an array of nonnegative integers of size n with the
   * population of the array being "random" and the values
   * between 0 ... bound.
   * <br>pre: n >= 0
   * <br>pre: bound >= 0
   * <br>post: a newly-allocated array of size n is returned
   * <p>
   * Example (10 integers between 0 and 100):
   *   <code>int[] stuff = IntegerArrayAlgorithms.random(10,100);</code>
   *
   * @exception Exception
   *   When the preconditions are not met.
   */
  public static int[] random(int size, int bound)
    throws Exception
  {
    // Set up an array of random integers with no particular bounds.
    int[] arr = random(size);
    // Bring the integers into the appropriate range.
    for (int i = 0; i < size; ++i) {
      arr[i] = Math.abs(arr[i]) % (bound + 1);
    } // for
    // That's it
    return arr;
  } // random(int,int)

  /**
   * Create an array of integers of size n with the population of
   * the array being "random".
   * <br>pre: n >= 0
   * <br>post: a newly-allocated array of size n is returned
   * <p>
   * Example:<br>
   *   <code>int[] stuff = IntegerArrayAlgorithms.random(10);</code>
   *
   * @exception Exception
   *   when <code>size < 0</code>
   */
  public static int[] random(int size)
    throws Exception
  {
    // The new array we're creating.
    int[] arr;
    // A random number generator.
    Random generator;

    // Make sure that the size is reasonable.
    if (size < 0) {
      throw new Exception("size must be greater than 0");
    }

    // Allocate the array.
    arr = new int[size];

    // Create the generator.
    generator = new Random();

    // Populate the array
    for (int i = 0; i < size; ++i) {
      arr[i] = generator.nextInt();
    } // for

    // That's it
    return arr;
  } // random(int)

  /**
   * Sort an array of integers using the selection sort algorithm,
   * in which the smallest remaining element is repeatedly identified
   * and moved to the front of the list.
   * <br>pre: (none)
   * <br>post: the original array is unmodified.
   * <br>post: for 0 <= i < length-1, sorted[i] <= sorted[i+1]
   * <br>post: if element x appears n times in the original array,
   *     it also appears n times in the sorted array
   *     array.
   */
  public static int[] selectionSort(int[] iarr)
  {
    // Make a copy of the array.
    int[] sorted = (int[]) iarr.clone();

    // Step through the array, moving the smallest element into the
    // correct position.
    for (int i = 0; i < sorted.length; ++i) {
      swap(sorted, i, indexOfSmallest(sorted, i));
    }
 
    // That's it
    return sorted;
  } // selectionSort(int[])

  /**
   * Search through an unsorted array of integers to determine whether
   * a particular value (key) is in the array.
   * <br>pre: (none)
   * <br>post: the array is unaffected
   * 
   * @return true if the key is in the array; false otherwise.
   */
  public static boolean sequentialSearch(int[] iarr, int key) 
  {
    // Look at each space in the array.
    for (int i = 0; i < iarr.length; ++i) {
      if (iarr[i] == key) return true;
    }
    // Haven't found it.  It must not be there.
    return false;
  } // sequentialSearch

  /**
   * Swap the elements at positions a and b in an integer array.
   * <br>pre: 0 <= a,b < iarr.length
   * <br>pre: the array is nonempty
   */
  public static void swap(int[] iarr, int a, int b) 
  {
    // A temporary holder.
    int tmp;
    // Guess.
    tmp = iarr[a];
    iarr[a] = iarr[b];
    iarr[b] = tmp;
  } // swap
} // IntegerArrayAlgorithms