cs231 Lecture Notes
Week 3, Wednesday

Invariants / preconditions
--------------------------

Invariant:  something that is provably true at some point in a program

Precondition: a condition that a method requires to be true when it
	      executes, in order to work correctly

Postcondition: a condition that is provably true at the end of a method
	       (provided that the precondition is satisfied)

What are the preconditions for isFlush?  isPair?  isStraightFlush?

What should a method do about its preconditions?

1) fail: the method says, "if you (the caller) don't satisfy my
   preconditions, I simply won't do what I said I would do."

   Often, that means generating a run time error (for example,
   if rankHist is null)

   Sometimes, it means just not doing the right thing.  For example,
   what does findBisect do if the deck is not actually in order?

2) check: some preconditions can be checked cheaply

   (rankHist != null)

   some can be checked, but they are a little expensive

   (is the array sorted)

   some cannot be checked (for various reasons).

   Obviously, this last group is the most unpleasant.

3) eliminate (minimize)

   it is often a good idea to both check and correct missing
   preconditions.  For example:

   if (rankHist == null) makeRankHist ();

PRECONDITIONS ARE THE MOST IMPORTANT THINGS TO INCLUDE IN COMMENTS.

The comments at the beginning of a method are like a contract.
They describe what the method does, but they include a catch

     The method is only guaranteed to work if the preconditions
     are satisfied.

Please read Appendix C.3, pages 496 through 501 for more
information about Proving Programs Correct.


Linked Data Structures
----------------------

Review of objects and references.

When you declare a new Object variable, you get space for
a reference, and by default it is set to null.

To get space for the object you have to use new.

Drawing pictures of references:  circles and arrows and a paragraph
on the back of each one explaining what each one is.

By now we are familiar with the notion that a variable can
contain a reference to an object.

We also know that instance variables are the elements that make
up object.

It follows (and turns out to be true) that objects can contain
references to other objects.

One of the most basic Data Structures that uses references in
this way is a LinkedList.

LinkedLists
-----------

In our implementation, a linked list is made up of a sentinal
that has type LinkedList followed by zero or more nodes that
have type ListNode.  The instance variables for these types
are:

public class LinkedList {
  int length;
  ListNode firstNode;
}

class ListNode {
  String airport;
  ListNode link;
}

Notice that LinkedList objects contain a reference to a ListNode.

Also, ListNode objects contain a reference to another ListNode.

Does that mean a ListNode object can contain a reference to itself?

Yes, although it is usually not useful to do so.

The String in a ListNode is an arbitrary bit of data we will be
using as a running example for this chapter.  In general, lists
can contain any kind of data (including other lists).

Constructors
------------

We'll assume there are generic constructors for these types:

  public LinkedList () {
    length = 0;
    firstNode = null;
  }

  public ListNode (String airport, ListNode link) {
    this.airport = airport;
    this.link = link;
  }

How do we build a list?

    // create an empty list
    List list = new List ();

    // create three new nodes, unlinked
    ListNode node1 = new ListNode ("PWM", null);
    ListNode node2 = new ListNode ("ORD", null);
    ListNode node3 = new ListNode ("OAK", null);

    // link up the nodes
    node1.link = node2;
    node2.link = node3;
    node3.link = null;

    list.firstNode = node1;
    list.length = 3;

What are the requirements for a list to be well-formed?

1) the last node should have link==null

2) if we start at list.firstNode and traverse the list until
   we get to the null reference at the end, the total number
   of nodes should equal length


Traversal
---------

How do you traverse a List?

  public void print () {
    System.out.print ("(");

    // start at the beginning of the list
    ListNode node = firstNode;

    // traverse the list, printing each element
    while (node != null) {
      System.out.print (node.airport);
      node = node.link;
      if (node != null) {
        System.out.print (", ");
      }
    }
    System.out.println (")");
  }    


OR, often

    for (ListNode node = firstNode; node != null; node = node.link) {

    }

This idiom is as common as traversing an array (and should
be as foolproof).


Traversing a list backward
--------------------------

There is also a standard idiom for traversing an array backward,
using recursion.  Here is what it looks like.

In LinkeList:

  public void printBackward () {
    System.out.print ("(");
    ListNode.printBackward (firstNode);
    System.out.println (")");
  }    

In ListNode:

  public static void printBackward (ListNode node) {
    if (node == null) return;
    printBackward (node.link);
    System.out.print (node.airport + ", ");
  }