How does subtraction do a comparison? Why does the code seem to avoid returning zero? What's the purpose in that? Why do we subtract o2 from o1 first and then the other way around later?

package edu.uwm.cs351;

import java.util.Comparator;

/**

* The Class Task.

*/

public class Task {

/** The maximum value for reward */

public static final int MAX_REWARD = 1000;

/** The maximum units of time this task takes to complete. */

public static final int MAX_DURATION = 1000;

/** The maximum amount of time we can run tasks. */

public static final int MAX_TIME = Integer.MAX_VALUE;

/** The name of this task. */

final String name;

/** How many units of good are received for accomplishing this task.

* In range: [0,MAX_VALUE] */

private final int reward;

/** How many units of time this task this task takes to complete.

* In range: [0,MAX_VALUE] */

private final int duration;

/** The time that this task must be completed by.

* The time must not be negative o more than MAX_TIME.

* The window to perform the task is [0, deadline]

* where 0 represents the moment performAll(int) is called. */

private final int deadline;

/** The links to the previous and next tasks. */

private Task prev, next;

/**

* Instantiates a new task.

* @param name the name of the task, must not be null

* @param reward the reward for doing the task

* @param deadline the deadline for the task in time

* @param duration the duration of the task

* @throws IllegalArgumentException if a parameter is negative or out of bounds.

* @see #MAX_REWARD

* @see #MAX_DURATION

* @see #MAX_TIME

*/

public Task(String name, int reward, int deadline, int duration) {

if (name == null) throw new NullPointerException("name must not be null");

checkParameter("reward",reward,MAX_REWARD);

checkParameter("duration",duration,MAX_DURATION);

checkParameter("deadline",deadline,MAX_TIME);

this.name = name;

this.reward = reward;

this.deadline = deadline;

this.duration = duration;

}

private static void checkParameter(String name, int p, int max) {

if (p < 0 || p > max) throw new IllegalArgumentException(name + " must be in range [0," + max + "]: " + p);}

/** Gets the name.

* @return the name */

public String getName() {return name;}

/** Gets the reward.

* @return the reward */

public int getReward() {return reward;}

/** Gets the deadline.

* @return the deadline */

public int getDeadline() {return deadline;}

/** Gets the duration.

* @return the duration */

public int getDuration() {return duration;}

/** Gets the previous task.

* @return the previous task */

public Task getPrevious() {return prev;}

/** Gets the next task.

* @return the next task */

public Task getNext() {return next;}

/**

* Add another task into this task's list by priority order.

*

* If the other task should come before, place it somewhere before this task.

* If the other task has equal priority, it should be placed immediately after this task,

* unless this task has some task before it and nothing after it, in which case

* it should come immediately before

* If the other task should come after, place it somewhere after this task.

* It may be necessary to move multiple times forward or multiple times backward (but not both!).

* Make sure tasks don't just pass a new task back and forth.

*

* @param other the task to add to our list

* @param priority comparator of tasks in the list.

* @throws IllegalArgumentException if we try to add a task that is already in a list.

* @throws IllegalArgumentException if we try to add a task to itself

*/

public void addInPriority(Task other, Comparator priority) {

if (other.prev !=null || other.next !=null || other ==this) throw new IllegalArgumentException();

int c = priority.compare(other, this);

if ( c > 0 || (c == 0 && (this.next !=null || this.prev == null))) {

if ( next ==null || c ==0 || priority.compare(other, next) <0) {

other.next =next;

other.prev = this;

if (next !=null) next.prev = other;

this.next = other;

}

else

next.addInPriority(other,priority);

}else {

if (prev == null || c ==0) {

other.prev = this.prev;

other.next = this;

this.prev = other;

if (other.prev !=null) other.prev.next = other;

}

else prev.addInPriority(other ,priority);

}

// System.out.println("Adding " + other + " to " + this); // perhaps useful for debugging

// TODO: Implement this method. No loops, only recursion.

//

// NB: While TaskList happens to call this method only on the head of the list,

// we can't assume all classes that utilize Task will do so. That is why

// we must consider all scenarios, including those where this method is

// called on a Task in the middle or end of the list.

}

/**

* Remove this item from its list.

* This method must not be called on the head or tail or a list

* because there is no way to update the Task List 's head or tail field.

* This task will be completely disconnected from any other tasks.

* @throws IllegalStateException if the task is first or last in its list.

*/

public void remove() {

if (prev == null ||next == null)

throw new UnsupportedOperationException("cannot head or tail");

//connect previous to next, skipping the current Task

prev.next = next;

next.prev = prev;

prev = null;

next = null;

}

// TODO: Implement this method. No loops or recursion required.

/*

* @see java.lang.Object#toString()

*/

@Override

public String toString() {

return "[Task " + name + "]-{Reward:" + reward + ", Deadline:" + deadline + ", Duration:" + duration + "}";

}

// needed to help test task list invariant. It's "default" access -- not accessible outside the package

/**

* Create a linked list with the given tasks.

* @param tasks series of non-null tasks none of which can have existing prev/next links.

* @throws IllegalArgumentException if any task has non-null prev and next links.

*/

static void connect(Task... tasks) {

for (Task t : tasks) {

if (t.prev != null || t.next != null) throw new IllegalArgumentException("task already in a list");

}

Task p = null;

for (Task t : tasks) {

if (p != null) {

p.next = t;

t.prev = p;

}

p = t;

}

}

}

