Amir Kamil
Summer 2001
Midterm 1 Solutions

1. 
class ZQueue {

  public ZQueue() {
    q = new SList(null, null); // sentinel node
  }

  public void add(ZPriority e) throws IllegalArgumentException {
    SList temp = q;
    SList tnext = q.next;
    while (tnext != null) {
      if (e.getPriority() == ((ZPriority) tnext.data).getPriority()) {
        throw new IllegalArgumentException();
      } else if (e.getPriority() > 
                 ((ZPriority) tnext.data).getPriority()) {
        break;
      }
      temp = tnext;
      tnext = tnext.next;
    }
    temp.next = new SList(e, tnext);
  }

  public ZPriority remove() throws NoSuchElementException {
    if (q.next == null) { // no elements in queue
      throw new NoSuchElementException();
    } else if (q.next.next == null) { // one element in queue
      ZPriority val = (ZPriority) q.next.data;
      q.next = null;
      return val;
    } else { // second-most priority in second node
      ZPriority val = (ZPriority) q.next.next.data;
      q.next.next = q.next.next.next;
      return val;
    }
  }

  SList q; // sentinel node; storage starts in q.next

}

2.
class SodaMachine {
  Soda[] sodas;
  int position;

  public SodaMachine(int capacity) {
    sodas = new Soda[capacity];
    position = 0;
  }

  public Soda buySoda() {
    Soda s = sodas[position];
    sodas[position] = null;
    if (position = sodas.length - 1) {
      position = 0;
    } else {
      position++;
    }
    return s;
  }

  public Soda stealSoda() {
    Soda s = sodas[position];
    sodas[position] = null;
    return s;
  }

  public int restock() {
    int num = 0;
    position = 0;
    for (int i = 0; i < sodas.length; i++) {
      if (sodas[i] == null) {
        sodas[i] = new Soda();
        num++;
      }
    }
    return num;
  }

}

3.
a) zop() swaps the elements in x at positions i and p
b) zap() sorts the array from position s and on in descending order. 
   For each position starting from s, it finds the largest element in 
   the rest of the array and swaps it with the element at s.  
c) For null x:

   zop(null, 0);

   This will result in a NullPointerException;

   For negative s:

   zop(x, -2); // x as in c)

   This will result in an ArrayIndexOutOfBoundsException.

   For x in which elements are duplicated:

   x = {1(#1), 1(#2), 1(#3)};
   zop(x, 0);

   This results in x = {1(#3), 1(#2), 1(#1)}, i.e. the sort is not 
   stable.

4.
NOTE: It's possible that a) was in different order on some tests.
a) 1. prints out "f2() in P"
   2. runtime error: ClassCastException
   3. executes, prints nothing
   4. compile-time error
   5. prints out "f2() in P"
   6. prints out "f2() in P"
b) 1. will not compile: since where() was declared private in P, its 
      child class D does not inherit where() and cannot access the 
      method.
c) Either:
   a) s1 is an instance variable and foo is a non-static method
   b) s1 is a class variable and foo is either static or non-static
   In either case, foo assigns directly to s1 rather than to the 
   argument it receives.