Computer Science 15-100 (Sections T & U), Spring 2008
Class Notes:  Inheritance (part 2) and Recursion (part 1)

Logistics

  1. Schedule
    1. sortingQuiz10 today
    2. quiz11 canceled (no more quizzes!)
    3. Extension:  Due Monday:  hw11 (term project)
      1. Note:  If you submit by original deadline (tomorrow), you get a 5-point bonus
    4. Test2 next class (Tuesday)
    5. Test2 review:  see Grant's email
    6. Final exam review:  also see Grant's email
  2. Reading:
    1. Ch 8: Inheritance

Topic Outline:

Code from class:

[ We wrote two programs in class -- the first completed our subclassing of AbstractList so our custom ArrayList is sortable using Collections.sort, and the second demonstrated some simple examples of recursion.   Both programs are included here. ]

// InheritanceDemo.java  (extends AbstractList)
// Written in class on 24-Apr-08 (with the usual disclaimers about code written
// in class...).  Also, we have not yet finished MyArrayList so it cannot
// yet be provided as an argument to Collections.sort.  Next class...

import java.util.*;

@SuppressWarnings("unchecked")
class InheritanceDemo {
  public static void main(String[] args) {
    Animal[] animals = { new Cow(), new Dog(), new Dog(), new Cat() };
    for (Animal a : animals) {
      System.out.println(a.speak());
      System.out.println(a.senseDoom());
    }
    MyArrayList l = new MyArrayList();
    l.add("one");
    l.add("two");
    l.add("three");
    l.add("four");
    System.out.println(l);
    Collections.sort(l);  // <-- This works now that we extend AbstractList
    System.out.println(l);
    
    l.clear();
    l.add(123);
    l.add(45);
    l.add(6);
    l.add(78);
    System.out.println(l);
    Collections.sort(l);  // <-- Will not compile (yet!)
    System.out.println(l);
  }
}

class MyArrayList extends AbstractList {
  Object[] array;
  int used;

  public Object set(int index, Object element) {
    Object result = this.array[index];
    this.array[index] = element;
    return result;
  }
  
  private void swap(int i, int j) {
    Object temp = this.array[i];
    this.array[i] = this.array[j];
    this.array[j] = temp;
  }
  
  public void add(int index, Object element) {
    add(element);
    for (int i=this.used-1; i>index; i--)
      swap(i,i-1);
  }
  
  public Object remove(int index) {
    Object result = this.array[index];
    for (int i=index+1; i<this.used; i++)
      this.array[i-1] = this.array[i];
    this.array[this.used-1] = null;
    this.used--;
    return result;
  }
  
  public int size() { return this.used; }
  
  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append("MyArrayList[");
    for (int i=0; i<this.used; i++) {
      if (i > 0) sb.append(",");
      sb.append(this.array[i]);
    }
    sb.append("]");
    return sb.toString();
  }
  
  public MyArrayList() {
    this.used = 0;
    this.array = new Object[2];
  }
  
  public void ensureCapacity(int c) {
    if (c < this.array.length) return;
    c = Math.max(c,2*this.array.length);
    Object[] oldArray = array;
    array = new Object[c];
    for (int i=0; i<oldArray.length; i++)
      array[i] = oldArray[i];
  }
  
  public boolean add(Object obj) {
    ensureCapacity(this.used+1);
    this.array[this.used++] = obj;
    return true; // lame, lame, lame, but required (in a doomish lame way)
  }
  
  public Object get(int i) {
    return this.array[i];
  }
}

abstract class Animal {
  abstract public String speak();
  public int getLegs() { return 4; }
  public boolean senseDoom() { return false; }
}

class Cow extends Animal {
  public String speak() { return "woof, I'm confused"; }  
}

class Dog extends Animal {
  // OVERRIDE (not overload)
  public String speak() { return "woof"; }  
  public boolean senseDoom() { return true; } // there is ALWAYS doom!
}

class Cat extends Animal {
  // OVERRIDE (not overload)
  public String speak() { return "meow"; }  
}
// RecursionIntro.java
// Written in class on 24-Apr-08 (with the usual disclaimers about code written
// in class...).

import java.util.*;

@SuppressWarnings("unchecked")
class RecursionIntro {
  public static void main(String[] args) {
    System.out.println(times(5,3));
    System.out.println(gcf(1540,1430));
  }

  // gcf(x,y) == gcf(y,x%y) (According to Euclid's method -- see Wikipedia page for details)
  public static int gcf(int x, int y) {
    System.out.println("gcf(" + x + "," + y + ")");
    if (y == 0)
      return x;
    else
      return gcf(y,x%y);
  }
  
  // we will assume y >= 0
  public static int times(int x, int y) {
    if (y == 0)
      // BASE CASE
      return 0;
    else
      // RECURSIVE CASE
      return x + times(x,y-1);
  }
}

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem