CSC152 2004F, Class 53: Array-Based Lists (2)

Admin:
* Questions on the exam?
  * DUE FRIDAY!
* Project stuff due tomorrow at 11:00 a.m.  I will attempt to merge and fix.
* Grade information released next Monday.

Overview:
* Deleting elements
* Checking that lists have changed
* Expanding cursors
* Designing an OrderedList ADT
* Sketch of array-based implementation

Review:
* Implementing lists with arrays
* Cursors hold positions in the array

Options for deletion
* "Leave a hole" (and update the cursor to skip holes)
* Shift everything left O(n)
* Shove the last thing into the place we just freed O(1)
* It works!

How do we know when our cursors are no longer valid?
* Question: What does "valid" mean?
  * A cursor should no longer be usable after the underlying list has been changed.  Such a cursor is "invalid".
* Pause to think for two minutes
  * Leigh's suggestion: Make a *copy* of the array when you create the cursor and compare it to the current array.
    * Positives: Could actually work.
    * Negatives: 
      * Lots of copies of the array waste space and is unappealing
      * Spends a lot of time scanning the array each step in the cursor
  * The list could keep track of its cursors and tell each of them that they are invalid.  (Or, better yet, only tell the ones that have to be invalid that they are invalid.)
    * Positives: Can be specific about which ones are invalid.
    * Negatives: Hmmm ... how do we keep track of the cursors.  I know!  A list!
    * Expensive to scan through all the cursors
  * Keep a boolean field that says whether or not the list has changed
    * Problem: We create a new cursor, it checks the field, and ...
  * Keep an integer field that gets incremented at each change.  Cursors compare their integer to that field.
    * Negative: Slight overhead
* Alternative: "It's the client's problem!"

What relationship should Cursor and SimpleCursor have?
* Cursor is a subinterface of SimpleCursor
  * Every method in SimpleCursor is in Cursor, so it seems like a natural relationship.
  * It simplifies the lists, since they can just take SimpleCursors as parameters (rather than having two sets of methods)
* SimpleCursor is a subinterface of Cursor
  * Doesn't make sense b/c Cursor provides more methods.
* The two are "unrelated"
  * They have different methods.

See notes on implementation

/Ordered Lists/

* What methods should OrderedList provide?
* Hint: They should relate to addition and removal