ChengJade10.java

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Scanner;
 
/**
 * Implementation for homework assignment 10.
 *
 * @author     Cheng Yu
 * @assignment ICS211 TA10
 * @date       Apr 14, 2010
 * @bugs       None
 */
public class ChengJade10 {
 
  /**
   * 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.
    if (args.length != 1) {
      System.err.println("Usage: java ChengJade10 <path>");
      System.exit(1);
      return;
    }
 
    // Create the priority queue of processes.
    final PriorityQueue<Process> queue = new PriorityQueue<Process>();
    long time = 0;
 
    // Check for any errors while processing the file.
    try {
      // Open the file for reading, and read until the end of the file.
      final Scanner scanner = new Scanner(new FileReader(args[0]));
      while (scanner.hasNext()) {
 
        // Get the next command from the file.
        final String command = scanner.next();
 
        // Check to schedule a command.
        if (command.equalsIgnoreCase("schedule")) {
          schedule(queue, time, scanner);
          continue;
        }
 
        // Check to run a command.
        if (command.equalsIgnoreCase("run")) {
          time = run(queue, time, scanner);
          continue;
        }
 
        // Otherwise, the file is illegal because the command is unknown.
        System.out.flush();
        try { java.lang.Thread.sleep(1000); } catch (Exception e2) { }
        System.err.println("Unknown command in file: " + command);
        System.err.println("Entries should start with 'schedule' or 'run'.");
        System.exit(1);
      }
 
    } catch (final FileNotFoundException e) {
      System.out.flush();
      try { java.lang.Thread.sleep(1000); } catch (Exception e2) { }
      System.err.println(e.getMessage());
      System.exit(1);
    } catch (final InputMismatchException e) {
      System.out.flush();
      try { java.lang.Thread.sleep(1000); } catch (Exception e2) { }
      System.err.println(e.getMessage());
      System.exit(1);
    } catch (final NoSuchElementException e) {
      System.out.flush();
      try { java.lang.Thread.sleep(1000); } catch (Exception e2) { }
      System.err.println("Unexpected end of file.");
      System.exit(1);
    }
 
    System.exit(0);
  }
 
 
  /**
   * Returns a positive long value from the scanner.
   *
   * @param scanner The scanner.
   * @return The value.
   * @throws InputMismatchException if the value is negative.
   */
  private static long nextPositiveLong(final Scanner scanner) {
 
    final long value;
    try {
      value = scanner.nextLong();
    } catch (final InputMismatchException e) {
      throw new InputMismatchException("Invalid integer value.");
    }
 
    if (value < 0)
      throw new InputMismatchException("Unexpected negative value.");
 
    return value;
  }
 
 
  /**
   * Runs a command.
   *
   * @param queue The priority queue of processes.
   * @param time The time before executing the command.
   * @param scanner The scanner reading the command.
   * @return The new time.
   */
  private static long run(final PriorityQueue<Process> queue, final long time,
      final Scanner scanner) {
 
    assert null != queue;
    assert null != scanner;
 
    // Read the new time from the scanner.  This method will execute until no
    // processes remain in the queue or this time is reached.
    final long newTime = nextPositiveLong(scanner);
    if (newTime < time)
      throw new InputMismatchException("Run time is in the past: " + newTime);
 
    // Loop while there are processes to perform and there is remaining time.
    long currentTime = time;
    while (currentTime < newTime && !queue.isEmpty()) {
 
      // Remove and display the next process from the queue.
      final Process process = queue.poll();
      final String activity = process.activity();
      final long duration = process.duration();
      final long due = process.due();
      System.out.print(currentTime + ": performing " + activity);
      System.out.print(" with deadline " + due);
      System.out.println(" and duration " + duration + '\n');
 
      // If the current process cannot be finished, calculate the remaining time
      // and reinsert the process into the queue. Return zero to indicate there
      // is no time left to execute more processes.
      if (currentTime + duration > newTime) {
        final long newDuration = duration - (newTime - currentTime);
        schedule(queue, currentTime, new Process(activity, due, newDuration));
        return newTime;
      }
 
      // Adjust the current time and execute the next process if there is one.
      currentTime += duration;
      System.out.print(currentTime + ": done performing " + activity);
      System.out.println(currentTime <= due ? "\n" : " (late)\n");
    }
 
    // Return the new time.
    return newTime;
  }
 
 
  /**
   * Schedules a new process to run.
   *
   * @param queue The priority queue.
   * @param time The current time.
   * @param process The process.
   */
  private static void schedule(final PriorityQueue<Process> queue,
      final long time, final Process process) {
 
    assert null != queue;
    assert null != process;
 
    queue.add(process);
    System.out.print(time + ": adding " + process.activity());
    System.out.print(" with deadline " + process.due());
    System.out.println(" and duration " + process.duration() + '\n');
  }
 