In the solution for Task.java, the method for addInPriority starts with the line:

if (other.prev != null || other.next != null || other == this) throw new IllegalArgumentException("Task already in a list");

Please explain why the argument cannot be added if any of these conditions apply.

package edu.uwm.cs351;

import java.util.Comparator;

import junit.framework.TestCase;

/** * The Class TaskList. */ public class TaskList {

private Comparator priority; private Task head, tail;

private static boolean doReport = true; private boolean report(String s) { if (doReport) System.out.println("Invariant error: " + s); return false; } /** * Check the invariant: *

1. *
2. The priority cannot be null *
3. Neither {@link #head} nor {@link #tail} is null. *
4. The {@link #head} is a most desirable task and {@link #tail} * is a least desirable task according to any priority that is * not "perverse" (see constructor documentation). *
5. There is nothing before {@link #head} or after {@link #tail} * in the list. *
6. The nodes link with consistent {@link Task#getPrevious()} and {@link Task#getNext()} links * starting at {@link #head} and ending at {@link #tail}. *

* If the invariant is not true, then a reason will be reported. *

* It is not required that the tasks are in priority order * since this is not under control of the Task List. *

* @return true is invariant is true, false otherwise * @see #TaskList(Comparator) {@link #TaskList(Comparator)} for the definition of "perverse" */ private boolean wellFormed() { // priority must not be null if (priority == null) report("Priority is null"); // head must not be null if (head == null) report("Head is null"); // tail must not be null if (tail == null) report("Tail is null"); if(head.getReward()< Task.MAX_REWARD || head.getDeadline() > 0 || head.getDuration()>0)return report ("head might not be most desirable"); if(tail.getReward()> 0 || tail.getDeadline() < Task.MAX_TIME|| tail.getDuration()< Task.MAX_DURATION)return report ("tail might not be least desirable"); if (head.getPrevious() != null) report("Head is not first node in list"); // Nothing must come after tail if (tail.getNext() != null) report("Tail is not the last node in list"); for (Task t = head; t !=tail; t=t.getNext()) { if (t.getNext() == null)return report ("list ends before tail"); if (t.getNext().getPrevious() !=t)return report ("node is not previous of its next"); } return true; } /** * Instantiates a new task list with the given priority comparator. * @param priority the priority comparator this TaskList will use. * It must not be null or "perverse". *

* A perverse priority is one that *

• *
• prefers low-reward tasks, or *
• prefers less urgent tasks, or *
• prefers longer tasks *

* The non-discrimination priority that treats all tasks as equally important * is not perverse, because it doesn't have any preferences. */ public TaskList(Comparator priority) { head = new Task("dummy", Task.MAX_REWARD, 0, 0); tail = new Task("dummy", 0, Task.MAX_TIME, Task.MAX_DURATION); head.addInPriority(tail, priority); this.priority = priority; assert wellFormed() : "invariant fails at end of constructor"; } private TaskList(boolean ignored) {} // DO NOT CHANGE THIS /** * Adds a task to this TaskList. * * @param t the task to add */ public void add(Task t) { assert wellFormed() : "invariant fails at beginning of add"; // We have crafted the head to have priority no less than // all other tasks according to all of our comparators. // Similarly the tail should have priority no greater than // any other task. // That way, the head is always at the beginning of its list, // and the tail at the end. assert (priority.compare(head, t) <= 0) : "Priority is perverse"; assert (priority.compare(t, tail) <= 0) : "Priority is perverse"; tail.addInPriority(t, priority); // Add to list // TODO: if you fail tests, check that you are starting at the // correct end. assert wellFormed() : "invariant fails at end of add"; } /** * Perform all possible tasks in the list that can be completed * before the final deadline and the task's own deadline. We will * treat the deadlines as relative to the moment this method is called. *

* Every time a task is completed, the task's reward is added to * totalReward and currentTime advances by the duration of the task. *

* Tasks should be performed in priority order, * except that no task should even be attempted unless there will be time * to complete it before the final deadline and before its own deadline. *

* Tasks should be removed from the task list as they are completed or discarded. * At the end, the task list should contain only our 'dummy' head node. * @param finalDeadline the deadline that all possible tasks must be completed by * @return reward sum of the rewards of each task completed on time */ public int performAll(int finalDeadline) { assert wellFormed() : "invariant fails at beginning of performAll"} /* This printout may help you to implement this method. System.out.println("My tasks: "); for (Task t = head.getNext(); t != tail; t = t.getNext()) System.out.println(" " + t); */ int currentTime = 0; int totalReward = 0; while (head.getNext() !=tail) { Task t =head.getNext(); t.remove(); if(t.getDeadline() < currentTime + t.getDuration()|| finalDeadline < currentTime + t.getDuration()) continue; currentTime += t.getDuration(); totalReward += t.getReward(); } // TODO: Implement this method. public static class TestInvariant extends TestCase { protected TaskList self;

private Task h0 = new Task("dummy",Task.MAX_REWARD,0,0); private Task h1 = new Task("dummy",Task.MAX_REWARD,0,0); private Task h2 = new Task("dummy",Task.MAX_REWARD,0,0); private Task h3 = new Task("dummy",Task.MAX_REWARD,0,0);

private Task t0 = new Task("dummy",0,Task.MAX_TIME,Task.MAX_DURATION); private Task t1 = new Task("dummy",0,Task.MAX_TIME,Task.MAX_DURATION); private Task t2 = new Task("dummy",0,Task.MAX_TIME,Task.MAX_DURATION); private Task t3 = new Task("dummy",0,Task.MAX_TIME,Task.MAX_DURATION);

private Task ha = new Task("dummy",Task.MAX_REWARD-1,0,0); private Task hb = new Task("dummy",Task.MAX_REWARD,1,0); private Task hc = new Task("dummy",Task.MAX_REWARD,0,1); private Task ta = new Task("dummy",1,Task.MAX_TIME,Task.MAX_DURATION); private Task tb = new Task("dummy",0,Task.MAX_TIME-1,Task.MAX_DURATION); private Task tc = new Task("dummy",0,Task.MAX_TIME,Task.MAX_DURATION-1);

private Task g1 = new Task("Task 1",1,100,5);

private Comparator perverse = (t1,t2) -> t1.getReward() - t2.getReward(); @Override protected void setUp() { self = new TaskList(false); self.priority = perverse; // not used in these tests } protected void assertWellFormed(boolean b) { boolean saved = doReport; try { doReport = b; assertEquals(b, self.wellFormed()); } finally { doReport = saved; } } public void testA() { self.head = null; self.tail = null; assertWellFormed(false); self.tail = t0; assertWellFormed(false); } public void testB() { self.head = h0; self.tail = null; assertWellFormed(false); self.tail = t0; assertWellFormed(false); Task.connect(h0,t0); assertWellFormed(true); } public void testC() { self.head = g1; self.tail = t0; Task.connect(self.head, self.tail); assertWellFormed(false); self.head = ha; self.tail = t1; Task.connect(self.head, self.tail); assertWellFormed(false); self.head = hb; self.tail = t2; Task.connect(self.head, self.tail); assertWellFormed(false); self.head = hc; self.tail = t3; Task.connect(self.head, self.tail); assertWellFormed(false); } public void testD() { self.head = h0; self.tail = g1; Task.connect(self.head, self.tail); assertWellFormed(false); self.head = h1; self.tail = ta; Task.connect(self.head, self.tail); assertWellFormed(false);

self.head = h2; self.tail = tb; Task.connect(self.head, self.tail); assertWellFormed(false);

self.head = h3; self.tail = tc; Task.connect(self.head, self.tail); assertWellFormed(false); } public void testE() { self.head = h0; self.tail = t2; Task.connect(self.head, t3, g1, ha, self.tail); assertWellFormed(true); self.priority = null; assertWellFormed(false); } public void testF() { Task.connect(h0,h1,t1); self.head = h1; self.tail = t1; assertWellFormed(false); Task.connect(h2,t2,t3); self.head = h3; self.tail = t3; assertWellFormed(false); } public void testG() { Task.connect(h0,h1,h2,h3); Task.connect(t0,t1,t2,t3); self.head = h0; self.tail = t3; assertWellFormed(false); } public void testH() { Task.connect(h0,t0); Task.connect(h1,t1); self.head = h0; self.tail = t1; assertWellFormed(false); } public void testI() { Task.connect(h0, g1, h1, g1, t0); self.head = h0; self.tail = t0; assertWellFormed(false); } public void testJ() { Task.connect(h0, g1, h1, t0, h2, t0); self.head = h0; self.tail = t0; assertWellFormed(false); } } } }

