Debugging (2)

Admin
* Welcome back again!
* Code for today will be in Examples/DLL.  (There's also an Examples/Lists
  where I was trying a different approach, but we'll be working in 
  Examples/DLL.)

Overview
* Review
* Another domain: Lists
  * What is a list?
  * API and Unit Tests
  * Implementation
  * Testing and debugging

Review
* Programs have bugs
* Learn a debugger, not only can it do the printf statements you use,
  it can do other stuff, too.
* We're moving on to debugging of C programs with memory management
  issues.

What is a list?
* A collection of values that are in some sort of order
  "Order" != "Sorted"
  "Order" = One thing is first, one thing is last, every other thing
     has exactly one predecessor and one successor.
* What distinguishes lists from arrays?  (What's the diff between
  a list and a dynamic array?)
  * Arrays emphasize indexed access: You can *quickly* get and set
    elements using their numeric position.
  * Lists are more dynamic: You can quickly insert or delete
    elements in the middle of the list.  "More dynamic than dynamic
    arrays."

Design issue: How do you look at the elements of the list?
* We need a "cursor" to keep track of where we are in the list.
* Good design: Cursors are independent values, so that you can
  have multiple cursors.
* Typical (and easier) design: Each list has an associated cursor which
  we call the "current" element.

  In terms of the ADT, it's a difference between

  List *l;
  ...
  reset (l);
  while (! at_end(l))
    {
      printf ("%s, ", current (l));
      advance (l);
    }
  printf ("%s\n", last (l));

vs.

  List *l;
  Cursor *c;
  c = new_cursor (l);
  while (! at_end (c))
    {
      printf ("%s, ", c.c
      ...

    }

Implementing the first option

typedef struct List 
  {
    Node *head;
    Node *tail;
    Node *current;
  } List;

int
advance (Node *current)
{
  if (current == tail)
    return 0;
  current = current->next;
  return 1;
} // advance

----

What's the API (.h file, Java interface, ...)?  And what are the unit tests?
* What are the operations we can do with lists?
  (Ignoring, for the time being, how we do those operations.)
* We're doing bi-direction lists with current

/**
 * Advance to the next element in the list.
 * Problems: What if it's the last element?  What if there are no
 *   elements?
 * Preconditions: ! empty (l), ! at_end (l)
 */
int advance (List *l);

int retreat (List *l);

/**
 * Tests!
 */
   // Create the list {a,b,c}
   // Reset the cursor to the front
   // Advance to the next element
   advance (l);
   // Make sure that it's b
   check (current (l), "b");
 
/**
 * Try to add an element to the list.
 */
int add_to_head (List *l, char *str);
int add_to_tail (List *l, char *str);
int add_before (List *l, char *str);    /* Pre: Nonempty. */ /* May be expensive. */
int add_after (List *l, char *str);     /* Pre: Nonempty. */

/**
 * Tests.
 */

l = list_new ();
add_to_head (l, "a");
check (l, {"a"});
add_to_head (l, "b");
check (l, {"b", "a"});
add_to_tail (l, "c");
check (l, {"b", "a", "c"});
reset (l);
add_after (l, "d");
check (l, {"b", "d", "a", "c"});
....

/**
 * Create a new list.  Return NULL upon failure.
 */
List * list_new (void);

// Tested implicitly by other unit tests.

/**
 * Move the cursor to the front of the list.
 */
int reset (List *l);

// Tested implicitly by other unit tests.

/**
 * Check to see that a list has the same elements as an array.
 */
int check (List *l, char *strings[]);

// Do we test the testers?

/**
 * Destroy the list.
 */
int list_free (List *l);

/**
 * Clear the elements, preserving the framework.
 */
int list_clear (List *l);

/**
 * Is the list empty?
 */
int is_empty (List *l);

/**
 * Is the cursor at the end?
 */
int at_end (List *l);