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