CS 537
Notes on Java


Contents


Introduction

The purpose of these notes is to help students in Computer Sciences 537 (Introduction to Operating Systems) or 536 (Introduction to Programming Langauges and Compilers) at the University of Wisconsin - Madison learn enough Java to do the course projects. This course will assume that all students are Java programmers at the level of someone who has completed CS 367 with an A or AB. Just about everything you will need to know about Java is at least mentioned in these notes, together with comments about the differences from C++, but if you're a novice Java programmer, you may need a gentler introduction. If you are familiar with C++ but not Java, check out Horwitz's notes comparing Java with C++. Java for C++ Programmers from CS 368. See The Java Tutorial and/or the The Java Programming Language by Arnold et al for lots more information about Java.

A decade ago, the Computer Sciences Department converted most of its classes from C++ to Java as the principal language for programming projects. CS 537 was the first course to make the switch, Fall term, 1996. At that time virtually all the students had heard of Java and none had used it. Over the next few years more and more of our courses were converted to Java until, by 1998-99, the introductory programming prerequisites for this course, CS 302 and CS 367, were taught in Java. The department now offers a "C++ for Java Programmers" course, CS 368.

The remainder of these notes provide some advice on programming and style that may be helpful to 536 and 537 students. In particular, we describe threads and synchronized methods, Java features useful for 537 that you probably haven't seen before.

Note that some of the examples assume that you are using Java version 1.5 or later.

The Java API

The Java language is actually rather small and simple - an order of magnitude smaller and simpler than C++, and in some ways, even smaller and simpler than C. However, it comes with a very large and constantly growing library of utility classes. Fortunately, you only need to know about the parts of this library that you really need, you can learn about it a little at a time, and there is excellent, browsable, on-line documentation. These libraries are grouped into packages. One set of packages, called the Java 2 Platform API comes bundled with the language (API stands for "Application Programming Interface"). At last count, there were over 166 packages in the Platform API, but you will probably only use classes from three of them:

Names, Packages, and Separate Compilation

Case is significant in identifiers in Java, so if and If are considered to be quite different. The language has a small set of reserved words such as if, while, etc. They are all sequences of lower-case letters. The Java language places no restrictions on what names you use for functions, variables, classes, etc. However, there is a standard naming convention, which all the standard Java libraries follow, and which you must follow in this class.

A more extensive set of guidelines is included in an online Code Conventions document and in the Java Language Specification itself.

Simple class definitions in Java look rather like class definitions in C++ (although, as we shall see later, there are important differences).

    public class Pair { int x, y; } 
Each class definition should go in a separate file, and the name of the source file must be exactly the same (including case) as the name of the class, with ".java" appended. For example, the definition of Pair must go in file Pair.java. You can compile this class with the command
    javac Pair.java 
Assuming there are no errors, you will get a file named Pair.class.

There are exceptions to the rule that requires a separate source file for each class but you should ignore them. In particular, class definitions may be nested. However, this is an advanced feature of Java, and you should not nest class definitions unless you know what you're doing.

There is a large set of predefined classes, grouped into packages. The full name of one of these predefined classes includes the name of the package as prefix. For example, the library class java.util.Random is in package java.util, and a program may use the class with code like this:

    java.util.Random r = new java.util.Random();
The import statement allows you to omit the package name from one of these classes. A Java program that includes the line
    import java.util.Random;
can abbreviate the use of Random to
    Random r = new Random();
You can import all the classes in a package at once with a notation like
    import java.util.*;
The package java.lang is special; every program behaves as if it started with
    import java.lang.*;
whether it does or not. You can define your own packages, but defining packages is an advanced topic beyond the scope of what's required for this course.

The import statement doesn't really "import" anything. It just introduces a convenient abbreviation for a fully-qualified class name. When a class needs to use another class, all it has to do is use it. The Java compiler will know that it is supposed to be a class by the way it is used, will import the appropriate .class file, and will even compile a .java file if necessary. (That's why it's important for the name of the file to match the name of the class). For example, here is a simple program that uses two classes:

    public class HelloTest {
        public static void main(String[] args) {
            Hello greeter = new Hello();
            greeter.speak();
        }
    }
    public class Hello {
        void speak() {
            System.out.println("Hello World!");
        }
    }
Put each class in a separate file (HelloTest.java and Hello.java). Then try this:
    javac HelloTest.java
    java HelloTest
You should see a cheery greeting. If you type ls you will see that you have both HelloTest.class and Hello.class even though you only asked to compile HelloTest.java. The Java compiler figured out that class HelloTest uses class Hello and automatically compiled it. Try this to learn more about what's going on:
    rm -f *.class
    javac -verbose HelloTest.java
    java HelloTest

Values, Objects, and Pointers

It is sometimes said that Java doesn't have pointers. That is not true. In fact, objects can only be referenced with pointers. More precisely, variables can hold primitive values (such as integers or floating-point numbers) or references (pointers) to objects. A variable cannot hold an object, and you cannot make a pointer to a primitive value.

