project-1.java

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.nio.BufferOverflowException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Scanner;
 
/**
 * This is an implementation of ICS 311 Project 1.
 * 
 * @author     Jade Cheng
 * @assignment ICS 311 Project 1
 * @date       Jan 30, 2009
 * @bugs       None
 */
public class JadeChengP1 {
 
  /**
   * A class thrown by the main method when it detects an error.
   */
  @SuppressWarnings("serial")
  private static class ProgramException extends RuntimeException {
 
    /**
     * Initializes a new instance of the MyException class.
     * 
     * @param message The message.
     */
    public ProgramException(final String message) {
      super(message);
    }
  }
 
 
  /**
   * The main entry point of the program.
   * 
   * @param args The command line arguments.
   */
  public static void main(final String[] args) {
 
    // Check the command line arguments for usage errors.
    if (args.length != 3) {
      System.out.println(
          "Usage: java JadeChengP1 filePath sortMethod iterations\n"
        + "\n"
        + "    filePath      The path to a text file containing integers\n"
        + "    sortMethod    The algorithm used to sort the numbers\n"
        + "    iterations    The number of times to sort the values\n"
        + "\n"
        + "The 'sortMethod' must be one of the following values:\n"
        + "\n"
        + "    'bubble'      --> uses Bubble Sort\n"
        + "    'insertion'   --> uses Insertion Sort\n"
        + "    'merge'       --> uses Merge Sort\n"
        + "    'selection'   --> uses Selection Sort\n"
        + "    'heap'        --> uses Heap Sort\n"
        + "\n"
        + "When the program executes, it loops 'iterations' number of times.\n"
        + "For each iteration i, the program sorts i number of values from\n"
        + "the specified file.  After each iteration, the program writes to\n"
        + "standard output the number of items sorted and the number of\n"
        + "operations performed by the specified sorting method.  The output\n"
        + "is tab-delimited.\n"
        + "\n"
        + "When the program terminates, it saves the sorted output to the\n"
        + "text file 'sorted.txt'.  Each integer is placed on a separate\n"
        + "line.");
      return;
    }
 
    final String filePath = args[0];
    final String sortMethod = args[1];
    final String iterationsText = args[2];
 
    try {
      // Read the number of iterations and check for errors.
      final int iterations;
      try {
        iterations = Integer.parseInt(iterationsText);
        if (iterations <= 0)
          throw new ProgramException("'iterations' must be a positive number.");
      } catch (final NumberFormatException e) {
        throw new ProgramException("'iterations' must be a positive number.");
      }
 
      // Determine the method used to sort the numbers and check for errors.
      final Sorter<Integer> sorter;
      if (0 == sortMethod.compareToIgnoreCase("bubble"))
        sorter = new BubbleSort<Integer>();
      else if (0 == sortMethod.compareToIgnoreCase("insertion"))
        sorter = new InsertionSort<Integer>();
      else if (0 == sortMethod.compareToIgnoreCase("merge"))
        sorter = new MergeSort<Integer>();
      else if (0 == sortMethod.compareToIgnoreCase("selection"))
        sorter = new SelectionSort<Integer>();
      else if (0 == sortMethod.compareToIgnoreCase("heap"))
        sorter = new HeapSort<Integer>();
      else
        throw new ProgramException("'sortMethod' is invalid.");
 
      // Open the file for reading and check for errors.
      final Scanner scanner;
      try {
        final File file = new File(filePath);
        scanner = new Scanner(file);
      } catch (final FileNotFoundException e) {
        throw new ProgramException("'" + filePath + "' is not found.");
      }
 
      // Read the maximum number of values from the file.
      final Integer[] unsorted = new Integer[iterations];
      for (int i = 0; i < iterations; i++) {
        try {
          unsorted[i] = Integer.valueOf(scanner.nextInt());
        } catch (final InputMismatchException e) {
          throw new ProgramException("Non-integer value detected in file.");
        } catch (final NoSuchElementException e) {
          throw new ProgramException("Not enough integers present in file.");
        }
      }
 
      // Loop the number of iterations specified on the command line. For each
      // iteration, copy the unsorted values, sort them, and display the
      // results. Also, as a sanity check, ensure the array is sorted after
      // each iteration.
      for (int i = 1; i <= iterations; i++) {
        final Integer[] copy = Arrays.copyOfRange(unsorted, 0, i);
        System.out.println(i + "\t" + sorter.sort(copy));
        verifySortedArray(copy);
      }
 
      // Finally, save the sorted output to the file 'sorted.txt'.
      try {
        final PrintStream stream = new PrintStream("sorted.txt");
        sorter.sort(unsorted);
        for (final Integer i : unsorted)
          stream.println(i);
      } catch (final FileNotFoundException e) {
        throw new ProgramException("Cannot write to file 'sorted.txt'");
      }
 
    } catch (final ProgramException e) {
      // Display errors to standard error and return a failure status.
      System.err.println(e.getMessage());
      System.exit(1);
    }
  }
 
 
  /**
   * Ensures an array of integers is sorted.
   * 
   * @param array The array of integers.
   */
  private static void verifySortedArray(final Integer[] array) {
    for (int i = 1; i < array.length; i++)
      if (array[i].compareTo(array[i - 1]) < 0)
        throw new ProgramException("Sorted algorithm failed.");
  }
}
 
/**
 * This generic class performs a bubble sort.
 */
class BubbleSort<T extends Comparable<T>> implements Sorter<T> {
 
  /**
   * Sorts an array using bubble sort.
   * 
   * @param array The array.
   * 
   * @return The number of operations performed.
   */
  public int sort(final T[] array) {
    if (array == null)
      throw new NullPointerException("array");
 
    int operations = 0;
 
    boolean isSwapped;
    do {
      isSwapped = false;
      for (int i = 0; i < array.length - 1; i++) {
        operations++;
        if (array[i].compareTo(array[i + 1]) > 0) {
          this.swap(array, i, i + 1);
          isSwapped = true;
        }
      }
    } while (isSwapped);
 
    return operations;
  }
 
 
  /**
   * This method swaps two values in an array.
   * 
   * @param array The array.
   * @param n The first index.
   * @param m The second index.
   */
  private void swap(final T[] array, final int n, final int m) {
    assert n >= 0;
    assert m >= 0;
    assert n < array.length;
    assert m < array.length;
 
    final T temp = array[n];
    array[n] = array[m];
    array[m] = temp;
  }
}
 
/**
 * This class implements a generic heap. The maximum size of the heap is
 * MAX_ELEMENTS.
 */
class Heap<T extends Comparable<T>> {
 
  /** The maximum number of elements that can exist in the heap. */
  public static final int    MAX_ELEMENTS = 10000;
 
  /** An array that implements the heap buffer. */
  private final ArrayList<T> myArray      = new ArrayList<T>(Heap.MAX_ELEMENTS);
 
