Computer Science 15-100 (Sections T & U), Spring 2008
Class Notes:  Inheritance (and Sorting Redux)

Logistics

1. Schedule
   1. sortingQuiz10 Thursday (next class)
   2. quiz11 Friday
   3. Due Friday:  hw11 (term project)
   4. Test2 next Tuesday (one week from today!)
   5. Extra office hours:
      1. Today:  Jamie, 5-6pm, Ilya 7-8pm
      2. Tomorrow: Grant, 5-6pm
      3. Thursday:  Usual office hours (DK: 1:30 - 3pm / CA's: 5pm - 9pm)
   6. Test2 review?
   7. Final exam review?
2. Reading:
   1. Ch 8: Inheritance

Topic Outline:

• Sorting Redux
  • swap
  • compareTo
  • bubblesort
  • insertionsort
  • selectionsort
     
• Ch 8: Inheritance
  • Creating Subclasses
  • Overriding Methods
  • "this" and "super" references
  • Class Hierarchies
     
• How to make a sortable custom ArrayList
  • Implement List + ListIterator interfaces
  • Better yet:  Subclass AbstractList  (great example of inheritance and abstract classes!!!)

Code from class:

[ We wrote two programs in class -- the first demonstrated the various quadratic sorting algorithms, the second demonstrated some aspects of inheritance.   Both programs are included here. ]

// QuadraticSorts.java
// Written in class on 22-Apr-08 (with the usual disclaimers about code written
// in class...)

  import java.util.*;
  @SuppressWarnings("unchecked")
  public class QuadraticSorts {
    public static void main(String[] args) throws Exception {
      ArrayList a = new ArrayList(Arrays.asList(
//            new Object[]{ new Object(), new Object()}));
//            new Object[]{ "a", "c", "d", "b"}));
              new Object[] { 1, 4, 2, 5, 3 }));
      System.out.println(a);
      swap(a,0,1);
      System.out.println(a);
      // System.out.println("foo".compareTo("bar")); // foo > bar
      // System.out.println("foo".compareTo(new Object()));
      selectionsort(a);
      System.out.println(a);
    }
    
    public static int indexOfMin(ArrayList a, int startIndex) {
      int minIndex = startIndex;
      for (int i=startIndex; i<a.size(); i++) {
        Comparable aI = ((Comparable)a.get(i));
        if (aI.compareTo(a.get(minIndex)) < 0)
          minIndex = i;
      }
      return minIndex;
    }
    
    public static void selectionsort(ArrayList a) {
      for (int i=0; i<a.size(); i++)
        swap(a,i,indexOfMin(a,i));
    }
    
    public static void insertionsort(ArrayList a) {
      for (int i=0; i<a.size(); i++) {
        for (int j=i; j>0; j--) {
          Comparable aJminus1 = ((Comparable)a.get(j-1));
          if (aJminus1.compareTo(a.get(j)) > 0)
            swap(a,j-1,j);
          else
            break;
        }
      }
    }
    
    public static void bubblesort(ArrayList a) {
      boolean changed = true;
      while (changed) {
        changed = false;
        for (int i=1; i<a.size(); i++) {
          Comparable aIminus1 = ((Comparable)a.get(i-1));
          if (aIminus1.compareTo(a.get(i)) > 0) {
            swap(a,i,i-1);
            changed = true;
          }
        }
      }
    }    
    
    public static void swap(ArrayList a, int i, int j) {
      Object temp = a.get(i);
      a.set(i,a.get(j));
      a.set(j,temp);
    }
  }  

// InheritanceDemo.java
// Written in class on 22-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);  // <-- Will not compile (yet!)
    System.out.println(l);
  }
}

class MyArrayList {
  Object[] array;
  int used;
  
  public String toString() {
    return "MyArrayList" + Arrays.toString(this.array);
  }
  
  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 void add(Object obj) {
    ensureCapacity(this.used+1);
    this.array[this.used++] = obj;
  }
  
  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"; }  
}

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