There are exactly eight primitive types in Java, boolean, char, byte, short, int, long, float, and double.

A boolean value is either true or false. You cannot use an integer where a boolean is required (e.g. in an if or while statement) nor is there any automatic conversion between boolean and integer.

A char value is 16 bits rather than 8 bits, as it is in C or C++, to allow for all sorts of international alphabets. As a practical matter, however, you are unlikely to notice the difference.

There are four integer types, each of which represents a signed integer with a specific number of bits.

TypeBitsMin ValueMax Value
byte8-128127
short16-32,76832,767
int32-2,147,483,6482,147,483,647
long64-9,223,372,036,854,775,808 9,223,372,036,854,775,807

The types float and double represent 32-bit and 64-bit floating point values.

Objects are instances of classes. They are created by the new operator. Each object is an instance of a unique class, which is itself an object. Class objects are automatically created whenever you refer the class; there is no need to use new. Each object "knows" what class it is an instance of.

    Pair p = new Pair();
    Class c = p.getClass();
    System.out.println(c);  // prints "class Pair"
Each object has a set of fields and methods, collectively called members. (Fields and methods correspond to data members and function members in C++). Like variables, each field can hold either a primitive value (a boolean, int, etc.) or a reference, which is either null or points to another object. When a new object is created, its fields are initialized to zero, null or false as appropriate, but a constructor (a method with the same name as the class) can supply different initial values (see below). By contrast, variables are not automatically initialized. It is a compile-time error to use a variable that has not been initialized. The compiler may complain if it's not "obvious" that a variable is initialized before use. You can always make it "obvious" by initializing the variable when it is declared:
    int i = 0;

Arguments to a Java procedure are passed "by value".

    void f() {
        int n = 1;
        Pair p = new Pair();
        p.x = 2; p.y = 3;
        System.out.println(n);    // prints 1
        System.out.println(p.x);  // prints 2
        g(n,p);
        System.out.println(n);    // still prints 1
        System.out.println(p.x);  // prints 100
    }
    void g(int num, Pair ptr) {
        System.out.println(num);  // prints 1
        num = 17;                 // changes only the local copy
        System.out.println(num);  // prints 17

        System.out.println(ptr.x);// prints 2
        ptr.x = 100;              // changes the x field of caller's Pair
        ptr = null;               // changes only the local ptr
    }
The formal parameters num and ptr are local variables in the procedure g initialized with copies of the values of n and p. Any changes to num and ptr affect only the copies. However, since ptr and p point to the same object, the assignment to ptr.x in g changes the value of p.x.

Unlike C++, Java has no way of declaring reference parameters, and unlike C++ or C, Java has no way of creating a pointer to a (non-object) value, so you can't do something like this


    /* C or C++ */
    void swap1(int *xp, int *yp) {
        int tmp;
        tmp = *xp;
        *xp = *yp;
        *yp = tmp;
    }
    int foo = 10, bar = 20;
    swap1(&foo, &bar);  /* now foo==20 and bar==10 */

    // C++ only
    void swap2(int &xp, int &yp) {
        int tmp;
        tmp = xp;
        xp = yp;
        yp = tmp;
    }
    int this_one = 88, that_one = 99;
    swap2(this_one, that_one);  // now this_one==99 and that_one==88
You'll probably miss reference parameters most in situations where you want a procedure to return more than one value. As a work-around you can return an object or array or pass in a pointer to an object or array. See Section 2.6.4 on page 62 of the Java book for more information.

Garbage Collection

