CS61B, lecture #3 06/21/00. Paul N. Hilfinger with Modifications by B. Chen

Administrative
--------------

1) Your reader may be missing page 51. If you bought your reader before
yesterday, please go to Copy Central to get that page.
 
2) Please address all of your non-private questions to either the
newsgroup or to cs61b@cory.eecs. Both of these are read by all of the TAs
and the instructor, hence you are more likely to get a quick reply.    

Readings  

For today:
Friesen pp. 64-73, 262-274
For tommorow: 
Friesen pp. 75-102, 235-249

More Control Structures
---- ------- ----------

(The term "control structure", by the way, refers to any language
construct that controls what expressions or statements are executed
and in what order.)

In 1968, a certain influential paper in the Communications of the ACM---
"Goto Considered Harmful" by Edsger Dijkstra---started a trend in
programming practice of avoiding the use of "unstructured" control
constructs, meaning those that cannot be explained as either
sequencing ("do this statement and then do the next statement"),
conditional execution (if-then-else), while loops, or function calls.
For example, FORTRAN, C, PL/1, Algol, C++, Pascal, Ada, and countless
other languages allow one to put `labels' on statements (typically,

        ALabel: AStatement;

) and have a control structure (typically 

        goto ALabel;

) that `transfers control' to the statement with the given label.
Dijkstra's observation was that the more one used `goto' in places
where the program could be re-written to use if's and while's, the
more confused one's program tended to be.  His conjecture, in essence,
was that the `structured' constructs corresponded to a disciplined,
systematic, top-down approach to programming (or at least to finished
programs).

His ideas have, for all intents and purposes, prevailed, although
people had a tendency to take `structured programming' as somewhat of
a religion, avoiding goto-like statements even where they do add
clarity.  We see the influence in Java, which abandoned the general
goto in favor of a general exit construct that allows one to leave any
statement (including a complex compound statement) in the middle.  
For example,

     /* Assume that allLists is a list of lists of integers.  Set
        p to the list item containing the integer 'target', or null
        if there is none. */
     List p;      

  SearchLists:
     for (ListList L = allLists; L != null; L = L.tail) {
         for (p = L.head; p != null; p = p.tail) {
             if (p.head == target)
                 break SearchLists;
         }
     }

