CS231 lecture notes, Fall 1998
Week 4, Friday

Java abstract classes
---------------------

Until now, we have build data structures that are made up of
one type of item.

    Lists are made of ListItems
    PriorityQueues are made of PQItems

If we want a list of something else (like PQItems), we have to
modify the List class, possibly making a new version.

It's generally easy to do that using a global search and replace,
but it is kind of silly, and it might result in many copies of the
List class, which would be hard to maintain.

It would be nice to build generic data structures.

One way to do that is with typecasting, which is how the Vector
class works.  You can put any kind of Object into a Vector.

1) before putting the thing into the Vector, cast it to be
   an Object.  This is always possible, because all classes
   are descended (inherited) from a primal Object class.

2) after removing the Object from the Vector, you have to
   cast it back into something else before you can access it.

3) casting things back can be tricky, since it is up to the
   programmer to insure that you cast it back into the right
   kind of object.

4) If you get it wrong, you get a ClassCastException (at run time)

5) typecasting is a funny kind of aliasing

   PQItem fred = ... whatever ...
   Object foo = (Object) fred;

   Both fred and foo reference the same object, but when I use
   the name fred, I treat the object as a PQItem, when I call
   it foo I treat it as an Object.

   fred.toString    invokes the toString method of PQItem
   foo.toString     invokes the toString method of Object
   fred.key         extracts the key field from fred
   foo.key          causes an error because Objects don't have a key field

6) so how do we add primitive types to a Vector?

   all primitive types have wrapper classes (Integer, Double, Float)

   the wrapper classes contain methods that pertain to these types

    (like Integer.toString that we saw last time)

   the wrapper classes also let you convert primitive types to Objects

    (see the Vector handout)


Generic PQ
----------

With PriorityQueues, there are rules about what can and
can't be added to a PQ.  Not just any Object will do.

The items have to be comparable, meaning that they have to provide
a method named compareTo.

What we want to do is specify an abstract class, which you can
think of as a category of classes.

In this case, the category is "all the classes that provide a method
named compareTo".

Another category might be Printable (all the classes that provide
toString) or Drawable (all the classes that provide draw(Graphics g)).

In general, the names of abstract classes are not so intuitive (as in
the book's ComparisonKey).

Java's word for an abstract class is an INTERFACE, which can be
confusing because we also use the word interface to refer to the
way a method is invoked (and also, for that matter, to refer to
the part of a program that users see).

Here's what an abstract class looks like:

public interface Comparable {
  int compareTo (Comparable other);
  String toString();
}

1) Syntax is the same as a class definition, except for "interface"
   instead of "class".

2) Same rules as classes: each abstract class in a file by itself.
   Name of file is the same as the name of the abstract class.

3) The definitions of the methods are the same as in a concrete
   class definition, except that there are no bodies -- all we
   specify is the name, argument types, and return types.

4) Don't forget the semi-colons.


How do we use one of these things:

1) first we have to rewrite PriorityQueue so that instead of insisting
   on a specific class (PQItem), it works with the abstract class
   Comparable.  For the most part this involves a global search and
   replace.

2) second we have to indicate somehow that PQItem is a class that belongs
   to the Comparable category.  We do that by changing the PQItem
   class definition:

public class PQItem implements Comparable {

       That's all.  The compiler will check to make sure we live up
       to this promise.

Implements might seem like a funny word here, but it just means that
PQItem provides implementations (bodies) for all the methods described
in Comparable.  Plus others, usually.

   Can a class implement more than one interface (belong to more
   than one category?).  Sure!

3) last we usually have to do a little typecasting to make everything
   works.  The compiler is very helpful for this step, since it
   complains in all the right places.

   (as an aside, compilers often do well at this kind of type-
   checking, generating good messages.  Much more so than for
   syntax errors).


The third part of the assignment walks you through this process.
Getting all the details right is tricky (primarily the typecasts).

0) make sure you understand the big picture before you start
   (read these notes and Section 5.4 a couple of times)

1) follow the instructions carefully

2) try to make sense of compiler errors.  they can be helpful.

   2a) but don't fall into the trap of letting the compiler lead
       you by the nose.  Think before you make changes.

3) pick a fixed amount of time to work on this problem (like
   2 hours) and quit if you don't have it working.  Print what
   you have and write notes on it explaining what was wrong.
   You can come back to it later, with the solutions, and make
   sense of it all.

   Good luck!