New objects are create by the new operator in Java just like C++ (except that an argument list is required after the class name, even if the constructor for the class doesn't take any arguments so the list is empty). However, there is no delete operator. The Java system automatically deletes objects when no references to them remain. This is a much more important convenience than it may at first seem. delete operator is extremely error-prone. Deleting objects too early can lead to dangling reference, as in


    // This is C++ code
    p = new Pair();
    // ...
    q = p;
    // ... much later
    delete p;
    q -> x  = 5; // oops!
while deleting them too late (or not at all) can lead to garbage, also known as a storage leak.

Static, Final, Public, and Private

Each field or method of a class has an access, which is one of public, protected, private, or package. The first three of these are specified by preceding the field or method declaration by one of the words public, protected, or private. Package access is specified by omitting these words.

    public class Example {
        public int a;
        protected int b;
        private int c;
        int d; // has package access
    }
It is a design flaw of Java that the default access is "package". For this course, all fields and methods must be declared with one of the words public, protected, or private. As a general rule only methods should be declared public; fields are normally protected or private.

Private members can only be accessed from inside the bodies of methods (function members) of the class, not "from the outside." Thus if x is an instance of C, x.i is not legal, but i can be accessed from the body of x.f(). (protected access is discussed further below).

The keyword static does not mean "unmoving" as it does in common English usage. Instead is means something like "class" or "unique". Ordinary members have one copy per instance, whereas a static member has only one copy, which is shared by all instances. Ordinary (non-static) fields are sometimes called "instance variables". In effect, a static member lives in the class object itself, rather than instances.

    public class C {
        public int x = 1;
        public static int y = 1;
        public void f(int n) { x += n; }
        public static int g() { return ++y; }
    }
    // ... elsewhere ...
    C p = new C();
    C q = new C();
    p.f(3);
    q.f(5);
    System.out.println(p.x);  // prints 4
    System.out.println(q.x);  // prints 6
    System.out.println(C.y);  // prints 1
    System.out.println(p.y);  // means the same thing as C.y; prints 1
    System.out.println(C.g());// prints 2
    System.out.println(q.g());// prints 3
    C.x;   // invalid; which instance of x?
    C.f(); // invalid; which instance of f?

Static members are often used instead of global variables and functions, which do not exist in Java. For example,

    Math.tan(x);            // tan is a static method of class Math
    Math.PI;                // a static "field" of class Math with value 3.14159...
    Integer.parseInt("123"); // converts a string of digits into a number
Starting with Java 1.5, the word static can also be used in an import statement to import all the static members of a class.
     import static java.lang.Math.*;
...
    double theta = tan(y / x);
    double area = PI * r * r;
This feature is particularly handy for System.out.
    import static java.lang.System.*;
    ...
    out.println(p.x); // same as System.out.println(q.x), but shorter
From now on, we will assume that every Java file starts with
    import static java.lang.System.*;

The keyword final means that a field or variable may only be assigned a value once. It is often used in conjunction with static to defined named constants.

    public class Card {
        public int suit = CLUBS;     // default
        public final static int CLUBS = 1;
        public final static int DIAMONDS = 2;
        public final static int HEARTS = 3;
        public final static int SPADES = 4;
    }
    // ... elsewhere ...
    Card c = new Card();
    out.println("suit " + c.suit);
    c.suit = Card.SPADES;
    out.println("suit " + c.suit);
Each Card has its own suit. The value CLUBS is shared by all instances of Card so it only needs to be stored once, but since it's final, it doesn't need to be stored at all.

Java 1.5 introduced enums, which are the preferable way of declaring a variable that can only take on a specified set of distinct values. Using enums, the example becomes

    enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES };
    class Card {
        public Suit suit = Suit.CLUBS;     // default
    }
    // ... elsewhere ...
    Card c = new Card();
    out.println("suit " + c.suit);
    c.suit = Card.SPADES;
    out.println("suit " + c.suit);
One advantage of this version is that it produces the user-friendly output
    suit CLUBS
    suit SPADES
rather than
    suit 1
    suit 4
with no extra work on the part of the programmer.

Arrays

In Java, arrays are objects. Like all objects in Java, you can only point to them. Unlike a C++ array variable, which is treated like a pointer to the first element of the array, a Java array variable points to the whole object. There is no way to point to a particular slot in an array.

Each array has a read-only (final) field length that tells you how many elements it has. The elements are numbered starting at zero: a[0] ... a[a.length-1]. Once you create an array (using new), you can't change its size. If you need more space, you have to create a new (larger) array and copy over the elements (but see the List library classes below).

    int[] arrayOne;         // a pointer to an array object; initially null
    int arrayTwo[];         // allowed for compatibility with C; don't use this!
    arrayOne = new int[10]; // now arrayOne points to an array object
    arrayOne[3] = 17;       // accesses one of the slots in the array
    arrayOne = new int[5];  // assigns a different array to arrayOne
                            // the old array is inaccessible (and so
                            // is garbage-collected)
    out.println(arrayOne.length);
                            // prints 5
    int[] alias = arrayOne; // arrayOne and alias share the same array object
                            // Careful! This could cause surprises
    alias[3] = 17;          // Changes an element of the array pointed to by
                            // alias, which is the same as arrayOne
    out.println(arrayOne[3]);
                            // prints 17

Strings

Since you can make an array of anything, you can make an an array of char or an an array of byte, but Java has something much better: the type String. The + operator is overloaded on Strings to mean concatenation. What's more, you can concatenate anything with a string; Java automatically converts it to a string. Built-in types such as numbers are converted in the obvious way. Objects are converted by calling their toString() methods. Library classes all have toString methods that do something reasonable. You should do likewise for all classes you define. This is great for debugging.

    String s = "hello";
    String t = "world";
    out.println(s + ", " + t);       // prints "hello, world"
    out.println(s + "1234");         // "hello1234"
    out.println(s + (12*100 + 34));  // "hello1234"
    out.println(s + 12*100 + 34);    // "hello120034" (why?)
    out.println("The value of x is " + x);  // will work for any x
    out.println("System.out = " + System.out);
                // "System.out = java.io.PrintStream@80455198"
    String numbers = "";
    for (int i=0; i<5; i++) {
        numbers += " " + i;  // correct but slow
    }
    out.println(numbers);            // " 0 1 2 3 4"