`SearchLists' is the label of the outer for loop.  We go through all
the lists in allLists, and look down each one for target.  When we
find one, we leave the outer loop immediately, with p set to the right
value.  The control statement `break L' means ``exit the enclosing
statement with label L.''  [Why is p declared outside the loop instead
of in the inner `for'?]  It is legal to leave off the label on the
break statement; a bare `break;' means ``exit the smallest enclosing
loop or switch statement.''  [C and C++ have only the bare break.  It
was a programmer's confusion about this---he thought that bare `break'
would get out of the smallest enclosing loop, switch, or if
statement---that is reported to have brought down a substantial part
of the phone system a few years ago.  AT&T, you see, invented C and
C++.]

The break is rather important in switch statements. The typical such
statement looks like this:

    switch (flag) {
    case 0:
        System.out.print("normal\n");
        break;
    case 1: case 2:
        System.out.print("verbose\n");
        break;
    default:
        System.out.print("taciturn\n");
        break;
    }
    ...

Depending on whether the variable flag is 0, 1, 2, or something else,
the program executes one of the prints and then goes immediately to
the "...".  Without the breaks, case 0, for example, would print all
three messages.  (Note on switch: All the case's must be different,
and all must be constant integral values of type int, short, byte, or
char). 

All the forms of loop are just variations on an infinite loop with a
break.   E.g.,

        Loop                            Is the same as
   ------------------------------------------------------------------

   while (condition)                    while (true) {
        Statement;                           if (! condition)
                                                break;
                                             Statement;
                                        }

   do {                                 for (;;) {  // Same as while(true)
       Statement;                            Statement;
   } while (condition);                      if (! condition)
                                                 break;
                                        }

[`for (;;) S' is the same as `while (true) S' because the test
(between the two ';'s) defaults to true, and the missing initializer
(before the first ';') and next statement (after the last ';') are
simply null statements, which do nothing.]

The `continue' statement is just a special form of break that ends the
current iteration of a loop:

        Loop                            Is the same as
   ------------------------------------------------------------------

   while (condition) {                  while (condition) {
       Statement1;                        LoopBody: {
       if (condition)                         Statement1;
         continue;                            if (condition)
       Statement2;                              break LoopBody;
   }                                          Statement2;
                                          }
                                        }

   for (start; test; next) {            start;
       Statement1;                      while (test) {
       if (condition)                     LoopBody: {             
         continue;                            Statement1;         
       Statement2;                            if (condition)      
   }                                            break LoopBody;   
                                              Statement2;         
                                          }                       
                                          next;
                                        }                         

In the case of a for loop, continue takes us to just before the third
clause of the for.

A common use of `break' is in the `time-and-a-half' loop, where there
is something one does each time through the loop BEFORE the
test:

        Instead of                      Write the equivalent
    -------------------------------------------------------------------
    X = stream.readInput();             while (true) {
    while (! stream.eof()) {                X = stream.readInput();
        process(X);                         if (stream.eof()) 
        X = stream.readInput();                 break;
    }                                       process(X);
                                        }


Arrays
======

Quick Review (from lecture 2)
------------

Values in Java are of two kinds: primitive types---numbers (including
characters) and booleans---and reference types.  Reference types are
what mostly saw in Scheme---pointers to things.  In Java, the
reference types include everything in the standard Java library, all
new types introduced by the programmer, and arrays.  We'll start with
arrays.


You can visualize an "array object" in Java as a collection of boxes,
numbered in sequence from 0, each containing a value.  Since array
types are reference types, any named variable or expression that "has
an array value" actually contains a pointer to an array object; the
object itself has no name.  Thus, the declaration

        int [] x;

means "at any time, x either contains a null pointer (like '() in
Scheme) or it contains a pointer to something like this:

        [ 42 | -3 | 1 ]
           0   1    2

The numbers underneath indicate the "indices" (plural of "index") of
the boxes.  Each box contains an int (integer representable in 31-bits
plus sign).  The elements in the object pointed to by x in this case
would be called x[0] (containing 42), x[1] (containing -3), and x[2]
(containing 1).  Finally, if x points to an array object, then
x.length contains the number of elements in that object.  In the
example above, x.length is 3 (NOT 2).

What makes arrays particularly interesting is that the number in
square brackets doesn't have to be a numeral; it can be *computed*.
We'll see numerous examples.  Here is one:

Example: Circular Shift
-------- -------- -----

   /** Move the value initially in A[k] to A[(k+1) % A.length]---that 
    *  is shift all elements "to the right" (toward higher indices), 
    *  moving the last to the front. */
   void shiftRight(int[] A)
   {
     if (A.length == 0)
       return;
     int tmp = A[A.length-1];
     for (int i = A.length-2; i >= 0; i -= 1)  // Why backwards?
       A[i+1] = A[i];
     A[0] = tmp;
   }


Creating Arrays
-------- ------

When an array variable is defined, its value is initially 'null' (the
pointer to nothing).  Thus,

    /** Returns an array of length N whose elements all contain K. */
    int[] makeConstArray(int N, int k) {    // WARNING: BAD function
        int[] result;

        for (int i = 0; i < N; i += 1)
            result[i] = k;           // Problem here.
    }

is erroneous; at the point of the assignment, `result' is not pointing
at an array object.

   >>>Declaring an array variable does not put a useful value in it.<<<

We want makeConstArray to create an array, so we write

    int[] makeConstArray(int N, int k) {
        int[] result = new int[N];
        // result now points to an array object; result.length = N

        for (int i = 0; i < N; i += 1)
            result[i] = k;
    }

The `new' expression generally creates new objects and returns a
pointer to them. With a trailing [...], it creates a new array.

