University of Virginia, Department of Computer Science CS201J: Engineering Software, Fall 2003

Notes: Friday 21 November 2003
 Schedule

• Monday, 24 November: Review Questions (email to me by 5pm)
• Tuesday, 25 November: PS6 Due
• Tuesday, 2 December: Exam 2 Out
• Friday, 5 December: Exam 2
Subtyping

The ForwardIterator and ForwardSortedIterator datatypes are specified below. According to the substitution principle:

1. Can ForwardIterator be a subtype of ForwardSortedIterator?
2. Can ForwardSortedIterator be a subtype of ForwardIterator?
Consider the signature, method and properties rules.

```public class ForwardIterator implements java.util.Iterator {
// OVERVIEW: A mutable collection of Objects that can be traversed.
//    A ForwardIterator is a tuple < seq, p < where
//    seq is a sequence of Object elements and p is a yield pointer
//   that identifies the next element to yield. A typical ForwardIterator is
//           < [x0, x1, ..., xn-1], p >
//    If p is between 0 and n-1, then the next element to yield is
//    x_p.  If p is greater than n-1, there are no more elements to yield.

// MODIFIES: this
// EFFECTS: Adds o to the end of the sequence.  Does not modify
//    the yield pointer.

public void deleteElement(Object o) throws NoSuchElementException
// MODIFIES: this
// EFFECTS: If this contains o, removes first occurance of o from this.
//    Otherwise, throws NoSuchElementException. Does not modify p.

public void remove() throws IllegalStateException
// MODIFIES: this
// EFFECTS:  Removes the element from a sequence that is just before
//    the yield pointer and decreases the yield pointer by 1.
//    If the yield pointer is 0 (there is no element before the
//    yield pointer) throws IllegalStateException.
//
//    e.g., if this_pre = < [ obj1, obj2, obj3 ], 1 >
//             this_post = < [ obj2, obj3 ], 0 >.

public boolean hasNext()
// EFFECTS: Returns true if there are more elements in a sequence to
//    yield (p < n - 1).  Otherwise, returns false.

public Object next () throws NoSuchElementException
// MODIFIES: this
// EFFECTS: If there are more elements to yield, returns the
//    next element and advances the yield pointer.  Otherwise,
//    throws NoSuchElementException.
//
//    e.g., if this_pre = < [ obj1, obj2, obj3 ], 1 >
//    next returns obj2 and this_post = < [ obj1, obj2, obj3 ], 2 >

public void restart()
// MODIFIES: this
// EFFECTS:  Sets the yield pointer to the first element in a
//    sequence: this_post = < this_pre.seq, 0 >
}
```

```public class ForwardSortedIterator implements Iterator {
// OVERVIEW: A mutable collection of Comparable objects that can be traversed
//    in sorted order.  A ForwardSorterIterator is a tuple < els, p <
//    where els is a set of Comparable elements and p is a yield pointer
//    that identifies the next element to yield. A typical ForwardSortedIterator is
//           < { x0, x1, ..., xn-1 }, p >
//    If p is between 0 and n-1, then the next element to yield is the
//    element of seq that comparably greater than p elements of seq.  The elements must
//    all be comparably distinct (that is, x_i.compareTo (x_j) == 0 implies i == j).

public void addElement (Comparable o) throws DuplicateEntryException
// MODIFIES: this
// EFFECTS: If o.compareTo (x_i) == 0 for any x_i element of this.els, throws
//    DuplicateEntryException.  Otherwise, adds o to els.  Does not modify the
//    yield pointer.

public void deleteElement(Object o) throws NoSuchElementException
// MODIFIES: this
// EFFECTS: If this contains o, removes o from this.  Otherwise, throws
//     NoSuchElementException. If o has been passed in the yield sequence
//     (that is o is greater than less than p elements of els), decreases
//     p by 1.

public void remove() throws IllegalStateException
// MODIFIES: this
// EFFECTS:  Removes the element from a sequence that would have
//    been yielded on the preceeding call to next.  If there is
//    no such element, throws IllegalStateException.

public boolean hasNext()
// EFFECTS: Returns true if there are more elements in a sequence to
//    yield (p < n - 1).  Otherwise, returns false.

public Object next () throws NoSuchElementException
// MODIFIES: this
// EFFECTS: If there are more elements to yield, returns the
//    element of els that is greater than p elements of els and
//    advances the yield pointer.  Otherwise, throws
//    NoSuchElementException.

public void restart()
// MODIFIES: this
// EFFECTS:  Sets the yield pointer to the first element in a
//    sequence: this_post = < this_pre.els, 0 >
}
```