Strings have lots of other useful operations:
    String s = "whatever", t = "whatnow";
    s.charAt(0);            // 'w'
    s.charAt(3);            // 't'
    t.substring(4);         // "now" (positions 4 through the end)
    t.substring(4,6);       // "no"  (positions 4 and 5, but not 6)
    s.substring(0,4);       // "what" (positions 0 through 3)
    t.substring(0,4);       // "what"
    s.compareTo(t);         // a value less than zero
                            // s precedes t in "lexicographic"
                            // (dictionary) order
    t.compareTo(s);         // a value greater than zero (t follows s)
    t.compareTo("whatnow"); // zero
    t.substring(0,4) == s.substring(0,4);
                            // false (they are different String objects)
    t.substring(0,4).equals(s.substring(0,4));
                            // true (but they are both equal to "what")
    t.indexOf('w');         // 0
    t.indexOf('t');         // 3
    t.indexOf("now");       // 4
    t.lastIndexOf('w');     // 6
    t.endsWith("now");      // true
and more.

You can't modify a string, but you can make a string variable point to a new string (as in numbers += " " + i;). The example above is not good way to build up a string a little at a time. Each iteration of numbers += " " + i; creates a new string and makes the old value of numbers into a garbage object, which requires time to garbage-collect. Try running this code

    public class Test {
        public static void main(String[] args) {
            String numbers = "";
            for (int i = 0; i < 10000; i++) {
                numbers += " " + i;  // correct but slow
            }
            out.println(numbers.length());
        }
    }
A better way to do this is with a StringBuffer, which is a sort of "updatable String".
    public class Test {
        public static void main(String[] args) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 10000; i++) {
                sb.append(" " + i);
            }
            String numbers = sb.toString();
            out.println(numbers.length());
        }
    }

Constructors and Overloading

A constructor is method with the same name as the class. It does not have any return type, not even void. If a constructor has arguments, you supply corresponding values when using new. Even if it has no arguments, you still need the parentheses (unlike C++). There can be multiple constructors, with different numbers or types of arguments. The same is true for other methods. This is called overloading. Unlike C++, you cannot overload operators. The operator "+" is overloaded for strings and (various kinds of) numbers, but user-defined operator overloading is not supported.

    class Pair {
        int x, y;
        Pair(int u, int v) {
            x = u;  // the same as this.x = u
            y = v;
        }
        Pair(int x) {
            this.x = x;  // not the same as x = x!
            y = 0;
        }
        Pair() {
            x = 0;
            y = 0;
        }
    }
    class Test {
        public static void main(String[] argv) {
            Pair p1 = new Pair(3,4);
            Pair p2 = new Pair();  // same as new Pair(0,0)
            Pair p3 = new Pair;    // error!
        }
    }

Inheritance, Interfaces, and Casts

Java supports two kinds of inheritance, which are sometimes called interface inheritance or sub-typing, and method inheritance.

Method inheritance is specified with the keyword extends.

    class Base {
        int f() { /* ... */ }
        void g(int x) { /* ... */ }
    }
    class Derived extends Base {
        void g(int x) { /* ... */ }
        double h() { /* ... */ }
    }
Class Derived has three methods: f, g, and h. The method Derived.f() is implemented in the same way (the same executable code) as Base.f(), but Derived.g() overrides the implementation of Base.g(). We call Base the super class of Derived and Derived a subclass of Base. Every class (with one exception) has exactly one super class (single inheritance). If you leave out the extends specification, Java treats it like "extends Object". The primordial class Object is the lone exception -- it does not extend anything. All other classes extend Object either directly or indirectly. Object has a method toString, so every class has a method toString; either it inherits the method from its super class or it overrides it.

Interface inheritance is specified with implements. A class implements an Interface, which is like a class, except that the methods don't have bodies. Two examples are given by the built-in interfaces Runnable and Enumeration.

    interface Runnable {
        void run();
    }
    interface Enumeration {
        Object nextElement();
        boolean hasMoreElements();
    }
An object is Runnable if it has a method named run that is public1 and has no arguments or results. To be an Enumeration, a class has to have a public method nextElement() that returns an Object and a public method hasMoreElements that returns a boolean. A class that claims to implement these interfaces has to either inherit them (via extends) or define them itself.
    class Words extends StringTokenizer implements Enumeration, Runnable {
        public void run() {
            for (;;) {
                String s = nextToken();
                if (s == null) {
                    return;
                }
                out.println(s);
            }
        }
        Words(String s) {
            super(s);
            // perhaps do something else with s as well
        }
    }
The class Words needs methods run, hasMoreElements, and nextElement to meet its promise to implement interfaces Runnable and Enumeration. It inherits implementations of hasMoreElements and nextElement from StringTokenizer , but it has to give its own implementation of run. The implements clause tells users of the class what they can expect from it. If w is an instance of Words, I know I can write
    w.run();
or
    if (w.hasMoreElements()) ...
A class can only extend one class, but it can implement any number of interfaces.

By the way, constructors are not inherited. The call super(s) in class Words calls the constructor of StringTokenizer that takes one String argument. If you don't explicitly call super, Java automatically calls the super class constructor with no arguments (such a constructor must exist in this case). Note the call nextToken() in Words.run, which is short for this.nextToken(). Since this is an instance of Words, it has a nextToken method -- the one it inherited from StringTokenizer.

