CM10135 / Programming II:   Lecture 9

Space, Class & Interfaces

I. Trees, Logs & Exponentiation

  1. Last time when I talked about AI, only one person saw that the tree was growing exponentially.
    1. By the rule of parallel search, someone should have come up with almost everything!
    2. Someone also said "factorial."
  2. Trees are a good way to think about both exponentiation & about logarithms.
  3. b = branching factor, d = depth of tree, N = number of elements.
                      o				b0 nodes in level 0
    / \
    o o b1 nodes in level 1
    / \ / \
    o o o o b2 nodes in level 2
    / \ / \ / \ / \
    o oo oo oo o b3 nodes in level 3
    In general, N= bd + bd-1 + ... b0
    1. As we know, this is dominated by the largest term, bd (see lecture 4). 
      1. Things would be different if we were multiplying, not adding.
      2. Factorial is when you multiply 1 * 2 * 3 * ... N
    2. So N grows exponentially on the depth of the tree,
      1. the base of the exponent is the branching factor of the tree.
    3. On the other hand, a length of the path from the root to the leaves of the tree is logarithmic on N,
      1. the branching factor is the base of the log too.
    4. N = O(bd), d = O(logb(N)).  In the case above, b =2, 8 = 23, 3 = log2(8).

II. Static Memory vs. Class Variables

  1. We're going to start out thinking about C, & then we'll talk about Java.
  2. Normally when you make a function or method call, temporary memory is allocated for the variables local to that function.
    1. variables are "added to the stack"
    2. "The stack" is the program's memory.
      1. Like a stack of papers, or a list in lisp -- the last thing you put on is the first thing you see if you are searching.
      2. You'll learn more about stacks from Dr. Paddon.
  3. When you leave the function, the variables aren't needed anymore so they are taken back off the stack
    1. the program stack is back the way it was before (unless you changed parameters passed by reference)
    2. all the values of function variables are lost.
  4. Once in a while, you don't want this to happen.
    1. Might want to remember a value calculated in a function between calls.
    2. For example, might want to know how often a function addNewUser has been called, so can make a new ID for each user.
  5. To make this happen, you need to ask the compiler to put those variables in permanent memory.
    1. Permanent memory is probably just somewhere very low on the stack.
    2. But anyway, they variable won't get created when you enter the function, or destroyed when you exit.
    3. But they are still private to the function -- no one else can see them.
  6. The way you ask a C compiler to do this is with the keyword static.
    /* returns the current number of users */
    int addNewUser (name)
    char *name;
    static int userID = 0; /*only gets set to 0 the first time the function is called!*/

    addToPasswordFile(name, userID);
    printf ("%s added to password file with userID = %d. There are now %d users.",
    name, userID, ++userID); /*note: this is where userID gets incremented!*/
    return (userID); /* this is now really the number of users */
    } /* addNewUser (name) */
  7. In Java, all memory is kept in an object.
  8. The only memory guaranteed to be around from the beginning to the end of the program is in class objects.
  9. Thus, class variables are sometimes called "static variables."  But this is kind of naughty:
    1. They are associated with the class & all its instances more than they are associated with a function.
    2. The fact they are static is sort of an implementation detail, it's not as salient as the fact they are in the class.
    3. Yet, you have to declare them using the word "static".
      1. No language is perfect!
      2. Java was not designed as a teaching language...
  10. Your first coursework asks you to put the hash in a class variable.
    1. This is because it would be a bit silly (for this problem) to put a hash in every object you are putting in the hash!
    2. A better way to do this would be to have two different classes.
      1. The hash one should be more generic.
      2. One way to do this was suggested under "bonus things to do" on Tutorial 2.
      3. Since I don't think anyone got that far in the tutorial, let's have a look at it (section IV below).
      4. This will also give you important revision on Interfaces, which will be useful when we talk about threading.

