Table of Contents

How do I write my recursive function?

First-  find a way to define the answer to a big problem in terms of 
        the answer to a smaller problem.

Second- determine the base case for the problem.

Third-  assume that the method that you are writing correctly gives the
        answer for the smaller problem.

Let's use the example of power:

we have alreay said that 

        x^y = x * (x^(y-1))

so we have defined the answer to the problem in terms of something 1 step
smaller. 

Second, we will use the fact that
 
  x^0 = 1  for any x

as our base case.

Finally, we implement the method with the assumption that power(x,y-1)
CORRECTLY computes x^(y-1):

 public static int power(int x,int y)
 {
    if(y==0)
      {
       return 1;  // base case
      }
    // ASSUME power(x,y-1) works right
    return x* power(x,y-1); // x^y= x * (x^(y-1)) 

 }    

Remember that use of the return values is CRUCIAL to writing correct
recursive functions.  Think about why

 public static int power(int x,int y)
 {
    
    int z=1;
    power(x,y,z);
    return z;
 }

 private static void power(int x,int y,int z)
 {
    if(y==0)
      return;
    z=z*x;
    power(x,y-1,z);
 }

does not work.  Think about how the value of z is local to the method it is in.
Next think about the errors caused by making z a static variable:
  
 private static int z=1;
 public static int power(int x,int y)
 {
    
   
    power(x,y,z);
    return z;
 }

 private static void power(int x,int y,int z)
 {
    if(y==0)
      return;
    z=z*x;
    power(x,y-1,z);
 }

Remember that this  common mistake frequently leads people into believing
that their code is correct, when in fact it is not. The FIRST time power
is called, it will return the correct result. On subsequent calls, power
will return results that continue to grow away from the correct answer.
Remember that use of static or instance variable to try to avoid using the
return value is BAD.

OBJECTS

• What are objects and classes?
• What are constructors and how do I make them?
• How do I use these constructors?
• What are accessors and modifiers?

What are objects and classes?

A class is a type.  When you define a class, you specify the variables
and methods that things of that type have.  When you actually make
one of those "things", you have created an object.  That object has
all of the properties defined in its class.  When you create such an
object, it is called "instantiating the class."  Let us take cars as a
simple example.  A car is a type of thing- so we can make a Car class.
Think what variables  should go into a Car class.  These variables should
be attributes of cars, such as the color, the model, etc.  (don't try
to write it in formal java code- just list them). Now, you have defined the 
class car- you have declared the attributes in a car.  Next, think about the
fact that you could have multiple cars, each with these attributes.  You should
realize how each car object is an instance of the Car class that you just
thought about.  What type of object are they? They are cars. 
Each one has the attributes that we specifies in the class.
In CS, each object gets its own piece of memory (which is dynamically 
allocated when the object is created with "new").  The contents of this
piece of memory are defined by the class that the object is.

What are constructors and how do I make them?

A constructor is a method that is called when an instance of the class
is created.  If no constructors are written in the class, java automatically
provides a constructor which takes no arguemnts and does nothing.  The 
code inside a constructor is typcially used to initalize the vaules in 
an object. 

When you write a constructor, the method name must match exactly with that
of the class, and it must be declared with NO return type (not even void).
For example:

  public class Foo{

    int x;
    public Foo() // constructor- no return type and the same name as the class
    {
       x=3;
    }
 }

The constructor can take values to be used to initalize the various variables
in the newly created instance:

 public class Pizza
 {
   int radius;
   public Pizza(int r)
   {
        radius=r;
   }
 }


Note that if you declare any constructor, java does not automatically provide
a default.  Also, note that it is legal to declare a method with the same
name as the class which is not a constructor.  If a method is declared with
the same name as the class, but is declared with any return type (including
void), then it is a normal method, not a constructor, and is treated as such.

How do I use these constructors?

You cannot call the constructors directly, instead, you use the new keyword
to create a new instance of the class, and you may pass any paramters to
the constructor as paramters to new.

Pizza myDinner= new Pizza(14);  //calls Pizza(int) to initalize the values
                                // in this pizza.

What exactly does this code do?
First, it declares a variable "myDinner" which is a reference to something
of type Pizza.  The new keyword creates a new instance of the Pizza.
The constructor Pizza(int) is called to initialize this new instance, so
the size of the pizza is 14.  Then the the assignment makes "myDinner"
reference the newly created Pizza.  

What are accessors and modifiers?

Accessors and modifiers are methods that allow other objects to get or
set the values in the variables of an object.  Accessors and modifiers
are named with "get" and "set" in java by convention. For example,
the accessor and modifier for a variable int size would be:

  int getSize(); //accessor
  and
  void setSize(int newSize);  //modifier

One might wonder "Why use accessors and modifiers? It would be easier to
just make size public and do x.size=newSize or blah=x.size."  This might
seem easier to start off, but accessors and modifiers can provide two
important features that direct variable access does not:

 - access control- the method could restrict what can get or set
   the values of the specific field.

 - flexibility- if the underlying representation of the data changes,
   code only needs to be changed in the accessor and modifier methods-
   not EVERYWHERE that the data is referenced.  There are also cases
   in which other actions should be taken when a field is changed.
   Consider a LinkedList that keeps track of a count of the number
   of items in it (it increments the count when something is added, and
   decrements that count when something is deleted)- if the head were set
   to null, then the count would still reflect items being in the list, 
   even though there is nothing.  By making the head private, and having
   a modifier that would recount the items in the list when the head changes,
   the count would always be correct.

REFERENCES

• What is a reference?
• What are the implication of references?
• What is "pass-by-constant-reference"?

What is a reference?

 
A reference specifies the location in memory of some object.  A reference
is very similar to a pointer.  Multiple references can point to the 
same object. In java, all variables which are declared as any object 
type are actually references to an object of that type.  

  Declaration of a reference:
   
       Object x;
 
 
Instantiation of an object. Note the new operation returns the
location (address) of the newly created object.

      x = new Object();

These two actions may be combined into one step:

      Object x =new Object();

The result of this could be conceptually depicted as follows:
 

  x-------->   +----------+
               | an object|
               +----------+

What are the implication of references?

There are several implication of references.  One of them is that when 
assignments are made (y=x), the reference is being assigned- no new object
is being made:


 Object y=x;  (could also be written in two statements)


  x-------->   +----------+
               | an object|
  y-------->   +----------+


Note that changes to the contents of x will affect the contents of y because
they both reference the same object.

Lets look at a simple example:

  public class StringHolder{
     public String s;
  }
 
 StringHolder c,d;
 c=new StringHolder();
 c.s="Hello";
 d=c;
 d.s="World";
 System.out.println("c has "+ c.s); //prints "c has World"

Note how c and d both point to the exact same object:

 c----> +----------+ 
        | --------------> "World"
 d----> |----------+
 
 (diagram shown this way, as s in StringHolder is ALSO a reference)   

Note that just changing c does NOT affect d, only changing the contents:

 c=null;
 System.out.println("d.s is "+ d.s);// d.s is still World

 c---> null

 d----> +----------+ 
        | --------------> "World"
        |----------+

What is "pass-by-value"?

In Java, both primitives and references to objects are passed (to
methods) by value. Pass by value means that a temporary copy of the
value is made to send to the called method. This copy is destroyed
when the called method returns. Any changes to the parameter itself
do not affect its value in the calling  method because it is a temporary
copy.  Note: When a reference is passed in to a method, the object to
which it is referring is not copied thus changes made to the object WILL
cause permanent or persistent changes.

Lets look at an example with the StringHolder class from above:

 public void methodThatDoesNothing(StringHolder sh)
 {
   sh=new StringHolder(); 
   sh.s="Hello World";
 }


 public void methodThatDoesSomething(StringHolder sh)
 {
  sh.s="Goodbye World";
 }

 
now if we take
 StringHolder a=new StringHolder();
 
we have


 a ------->+---------+
           | (null)  |
           +---------+

now lets look at a call to methodThatDoesNothing(a)

 
we make a copy of the REFERENCE a and pass it as sh"

  a ------->+---------+ 
            | (null)  | 
 sh-------->+---------+ 

The method now points sh at a NEW StringHolder: 

  a ------->+---------+ 
            | (null)  | 
            +---------+

  sh------->+---------+
            | (null)  |
            +---------+

and "Hello World" is put in this new object:

  a ------->+---------+
            | (null)  |
            +---------+

  sh------->+---------+
            | --------------->"Hello World"
            +---------+