Interfaces can also be used to declare variables.

    Enumeration e = new StringTokenizer("hello there");
Enumeration is an interface, not a class, so it does not have any instances. However, class StringTokenizer is consistent with (implements) Enumeration, so e can point to an object of type StringTokenizer In this case, the variable e has type Enumeration, but it is pointing to an instance of class StringTokenizer.

A cast in Java is a type name in parentheses preceding an expression. A cast can be applied to primitive types.

    double pi = Math.PI;
    int three = (int) pi;  // throws away the fraction 
A cast can also be used to convert an object reference to a super class or subclass. For example,
    Words w = new Words("this is a test");
    Object o = w.nextElement();
    String s = (String) o;
    out.println("The first word has length " + s.length());
We know that w.nextElement() is ok, since Words implements the interface Enumeration, but all that tells us is that the value returned has type Object. We cannot call o.length() because class Object does not have a length method. In this case, however, we know that o is not just any kind of Object, but a String in particular. Thus we cast o to type String. If we were wrong about the type of o we would get a run-time error. If you are not sure of the type of an object, you can test it with instanceof (note the lower case "o"), or find out more about it with the method Object.getClass()
    if (o instanceof String) {
        n = ((String) o).length();
    } else {
        err.println("Bad type " + o.getClass().getName());
    }

Exceptions

A Java program should never "core dump," no matter how buggy it is. If the compiler excepts it and something goes wrong at run time, Java throws an exception. By default, an exception causes the program to terminate with an error message, but you can also catch an exception.

    try {
        // ...
        foo.bar();
        // ...
        a[i] = 17;
        // ...
    }
    catch (IndexOutOfBoundsException e) {
        err.println("Oops: " + e);
    }
The try statement says you're interested in catching exceptions. The catch clause (which can only appear after a try) says what to do if an IndexOutOfBoundsException occurs anywhere in the try clause. In this case, we print an error message. The toString() method of an exception generates a string containing information about what went wrong, as well as a call trace.

WARNING Never write an empty catch clause. If you do, you will regret it. Maybe not today, but tomorrow and for the rest of your life.

Because we caught this exception, it will not terminate the program. If some other kind of exception occurs (such as divide by zero), the exception will be thrown back to the caller of this function and if that function doesn't catch it, it will be thrown to that function's caller, and so on back to the main function, where it will terminate the program if it isn't caught. Similarly, if the function foo.bar throws an IndexOutOfBoundsException and doesn't catch it, we will catch it here.

The catch clause actually catches IndexOutOfBoundsException or any of its subclasses, including ArrayIndexOutOfBoundsException , StringIndexOutOfBoundsException , and others. An Exception is just another kind of object, and the same rules for inheritance hold for exceptions as any other king of class.

You can define and throw your own exceptions.

    class SytaxError extends Exception {
        int lineNumber;
        SytaxError(String reason, int line) {
            super(reason);
            lineNumber = line;
        }
        public String toString() {
            return "Syntax error on line " + lineNumber + ": " + getMessage();
        }
    }
    class SomeOtherClass {
        public void parse(String line) throws SyntaxError {
            // ...
            if (...)
                throw new SyntaxError("missing comma", currentLine);
            //...
        }
        public void parseFile(String fname) {
            //...
            try {
                // ...
                nextLine = in.readLine();
                parse(nextLine);
                // ...
            }
            catch (SyntaxError e) {
                err.println(e);
            }
        }
    }
Each function must declare in its header (with the keyword throws) all the exceptions that may be thrown by it or any function it calls. It doesn't have to declare exceptions it catches. Some exceptions, such as IndexOutOfBoundsException, are so common that Java makes an exception for them (sorry about that pun) and doesn't require that they be declared. This rule applies to RuntimeException and its subclasses. You should never define new subclasses of RuntimeException.

There can be several catch clauses at the end of a try statement, to catch various kinds of exceptions. The first one that "matches" the exception (i.e., is a super class of it) is executed. You can also add a finally clause, which will always be executed, no matter how the program leaves the try clause (whether by falling through the bottom, executing a return, break, or continue, or throwing an exception).

Threads

Java lets you do several things at once by using threads. If your computer has more than one CPU, it may actually run two or more threads simultaneously. Otherwise, it will switch back and forth among the threads at times that are unpredictable unless you take special precautions to control it.

There are two different ways to create threads. I will only describe one of them here.

    Thread t = new Thread(command); // 
    t.start();  // t start running command, but we don't wait for it to finish
    // ... do something else (perhaps start other threads?)
    // ... later:
    t.join();  // wait for t to finish running command
The constructor for the built-in class Thread takes one argument, which is any object that has a method called run. This requirement is specified by requiring that command implement the Runnable interface described earlier. (More precisely, command must be an instance of a class that implements Runnable). The way a thread "runs" a command is simply by calling its run() method. It's as simple as that!