III. Inheritance vs. Interface

  1. You should have learned about Interfaces last term, but judging by your exams they still confuse you!
  2. Look at your Blue J book, Chapter 10.
  3. Here's a table to help you think more about this:

    State / Memory / Variables
    Multiple Inheritance
    (not in Java anyway, can in Lisp)
    (In Java.  Don't exist in Lisp!)
    Methods / Code
    only specifications

    Bottom Line
    A real thing you can make instances of.
    A contract you can choose to have your meet.
  4. Interfaces are cool because you can have multiple different classes that let you do the same thing.
    1. If you decide to change the back end of how you do something, all you have to change is the class type of the object that you were having do it.
    2. For example, there are multiple classes for doing hashes provided by Java.  
      1. The one that works with threading is slower than any of the others. 
      2. So you probably wouldn't use it.
      3. But if you decide to convert a non-threaded program into a threaded program, then its easy!
      4. The interface all of these hash classes meet is called Map.
  5. What confuses people sometimes is how these differ from abstract classes.  Abstract classes are classes, not interfaces!

    Can make instances of
    Can inherit from
    Can call the methods of
    as long as they aren't abstract!
    Bottom Line
    A real thing you can make instances of.
    An almost real thing that can be the superclass of a real thing.
  6. What's confusing is that Abstract Classes & Interfaces are both sort of specifications, but they are different sorts.
    1. You can think of abstraction as another kind of privacy -- it's so private it can't even call itself!
    2. You can think of interfaces sort of like contracts or roles
      1. People can have multiple jobs or roles, objects can implement interfaces.
  7. Sometimes abstract classes are provided to help you implement an interface,
    1. e.g. if you subclass from AbstractMap, you'll have most of what you'll need to implement interface Map.
  8. The idea of abstract classes has been around longer than the idea of interfaces.
  9. Some people think that interfaces are more useful than class hierarchy.

IV. Using the Comparable Interface

  1. Comparable is an interface that lives in Collections & allows you to use Collections.sort().
  2. This is a modification of the program I showed you in Lecture 7.
  3. Notice that besides using sort when the user types "sort" (blue), I've also demonstrated the use of class & instance variables (green).
import java.util.ArrayList;
import java.util.Collections;

* @author joanna
* Demonstrate how to use built-in sorting functions through the
* Comparable interface.
public class SortedBadIndices
implements Comparable {

// class variable holds a list of all instances
private static ArrayList myStuff = new ArrayList();
private int favNumber;

// new constructor to make instances with their favNumber set
// also stores them into myStuff
public SortedBadIndices (int myfav) {
this.favNumber = myfav;

/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
public int compareTo(Object o) {
if (this.favNumber < ((SortedBadIndices) o).favNumber) {
return -1;
} else if (this.favNumber > ((SortedBadIndices) o).favNumber) {
return 1;
} else { // must be equal!
return 0;
} // compareTo (Object o)

public static void main(String[] args) {

// this looks pointless, but in fact the constructor is saving the
// instances into myStuff!
new SortedBadIndices(8); // will be the 0th element.
new SortedBadIndices(5);
new SortedBadIndices(13);
new SortedBadIndices(2);

int newIx = -1;
try {
BufferedReader stdin =
new BufferedReader(new InputStreamReader(;
String myNumString;

System.out.print("Welcome to my program. The prompt looks like >>." +
"\n >> ");
while ((myNumString=stdin.readLine()) != null) {
if (myNumString.equals("sort")) {
else try {
newIx = Integer.decode(myNumString).intValue();
} catch (NumberFormatException nfe) {
System.out.println("you nurf herder, put in integers!");
newIx = 0;
} catch (Exception ex) {
System.out.println("Wow, I didn't expect a " + ex);
} finally {
System.out.println("I have " + newIx + " as my index.");
try {
System.out.println("The fav number at " + newIx + " is " +
((SortedBadIndices) myStuff.get(newIx)).favNumber);
} catch (IndexOutOfBoundsException iobe) {
System.out.println("We're sorry, " +
"there is no such array element.");

System.out.print("\n >> ");
} // while reading
} catch (IOException ioe) {
ioe.printStackTrace(); // printStackTrace is always a useful way to see what happened!
} // main()

} // class SortedBadIndices

V. The Class Class

  1. For every class that you use in a program, there's an instance of the class Class.
  2. This makes sense, because where else would the class variables go?  Variables live in objects / instances.
  3. You can do cool things with class Class, e.g.
    1. Find out the class of an object you've been passed.
      String s = "Arvice";
      Class myclass = s.getClass();
      System.out.println(myclass.getName()); // prints "java.lang.String"
    2. Get the class object of something you've heard of.
      try {
      Class sneakersClass = Class.forName("Sneakers");
      } catch (ClassNotFoundExcepiton e) {e.printStackTrace();}
    3. Use the class object to make an instance (assuming we have a good type for the object, in this case an interface...)
      interface Shoe {...

      Shoe shoeish = (Shoe) sneakerClass.newInstance();
  4. These sorts of things are particularly useful if you have been given new code from somewhere, e.g. a plugin from the internet.
  5. We might talk more about this the week after next!
  6. Another related issue (for the keen): Reflection.  See O'Reilly's "Learning Java" by Niemeyer & Knudsen, Chapter 7.
  7. For the less keen, the important thing is to realize that interfaces don't have objects.  They are always purely specifications.

VI. Summary

  1. Variables take space. 
    1. If you think about that space, it makes it more obvious what things are "real", have objects.
  2. Covered classes vs. interfaces, abstract vs. concrete classes, class objects, class variables, and what `static' really means.
  3. Explained log vs. exp one more time!

page author: Joanna Bryson
2 March 2004