then, the method returns and sh is destroyed:


   a ------->+---------+
             | (null)  |
             +---------+

a still points to the same object that it used to.


Now, lets look at a call to methodThatDoesSomething(a):

  a copy of the REFERENCE a is passed in as sh
  a ------->+---------+
            | (null)  |
 sh-------->+---------+
  
  
the CONTENTS of that reference are changed:


  a ------->+---------+
            | ----------------> "Goodbye World"
 sh-------->+---------+
  

The method returns and the sh REFERENCE is destroyed, but a 
still references the same object, which now contains a different String:

  a ------->+---------+
            | ----------------> "Goodbye World"
            +---------+

SCOPE AND SHADOWING

• What is scope?
• What is variable shadowing?

What is scope?

Scope refers to where a variable can be "seen" by the compiler.
A variable is said to be "in scope" when the compiler can "see" it.
An attempt to use a variable when there is no variable by that name
"in scope" results in an "Undefined variable" error.
The scope of a variable is generally anything inside of the same set of
curly braces as the variable declaration (note: for local variables,
the scope begins with the declaration.  for variables declared at the
class scope- i.e. static or instance variable, the scope is the entire class)
The exception to this is if a variable is declared in a for statement,
the scope of that variable is limited to the body of the loop.
Also, the scope of a parameter to a method is the method in which it resides.

 public class Foo
  {

     int x;  // x is declared at the class scope- it may be used
             //anywhere in the class
   
    public static void someMethod(int y)
    {
        int z;
        // y and z can be used in this method
        for(int i=0;i<10;i++) // i can only be used in this loop
            {
              S.O.P(i);
            }
        // i can NOT be used here
       if(y==0)
         {
           char c;  // c can be used in this if block
            while(z)
                {
                     // c can also be used in here, since this  
                     // block is in the one in which c is declared
                }
        }
         // c can not be used here
    }
 }//end of class Foo

What is variable shadowing?

Variable shadowing occurs when there are two different variables of the same 
name in scope at the same time.  When this happens, the compiler will always
choose to use the variable that was declared in the innermost scope.
Lets look at an example:

 public class Foo{

       int x; // an instance variable x
      
       public void setX(int x) // a modifier for x
       {
         x= x; //this line does nothing useful.
       }
 }

The instance variable x is shadowed by the pararmeter x in the setX method.
This shadowing means that the line x=x assigns the value of the x parameter
back to the x parameter- in effect, doing nothing.

CONSTRUCTOR CHAINING

• What is constructor chaining?
• Why is it useful?

What is constructor chaining?

Constructor chaining occurs when the constructor is overloaded, and
one constructor delegates some or all of its work to another constructor.
Remember that a constructor cannot be called directly.  Also, realize
that we do NOT want to use new in this case, because that would make
 another object rather than initalizing the current object, which is not
what we want.  Instead, we must use another keyword - this.
The keyword this has multiple uses- in the case in which this
is called as if it were a function, this is treated as a call to another
constructor in the same class.   Calling this as if it were a function
may only be done inside a constructor, and it MUST be the first line of
that constructor.
Lets take a simple example:

 public class Foo
 {
       int myNumber;
       String myName;
     
       public Foo()
       {
         this(0);  //chains to the constructor that takes an int
       }
       public Foo(int x)
       {
         this(x,"Baz"); //chains to the constructor that takes an int and
                        //a String
       }
       public Foo(int x,String s)
       {
         myNumber=x;  //does the actual initialization
         myName=s;
       }
  } 

Why is it useful?

So why is this useful? The main reason is that it avoids code duplication
(and all the good stuff that goes along with that- less to write and debug,
easier to change, etc)...  Consider if we had a class with say 5 constructors
in it, and we needed to make a change: maybe we add a new variable, or 
realize that some other initialization needs to be performed.  If the
constructors are chained, then only one code change needs to be made, as
opposed to the 5 required if they are not chained.

MULTIDIMENSIONAL ARRAYS

• Arrays of arrays
• Initializing multidimnsional arrays
• Accessing multidimensional arrays

Arrays of arrays

As you should already know, arrays are objects in java.  The implication of
this is that an array type can be treated like any other type.  Since 
an array type (say int[]) is a class itself, one could make an array
of int[]s (in other words, an array of arrays).  How would you declare such
a thing? The same way as any other array declaration:

  type [] name;

in this case, type is "int[]", so you might have

  int[] [] foo;

This is an array of int arrays.  This is also called a 2 dimensional int
array. Note that dimension should not be confused with length- the dimension
of the array refers to the number of sets of []s that there are.

This same concept can be applied to create an array of any number of
dimensions that is desired.  int[] [] is a class, so it is valid to make
an array of int[][]s, which would be an int[][][], or a 3 dimensional
int array and so on.

Initializing multidimensional arrays

Like 1D arrays, multidimensional arrays may be initalized by specifying
the contents of the array along with its declaration:

 int [][] x= {
   {1,2,3},
   {4,5,6},
   {7,8,9}};

Note how each element in x is an array containg ints.  The 3 elements of x
are separated by commas, just like the elements of any other array being
initalized this way.  There is nothing that restricts muldimensional arrays
to hold the same size array in each index either:

 int[][] y= {
  {1},
  {2,3,4},
  {5,0},
  {-4,8,9,-1}};

is also perfectly legal.

Multidimensional arrays may also be initialized dynamically with the new 
keyword:

 int [][] z=new int[3][4];

 creates a 3x4 int array.  It is basically the same as

 int[][] z={
 {0,0,0,0},
 {0,0,0,0},
 {0,0,0,0}};

It is also possible to specify only the leftmost dimension for the array
when you instantiate it with new:

 int[][] a= new int[3][];

In this case, a is an int[][] which holds three null references to int[]s.
These references must be initalized with valid array references (either
existing arrays, or ones created with new) before they can be used.
 

Accessing multidimensional arrays

Remember that each element in a multidimensional array is in itself an array.
If we look at the single dimensional case:

 int [] iArray=new int[3];
 iArray[0]=1;
 int x=iArray[0];
 
We remember that by indexing into the array, we get an int from an int[].
A similar principle applies with multidimensional arrays- if we index into
an int[][], we get an int[].  We can then index into that array to get an
int. 
 
 int[][] x= new int[3][];

 for(int i=0;i<x.length;i++) // What is x.length? (Ans: 3)
  {
     x[i] = new int[4]; //x is an int[][], so x[i] is an int[]
                        //we can make a new int[] and store it into
                        //something whose type is int[]

  }

  x[0][1] = 3;  //x[0] is an int[]- it is the first int[] held in x
                //so we can index into that array and store 3
  
What would x[1].length be?

Answer: 4.    
  
What would the following code segment print:

  x[2][0]=3;
  int [] iArray=x[2];
  iArray[0]=2;
  System.out.println("x[2][0]= "+x[2][0]);
  System.out.println("iArray[0]= "+iArray[0]);

Answer:
  x[2][0]= 2
  iArray[0]= 2

The reason for this is because iArray references an arrary- in this
case, it references x[2], so since they both reference the same 
memory, changing x[2][0] is the same as changing iArray[0].

 
           0       1         2
 x-->  +--------+---------+--------+
       |        |         |        |         
       |    |   |     |   |    |   |          
       +----|---+-----|---+----|---+            
            |         |        |             
            |         |       \ /
            |         |        V
            |         |       +------+------+------+------+
 iArray --------------------->|      |      |      |      |
            |         |       |      |      |      |      |
            |        \ /      +------+------+------+------+
            |         V          0       1     2      3
            |      +------+------+------+------+
            |      |      |      |      |      |
            |      |      |      |      |      |
           \ /     +------+------+------+------+
            V         0      1       2     3
        +------+------+------+------+
        |      |      |      |      |
        |      |      |      |      |
        +------+------+------+------+
           0      1      2      3

The above drawing indicates how this situation works.
x[2] is a reference to to the array on the rightmost side of the drawing.
iArray is assigned this reference, so it also points to the same array.
Walk through the code with this drawing- be sure to understand how the number
3 gets put in the x[2][0] box and then the same box is overwritten 
with an access to iArray[0].

INSTANCE VS STATIC

• What is the difference between an instance method/variable and a static method/variable?
• When would I want something to be static?
• Why can't I make everything static?

What is the difference between instance and static?