In project 1, you are supposed to run each command in a separate thread. Thus you might declare something like this:

    class Command implements Runnable {
        String commandLine;
        Command(String commandLine) {
            this.commandLine = commandLine;
        }
        public void run() {
            // Do what commandLine says to do
        }
    }
You can parse the command string either in the constructor or at the start of the run() method.

The main program loop reads a command line, breaks it up into commands, runs all of the commands concurrently (each in a separate thread), and waits for them to all finish before issuing the next prompt. In outline, it may look like this.

    for (;;) {
        out.print("% "); out.flush();
        String line = inputStream.readLine();
        int numberOfCommands = // count how many commands there are on the line
        Thread t[] = new Thread[numberOfCommands];
        for (int i=0; i<numberOfCommands; i++) {
            String c = // next command on the line
            t[i] = new Thread(new Command(c));
            t[i].start();
        }
        for (int i=0; i<numberOfCommands; i++) {
            t[i].join();
        }
    }
This main loop is in the main() method of your main class. It is not necessary for that class to implement Runnable.

Although you won't need it for project 1, the next project will require to to synchronize threads with each other. There are two reasons why you need to do this: to prevent threads from interfering with each other, and to allow them to cooperate. You use synchronized methods to prevent interference, and the built-in methods Object.wait() , Object.notify() , Object.notifyAll() , and Thread.yield() to support cooperation.

Any method can be preceded by the word synchronized (as well as public, static, etc.). The rule is:

No two threads may be executing synchronized methods of the same object at the same time.

The Java system enforces this rule by associating a monitor lock with each object. When a thread calls a synchronized method of an object, it tries to grab the object's monitor lock. If another thread is holding the lock, it waits until that thread releases it. A thread releases the monitor lock when it leaves the synchronized method. If one synchronized method of a calls contains a call to another, a thread may have the same lock "multiple times." Java keeps track of that correctly. For example,

    class C {
        public synchronized void f() {
            // ...
            g();
            // ...
        }
        public synchronized void g() { /* ... */ }
    }
If a thread calls C.g() "from the outside", it grabs the lock before executing the body of g() and releases it when done. If it calls C.f(), it grabs the lock on entry to f(), calls g() without waiting, and only releases the lock on returning from f().

Sometimes a thread needs to wait for another thread to do something before it can continue. The methods wait() and notify(), which are defined in class Object and thus inherited by all classes, are made for this purpose. They can only be called from within synchronized methods. A call to wait() releases the monitor lock and puts the calling thread to sleep (i.e., it stops running). A subsequent call to notify on the same object wakes up a sleeping thread and lets it start running again. If more than one thread is sleeping, one is chosen arbitrarily2 and if no threads are sleeping in this object, notify() does nothing. The awakened thread has to wait for the monitor lock before it starts; it competes on an equal basis with other threads trying to get into the monitor. The method notifyAll is similar, but wakes up all threads sleeping in the object.

    class Buffer {
        private List queue = new ArrayList();
        public synchronized void put(Object o) {
            queue.add(o);
            notify();
        }
        public synchronized Object get() {
            while (queue.isEmpty()) {
                wait();
            }
            return queue.remove(0);
        }
    }
This class solves the so-call "producer-consumer" problem. (The class ArrayList and interface List are part of the java.util package.) "Producer" threads somehow create objects and put them into the buffer by calling Buffer.put(), while "consumer" threads remove objects from the buffer (using Buffer.get()) and do something with them. The problem is that a consumer thread may call Buffer.get() only to discover that the queue is empty. By calling wait() it releases the monitor lock and goes to sleep so that producer threads can call put() to add more objects. Each time a producer adds an object, it calls notify() just in case there is some consumer waiting for an object.

