CSC152 2004F, Class 50: Pause for Breath

Admin:
* DO NOT USE OTHER PEOPLE'S ACCOUNTS!
* Homework: Reread "Lists with Current Considered Harmful" (see link in Homework 35)
* What can we reasonably get done for next week?
  * No public presentation
  * Perhaps a little extra work next week
* Exam distributed tomorrow

Overview:
* Failed Attempt to Integrate
* Designing Lists

New Topic: Lists
* A non-indexed (by integer or objects) dynamic collection of elements that you can iterate (move through/look at/visit one at a time)
* Three kinds of lists:
  + Simple (little control over order)
  + Ordered (complete control over order)
  + Sorted (a comparator controls the order)

Task: How to we represent this "philosophy" for simple lists in terms of methods?

/**
 * Add an element somewhere in the list.
 */
public void add(Object addme);

/**
 * Remove an element from the list.
 * We have not yet decided what to do if it's not there.
 */
public void remove(Object removeme);

/**
 * Determine if the list is empty.
 */
public boolean isEmpty();

PROBLEM: HOW DO WE ITERATE?

IDEA (Ahlgren 2004): Lists keep track of where they are and you can ask for the next value

IDEA, revisited: Lists permit you to get Cursors, and Cursors keep track of where they are.

public SimpleCursor getCursor();

public interface SimpleCursor
{
  /**
   * Get the next unvisited element in the list.
   *
   * @pre The list is nonempty.
   * @pre There is an unvisited element.
   * @pre The list has not been modified by add or delete since
   *      this cursor was created.
   */
  public Object next()
  	throws NoSuchElement;

  /**
   * Determine if this cursor is at the end of the list.
   * (That is, has not visited any elements.)
   */
  public boolean atEnd();
}

SAM DOES NOT WANT TO INCLUDE

/**
 * Search for an element in the list.
 */
public ??? searchFor(Object findme);

/**
 * Delete the first element.
 */
public void deleteFirst();

/**
 * Get the first element of this list.
 *
 * @pre
 *   The list is nonempty.
 * @exception EmptyList
 *   If the list is empty.
 */
public Object first()
  throws EmptyList;

Making cursors fancier:

* resetToFront
* setToEnd
* previous
* Have delete take a cursor as a parameter

Sample code to print all the values in list l
i
	Cursor c = l.getCursor();
	while (!c.atEnd())
		pen.println(c.next());

	Or
	// The while loop exits at the end of the list
	// because c.next() throws an exception only when
	// it goes beyond the end of the list.
	try {
		while (true)
			pen.println(c.next());
	}
	catch (AtEndException aee) { }
	
Problem:

* What happens to the cursors if you add or delete an element?