When a variable is an instance variable, each instance of the class
that is created gets its own copy of that variable- changes to one 
instance's copy do not affect the copies that exist in any other instances.
If a variable is a static (class) variable, then there is only one copy of 
it, regardless of the number of instance of the class that are created.
Any reference to the static variable from an instance will refer to 
the one variable shared by all instances.  An instance method is
invoked upon a specific instance of the class and acts upon that instance.
Any references to instance variables are implicitly references to the
variables that live in that instance of the class.  A static method 
does not act on any specific instance- rather it acts on the class as a whole.
Static methods cannot reference any instance variables, as there is no
current instance that the method is acting on.

Lets take the simple example:

 public class Foo{

   public int x; // instance variable
   public static int y; //static variable
 }

Conceptually, we have this:

  +----------+
  | Foo      |
  +----------+
  |  y       |
  +----------+

The Foo class holds the y variable.  We have not made any instances of 
Foo yet, so there are no xs anywhere.

lets say we now do

Foo a,b,c;
a=new Foo();
b=new Foo();
c=new Foo();

now, we conceptually have

  +----------+  +----------+ 
  | Foo      |  |  a       |
  +----------+  +----------+
  |  y       |  |  x       |
  +----------+  +----------+

  +----------+  +----------+ 
  | b        |  |  c       |
  +----------+  +----------+
  |  x       |  |  x       |
  +----------+  +----------+


there are three different xs (one in a, one in b, and one in c), but
ONLY one y.

Note that since a knows that it is a Foo, it is legal to say
 
 a.y=4;

this is exactly the same thing as saying

 Foo.y=4;  

think for a minute about what the following code does:

a.y=4;
b.y=5;
c.y=6;
System.out.println("a.y = " + a.y);
System.out.println("b.y = " + b.y);
System.out.println("c.y = " + c.y);
System.out.println("Foo.y = " + Foo.y);

(Answer: it prints
6
6
6
6
because y is static, so c.y, a.y,b.y, and Foo.y are the same)

When would I make something static?

Something should be static when it is an attribute of the class as a whole,
not of an instance in specific.  Consider the example of a Person class.
If the person class were to track population, the population should be static.
Why? because each person does not have a population count, instead, the 
population count talks about the number of people there are in general.

Why can't I just make everything static?

If you make everything static, then you lose out on most of the benefits of
OO.  If you find that you are making many things static, you are probably
not designing your program well.  Consider a Radio class.  The station 
that the Radio is tuned to should definately be an instance variable.
If you make the station a static variable, then you are saying that 
all Radios are always tuned to the same station- by changing the
station on one Radio, you automatically change the station that every other
Radio in the world is tuned to.  Such a situtation is clearly wrong, and
we see that since each Radio instance needs to have its own station,
the station should be an instance variable.  To tell if something
should be an instance or a static varaible, ask yourself "if I change 
this on one instance, should it change for another instance" if so, 
then use static, if not, use instance.  Methods that need to be invoked
on an instance so they can deal with the variables in that instance must
be instance methods.  If the method does not need to deal with any instance
variables, it can safely be made static.

Lets look at a small example:

  class Widget
  {
     String name;
     int serialNumber; //instance variable
     static int census = 0; //keeps a count of all Widgets made

     public Widget(String name)
     {
         setName(name);
         census++;   
         serialNumber = census;  
     }
  }

Why is census a static variable and why is serialNumber an instance
variable.  What would happen if census were an instance variable?  If
serialNumber were static?  These types of things COULD be a key part
of a misguided java programmer question.

== vs .equals()

• The difference between .equals and ==
• How does .equals tell if the objects are equal?

The difference between .equals and ==

Primitives may only be tested for equality with ==, but for objects, there
are two differents ways to test for equality: using the .equals method,
or the == operator - they can have very different results. The ==
operator compares two references to see if they are the same.  The 
.equals method asks the object to determine if it is equivalent to 
another object.  Two objects can have the same contents, but reside
at different memory locations, making (a==b) false, but (a.equals(b)) true.
Let's look at a simple example with Integers:

   Integer a=new Integer(1);
   Integer b=new Integer(1);
   if(a==b)
      System.out.println("Same reference for both objects");
   else
      System.out.println("Different references for the objects");
   if(a.equals(b))
     System.out.println("a and b have the same contents");
   else
     System.out.println("a and b have different contents");

Think for a minute as to what the output from this example is.

Answer:

   Different references for the objects
   a and b have the same contents

If you wanted to tell if a and b were equivalent (and in this case they are-
they are both identical Integers- each holds 1), then == would NOT
give you the correct results- only by using the .equals method would 
you be able to tell that they are in fact identical.

How does .equals tell if the objects are equal?

  
The way that the .equals method tells if the objects are equal is 
completely dependent on the code written for it in that particaluar
object's class.  The .equals method in the String class, for example,
checks character by character to see if the two Strings are lexigraphically
equivalent (if the second object in not a String, it returns false).  The
.equals method in the Integer class checks to see if the two Integers both
are holding the same int(if the second object in not an Integer, it returns
false).  If you were making a Box class, you might decide that two
Boxes are equal if they have the same size regardless of their contents:
 

  class Box
    {
        int l, w, h;
        String contents;

        public boolean equals(Object o)
        {
            boolean retval = false;
            if(o instanceOf Box)
            {
	      Box b=(Box)o;
              if(l==b.l&&w==b.w&&h==b.h)
                 retval=true;                
            }
            return retval;
        }
    }
 
or you might decide that the Boxes must ALSO have the same contents, as
well as the same size:

 class Box
    {
        int l, w, h;
        String contents;

        public boolean equals(Object o)
        {
            boolean retval = false;
            if(o instanceOf Box)
            {
	      Box b=(Box)o;
              if(l==b.l&&w==b.w&&h==b.h
                 &&contents.equals(o.contents))
                 retval=true;                
            }
            return retval;
        }
    }

  (Note: use of a/m methods + check for null ommited for brevity)

Which .equals method is correct? It depends on how boxes need to be
compared for equality in the program.  If the program wants boxes
with different contents to be treated as if they are the same, then
the first example is correct.  If the program needs for boxes with
different contents to be treated as different, then the second is correct.

INHERITANCE

• is-a versus has-a and What is inheritance?
• How do I extend a class?
• What is an interface?

is-a versus has-a and What is inheritance?

The distinction between an "is-a" relationship and a "has-a" relationship
is an crucial part of object oriented programming.  An "is-a" relationship
exists between two classes when one is a more specific type of another:

   A Cat is-an Animal.
   A Banana is-a Fruit.
   
A "has-a" relationship exists when one class is the type for an attribute 
of another:

  A Salad has-a Tomato.
  A Car has-an Engine.

