cs230 Lecture Notes
Week 6, Thursday

Homework 4 was due on Tuesday in lab, or one day late on Wednesday.

Homework 5 will be handed out today and is due next Thursday.

For today you should have read Chapter 15 and prepared for a quiz.

Quiz 5 Solutions
----------------





















Wrapper classes
---------------

Basic constructors:

    Integer iobj = new Integer (17);
    Double dobj = new Double (3.14159);
    Character cobj = new Character ('b');

Getting the primitive values back:

    int iprim = iobj.intValue ();
    double dprim = dobj.doubleValue ();
    char cprim = cobj.charValue ();

This is not one of Java's finer moments, especially when
combined with a generic data structure:

    stack.push (new Integer (iprim));
    Integer iobj = (Integer) stack.pop ();
    int i = iobj.intValue ();


Run time class
--------------

Every variable has a compile time class: the class the
compiler knows it belongs to.

   Integer integer = new Integer (17);
   Object obj = (Object) integer;

The compiler knows that integer is an Integer and obj
is an Object.

In addition, each object has a run-time class, which is
the class it _really_ belongs to.

In the example, the variable named obj refers to an
object whose run-time class is Integer.

How could we tell?

    Class class = obj.getClass();
    System.out.println (class.getName());

If you get a ClassCastException, you can use this to print
the run time class and figure out what's wrong.

See the documentation of java.lang.Class for more info.


hw04 comments
-------------

addFirst and removeFirst are fast (constant time), and
they're going to turn out to be useful soon.

removeFirst has an error condition.  In this case, we
handle it by returning a special value.  Alternatives:

1) print error message and return

2) print error message and quit

3) throw an exception!

set checks the error condition first and returns immediately.
that spares us a level of indentation in the rest of the method.

     performance of set?

add and set are very similar.  add has an extra special case
(when the index is zero we have to modify the LinkedList;
otherwise we modify a Node)

     performance of add?

clone has to return an Object.  In Test:

	LinkedList copy = (LinkedList) list.clone ();

     performance of clone?

reverse takes advantage of an idiom (traversing a list) and
a helper method (addFirst) and garbage collection

     performance of clone?

reverse is efficient (linear order of growth) but it wastes
some overhead allocating new Nodes and a LinkedList object

addLast uses appendNode

append uses appendNode

appendNode contains the common code we need to find the
end of the list and link a new node.

Linking a new node is the same as linking a new set of nodes,
due to the fundamental ambiguity theorem.

BUT, the interface to appendNode is error-prone!

     1) it doesn't update length
     2) it doesn't make sure that the end of the list is null

Therefore, we want to restrict access to it.  addLast and append
can use it (because we know that they maintain the invariants).

By making it private, we disallow invocations from other files.



Public vs. private
------------------

public instance variable can be accessed anywhere

private instance variable: only this file

public method can be invoked from anywhere

private method: only this file.

Private instance variables help maintain object invariants.

Private methods restrict access to ugly, error-prone methods.





Performance analysis
--------------------

What is the performance of the following method?

     public static Node reverse (Node list) {
         if (list == null) return null;

	 Node rest = reverse (list.next);
	 return Node.addLast (list, rest);
     }

Assume that Node.addLast exists and works by traversing the list.