  /** The number of elements used in the array. */
  private int                mySize       = 0;
 
 
  /**
   * Initializes a new instance of the Heap class.
   */
  public Heap() {
    // Initialize the array of elements all to null.
    for (int i = 0; i < Heap.MAX_ELEMENTS; i++)
      this.myArray.add(null);
  }
 
 
  /**
   * This method adds an item to the heap. This method does not allow null
   * values to be added to the collection, but it does allow duplicates.
   * 
   * @param o element whose presence in this collection is to be ensured.
   * 
   * @return The number of operations performed.
   * 
   * @throws BufferOverflowException Thrown if the item cannot be added.
   */
  public int add(final T o) throws BufferOverflowException {
    if (o == null)
      throw new NullPointerException();
 
    int operations = 0;
 
    if (this.mySize == Heap.MAX_ELEMENTS)
      throw new BufferOverflowException();
 
    this.set(this.mySize++, o);
    int n = this.mySize - 1;
 
    while (n > 0) {
      operations++;
      final int nParent = (n - 1) / 2;
      if (o.compareTo(this.get(nParent)) >= 0)
        break;
 
      this.swap(n, nParent);
      n = nParent;
    }
 
    return operations;
  }
 
 
  /**
   * Compares to elements at the specified index values.
   * 
   * @param left The index of the left value.
   * @param right The index of the right value.
   * 
   * @return The result of the compareTo method.
   */
  private int compare(final int left, final int right) {
    assert left >= 0;
    assert left < this.mySize;
    assert right >= 0;
    assert right < this.mySize;
    assert this.mySize <= this.myArray.size();
 
    return this.get(left).compareTo(this.get(right));
  }
 
 
  /**
   * This method returns an element at the specified index.
   * 
   * @param index The index.
   * @return The element at the specified index.
   */
  private T get(final int index) {
    assert index >= 0;
    assert index < this.mySize;
    assert this.mySize <= this.myArray.size();
 
    return this.myArray.get(index);
  }
 
 
  /**
   * Retrieves and removes the smallest value in the heap. This method differs
   * from the poll method in that it throws an exception if this heap is empty.
   * 
   * @return The smallest value in the heap and the number of operations
   *         performed.
   * 
   * @throws NoSuchElementException if this queue is empty.
   */
  public Pair<T> remove() throws NoSuchElementException {
    if (this.mySize == 0)
      throw new NoSuchElementException();
 
    int operations = 0;
 
    final T result = this.get(0);
    this.set(0, this.get(this.mySize - 1));
    this.set(this.mySize - 1, null);
    this.mySize--;
 
    int n = 0;
    while (true) {
      final int nLeft = n * 2 + 1;
      final int nRight = n * 2 + 2;
 
      operations++;
 
      if (nLeft >= this.mySize)
        break;
 
      if (nRight >= this.mySize || this.compare(nLeft, nRight) < 0) {
 
        if (this.compare(nLeft, n) >= 0)
          break;
 
        this.swap(nLeft, n);
        n = nLeft;
        continue;
      }
 
      if (this.compare(nRight, n) >= 0)
        break;
 
      this.swap(nRight, n);
      n = nRight;
    }
 
    return new Pair<T>(result, operations);
  }
 
 
  /**
   * This method sets a value in the heap array.
   * 
   * @param index The index of the value to set.
   * @param value The value to set.
   */
  private void set(final int index, final T value) {
    assert index >= 0;
    assert index < this.mySize;
    assert this.mySize <= this.myArray.size();
 
    this.myArray.set(index, value);
  }
 
 
  /**
   * This method swaps two values.
   * 
   * @param n The first index.
   * @param m The second index.
   */
  private void swap(final int n, final int m) {
    assert n >= 0;
    assert m >= 0;
    assert n < this.mySize;
    assert m < this.mySize;
    assert this.mySize <= this.myArray.size();
 
    final T temp = this.get(n);
    this.set(n, this.get(m));
    this.set(m, temp);
  }
}
 
/**
 * This class performs a heap sort.
 */
class HeapSort<T extends Comparable<T>> implements Sorter<T> {
 
  /**
   * Sorts an array using heap sort.
   * 
   * @param array The array.
   * 
   * @return The number of operations performed.
   */
  public int sort(final T[] array) {
    if (array == null)
      throw new NullPointerException("array");
 
    int operations = 0;
 
    final Heap<T> heap = new Heap<T>();
    for (final T element : array)
      operations += heap.add(element);
 
    for (int j = 0; j < array.length; j++) {
      final Pair<T> pair = heap.remove();
      array[j] = pair.value;
      operations += pair.operations;
    }
 
    return operations;
  }
}
 
/**
 * This generic class performs an insertion sort.
 */
class InsertionSort<T extends Comparable<T>> implements Sorter<T> {
 
  /**
   * Sorts an array using insertion sort.
   * 
   * @param array The array.
   * 
   * @return The number of operations performed.
   */
  public int sort(final T[] array) {
    if (array == null)
      throw new NullPointerException("array");
 
    int operations = 0;
 
    for (int i = 0; i < array.length; i++)
      for (int j = 0; j < i; j++) {
        operations++;
        if (array[j].compareTo(array[i]) > 0) {
          final T temp = array[i];
          for (int k = i; k > j; k--)
            array[k] = array[k - 1];
          array[j] = temp;
        }
      }
 
    return operations;
  }
}
 
/**
 * This class performs a merge sort.
 */
class MergeSort<T extends Comparable<T>> implements Sorter<T> {
 