If you see an is-a relationship exists between classes, then inheritance 
is appropriate.  If a has-a relationship exists between classes, then
composition is appropriate.  (Composition is simply the fancy term
for when one class holds an instance variable whose type is the other class). 
Inheritance allows one class to implicitly have all of the properties 
(methods and variables) of a parent class.  The "child class" can override
these methods to specify new behavior, or can add completely new methods 
that were not present at all in the parent class.  For example,
if an Animal could move and sleep, a Cat (which is-an Animal) would inherit
these methods from Animal.  The Cat class could specify new behavior
that is not present in all Animals (such as chasing string and pouncing
on things- which Birds and Fish don't do).  The Cat class could also 
redefine the behavior that is already specified in Animal by overriding
the methods found in the Animal class.

How do I extend a class?

Let's assume that we have the Animal class written:

  public class Animal
  {
     public void sleep(){...}
     public void move() {...}
  }

We can tell Java that Cat inherits from Animal with the extends keyword:

  public class Cat extends Animal
                   \-------------/
                         \
                          specifies that the parent class is Animal

Cat is now said to be a "subclass" of Animal.  Inside of the Cat class,
we do NOT have to redeclare sleep or move if we want them to have the
same behavior as Animal- they are automatically inherited:

 public class Cat extends Animal
 {
   public void chaseString(){...}
   public void pounce()     {...}
 }

 .....
 Cat c=new Cat();
 c.sleep();  // OK even though no sleep() written in Cat- it comes from 
            // the parent class- Animal.

What is an interface?

An interface defines a type in the most abstract sense.  It also 
specifies a contract which classes must meet to implement it.  An interface
may specify 
 

 
public static variables (usually final to make them constants)
 
methods headers
 
No code may be written within the method declarations in an interface-
they must simply be followed by a ;
 
Any class may implement an interface if it defines all of the methods
that are declared in that interface.  When a class implements an interface,
then instances of that class may be treated as if their type were that
interface- i.e. if 

  public class Foo implements FooType 
                   \-----------------/
                           \ 
                           specifies that Foo implements the FooType interface


then it is legal to say

  FooType ft= new Foo();
  
    or to have
 
  public void methodThatTakesAFooType(FooType something)
  .................
  Foo f=new Foo();
  methodThatTakesAFooType(f);

Note that an interface cannot be instantiated.  It is illegal to try to
do 

   new FooType(); //ILLEGAL

anywhere in the program if FooType is an interface.

EXCEPTIONS

• What are exceptions and why do we use them?
• How do I deal with exceptions?
• How can my method ignore an exception?
• What is the difference between checked and unchecked exceptions?
• Why do we use them?

What are exceptions and why do we use them?

When a situation arises which prevents the program from continuing to 
execute normally, an exception is raised (so called because the circumstance
is exceptional).  In Java, these exceptions are treated as objects, just
like most everything else.  The Exception class is the superclass of
all exceptions.  There is also an Error class- Errors are similar to 
exceptions, but are indicative of a much more fatal problem in the program-
usually one which cannot be recovered from.  If an Exception or an 
Error is not dealt with, the program will terminate and provide
a stack trace to indicate where the problem occured.

How do I deal with exceptions?

The occurrence of an exception does not have to be fatal to the program-
if the programmer specifies the behavior that the program should take
in the event of an exception occuring, then that action will be taken, 
and the program will not terminate.  When an exceptional sitaution occurs,
the exception is said to be "thrown."  In order to specify how to deal with
exceptions, the try-catch construct is used.  The code in which
an exception might occur is enclosed in a try block, which is followed
by one or more catch blocks, that specify what to do if a certain
type of exception is thrown in the corresponding try block- i.e.

  try{

   code that could throw an exception

  }
  catch(SomeException se)
   {
      code to execute if SomeException is thrown from the try block.
   }
 
Note that the catch statement holds what looks like a variable declaration:

             looks like a variable declaration- acts like one too.
            /
        /-----------------\
 catch ( SomeException se )
\----/  \------------/\--/
  \         \           \
   \         \           name of variable that will hold the caught exception
    \        type of exception that is being caught
    the catch keyword

Inside of the catch block, se may be treated like a variable of type
SomeException.  se will automatically be initialized to hold the 
exception instance that was thrown and caught.  A typical use for
the variable with the caught exception (se in this case) is to
print a stack trace from when the error occured.  This is done
with the printStackTrace() method- which prints the stack dump 
to the error stream, although other actions may be taken.  For example:

 catch(SomeException se) 
  {
    se.printStackTrace();
  }
 
 
In java, the exception can either  be automatically instantiated and thrown
by the vm, or explicitly thrown by the program with the throw keyword. 
When an exception is thrown, the exception propogates up the call stack 
until a catch block which catches its class (or a superclass) stops it.
If no such catch block is found when the exception has propogated out of 
the main method, then the stack trace is printed to the error stream and 
the program is terminated abnormally.  As the exception propogates up
the call stack, the stack frames are destroyed.  Once the exception 
is handled, control continues from the catch block- it does not return 
to the point at which the exception was thrown.  For example:

 public class Foo{
 public static void foo()
 {
  System.out.println("in foo");
  try{
    bar(0);
    System.out.println("after bar");
   }
  catch(Exception e)
  {
   System.out.println("caught "+e);
   e.printStackTrace();
  }
  System.out.println("at the end of foo");
 }

 public static void bar(int x)
 {
 System.out.println("in bar with x= "+x);
 if(x==0)
   {
   System.out.println("im going to throw an exception");

   }
 System.out.println("3 /x = "+ (3/x));
 System.out.println("at the end of bar");

 }

 public static void main(String [] args)
 {
  foo();
 }
}

prints

   in foo
   in bar with x= 0
   im going to throw an exception
   caught java.lang.ArithmeticException: / by zero
   java.lang.ArithmeticException: / by zero
           at Foo.bar(Foo.java:25)
           at Foo.foo(Foo.java:6)
           at Foo.main(Foo.java:30)
 at the end of foo

when it is run.  Trace through the code.  Be sure that you understand how
the thrown exception causes control to jump out of bar as the stack unwinds
back into foo where the rest of the try block is skipped, the catch block is
executed, and then execution proceeds from there.  Also, be sure to
understand how the stack trace shown above can help pinpoint an error when
the program crashes:
 
 java.lang.ArithmeticException: / by zero    <-- this line tells you what
                                                 went wrong
           at Foo.bar(Foo.java:25)           <-- this tells you where it 
                                                 happened
           at Foo.foo(Foo.java:6)            <-- where the bar method was 
                                                 called from
           at Foo.main(Foo.java:30)          <-- where the foo method was
                                                 called from

This stack trace shows us that main got to line 30, where it called
foo().  foo executed until line 6, where it called bar(0).  bar got
to line 25 where it attempted to divide by 0, which is illegal, and
generated an exception.

The catch blocks will catch not only the class whose name is specified,
but also, any subclasses of the specified class.  Because of this fact,
more specific exception classes must be caught first when multiple catch
block are present.  For example, if the programmer wanted to catch
Exception, RuntimeException, and AritmeticException (ArithmeticException
extends RuntimeException, RuntimeException extends Exception), then
the catch blocks MUST go in this order:

   try{
      code here
   } 
   catch (AritmeticException ae)
   {
      code here 
   }
   catch (RuintimeException re)
   {
      code here 
   }
   catch (Exception e)
   {
      code here 
   }
If an exception class has a catch block, and a later catch block for the
same try block is declared to catch a subclass of that exception class,
then a compiler error is generated.

As a side note:
Due to their fatal nature, Errors should not be caught except in very 
rare circumstances.  For the purposes of this course, Error and 
its subclasses should NEVER be caught.

How can my method ignore an exception?

It may not be the case that your method will always want to specify code
to handle some or all of the exceptions that may occur inside of it.
If the method does not handle the exception, then the exception will
simply propogate upwards to the calling method (which might handle it,
or might simply let it propogate upwards again- and so on).  If the 
exception is a certain type of exception called an "unchecked exception,"
then this behavior of allowing the exception to pass upwards is automatically
allowed with no extra code or precautions on the part of the programmer.
If the exception is a "checked exception," then the programmer must take
care to indicate via the method header that the method can possibly
throw the exception so that calling methods will know that the exception 
must either be caught or continue to propogate upwards.  By adding a
"throws clause" to the end of the method header, the compiler will know
that it is possible, and permissible for checked exceptions of the types
listed in the throws clause to propogate out of the method.

 public void baz() throws FileNotFoundException
                   \----------------------------/
                       \ 
                      the throws clause specifies that the baz method
                      could throw a FileNotFoundException.  Any
                      method that calls baz must either catch this exception,
                      or be declared with a throws clause that includes 
                      FileNotFoundException.

(acceptable methods):

 public void method1() throws FileNotFoundException
 {
  blah blah
  baz();
  blah blah
 }

 public void method2()
 {
   try{
     baz();
   }
   catch(FileNotFoundException fnfe)
   {
   blah blah
   }
 }
public void method3()
 {
   try{
     baz();
   }
   catch(IOException ioe) //IOException is a superclass of FNFE, so this
     //will catch it too, so it is ok.
   {
   blah blah
   }
 }

What is the difference between checked and unchecked exceptions?

RuntimeExceptions (and subclasses thereof) are referred to as "unchecked 
exceptions" (subclasses of Error are also unchecked).  All other exceptions
are refered to as "checked exceptions." Unchecked exceptions are considered 
to be either so frequently possible (RuntimeExceptions) or infrequent and
fatal (Errors) as to not need to be explicitly checked for wherever they
might occur.   Consider for a moment the following code:

 int[] iArr=new int[y]; //y is an int
 ...
 a=b/iArr[c]; //a,b,c ints
 ...
 foo1.setX(a+foo2.getX()); //foo1, foo2 objects with relevant methods 

Think about the possible runtime exceptions that could occur in just those
two simple lines of code.  In this case, there are at least
4 possible exceptions that could occur: NegativeArraySizeException,
NullPointerException, ArrayIndexOutOfBoundsException, and ArithmeticException.
If RuntimeExceptions were checked, then just about every method would
have to either catch or declare two to five exception types, making 
for a lot of useless coding overhead.  Checked exception, on the otherhand,
have the possibility of occuring much less frequently- for example,
a FileNotFoundException could only be (reasonably) thrown when looking for 
a file. 

Why do we use them?

Structured exception handling simplifies dealing with error a great deal
over testing each method call for success or failure.  In C, for example,
the return value of a function must be checked (different values indicate
failure for different functions too), to see if it succeded or failed.
If the function failed, the program must look at the value in the global
variable errno to determine why the function failed.  C has no compile 
time enforcement of error checking, whereas with exceptions in java,
the compiler requires that you recognize the fact that a checked exception
could be thrown.

POLYMORPHISM

• What is polymorphism?
• Why is it useful?
• What are abstract classes?

What is polymorphism?

Polymorphism is the property by which an instance of a subclass may be
treated as an instance of its parent class. This means that if we declare
a variable or parameter whose type is class Animal, and we have an instance 
of Cat (where Cat is a subclass of Animal), we may freely assign that cat
to the variable, or pass it as the parameter whose types are Animal:

 Cat c= new Cat();

 Animal a=c; // this is ok

 methodThatTakesAnAnimal(c); // parameter type is Animal- this is ok,
                             // because a Cat is-an Animal

>From a conceptual standpoint, this works because the inheritance relationship
means "is-a", and since a Cat is-an Animal, we can use it just like one.
 

Why is it useful?

Polymorphism allows for flexibility in a program.  Consider if you had
a Person class which had

  public void pet(Animal a)

so that the Person could pet an Animal.  This one method could be used to
pet any type of Animal- cats, dogs, rabbits, etc.  If there were no 
polymorphism, then the Person class would need a separate method
to pet each type of animal.  When a new animal is added, then 
the Person class would have to be changed to accomodate it. Because
of polymorphism, the pet method can take in any Animal and deal with 
it appropriately.  Likewise, many Animals of different types could
be stored in an array whose type is declared as Animal []:

  Animal[] theZoo=new Animal[3];
  theZoo[0]=new Cat();
  theZoo[1]=new Dog();
  theZoo[2]=new Lion();

What are abstract classes?

In some cases, we find that a type does not really have instances,
rather its subtypes do- for example, you don't see anything that is
"just an Animal" walking down the street- you might see a Cat or a
Dog, both of which are Animals, but both of which also have a more 
specific type.  In this type of situation, we also find that there
may be behaviors which all subtypes have, but do differenlty.  For
example, Animals can move, but a Fish does not move the same way that
a Dog does.  It would be nice for Animal to have a move method, but
which one is the correct one?  The answer is that neither Fish's nor
Dog's manners of movement should be in Animal's move method- instead,
it should be declared abstract.  An abstract method ensures that subclasses
will implement that method to provide their own version of that functionality
without attempting to specify the behavior of the more generic class.
Once a class has an abstract method, it is said to be an abstract class,
which means that it cannot be instantiated- only its subclasses may be
instantiated, and only once they supply the required abstract methods.
Let us look briefly at the syntax for abstract declarations:

 public abstract class Animal
 \-------------/ \------------/
     \                 \ 
      \                 The rest of the class declaration is as usual.
       \                A parent class, or interfaces that are implemented
        \               may be supplied as usual.
         Adding abstract to the modifier list specifies that this class
         is abstract and may not be instantiated.  Putting the abstract
         keyword here is required if one or more abstract methods are declared,
         or if the class does not fully implement an interface.

 {
   public abstract void move() ;
   \--------------/\---------/\-/
        \               \      \
         \               \      Instead of following the method declaration 
          \               \     with a body, a single semi-colon is placed
           \               \    afterwards to end the declaration.
            \               The return type, name, and parameters are put 
             \              as usual.
              Abstract is added to the modifier list to indicate that
              the method is abstract.
 

 }
 



With the above code, the following would be legal:

 public static void someMethod(Animal a)
 {
  a.move();
 }

How can this be legal? We just saw that Animal doesn't have the any code 
in the move method- so what does it do? Remember that we cannot make an
instance of Animal- it is abstract, instead, a is really some specific
Animal (with code to move) polymorphed as a generic Animal- the method might
be called like:


 Cat c=new Cat();
 someMethod(c);

in this case, it will use the move from Cat.

DYNAMIC BINDING

• What is dynamic binding?
• How does it relate to polymorphism?

What is dynamic binding?

When we talk about dynamic binding in java, we are referring to the process
by which a method call is resolved at runtime.  When a method is invoked
on an object- the method that is actually invoked depends on the type of 
the actual object referenced, not on the type that the reference was declared
as.  More simply put, if we have

 Animal a= new Cat();
 a.speak();

the method that gets called is the speak() method declared in Cat (the
actual type of the Object), not in the speak() method in Animal (the declared
type of the Object).  Let us consider what is happening here:

 Animal a= new Cat(); 

a Cat object is created and a is set to reference it:


 +---+
 | a |---------------\
 +---+               |
                    \ /
                     V
                 /\       /\ 
                /  \ _-_ /  \
               '    '   '    '                             '`
              '   O    O      '                           / /
             (      /\        )                          / /
              `              '                          / /
               `   \--/     '                          / /
		\----------/                          / /                
                  \      \                           / /                 
                   \      \                         / /                  
                    \     -------------------------/ /                     
                     |                              /                       
                     |                              |
                     |                              |
                     --------------------------------
                      / /                    / /
                     / /                    / /
                    / /                    / /
                  #' /                   #' /
                 #--'                   #--'

(yes, that is a Cat, and yes I am aware that real cats aren't square)
When you think about the fact that there is a Cat on the end of that 
reference, it becomes much more apparent that calling the speak method
will result in the invocation of the speak method in Cat.
If we were to call a Cat fido, it would still meow:

Animal fido=a;

 +---+                         +------+
 | a |---------------\         | fido |
 +---+               |         +------+
                    \ /             |
                     V              |
                 /\       /\        |
                /  \ _-_ /  \  <----/
               '    '   '    '                             '`
              '   O    O      '                           / /
             (      /\        )                          / /
              `              '                          / /
               `   \--/     '                          / /
		\----------/                          / /                
                  \      \                           / /                 
                   \      \                         / /                  
                    \     -------------------------/ /                     
                     |                              /                       
                     |                              |
                     |                              |
                     --------------------------------
                      / /                    / /
                     / /                    / /
                    / /                    / /
                  #' /                   #' /
                 #--'                   #--'

Any references that we make of any valid type will still point to the actual
Cat.  When the method is invoked, remember that the referenced object is asked
to perform the method- so since the actual object here is a Cat, the Cat's 
speak method would be used.

How does it relate to polymorphism?

Polymorphism allows us to treat things as a more generic type- dynamic binding
guarantees that they will retain their correct behavoir while being treated
as that more generic type.  If we were to have an array of Animals (say
for a zoo), then we would probably like them all to eat, speak, etc. 
as their correct type.  Let's presume we have a (small) zoo with  
a Cat, a Fish, and a Bat:

 Animal[] myZoo=new Animal[3];
 
 myZoo[0]=new Cat();
 myZoo[1]=new Fish();
 myZoo[2]=new Bat();
 //let us then say that we were to iterate across the array and ask
 //each animal to speak
 for(int i=0;i<myZoo.length;i++)
    {
       myZoo[i].speak();
    }
 //then let us make them eat
 for(int i=0;i<myZoo.length;i++)
  {
      ((Animal)myZoo[i]).eat(); //hmm.. an explicit cast back to Animal?
  }


Which methods get called in each of these cases? 
Think about it for a minute.
Does the explicit cast fool dynamic binding? lets see why not..

Lets look at what our array has:


 myZoo -------> +------------+-------------+------------+
                |            |             |            | 
                +-----|------|------|------+------|-----+
                      |             |             | 
                      |             |             |
                      |             |            \ /
                      |             |             V
                      |             |              
                      |             |         .'.   .'.   (Thats a bat)
                      |             |        /   \ /   \
                      |             |       '     O     '
                      |            \ /   
                      |       .     V   ,,
                      |       |\       /  `,           (Thats a fish)        
                      |       | \     /  O  `,      0  (Those are bubbles)    
                      |       |  \   /        `  0                             
                      |       |   \ /          )  o                            
                      |       |    X          ,'o                             
                      |       |   / \       ,'                             
                      |       |  /   \    ,'                              
                      |       | /     \ ,'                                  
                      |       '/       .                                
                      |                                                      
                     \ /                                                    
                      V
                 /\       /\  (same old square Cat)
                /  \ _-_ /  \
               '    '   '    '                             '`
              '   O    O      '                           / /
             (      /\        )                          / /
              `              '                          / /
               `   \--/     '                          / /
		\----------/                          / /                
                  \      \                           / /                 
                   \      \                         / /                  
                    \     -------------------------/ /                     
                     |                              /                       
                     |                              |
                     |                              |
                     --------------------------------
                      / /                    / /
                     / /                    / /
                    / /                    / /
                  #' /                   #' /
                 #--'                   #--'

if we follow the reference along and cast it, we still have the same cat, fish,
or bat that we originally had- it doesn't matter how we cast it- its still
a (badly drawn) cat/fish/bat there at the end of that reference, so it
eats accordingly.

SUPER AND THIS

• The "this" keyword
• The "super" keyword

The "this" keyword

The this keyword can be used to refer to the current instance of the class.
It is also used in constructor chaining, in place of the method name for
the call to another constructor.  We will consider two primary uses for it
here:

 1) To resolve ambiguity in shadowed names

 For the first case, consider what happens when we have both an instance
 variable, and a local variable in scope at the same time, and we 
 attempt to assign one to the other:

 public class Foo
 {
   int someNumber;
   public void setSomeNumber(int someNumber)
   {
      someNumber=someNumber; //does nothing
   }
 }


 The left side "someNumber" is intended to be the instance variable, someNumber
 in the current instance of the class.  Therefore, we can use the expression

   this.someNumber 

 to refer to the correct variable, such as:

   this.someNumber=someNumber;

 2) When a reference to the current instance is needed as a paramter to 
    another method.
  
    Sometimes you will create an object which needs to know about the 
    instance of the object that created it.  When this is the case, 
    you may use the keyword this.  this is a reference to the current
    instance of the class.  Lets assume that we have dragons that lay eggs.
    The eggs know who their mother dragon is:

  class Dragon
  {
    String name;
    

    // Assume normal accessors and modifiers

    public Egg layEgg(String eggname)
    {
        e = new Egg(eggname, this); //because we are in an instance
        //method in the Dragon class, this is of type Dragon
        //and references the Dragon laying the egg
     
        return e; 
   }

    
 }


 class Egg
 {
    String name;
    Dragon mom;

    // Assume normal accessors and modifiers

    public Egg(String name, Dragon mom)
    {
        setName(name);
        setMom(mom);
    }

    public String toString()
    {
        return name + " and my mom is " + getMom().getName();  
    }
 }  

