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

What is a list?
* A list is an ADT that allows us to store data so that
  we can dynamically add members to that data structure
  without having to pre-allocate the full size to the data
  structure in the beginning
* What distinguishes it from a set?
* What distinguishes it from a dynamic array?
  * Implementation details

* Sets (and bags): Unordered; In lists and arrays, elements have
  predecessors and successors
* Arrays emphasize indexed access - Assumption that such operations
  are quick: O(1), amortized; Except in Java, we don't think of lists
  as indexed, or at least not efficiently indexed
* Both arrays and lists are often dynamic in that you can expand them
  as necessary
* Lists permit efficient insertion and deletion "anywhere" in the list;
  Arrays permit efficient insertion and deletion at the end (and maybe
  the front)

The API helps us understand how we insert and delete
* Lists should have "cursors" that let us know "here we are in the list"
* Bad design: Each list has one cursor (current element)
* Good design: Each list can have an arbitrary number of cursor
* We'll do the bad design

API for bi-directional lists of strings (implemented as doubly-linked lists)

* Construct/Destruct
  struct dll *dll_new ();
  int dll_free (struct dll *lst);
                // Tests
                // 1. Can we create a new list?
                // 2. When we create that list, is the length 0
                // 3. If we try to get the first element of the list,
                //    we should get an error.  (Although this may
                //    violate preconditions.)

* Basic information
  int length (struct dll *lst);

* Adding elements
  // Add an element to the beginning
  int dll_prepend (struct dll *lst, char *str);
  // Add an element to the end
  int dll_append (struct dll *lst, char *str);
  // Add an element after
  int dll_add_after (struct dll *lst, char *str);
  // Add an element before the cursor
  int dll_add_before (struct dll *lst, char *str);
  // Replace the current element
  int dll_replace (struct dll *lst, char *str);

* Removing elements
  // Delete the current element. 
  //   Design question: Where does the cursor go after deletion
  //   * Advance the element to the next element (or 
  //     back it up to the last element, if it was the last element)
  //   * It is no longer valid, and has to be reset
  //   * Back up ...
  int dll_delete (struct dll *lst);
  // Might also want to delete the first and last elements

* Getting elements
  // Get the current element from the list
  char *dll_current (struct dll *lst);
                // Add "a" to the empty list
                // Get the current element, it should be "a"
  // Get the head and the tail (first and last elements)

* Manipulating the current element (cursor)
  dll_to_head
  dll_to_tail
  dll_advance
  dll_retreat