  /** A temporary array used while merging the sorted elements. */
  private T[] myBuffer;
 
 
  /**
   * This method merges two ranges of values in the array, each sorted. The
   * largest index of the first range is smaller than the smallest index of the
   * second range.
   * 
   * @param array The array.
   * @param start The first index (inclusive) for the first range.
   * @param mid The first index (inclusive) for the second range.
   * @param end The last index (exclusive) for the second range.
   * 
   * @return The number of operations performed.
   */
  private int merge(final T[] array, final int start, final int mid,
      final int end) {
 
    assert array != null;
    assert start >= 0;
    assert start < mid;
    assert mid < end;
    assert end <= array.length;
 
    int operations = 0;
 
    int i = 0;
    int i1 = start;
    int i2 = mid;
 
    while (i1 < mid && i2 < end) {
      operations++;
      if (array[i1].compareTo(array[i2]) < 0)
        this.myBuffer[i++] = array[i1++];
      else
        this.myBuffer[i++] = array[i2++];
    }
 
    if (i1 < mid) {
      operations += mid - i1;
      System.arraycopy(array, i1, this.myBuffer, i, mid - i1);
    }
 
    if (i2 < end) {
      operations += end - i2;
      System.arraycopy(array, i2, this.myBuffer, i, end - i2);
    }
 
    operations += end - start;
    System.arraycopy(this.myBuffer, 0, array, start, end - start);
 
    return operations;
  }
 
 
  /**
   * This method performs the merge sort recursively.
   * 
   * @param array The array.
   * @param start The start index (inclusive).
   * @param end The end index (exclusive).
   * 
   * @return The number of operations performed.
   */
  private int mergeSort(final T[] array, final int start, final int end) {
    assert array != null;
    assert start >= 0;
    assert start < end;
    assert end <= array.length;
 
    if (start + 1 == end)
      return 1;
 
    int operations = 0;
 
    final int mid = (start + end) / 2;
    operations += this.mergeSort(array, start, mid);
    operations += this.mergeSort(array, mid, end);
    operations += this.merge(array, start, mid, end);
    return operations;
  }
 
 
  /**
   * Sorts an array using merge sort.
   * 
   * @param array The array.
   * 
   * @return The number of operations performed.
   */
  public int sort(final T[] array) {
    if (array == null)
      throw new NullPointerException("array");
 
    // Handle a special case: when the array has no items in it.
    if (array.length == 0)
      return 0;
 
    // Make a copy of the array. It's used as a temporary array while merging
    // the sorted elements.
    this.myBuffer = array.clone();
 
    try {
      return this.mergeSort(array, 0, array.length);
    } finally {
      this.myBuffer = null;
    }
  }
}
 
/**
 * A generic class that contains a generic value and a recorded number of
 * operations.
 */
class Pair<T> {
 
  /** The number of operations performed. */
  public final int operations;
 
  /** A value. */
  public final T   value;
 
 
  /**
   * Initializes a new instance of the Pair class.
   * 
   * @param value A value.
   * @param operations The number of operations performed.
   */
  public Pair(final T value, final int operations) {
    this.value = value;
    this.operations = operations;
  }
}
 
/**
 * This class performs a selection sort.
 */
class SelectionSort<T extends Comparable<T>> implements Sorter<T> {
 
  /**
   * Sorts an array using selection sort.
   * 
   * @param array The array.
   * 
   * @return The number of operations performed.
   */
  public int sort(final T[] array) {
    if (array == null)
      throw new NullPointerException("array");
 
    int operations = 0;
 
    for (int i = 0; i < array.length; i++) {
      T smallest = array[i];
      int smallestIndex = i;
 
      for (int j = i; j < array.length; j++) {
        operations++;
        if (array[j].compareTo(smallest) < 0) {
          smallest = array[j];
          smallestIndex = j;
        }
      }
 
      for (int k = smallestIndex; k > i; k--) {
        operations++;
        array[k] = array[k - 1];
      }
 
      array[i] = smallest;
    }
 
    return operations;
  }
}
 
/**
 * The interface to an object that sorts an array of values.
 */
interface Sorter<T extends Comparable<T>> {
 
  /**
   * Sorts an array.
   * 
   * @param array The array to sort.
   * 
   * @return The number of operations performed.
   */
  int sort(final T[] array);
}
 
Valid HTML 4.01 Valid CSS