Once an array object is created, its length may not be changed.
Attempting to store into element number N of an N-element array is an
error (so is storing into element -1).  However, we can get the
effect of `resizing' an array by simply making the variable with
which we refer to it point to a new, bigger (or smaller) array object
containing a copy of its contents, perhaps like this:

     /** Return a pointer to a new array object of size NEWSIZE,
      *  whose first elements (up to the first A.length) are
      *  copied from A, and whose other elements (if any) contain
      *  INIT. */
     int[] resize(int[] A, int newSize, int init)
     {
        int[] newA = new int[newSize];
        int k;
        for (k = 0; k < A.length; k += 1)  // Copy the old contents
           newA[k] = A[k];
        for (; k < newSize.length; k += 1) // Initialize any new values.
           newA[k] = init;
        return newA;
     }

[What's with that second for loop?  What happens if newSize <
A.length?]  Now we can use this to make an array bigger, in effect:

     table = resize(table, table.length*2, 0);  // Double size of table.

Arrays can contain anything, including arrays.  To get the effect of
a rectangular matrix, such as

        [ 1   5   9  ]
        [ 6   7   2  ]
        [ 8   3   4  ]

We create an array of arrays

  magic: [*]--->[*]----->[ 1 | 5 | 9 ]
                [*]----->[ 6 | 7 | 2 ]
                [*]----->[ 8 | 3 | 4 ]

Thus, magic[0] points to [ 1 | 5 | 9 ] and so magic[0][1] == 5.  Creating
magic requires some thought.  We already know that

   int[][] magic;

doesn't suffice; it just gets us to

  magic: [/]  (contains null)

The next step is

   int[][] magic = new int[3][];

which gets us to

  magic: [*]--->[/]    These three boxes contain null.
                [/]
                [/]

We could now get to the full result with a loop:

   int[][] magic = new int[3][];
   for (int i = 0; i < 3; i += 1) magic[i] = new int[3];

This last fragment is so common that the Java designers gave us a
break and said that

   int[][] magic = new int[3][3];

is short for it.

We still haven't initialized the magic array.  We could do it with a
bunch of assignments or some computation.  When the initial contents
of an array are some specific constant, it is useful to be able to
specify them explicitly, which we can do with an array initializer.
The declaration

   SomeType[] var = { val0, val2, ..., valk };

is equivalent to

   SomeType[] var = new SomeType[k+1];
   var[0] = val0; var[1] = val1; ...

Furthermore, the val's can themselves be array initializers, so that

   int[][] magic = { { 1, 5, 9 }, { 6, 7, 2 }, { 8, 3, 4 } };

creates our array for us.

Because each element of an array of arrays is a pointer, nothing
forces us to make all the rows the same length, or even all there:

   int[][] uneven = { { 1, 2 }, null, { 3 }, { 4, 5, 6 } };

is equivalent to

   int[][] ragged = new int[4][];
   ragged[0] = new int[2]; ragged[0][0] = 1; ragged[0][1] = 2;
   ragged[1] = null;
   ragged[2] = new int[1]; ragged[2][0] = 3;
   ragged[3] = new int[3]; ...

WARNING: for certain technical reasons, array initializers may ONLY
appear to the right of `=' in variable declarations.  You can't write

        f({1, 2, 3});

It's a shame, but There Are Reasons (not great ones, but reasons
nevertheless).

A test of your understanding.  Suppose that "magic" is as above, and I
write

   int[][] magic2 = magic;
   int[][] magic3 = new int[3][];
   for (int i = 0; i < 3; i += 1) magic3[i] = magic[i];
   magic3[2] = null;  magic2[1] = null; magic[0][1] = 2;

What are magic[2], magic[1], magic2[2], magic3[1], magic2[0][1], and
magic3[0][1]?   Then, after

   magic = null;

what is magic2[0][1]?