  /**
   * Schedules a new process to run.  The process is read from a scanner.
   *
   * @param queue The priority queue.
   * @param time The current time.
   * @param scanner The scanner.
   */
  private static void schedule(final PriorityQueue<Process> queue,
      final long time, final Scanner scanner) {
 
    assert null != queue;
    assert null != scanner;
 
    // Read the name, due time, and duration for the process.
    final String activity = scanner.next();
    final long due = nextPositiveLong(scanner);
    final long duration = nextPositiveLong(scanner);
 
    // Initialize a new process, and add it to the queue.
    schedule(queue, time, new Process(activity, due, duration));
  }
}
 
/**
 * A generic minimization heap.
 */
class MinHeap<T extends Comparable<T>> {
  /**
   * The maximum size of the heap.
   */
  public final static int    MAX_SIZE = 1000;
 
  private final ArrayList<T> heap     = new ArrayList<T>();
 
 
  /**
   * Adds an item to the collection. This is an iterative method.
   *
   * @param value The value to add to the collection.
   * @return True indicates the item was added, false otherwise.
   */
  public boolean add(final T value) {
    if (value == null)
      throw new NullPointerException("value");
 
    // Return false if the heap is full.
    if (heap.size() == MAX_SIZE)
      return false;
 
    // Measure the time to add the item.
    final long startTime = System.nanoTime();
 
    // Add the item to the end of the heap.
    heap.add(value);
 
    // Get the index of the last item in the heap.
    int index = heap.size() - 1;
 
    // Count the number of levels traversed in the tree.
    int levelsTraversed = 0;
 
    // Loop from the bottom level to the top level.
    while (index > 0) {
      // Get the index of the parent item in the heap, and break out of the
      // loop if the parent value is smaller than the current value.
      final int parentIndex = (index - 1) / 2;
      if (compare(parentIndex, index) < 0)
        break;
 
      // Swap this item and the parent, and then loop again one level higher.
      swap(index, parentIndex);
      index = parentIndex;
      levelsTraversed++;
    }
 
    // Display information about the time to add the item.
    final long timeConsumption = System.nanoTime() - startTime;
    System.out.println("Levels traversed:   " + levelsTraversed);
    System.out.println("Time consumed (ns): " + timeConsumption);
 
    // Return true to indicate the item was added successfully.
    return true;
  }
 
 
  /**
   * Compares the heap value at the specified indexes. This is used to make the
   * code more readable.
   *
   * @param left The left index.
   * @param right The right index.
   * @return The comparison result.
   */
  private int compare(final int left, final int right) {
    assert left < heap.size();
    assert right < heap.size();
    return heap.get(left).compareTo(heap.get(right));
  }
 
 
  /**
   * Returns true if the collection is empty.
   *
   * @return True if the collection is empty, false otherwise.
   */
  public boolean isEmpty() {
    return heap.isEmpty();
  }
 
 
  /**
   * This method recursively reorders the heap.
   *
   * @param index The index of the item being ordered.
   * @return The number of levels traversed.
   */
  private int reheapify(final int index) {
    assert index < heap.size();
 
    // Get the index of this value's left and right child in the heap tree.
    final int leftIndex = index * 2 + 1;
    final int rightIndex = index * 2 + 2;
 
    // Return immediately if there are no children for this value.
    if (leftIndex >= heap.size())
      return 0;
 
    // Check if there is no right child or if the left child has a smaller value
    // than the right child.
    if (heap.size() == rightIndex || compare(leftIndex, rightIndex) < 0) {
 
      // If the left child is smaller than this value, swap this value and the
      // child, and continue recursively.
      if (compare(leftIndex, index) < 0) {
        swap(leftIndex, index);
        return 1 + reheapify(leftIndex);
      }
 
    // If the right child is smaller than this value, swap this value and the
    // child, and continue recursively.
    } else if (compare(rightIndex, index) < 0) {
      swap(rightIndex, index);
      return 1 + reheapify(rightIndex);
    }
 
    // Arriving here means the children are smaller than the current value, so
    // stop the recursion.
    return 0;
  }
 
 
  /**
   * Removes an item from the collection. This method is implemented
   * recursively.
   *
   * @return The item at the top of the heap.
   * @throws NoSuchElementException if the heap is empty.
   */
  public T remove() {
    // Throw an exception if the heap is empty.
    if (heap.isEmpty())
      throw new NoSuchElementException("The heap is empty.");
 
    // Measure the time to remove the item.
    final long startTime = System.nanoTime();
 
    // Get the value at the top of the heap as the result.
    final T result = heap.get(0);
 
    // Move the value from the last index of the heap to the top of the heap.
    final int lastIndex = heap.size() - 1;
    heap.set(0, heap.get(lastIndex));
 
    // Remove the last value in the collection because it is no longer used.
    heap.remove(lastIndex);
 
    // Recursively order the heap if there are items in the heap.
    final int levelsTraversed = heap.isEmpty() ? 0 : reheapify(0);
 
    // Display information about the time to add the item.
    final long timeConsumption = System.nanoTime() - startTime;
    System.out.println("Levels traversed:   " + levelsTraversed);
    System.out.println("Time consumed (ns): " + timeConsumption);
 
    // Return the item that was originally at the top of the heap
    return result;
  }
 
 
  /**
   * Swaps two values in the heap.
   *
   * @param index1 The first index.
   * @param index2 The second index.
   */
  private void swap(final int index1, final int index2) {
    assert index1 < heap.size();
    assert index2 < heap.size();
 
    final T temp = heap.get(index1);
    heap.set(index1, heap.get(index2));
    heap.set(index2, temp);
  }
}
 
