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]?