This example is not correct as it stands (and the Java compiler will reject it). The wait() method can throw an InterruptedException exception, so the get() method must either catch it or declare that it throws InterruptedException as well. The simplest solution is just to catch the exception and print it:

    class Buffer {
        private List queue = new ArrayList();
        public synchronized void put(Object o) {
            queue.add(o);
            notify();
        }
        public synchronized Object get() {
            while (queue.isEmpty()) {
                try {
                    wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            return queue.remove(0);
        }
    }
The method printStackTrace() prints some information about the exception, including the line number where it happened. It is a handy thing to put in a catch clause if you don't know what else to put there. Never use an empty catch clause. If you violate this rule, you will live to regret it!

There is also a version of Object.wait() that takes an integer parameter. The call wait(n) will return after n milliseconds if nobody wakes up the thread with notify or notifyAll sooner.

You may wonder why Buffer.get() uses while (queue.isEmpty()) rather than if (queue.isEmpty()). In this particular case, either would work. However, in more complicated situations, a sleeping thread might be awakened for the "wrong" reason. Thus it is always a good idea when you wake up to recheck the condition that made to decide to go to sleep before you continue.

Input and Output

Input/Output, as described in Chapter 20 of the Java book, is not as complicated as it looks. You can get pretty far just writing to System.out (which is of type PrintStream ) with methods print , println , and printf . The method print simply writes converts its argument to a String and writes it to the output stream. The method println is similar, but adds a newline so that following output starts on a new line. The method printf is new in Java 1.5. It expects a String as its first argument and zero or more additional arguments. Each '%' in the first argument indicates a request to print one of the other arguments. The details are spelled out by one or more characters following the '%'. For example,

    out.printf("pair(%d,%d)%n", pair.x, pair.y);
produces exactly the same thing as
    out.println("pair(" + pair.x + "," + pair.y + ")");
but is much easier to read, and to write. The characters %d are replaced by the result of converting the next argument to a decimal integer. Similarly, "%f" looks for a float or double, "%x" looks for an integer and prints it in hexadecimal, and "%s" looks for a string. Fancier formatting is supported; for example, "%6.2f" prints a float or double with exactly two digits following the decimal point, padding with leading spaces as necessary to make the result at least 6 characters long.

For input, you probably want to wrap the standard input System.in in a BufferedReader , which provides the handy method readLine()

    BufferedReader input =
        new BufferedReader(new InputStreamReader(System.in));
    for(;;) {
        String line = input.readLine();
        if (line == null) {
            break;
        }
        // do something with the next line
    }

If you want to read from a file, rather than from the keyboard (standard input), you can use FileReader, probably wrapped in a BufferedReader.

    BufferedReader input =
        new BufferedReader(new FileReader("somefile"));
    for (;;) {
        String line = input.readLine();
        if (line == null) {
            break;
        }
        // do something with the next line
    }
Similarly, you can use new PrintWriter(new FileOutputStream("whatever")) to write to a file.

Other Goodies

The library of pre-defined classes has several other handy tools. See the online manual , particularly java.lang and java.util for more details.

Integer, Character, etc.

Java makes a big distinction between values (integers, characters, etc.) and objects. Sometimes you need an object when you have a value (the next paragraph has an example). The classes Integer, Character, etc. serve as convenient wrappers for this purpose. For example, Integer i = new Integer(3) creates a version of the number 3 wrapped up as an object. The value can be retrieved as i.intValue(). Starting with Java 1.5, "autoboxing" automatically converts between int and Integer, char and Character, etc. in many contexts. For example,
    int i;
    Integer ii;
    ii = 3;     // Same as ii = new Integer(3);
    i = ii;     // Same as i = ii.intValue();
These classes also serve as convenient places to define utility functions for manipulating value of the given types, often as static methods or defined constants.
    int i = Integer.MAX_VALUE;          // 2147483648, the largest possible int
    int j = Integer.parseInt("123");    // the int value 123
    String s = Integer.toHexString(123);// "7b" (123 in hex)
    double x = Double.parseDouble("123e-2");
                                        // the double value 1.23
    Character.isDigit('3')              // true
    Character.isUpperCase('a')          // false
    Character.toUpperCase('a')          // 'A'

List

A List is like an array, but it grows as necessary to allow you to add as many elements as you like. The elements can be any kind of Object, but they cannot be primitive values such as integers. When you take objects out of a List, you have to use a cast to recover the original type. Use the method add(Object o) to add an object to the end of the list and get(int i) to remove the ith element from the list. Use iterator() to get an Iterator for running through all the elements in order.3 List is an interface, not a class, so you cannot create a new list with new. Instead, you have to decide whether you want a LinkedList or an ArrayList. The two implementations have different preformance characteristics.

    List list = new ArrayList();     // an empty list
    for (int i = 0; i < 100; i++) {
        list.add(new Integer(i));
    }
    // now it contains 100 Integer objects

    // print their squares
    for (int i = 0; i < 100; i++) {
        Integer member = (Integer) list.get(i);
        int n = member.intValue();
        out.println(n*n);
    }

    // another way to do that
    for (Iterator i = list.iterator(); i.hasNext(); ) {
        int n = ((Integer) i.next()).intValue();
        out.println(n*n);
    }
    list.set(5, "hello");        // like list[5] = "hello"
    Object o = list.get(3);      // like o = list[3];
    list.add(6, "world");        // set list[6] = "world" after first shifting
                                 // element list[7], list[8], ... to the right
                                 // to make room
    list.remove(3);              // remove list[3] and shift list[4], ... to the
                                 // left to fill in the gap
Elements of a List must be objects, not values. That means you can put a String or an instance of a user-defined class into a Vector, but if you want to put an integer, floating-point number, or character into List, you have to wrap it:
    list.add(new Integer(47));
        // or list.add(47), using Java 1.5 autoboxing
    sum += ((Integer) list.get(i)).intValue();
                                    // ugly, but right
    sum += list.get(i);             // better
The class ArrayList is implemented using an ordinary array that is generally only partially filled. As its name implies LinkedList is implemented as a doubly-linked list.

Don't forget to import java.util.List; import java.util.ArrayList; or import java.util.*; .

Lists and other similar classes are even easier to use with the introduction of generic types in Java 1.5. Instead of List l which declares l to be a list of Objects of unspecified type, use List, read as "List of Integer". When you add an object list l, the compiler checks that the object is of type Integer or a subclass of Integer and gives a compile-time error if not, and the expression l.get(3) has type Integer, not Object eliminating the need for a cast. Using generic types, autoboxing and the new "foreach" loop also introduced in Java 1.5, the previous example becomes much simpler.

    List<Integer> list = new ArrayList<Integer>();     // an empty list
    for (int i = 0; i < 100; i++) {
        list.add(i);
    }
    // now it contains 100 Integer objects

    // print their squares
    for (Iterator<Integer> i = list.iterator(); i.hasNext(); ) {
        int n = i.next();
        out.println(n*n);
    }
    // or even simpler
    for (int n : list) {
        out.println(n*n);
    }

    List<String> strList = new ArrayList<String>();
    for (int i = 0; i < 100; i++) {
        strList.add("value " + i);
    }
    strList.set(5, "hello");   // like strList[5] = "hello"
    String s = strList.get(3); // like o = strList[3];
    strList.add(6, "world");   // set strList[6] = "world" after first shifting
                               // element strList[7], strList[8], ... to the
                               // right to make room
    strList.remove(3);         // remove strList[3] and shift strList[4], ... to
                               // the left to fill in the gap

Maps and Sets

The interface Map4 represents a table mapping keys to values. It is sort of like an array or List, except that the "subscripts" can be any objects, rather than non-negative integers. Since Map is an interface rather than a class you cannot create instances of it, but you can create instances of the class HashMap, which implements Map using a hash table or TreeMap which implements it as a binary search tree (a "red/black" tree).

    Map<String,Integer> table           // a mapping from Strings to Integers
        = new HashMap<String,Integer>();
    table.put("seven", new Integer(7)); // key is the String "seven";
                                        //   value is an Integer object
    table.put("four", 4);               // similar, using autoboxing
    Object o = table.put("seven", 70);  // binds "seven" to a different object
                                        //   (a mistake?) and returns the
                                        //   previous value
    int n = ((Integer)o).intValue();
    out.printf("n = %d\n", n);          // prints 7
    n = table.put("seven", 7);          // fixes the mistake
    out.printf("n = %d\n", n);          // prints 70
    out.println(table.containsKey("seven"));
                                        // true
    out.println(table.containsKey("twelve"));
                                        // false

    // print out the contents of the table
    for (String key : table.keySet()) {
        out.printf("%s -> %d\n", key, table.get(key));
    }
    n = table.get("seven");           // get value bound to "seven"
    n = table.remove("seven");        // get binding and remove it
    out.println(table.containsKey("seven"));
                                      // false
    table.clear();                    // remove all bindings
    out.println(table.containsKey("four"));
                                      // false
    out.println(table.get("four"));   // null
Sometimes, you only care whether a particular key is present, not what it's mapped to. You could always use the same object as a value (or use null), but it would be more efficient (and, more importantly, clearer) to use a Set.
    out.println("What are your favorite colors?");
    BufferedReader input =
        new BufferedReader(new InputStreamReader(in));
    Set<String> favorites = new HashSet<String>();
    try {
        for (;;) {
            String color = input.readLine();
            if (color == null) {
                break;
            }
            if (!favorites.add(color)) {
                out.println("you already told me that");
            }
        }
    } catch (IOException e) {
        e.printStackTrace();
    }
    int n = favorites.size();
    if (n == 1) {
        out.printf("your favorite color is:");
    } else {
        out.printf("your %d favorite colors are:", n);
    }
    for (String s : favorites) {
        out.printf(" %s", s);
    }
    out.println();

StringTokenizer

A StringTokenizer is handy in breaking up a string into words separated by white space (or other separator characters). The following example is from the Java book:

    String str = "Gone, and forgotten";
    StringTokenizer tokens = new StringTokenizer(str, " ,");
    while (tokens.hasMoreTokens())
        System.out.println(tokens.nextToken());
It prints out
    Gone
    and
    forgotten
The second argument to the constructor is a String containing the characters that such be considered separators (in this case, space and comma). If it is omitted, it defaults to space, tab, return, and newline (the most common "white-space" characters).

There is a much more complicated class StreamTokenizer for breaking up an input stream into tokens. Many of its features seem to be designed to aid in parsing the Java language itself (which is not a surprise, considering that the Java compiler is written in Java).

Other Utilities

See Chapters 16 and 17 of the Java book for information about other handy classes.


Previous Introduction
Next Processes and Synchronization
Contents

1All the members of an Interface are implicitly public. You can explicitly declare them to be public, but you don't have to, and you shouldn't.

2In particular, it won't necessarily be the one that has been sleeping the longest.

3Interface Iterator was introduced with Java 1.2. It is a somewhat more convenient version of the older interface Enumeration discussed earlier.

4Interfaces Map and Set were introduced with Java 1.2. Earlier versions of the API contained only Hashtable, which is similar to HashMap.


solomon@cs.wisc.edu
Mon Sep 10 15:47:07 CDT 2007

Copyright © 1996-2007 by Marvin Solomon. All rights reserved.