Programming Assignment 3

Wrapper Classes, Text Processing, and Recursion with Merge Sort

Example Implementation

/**
 * Implementation of Assignment 3: Wrapper Classes, Text Processing, and
 * Recursion with Merge Sort
 *
 * @author     Cheng, Jade
 * @assignment CSCI 2912 Assignment 3
 * @date       Jan, 29, 2012
 */


import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Implementation of Assignment 3: Wrapper Classes, Text Processing, and
 * Recursion with Merge Sort
 */

public class ChengJade3 {

  /**
   * The main entry point of the program.
   *
   * @param args The command-line arguments.
   */

  public static void main(final String[] args) {
    assert null != args;

    // Check if the wrong number of arguments are specified on the
    // command line.
    if (args.length != 1) {
      System.err.println("Invalid command-line arguments.");
      return;
    }

    // Read a list of floating-point values into this array list.
    final ArrayList<Double> list = new ArrayList<Double>();

    // Use a scanner to read the list of values, one per line; the values are
    // boxed as they are added to the array list.
    try {
      final Scanner scanner = new Scanner(new File(args[0]));
      while (scanner.hasNextLine()) {

        // Read the next line from the file.
        final String line = scanner.nextLine();

        // If the line is empty, then display an error and terminate.
        if (line.isEmpty()) {
          System.err.println("Empty line encountered.");
          return;
        }

        // Otherwise, attempt to parse the line as a double; if this fails,
        // display an error and terminate.
        try {
          list.add(new Double(line));
        } catch (final NumberFormatException e) {
          System.err.println("Invalid line encountered: '" + line + "'.");
          return;
        }
      }

    } catch (final IOException e) {
      // If an error occurs, display the error message and terminate.
      System.err.println("Failed to read input file: " + e.getMessage());
      return;
    }

    // Un-box the values from the array list.
    final double[] array = new double[list.size()];
    for (int i = 0; i < list.size(); i++)
      array[i] = list.get(i).doubleValue();

    // Sort the values using Merge Sort.
    mergeSort(array);

    // Print each value to standard output (in order).
    for (final double value : array)
      System.out.println(value);
  }

  /**
   * Sorts the specified values using the merge sort algorithm.
   *
   * @param values The values to sort.
   */

  private static void mergeSort(final double[] values) {
    assert null != values;

    // There is no need to sort an arrow zero length.
    if (values.length == 0)
      return;

    // For efficiency, create a scratch array for temporary values.
    final double[] scratch = new double[values.length];

    // Merge-sort the entire array using recursion.
    mergeSort(values, scratch, 0, values.length - 1);
  }

  /**
   * Sorts the specified values using the merge sort algorithm.
   *
   * @param values The values to sort.
   * @param scratch A scratch array, the same size as the list.
   * @param min The lowest index in the array (inclusive).
   * @param max The highest index in the array (inclusive).
   */

  private static void mergeSort(
      final double[] values,
      final double[] scratch,
      final int min,
      final int max) {

    assert null != values;
    assert null != scratch;
    assert values.length == scratch.length;
    assert min >= 0;
    assert max <= values.length;
    assert min <= max;

    // Check for the end case: The range is one element.
    if (min == max)
      return;

    // Find the middle index of the range, and merge-sort both partitions.
    final int lhsMax = (min + max) / 2;
    final int rhsMin = lhsMax + 1;
    mergeSort(values, scratch, min, lhsMax);
    mergeSort(values, scratch, rhsMin, max);

    // Copy the desired range from the values array to the scratch array.
    System.arraycopy(values, min, scratch, min, 1 + max - min);

    // Loop over both partitions in the scratch array, and copy the values
    // in order back into the values array.
    int lhs = min, rhs = rhsMin, dst = min;
    while (lhs <= lhsMax && rhs <= max)
      values[dst++] = scratch[lhs] < scratch[rhs]
          ? scratch[lhs++]
          : scratch[rhs++];

    // Copy the remaining items into the list.
    while (lhs <= lhsMax)
      values[dst++] = scratch[lhs++];
    while (rhs <= max)
      values[dst++] = scratch[rhs++];
  }
}