7/2/02
Amir Kamil

Topic: Inheritance, Static vs. Dynamic, Modifiers, Exceptions, Vectors,
       Queues, Stacks

Announcements:
- Many people did not do very well on hw1, and since the majority of 
  submissions were in the last hour, it was probably because they 
  started too late. This isn't 61A, homeworks are going to take time to 
  do.
- Start the project NOW. It's long.
- No class or section on Thursday.

Inheritance:
- Interfaces:
Interfaces are collections of methods prototypes that must be 
provided by implementing classes. No code is provided by the 
interface, only signatures. There are two reasons to use interfaces: 
any class implementing an interface is guaranteed to have the methods 
declared in that interface, and instances of implementing classes can 
be assigned to variables of type of that interface. Interfaces also 
allow multiple inheritance in a sense. A class can only extend one 
other class, but it may implement arbitrary number of interfaces.

Ex:

public interface Laptop {
  public void charge(int min);
  public void discharge(int min);
  public void getStolen();
}

public class PCLaptop extends PC implements Laptop {
  private int remainingTime;
  public void charge(int min) {
    remainingTime += min;
  }
  public void discharge(int min) {
    remainingTime += min;
  }
  public void getStolen() {
    throw new Exception("Finders keepers, loser weepers.");
  }
  ... // other methods, fields
}

- Abstract Classes:
An abstract class is halfway between an interface and a normal class; 
it implements some methods and only declares others. Unimplemented 
methods must be declared abstract. Abstract classes cannot be 
instantiated. Inheritance with abstract classes works the same way as 
with regular classes, except inheriting classes must implement the 
abstract methods.

Ex:

public abstract class Computer {
  protected int state;
  protected String os;
  protected Vector programs;
  public void turnOn() {
    state = 1;
    boot();
  }
  protected abstract void boot();
  ... // other methods, fields
}

public class PC extends Computer {
  protected void boot() {
    if (os.equals("Windows 95")) {
      throw new Exception("CRASH!");
    } else {
      programs.addElement(os);
    }
  }
}

Static vs. Dynamic:
- Static = compile-time
  Dynamic = run-time
- Static vs. Dynamic Types:
Define some terminology: Let class A "conform" to class B if A is a 
descendent of, or is B, or in the case of interfaces, implements or 
extends a class that implements B. Let "A <= B" mean A conforms to B.

Then:
  a) A variable of type A can be assigned a reference to an object of 
     type B if B <= A.
  b) An object of type A must be cast in order to assign it to a 
     variable of type B, if B <= A. Note that if the actual run-time 
     object is not of type <= B, a ClassCastException will result.
Note: The compiler can only use the static type of a variable in 
determining the above relationships.

Ex:

PC pc = new PC();
Laptop lt = new PCLaptop();
Computer comp;
comp = pc; // OK since PC <= Computer
pc = comp; // not OK since Computer is not <= PC
pc = (PC) comp; // OK since run-time object is <= PC
pc = lt; // not OK since Laptop is not <= PC
pc = (PC) lt; // OK since the run-time object is <= PC

- Static vs. Dynamic Method Calls
Static methods may be overridden. The method used will be based on the 
static type of the variable.

Ex:

PC pc = new PCLaptop();
pc.foo(); // uses foo() defined in PC class if foo() is static

It's preferable to call static methods using the type name rather than 
an instance of the class.

Ex:

PC.foo();

Calls to non-static methods use the method defined in the dynamic type 
of the variable.

Ex:

PC pc = new PCLaptop();
pc.bar(); // uses bar() defined in PCLaptop class if bar() isn't static

- "super" can be used to call methods or access fields of the parent 
  class.

Ex:

public class PCLaptop extends PC implements Laptop {
  .. // fields and methods
  public void turnOn() {
    if (remainingTime < 5) {
      return;
    } else {
      super.turnOn(); // calls turnOn() method in PC class
    }
  }
}

Modifiers:
- "static" makes the field or method a class field or method.
- A field declared "final" cannot be changed after the object is 
  instantiated. A method declared "final" cannot be overridden by a 
  child class.