so lets look at what happens when we say

 Dragon d=new Dragon();
 Egg e=d.layEgg();

  +----+                              _   __,----'~~~~~~~~~`-----.__
  | d  |--------------------->     .  .    `//====-_             ___,-' `
  +----+           -.            \_|// .   /||\\  `~~~~`---.___./
             ______-==.       _-~o~  \/    |||  \\           _,'`
       __,--'   ,=='||\=_    ;_--~/_-'|-   |`\   \\        ,'
    _-'        '    |  \\`.   '-'~7  /-   /  ||   `\.     /
  .'                |   \\ \_    /  /-   /   ||      \   /
 / ______-----=     |     \\.`-_/  /|- _/   ,||       \ /
,-'           \_ --_ \     `==-/  `| \'--===-'       _/`
                    `-|      /|    )-'\~'      _,--~'
                      '-~~\_/ |    |   `\_   ,~             /\
                           /  \     \__   \/~               `\__
  +----+         /-->  _,-' _/'\ ,-'~____-'`-/                 ``===\
  | e  |        /     ((->/'    \|||' `.     ~`-/ ,                _||
  +----+       /                 \_     ~\      `^---|__i__i__\--~'_/
      |       /                 __-^-_    `)  \-.______________,-~'
      |      /                 //,-'~~`__--^-  |-------~~~~~'
     \ /    /                         //,--~~`-\
      V    /  
   .-----./       
  /      /\                     
 (   mom/  )
  \       /
   '-----'
 (Note: The above dragon is not original artwork: it was taken from
  an ASCII art collection in the public domain).

 When we do d.layEgg(), inside of the lay egg method, this is the same
 reference as d, so when d lays an egg and passes in this, the Egg that
 is created has a reference to d as its mom.  This ability comes in quite
 useful when writing GUIs and an instance of an event handling class
 needs to know about the the instance of the class that created it- which
 it will be interacting with when events come in.
i.e

  public class MyGUI{
       ..............
       this.addSomethingListener(new SomethingHandler(this));
  }

  public class SomethingHandler implements SomethingListener{
      MyGUI owner;
      public SomethingHandler(MyGUI owner)
      {
        this.owner=owner;
      }
      .........
      public void somethingHappened(SomeEvent e)
       {
        .........
        owner.someMethod();
        ..........
       }
  }
 

The "super" keyword

The super keyword can be used two ways:

 1) As the first line of a constructor to specify what constructor in 
    the parent class is invoked.  When an object is created,
    constructors are invoked all the way down the inheritance tree,
    starting with Object, and proceeding downwards until the class
    being instantiated is reached- this is accomplished by a call to the 
    super constructor as the first line of the constructor.  This call to the
    super constructor is accomplished with the super keyword being use as
    if it were a method invocation.   If no call to super is explicitly
    written in the constructor, then a call to super() is implicitly 
    made as the first line of the constructor, unless the constructor 
    is chained to another constructor via a call to this() as the first
    line (in which case, super will be the first call "at the end of the 
    chain").  Consider the following classes:

    public class Animal
    { 
      String name;
      public Animal()
      { 
         this("nothing");
         S.O.P("In Animal()");
      }
      public Animal(String initName)
      {
        name=initName;
        S.O.P("In Animal(String) with name="+name);
      }
    }
    public class Dog extends Animal
    {
        public Dog()
        {
           System.out.println("In Dog()");
        }  
    }
    public class Fish extends Animal
    {
    }
    public class Cat extends Animal
    {
       boolean bIndoors; //indicates if this cat is an indoor only cat
       public Cat()
       {
          this(false);
          S.O.P("In Cat()");
       }
       public Cat(boolean indoors)
       {
          super("Fluffy");
          bIndoors=indoors;
	  S.O.P("In Cat(boolean) indoors="+indoors);
       }
    }
  What is the output when a new Dog() is created?
  
  Answer:
       In Animal(String) with name=nothing
       In Animal()
       In Dog()
  Why is this?  The default constructor has an implicit call to super()
  as if it were the first line of code (right before the SOP).
  When that is called, it goes into Animal() which chains to Animal(String).
  That method sets the value, prints, and returns back to Animal(),
  which prints, and returns back to Dog().  Dog() prints its message
  last.
 
  What is the output when a new Fish() is created?
  Answer:
       In Animal(String) with name=nothing
       In Animal()
  Why is this? With no constructors supplied, java provides a default
  constructor that does nothing, but the implict call to super is still
  there.
      
  What is the output when a new Cat() is created?
  Answer:
        In Animal(String) with name=Fluffy
        In Cat(boolean) indoors=false
        In Cat()

  Why is this?  The default constructor for Cat chains to the
  constructor that takes a boolean.  For there, there is an explicit
  call to super("Fluffy") which makes it go into the Animal(String)
  constructor. The Animal constructor sets the name, prints, and returns
  back to the Cat(boolean) method, which sets the value, prints, and
  returns to the default Cat constructor,which prints.

 Question for thought: What happens if a super class has no default
 constructor?

 Answer: An explicit call to super (with parameters that match the types of
 a constructor in the super class) must be made from all constructors
 that do not call this() as their first line of code- at least one
 constructor must be provided- or a compile time error will result.
   
 2) In a method to invoke a method with the method resolution begining
    with the parent class, not the actual type of the instance.

   There are situations in which a class does not want to completely replace
   the functionality of its parent class, but instead it wants to perform
   its parent class's functionality and add additional functionality to 
   the method.  In such a situation, the method may call the version in 
   the parent class by using the super keyword when specifying the object
   to invoke upon:

      super.aMethod();

   Let us take as an example our typical Animal/Cat example.
   Let us say that an Animal has a name, size, fuzziness,
   and number of feet.  Let us also say that the toString() method
   in Animal returns a String which represents all of this information
   in a nice way.  Let us then say that Cat's also have information
   as to whether or not they are declawed, and if they are indoor cats
   only. Rather than duplicating all of the code in Animal's toString()
   to get the information about the information in Animal, it would be 
   nice to be able to simply call the method and append to that String:

   (in Cat)

   public String toString()
   {
      String ans=super.toString();  //call the toString on this
                                    //instance, but use the toString
                                    //from the super class, Animal
      if(bHasClaws)
         {
          ans=ans+"With claws\n";
         }
      else
         {
          ans=ans+"With no claws\n";
         }
     if(bIndoors)
         {
           ans=ans+"Indoor only\n";
         }
     else
         { 
           ans=ans+"Indoor and outdoor\n";
         }
  return ans;
  }