In the solution for TaskList.java, the wellFormed method has three checks at the beginning:

if (priority == null) return report("priority is null");

if (head == null) return report("head is null");

if (tail == null) return report("tail is null");

Please explain why each of these situations are bad for the data structure. Why can't these be null even for an empty list?

package edu.uwm.cs351;

import java.util.Comparator;

/**

* The class TyrannyOfTheUrgent.

*

* Return t1 < t2 (comes before) if t1 has an earlier deadline.

* For tasks with equal deadline, compare based on reward.

*/

public class TyrannyOfTheUrgent implements Comparator {

@Override

public int compare(Task o1, Task o2) {

int deadlineDif= o1.getDeadline()-o2.getDeadline();

if (deadlineDif !=0)return deadlineDif;

return o2.getReward()-o1.getReward();

} // TODO: Implement this method.

@Override

public String toString() {

return "Tyranny of the Urgent";

}

private static Comparator instance = new TyrannyOfTheUrgent();

/**

* Gets a single instance of TyrannyOfTheUrgent comparator.

* @return a single instance of TyrannyOfTheUrgent comparator

*/

public static Comparator getInstance() { return instance; }

}

The solution to TyrannyOfTheUrgent's compare method has these three line:

int deadlineDif = o1.getDeadline() - o2.getDeadline();

if (deadlineDif != 0) return deadlineDif;

return o2.getReward() - o1.getReward();