- Access Modifiers: (<default> = no modifier specified)
             world | package | children | defining class
  public       X   |    X    |    X     |       X
  private          |         |          |       X
  protected        |    X    |    X     |       X
  <default>        |    X    |          |       X

Exceptions:
- Used to signify a run-time error in the program.
- Does not necessarily mean your code is bad. For example, an 
  IOException will result if a file you are reading from is corrupt, or 
  an IllegalArgumentException if an outside class calls one of your 
  methods using invalid parameters.
- Exceptions are objects, so they are instantiated like objects and you 
  can even define your own exceptions. The only requirement is that 
  they inherit Throwable.

Ex:

public class CrashException extends Exception {
  // We don't really need to write any code.
}

- Can be thrown using "throw E" where E is an exception object.
- Are either handled using "try {..} catch (ExpType e) {..}" or passed 
  on to the calling method by declaring it to be thrown.

Ex:

public String readLine() throws IOException {..} // passes exception on

public String readLine() {
  try {
    char[] cbuf = new char[1000];
    str.read(cbuf, 0, 1000);
    return new String(cbuf);
  } catch (IOException ie) {
    return null;
  } catch (Exception e) {
    System.out.println("Error: unknown exception");
    return null;
  }
  return null;
}

- When an exception is thrown within the try block, the JVM tries to 
  match the exception with the exception types in the catch blocks. The 
  first catch block for which the type is <= the type of the exception 
  is executed. For example, if the two catch blocks in the previous 
  code were switched, an IOException would result in the Exception 
  catch block to execute, since IOException <= Exception.
- Exceptions are "checked" or "unchecked". "checked" exceptions must be 
  caught or declared, "unchecked" don't have to be. You don't need to 
  memorize which exceptions are checked or unchecked, just let the 
  compiler tell you.
- Exceptions that inherit Error or RunTimeException are unchecked.

Vectors:
- Expandable arrays; underlying storage structure is an array.
- Can be accessed using indices, like arrays.
- Elements can be added using addElement(); you don't have to 
  explicitly set an index to a value.
- Diagram on board.
- Ex:

public class Vector() { // A simple Vector class
  private Object[] store; // Can store any object.
  private int elements; // # of elements contained
  public Vector() {
    store = new Object[10]; // default size 10
    elements = 0;
  }
  // Assume for simplicity size >= current size.
  public void resize(int size) {
    Object[] temp = new Object[size];
    // Copy all elements into new array.
    System.arrayCopy(store, 0, temp, elements);
    store = temp;
  }
  public void addElement(Object o) {
    if (elements == store.size) {
      resize(2 * elements); // Double size of array.
    }
    store[elements] = o;
    elements++;
  }
  // Access elements using indices.
  public Object elementAt(int index) {
    return store[index];
  }
}

A few complications: 
Removing an element from a Vector requires elements at higher indices
to move down one index, and inserting at a particular index requires
elements at higher indices to move up one index. These operations can
be very slow.
Resizing a Vector requires copying all elements from the old array to
the new array, which is also slow. So occasionally an insertion takes
a long time, but on average, it's fast.

Queues:
- A FIFO (first in first out) data structure.
- Implemented using linked lists.
- Adding an element appends that element to the end of the list.
- Getting the next element removes and returns the first element in the 
  list.
- Diagram on board.
- Ex:

public class Queue {
  private LinkedList list;
  public Queue() {
    list = new LinkedList();
  }
  public void enqueue(Object o) {
    list.addLast(o);
  }
  public Object dequeue() {
    return list.removeFirst();
  }
}

Stacks:
- A FILO (first in last out) data structure.
- Implemented using linked lists.
- Adding an element inserts that element at the front of the list.
- Getting the next element removes and returns the first element in the 
  list.
- Diagram on board.
- Ex:

public class Stack {
  private LinkedList list;
  private int size;
  public Stack() {
    list = new LinkedList();
    size = 0;
  }
  public void push(Object o) {
    list.addFirst(o);
    size++;
  }
  public Object pop() throws EmptyStackException {
    if (size == 0) {
      throw new EmptyStackException();
    }
    size--;
    return list.removeFirst();
  }
  public int size() {
    return size;
  }
  public boolean isEmpty() {
    return size == 0;
  }
}