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