FILE IO

• What is File I/O?
• How do I do File I/O? and why are there so many classes?
• What exceptions do I need to worry about?

What is File I/O?

I/O stands for "input and output." File I/O is reading from or writing to
files on the disk.  It should be noted that java treats network 
sockets like files as far as IO goes, like UNIX does.  Although networking
is not covered in this class, it is quite similar to accessing files on 
the disk.  The standard input, standard error, and standard output are
also very similar to files, and in fact the types for these three streams
are found in java.io, along with the classes to perform other file operations.

How do I do File I/O? and why are there so many classes?

There are many slight variations in what needs to be done to perform
File IO depending on what type of file is being dealt with and what needs
to be done with it.  We will first focus our attention on reading lines from
a text file.  The first thing that we should do is open the file in a
FileReader (Note that we are creating a FileReader object):

  FileReader fr= new FileReader("myFile.txt");
  
The next thing that we should do is to wrap the FileReader in a 
BufferedReader:

  BufferedReader br= new BufferedReader(fr);
 
This code creates a BufferedReader which will ask fr what is in the file
and return it to the program line by line.

The designers of Java decided to use this wrapper class concept to allow a
lot of flexibility without having to create hundreds of different classes.
Sometimes people will accomplish the above in one statement where perhaps
the "wrapper" idea will be more obvious:

    BufferedReader br= new BufferedReader(new FileReader("myFile.txt"));
                       \                  \                          //
                        \                  \                        //
                         \                  \______________________//
                          \                            A           /
                           \                           |          /
                            \                          |         /
                             \                         |        /
                              \         This  wraps  This      /
                               \          |                   /
                                \         |                  /
                                 \________V_________________/



