teaching machines

CS 1: Lecture 35 – Implementing a Growable Array

December 6, 2017 by . Filed under cs1, cs145, cs148, fall 2017, lectures.

Dear students,

Today, December 6, is National Growable Array Day. We will celebrate growable arrays everywhere by growing one of our own growable arrays, right here, in our classroom. I hope you wore your festive gear.

Behind every growable array is an plain old ungrowable array. When that ungrowable array gets filled up, a new and larger ungrowable array is made—containing both the old contents plus some empty cells waiting to be filled. Like the phoenix, the old one dies while the new one takes its place.

The growable array that we use in Java is ArrayList. These growable arrays can hold elements of any object type—but not primitives. We will constrain the problem a bit: we’ll only hold Strings.

Each row of the classroom will take on two of the behaviors/methods that growable arrays tend to support:

Please write your solutions down on paper, consult with your rowmates, and elect one of you to provide your solution on the board.

Check each other’s work. If your collective solution passes all tests, I’ll grant an extra credit participation point to everyone in attendance.

Here’s your TODO to complete before we meet again:

See you next class!

Sincerely,

P.S. It’s time for a haiku!

“What’s already done,
do not do.” But they forget
I am never done

P.P.S. Here’s the code we wrote together…

StringList.java

package lecture1206;

import java.lang.reflect.Array;

public class StringList {
  int N;
  String [] a;
  
  public StringList () {
    int N = 0;
    String [] a = new String[2];
  }
  
  public void add(String element) {
    if(N >= a.length) {
      String[] b = new String[a.length*2];
      for(int i = 0; i < a.length; i++) {
        b[i] = a[i];
      }
      a = b;
    }
    a[N] = element;
    N++;
    
  }
  
  public void remove(int index) {
    String[] dst = new String[a.length - 1];
    for (int i = 0; i < a.length; i++) {
      if(i < index) {
        dst[i] = a[i];
      }
      if(i > index) {
        dst[i - 1] = a[i];
      }
    }
    a = dst;
    N--;
  }
  public int size() {
    return N;
  }
  public boolean contains(String str) {
    for (int i = 0; i < a.length;++i) {
      if (a[i].equals(str)){
        return true;
      }
    }
    return false;
  }
  public String get(int index) {
    return a[index];
  }
  public boolean isEmpty() {
    return N == 0;
  }
  public int indexOf(String[] s, String a) {
    int counter = 0;
    while (!s[counter].equals(a)) {
      counter++;
    }
    return counter;
}
}

GrowableArray.java

package lecture1206;

public class GrowableArray {

  private String[] currentStringArray;

  public GrowableArray() {
    currentStringArray = new String[10];
  }

  public String get(int i) {
    return currentStringArray[i];
  }

  public boolean isEmpty() {
    for (String s : currentStringArray) {
      if (s != null) {
        return false;
      }
    }
    return true;
  }

  public void remove(int index) {
    String[] newArray = new String[currentStringArray.length - 1];
    for (int i = 0; i < index; i++) {
      newArray[i] = currentStringArray[i];
    }
    for (int i = index; i < newArray.length; i++) {
      newArray[i] = currentStringArray[i + 1];
    }
    currentStringArray = newArray;
  }

  public boolean contains(String string) {
    boolean isTrue = false;
    for (int i = 0; i < currentStringArray.length; i++) {
      if (currentStringArray[i].equals(string)) {
        isTrue = true;
      }
    }
    return isTrue;
  }

  public int indexOf(String s) {
    for (int i = 0; i < currentStringArray.length; i++) {
      if (currentStringArray[i].equals(s)) {
        return i;
      }
    }
    return -1;
  }

  public int size() {
    int length = 0;
    for (int i = 0; i < currentStringArray.length; ++i) {
      if (!get(i).isEmpty()) {
        length++;
      }
    }
    return length;
  }
}