/**
 * A generic priority queue implemented with a heap.
 */
class PriorityQueue<T extends Comparable<T>> {
 
  /** The queue that contains the generic values. */
  private final MinHeap<T> myQueue = new MinHeap<T>();
 
 
  /**
   * Adds an item to the collection.
   *
   * @param value The item to add to the collection.
   * @return True if the item is added.
   * @throws NullPointerException if the value is null.
   */
  public boolean add(final T value) {
    if (value == null)
      throw new NullPointerException("value");
    return myQueue.add(value);
  }
 
 
  /**
   * Returns true if the collection is empty.
   *
   * @return True if the collection is empty, otherwise false.
   */
  public boolean isEmpty() {
    return myQueue.isEmpty();
  }
 
 
  /**
   * Returns the next item from the queue. This method returns null if there are
   * no more items in the queue.
   *
   * @return The next item from the queue or null if there are no more items.
   */
  public T poll() {
    if (myQueue.isEmpty())
      return null;
    return myQueue.remove();
  }
 
 
  /**
   * Returns the string representation of the class.
   *
   * @return The string representation of the class.
   */
  @Override
  public String toString() {
    return myQueue.toString();
  }
}
 
/**
 * A process class. This class contains an activity string, a due time, and a
 * duration.
 */
class Process implements Comparable<Process> {
 
  /** The name of the activity. */
  private final String myActivity;
 
  /** The due time for the process. */
  private final long   myDue;
 
  /** The duration of the process. */
  private final long   myDuration;
 
 
  /**
   * Initializes a new instance of the Process class.
   *
   * @param activity The activity.
   * @param due The due time.
   * @param duration The duration.
   */
  public Process(final String activity, final long due, final long duration) {
    if (activity == null)
      throw new NullPointerException("activity");
    if (duration < 0)
      throw new IllegalArgumentException("duration");
 
    myActivity = activity;
    myDue = due;
    myDuration = duration;
  }
 
 
  /**
   * Returns the activity.
   *
   * @return The activity.
   */
  public String activity() {
    return myActivity;
  }
 
 
  /**
   * Compares this instance to another instance.
   *
   * @param process The other process.
   *
   * @return The comparison value.
   */
  public int compareTo(final Process process) {
    if (process == null)
      return 1;
    final long due = process.due();
    return myDue > due ? 1 : myDue < due ? -1 : 0;
  }
 
 
  /**
   * Returns the due time.
   *
   * @return The due time.
   */
  public long due() {
    return myDue;
  }
 
 
  /**
   * Returns the duration.
   *
   * @return The duration.
   */
  public long duration() {
    return myDuration;
  }
}
 
Valid HTML 4.01 Valid CSS