Computer Science 15-100 (Sections T & U), Spring 2008
Class Notes:  Writing Custom ArrayLists (Day 1)

Logistics

1. Schedule
   1. quiz8 today
   2. Due Friday:  hw10a and hw10b
2. Reading:
   1. Ch 7.3:  Arrays of Objects

Topic Outline:

Custom ArrayList

// ArrayListDemo.java
// This code was developed (quickly) in class on 8-Apr-2008.
// As such, it does not have great style, is not well-commented,
// does not handle illegal parameter values, etc...

@SuppressWarnings("unchecked")
public class ArrayListDemo {
  
  public static void listExample() {
    MyArrayList list = new MyArrayList();
    // java.util.ArrayList list = new java.util.ArrayList();
    list.add("Let's");
    list.add("Go");
    list.add("Pens!");
    verify(list.size() == 3);
    verify(list.toString().equals("[Let's, Go, Pens!]"));
    list.add(1,"Really");
    System.out.println(list.toString());
    verify(list.toString().equals("[Let's, Really, Go, Pens!]"));
    System.out.println("wahoo!");
    // Add a bunch of elements to the list and see how many doublings we get!
    for (int i=0; i<10000; i++)
      list.add(i);
  }
  
  public static void verify(boolean b) {
    if (!b) throw new RuntimeException("Ack!");
  }
  
  public static void main(String[] args) {
    listExample();
  }
}

class MyArrayList {
  private Object[] array;
  private int used;
  
  public MyArrayList() {
    this.array = new Object[1];
    this.used = 0;
  }
  
  public void ensureCapacity(int n) {
    if (n >= this.array.length) {
      int newSize = Math.max(n,2*this.array.length);
      System.out.println("  Resizing from " + this.array.length + " to " + newSize);
      Object[] newArray = new Object[newSize];
      for (int i=0; i<this.array.length; i++)
        newArray[i] = this.array[i];
      this.array = newArray;
    }
  }
  
  public void add(Object element) {
    add(this.used, element);
  }
  
  public void add(int index, Object element) {
    boolean dbOutput = (this.used < 10);
    if (dbOutput)
      System.out.println("Adding " + element + " at index " + index + " ...");
    ensureCapacity(this.used+1);
    for (int i=this.used; i>index; i--)
      this.array[i] = this.array[i-1];
    this.array[index] = element;
    this.used++;
    if (dbOutput)
      System.out.println("  Now list = " + this.toString() +
                            ", used=" + this.used +
                            ", size=" + this.array.length);
  }
  
  public int size() {
    return this.used;
  }
  
  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append("[");
    for (int i=0; i<this.used; i++) {
      if (i>0) sb.append(", ");
      sb.append(array[i].toString());
    }
    sb.append("]");
    return sb.toString();
  }
}

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