BufferedReader has, among other methods, the method

   String readLine()

which returns the next line of text from the file without the '\n' on the 
end- this method also automatically goes to the next line, so the next
call to readLine() will give the next line, not the same one.  When
the program is done reading from the file, it should call the close method
on the BufferedReader (which will close the underlying FileReader) so
that the associated file resources may be freed (note that while
memory is garbage collected, other resources, such as file descriptors 
are not). The above code, must of course have the exceptions dealt with
properly, but that will be discussed in a minute. 

The other major operation that we will concern ourselves with is writing 
lines of text to a file.  This can be accomplished similarly via the
use of the FileWriter and PrintWriter classes:

 FileWriter fr=new FileWriter("output.txt");
 PrintWriter pr= new PrintWriter(fr);

The PrintWriter class has print() and println() methods which are overloaded
to accept just about any paramter type and write it to the underlying
FileWriter.  It should be noted that print and println do NOT throw
exceptions if a problem occurs while writing to the underlying file- 
instead, they just set an error variable in the PrintWriter instance,
which may be checked with the checkError() method.  The FileWriter class, 
may throw an exception when created, as described later.   The PrintWriter
must also be closed when the program is finished with it.  If an output 
stream in not closed, then not only will the resources not be freed,
but also, the data will never actually be written out to the disk, 
as it is buffered in memory, and flushed only when a certain amount
is present, or the close() or flush() method gets called.

So why do we need to deal with these extra classes?  Why can't we 
just have one class to do it all? And how do these classes interact?
 
Each class does a specific job and provides a certain ammount of modularity
and abstraction.  Lets look at the FileReader and BufferedReader:

 FileReader-  has the job of reading characters from a file and
              assumes that the characters use default encoding.

 BufferedReader- has the job of reading text from a character-input stream,
                 buffering characters so as to provide for the efficient
                 reading of characters, arrays, and lines. 

there are other classes that could be put into a BufferedReader, for example,
an InputStreamReader- which basically reads from a byte stream and converts
to a character stream, using some encoding scheme, which may be specified.
So for example, if the file that you wanted to read used a different Unicode
encoding scheme than the default for your system (maybe you are writing
some international buisness software), then you would instead need to 
make a FileInputStream, wrap that in an InputStreamReader, then wrap that
in a BufferedReader.  In general, "Stream" deals with bytes, whereas 
 "Reader" deals with characters. 

This abstraction gives the input classes more flexibility, in that 
they can also be used to allow for reading from other input streams
than those avaiable from files on the disk- a network connection 
provides an instance of InputStream to read incoming data from 
the connection- InputStreams (as just mentioned) deal with bytes-
if the program wants to read lines of text, for example, the same
wrapping can be performed with the same classes to get a BufferedReader
to give lines of text at a time from the network.  

A similar relationship occurs with the output classes- OutputStreams
deal with bytes, whereas Writers deal with characters.  How do these
classes interact? Lets look at what happens when we ask a PrintWritter
to println something- here is what we have:

                          +----+
                          | fr |-----------------\
                          +----+                 |
                                                 V
 +----+       +-----------------+        +-------------------+
 | pr |------>| (a PrintWriter) |        |( a FileWriter)    |
 +----+       |                 |        |                   |
              | [a writer]-------------->|  [an ouput stream]|
              +-----------------+        +---------|---------+
                                                   |
                                                   |
                                                   V
                                         +---------------------+
                                         | (a FileOutputStream)|
                                         |                     |
                                         +---------------------+

The PrintWriter holds an instance of Writer (a superclass of FileWriter)
which basically has the capability of writing a char[] or a String.
The PrintWriter takes the parameter, converts it into a String (except for
if it is a char[] or a String), and then asks the underlying Writer
to write it.  The FileWriter class secretly wraps a FileOutputStream
to handle the writing of the bytes to the underlying file (you don't
see it but it does it automatically).  The FileWriter takes the data
passed in for write and converts the chars to bytes, then asks
the underlying stream to write them to the disk, via a call to write(byte[])
which then does the actual writing.


(Note the above section has certain class descriptions taken from the 
jdk1.2.2 API)

What exceptions do I need to worry about?

The methods for file IO can produce various types of IOExceptions
depending on what goes wrong.  Your program could just catch IOException
to deal with the situation, or could catch some more specific types the main
one being FileNotFoundException which occurs when you try to open a file that
doesn't exist, or if the access is not permitted.  (For example, a read only
file is opened for writing).

LINKED LISTS

• What are Linked Lists? and why would I use one?
• How do I add to one?
• How do I remove from one?
• How do I search one?

What are Linked Lists? and why would I use one?

So far, you have been using arrays to hold data.  Arrays are what is 
known as "static data structures"  (not to be confused with static 
as in 'static variables').  This means that the array can only hold a 
fixed amount of information--you have to say how many elements are in 
it when you create it, and you can't change the size after it is 
created. Linked Lists are a dynamic data structure--that means that 
there is no limit, except the amount of memory in the computer, so as 
more data needs to be held, it can just be added to the Linked List. 
This is useful when the programmer does not know in advance how much 
data there will be when the data structure to hold it needs to be 
created.  A Linked List is composed of nodes which have a data 
reference and a next reference. The last node in the list has its next 
reference set to null to indicate that there is nothing else in the 
list.  The Linked List itself has a reference, commonly called 
"head" which refers to the first node in the list.

A Linked List with 2 nodes:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+       +----------+---------+         |
 | head --->|          |         |       |          |         |         |
 |          |   data   |  next---------->|   data   |  next-------||    |  
 |          |    |     |         |       |    |     |         |         |
 |          +----|-----+---------+       +----|-----+---------+         |
 +---------------|----------------------------|-------------------------+
                 |                            |
                \ /                          \ /
                 V                            V
               (some data)                  (some data)

How do I add to a linked list?

First, we shall consider the case of adding to an unsorted linked list.
When adding to an unsorted linked list, the fastest and easiest way to
do so is to add to the front of the list.  When adding to the front of 
the linked list, the new node's next reference must be set to the current
head of the list, then the head reference must be set to the new node.
With this approach, it does not matter whether the list is empty or
has many elements.  If the list is empty, head references null:

 +----------------------------------------------------------------------+
 |                                                                      |
 |                                                                      |
 | head --->||                                                          |
 |                                                                      |  
 |                                                                      |
 |                                                                      |
 +----------------------------------------------------------------------+

node to add
  +------+-------+
  |      |       |
  | data | next  | 
  |  |   |       |
  +--|---+-------+
     |
    \ /
     V
  (some data)

We set the next reference equal to head (which is null).
 
 +----------------------------------------------------------------------+
 |                                                                      |
 |                                                                      |
 | head ----||                                                          |
 |           ^                                                          |  
 |           |                                                          |
 |           |                                                          |
 +-----------|----------------------------------------------------------+
             |
node to add  |
  +------+---|---+
  |      |       |
  | data | next  | 
  |  |   |       |
  +--|---+-------+
     |
    \ /
     V
  (some data)

Then we set the head reference to the node that we are adding:
 +----------------------------------------------------------------------+
 |                                                                      |
 |                                                                      |
 | head     ||                                                          |
 | |         ^                                                          |  
 | |         |                                                          |
 | |         |                                                          |
 +-|---------|----------------------------------------------------------+
  \ /        |
   V         |
  +------+---|---+
  |      |       |
  | data | next  | 
  |  |   |       |
  +--|---+-------+
     |
    \ /
     V
  (some data)

Now the node is added, and is a part of the Linked List

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+                                      |
 | head --->|          |         |                                      |
 |          |   data   |  next-----------||                             |  
 |          |    |     |         |                                      |
 |          +----|-----+---------+                                      |
 +---------------|------------------------------------------------------+
                 |                             
                \ /                             
                 V                             
               (some data)                       
                      
If we already have something in the list, the same procedure works.
Set the next of the new node to the head of the list:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+                                      |
 | head --->|          |         |                                      |
 |          |   data   |  next-----------||                             |  
 |          |    |     |         |                                      |
 |          +----|-----+---------+                                      |
 +-----------^---|------------------------------------------------------+
             |   |                             
             |  \ /                             
             |   V                             
             | (some data)              
             |
             |
node to add  |
  +------+---|---+
  |      |       |
  | data | next  | 
  |  |   |       |
  +--|---+-------+
     |
    \ /
     V
  (some data)

Then set the head of the list to the new node:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+                                      |
 | head     |          |         |                                      |
 |  |       |   data   |  next-----------||                             |  
 |  |       |    |     |         |                                      |
 |  |       +----|-----+---------+                                      |
 +--|--------^---|------------------------------------------------------+
    |        |   |                             
    |        |  \ /                             
    |        |   V                             
    |        | (some data)              
   \ /       |
    V        |
node to add  |
  +------+---|---+
  |      |       |
  | data | next  | 
  |  |   |       |
  +--|---+-------+
     |
    \ /
     V
  (some data)
  
Now the new node is in the list--note that the next of the old head of 
the list is not affected, so, if there were more than one node in the 
list, they would remain in the list as before:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+       +----------+---------+         |
 | head --->|          |         |       |          |         |         |
 |          |   data   |  next---------->|   data   |  next-------||    |  
 |          |    |     |         |       |    |     |         |         |
 |          +----|-----+---------+       +----|-----+---------+         |
 +---------------|----------------------------|-------------------------+
                 |                            |
                \ /                          \ /
                 V                            V
               (some data)                  (some data)

Adding to a sorted linked list involves slightly more code.
We must first find out where the new node is supposed to go in the list,
then insert it appropriately.  Once we find where the node is supposed
to go, the insertion procedure is similar to an unsorted list--set
the next reference of the new node to the node that will be after it
(could be null), then set the previous node's next reference (or the 
list's head reference if the first node) to the new node.
 
Think for a minute about what cases you would have to consider when adding.

Answer:
  - empty list (set head)
  - node should go first (set head)
  - node does not go first ( be sure to understand the need to remember the
    previous node to be sure you can setNext() on it)

How do I remove from linked list?

When we remove a node from a linked list, we want to change the previous
node's next reference to "jump over" the deleted node to the next one.
When this is done, the deleted node is no longer in the list, as it is
not referenced by any part of the chain.

We have a list, and we want to delete the second node:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+       +----------+---------+         |
 | head --->|          |         |       |          |         |         |
 |          |   data   |  next---------->|   data   |  next-------||    |  
 |          |    |     |         |       |    |     |         |         |
 |          +----|-----+---------+       +----|-----+---------+         |
 +---------------|----------------------------|-------------------------+
                 |                            |
                \ /                          \ /
                 V                            V
               (some data)                  (some data)

So we take the first node's next reference and point it to the next
node after the second one:


 +----------------------------------------------------------------------+
 |                              ----------------------------------+     |
 |          +----------+-------/-+       +----------+---------+   |     |
 | head --->|          |      /  |       |          |         |   V     |
 |          |   data   |  next   |       |   data   |  next-------||    |  
 |          |    |     |         |       |    |     |         |         |
 |          +----|-----+---------+       +----|-----+---------+         |
 +---------------|----------------------------|-------------------------+
                 |                            |
                \ /                          \ /
                 V                            V
               (some data)                  (some data)

The second node is no longer referenced in the list, so it disappears:

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+                                      |
 | head --->|          |         |                                      |
 |          |   data   |  next-----------------------------------||     |  
 |          |    |     |         |                                      |
 |          +----|-----+---------+                                      |
 +---------------|------------------------------------------------------+
                 |                             
                \ /                              
                 V                             
               (some data)                             

What cases do you need to consider for delete?

Answer:
  - Node to delete is the first node in the list (must set head)
  - Any other node (must remember to know previous node)

One of the simplest ways to remove from a list is with recursion
(in pseudo Java):

 void remove(Object theData)
 {
    set the head to remove(head, theData);
 }

 Node remove(Node curr, Object data)
 {
   if current node is null
        return null
   if the current node has the data required
        return the next node after curr

   else
       set curr's next to remove(curr's next, theData);
       return curr
 }
 
 (This removes only the first occurrence)

Be sure to understand why and how this works. You might even want to draw
pictures of the call stack  and list references make sure that you understand.
fully.  What would you have to do to remove all occurences of the data 
instead?
 
Answer: 
 change in helper under "if the current node has the data required"
  from "return the next node after curr" 
  to   "return remove(curr's next, theData)"

How do I search one?

 
To traverse through a linked list, we make a temporary node reference, 
set it to the head, the loop until we find what we want, examine
the data inside the current node, then move to the next node in the list.

 Start with curr at head
 then loop

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+       +----------+---------+         |
 | head --->|          |         |       |          |         |         |
 |          |   data   |  next---------->|   data   |  next-------||    |  
 |        ->|    |     |         |       |    |     |         |         |
 |       /  +----|-----+---------+       +----|-----+---------+         |
 +------/--------|----------------------------|-------------------------+
       /         |                            |
      /         \ /                          \ /
     /           V                            V
    /          (some data)                  (some data)
   /
 curr

 Look at curr.data and see if it is what we want.
 Move curr to curr.next

 +----------------------------------------------------------------------+
 |                                                                      |
 |          +----------+---------+       +----------+---------+         |
 | head --->|          |         |       |          |         |         |
 |          |   data   |  next---------->|   data   |  next-------||    |  
 |          |    |     |         |       |    |     |         |         |
 |          +----|-----+---------+       +----|-----+---------+         |
 +---------------|-----------------------^----|-------------------------+
                 |                       |    |
                \ /                     -+   \ /
                 V                     /      V
               (some data)            /     (some data)
                                     /
 curr-------------------------------'

 Look at curr.data and see if it is what we want... etc...
 
This continues till we find what we need or until curr is null..
The same principle may be applied to perform any operation on
the data of a linked list (such as printing it or whatever).

For your information...in lecture, the linked list manipulations were
done by passing in a node and checking and changing the next reference
instead of the technique illustrated here- both are valid- use whichever
you prefer.

STACKS AND QUEUES

• What is a Stack?
• What is a Queue?
• How do they relate to LinkedLists?

What is a Stack?