ArrayLists and Generics

ArrayLists

http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
http://docs.oracle.com/javase/7/docs/api/java/util/List.html

• Resizable
• Generic
• Implements the List interface

Example: Basic Usage

ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(5);
nums.add(0, 4);

System.out.println(nums.contains(4)); // true
System.out.println(nums.contains(6)); // false
System.out.println(nums); // [4, 5]

System.out.println(nums.remove(0)); // 4
//System.out.println(nums.remove(5)); // Index out of bounds exception

nums.clear();
System.out.println(nums); // []

nums.add(22);
nums.set(0, 25);
System.out.println(nums); // [25]

Example: Storing prime numbers in an ArrayList

import java.util.ArrayList;

/**
 * Generates prime numbers using the Sieve of Eratosthenes.
 */
public class ArrayListTest {
    public static void main(String[] args) {
        ArrayList<Integer> primes = generatePrimes(1000);
        
        for(int i = 0; i < primes.size(); i++) {
            System.out.println(primes.get(i));
        }
        
        // or...
        
        for(Integer prime : primes) {
            System.out.println(prime);
        }
    }
    
    /**
     * Generates an ArrayList of prime numbers up to maxSize.
     * @param maxSize The maximum number to generate primes up to.
     * @return An ArrayList of primes.
     */
    public static ArrayList<Integer> generatePrimes(int maxSize) {
        boolean[] primeMap  = new boolean[maxSize];
        ArrayList<Integer> primes   = new ArrayList<Integer>();
        
        primeMap[0] = false;
        primeMap[1] = false;
        
        // Initially set all values to be prime
        for(int i = 2; i < maxSize; i++) {
            primeMap[i] = true;
        }
        
        // Loop through and mark all multiples as non-prime
        for(int i = 2; i < maxSize; i++) {
            for(int j = i + i; j < maxSize; j+= i) {
                primeMap[j] = false;
            }
        }
        
        // Each value that is still true is prime, add it to the ArrayList
        for(int i = 0; i < primeMap.length; i++) {
            if(primeMap[i]) {
                primes.add(i);
            }
        }
        
        return primes;
    }
}

In-Lab Activity

Groups will be selected to complete the following ADT. Within your group:

• Come up with a solution for the methods given to you
• Determine the Big-O for your methods

/**
 * ADT to store a list of integers, backed by an array.
 */
public class SimpleArrayList {
    /**
     * Stores the contents of the list.
     */
    private int[] list;
    
    /**
     * Stores the size of the list.
     */
    private int size;
    
    /**
     * Initializes the list.
     */
    public SimpleArrayList() {
        // TODO
    }
    
    /**
     * Adds an item to the end of the list.
     * @param item The item to be added to the end of the list.
     * @return The index location that the item was added to.
     */
    public int add(int item) {
        // TODO
    }
    
    /**
     * Adds an item to the specified index in the list.
     * @param index The index to insert the item at.
     * @param item The item being added to the list.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public void add(int index, int item) {
        // TODO
    }
    
    /**
     * All items are removed from the list.
     */
    public void clear() {
        // TODO
    }
    
    /**
     * Returns the item at the specified index location.
     * @param index The index location to remove the item from.
     * @return The item at the index location.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public int get(int index) {
        // TODO
    }
    
    /**
     * Returns the index location of a given item, or -1 if the item can't be found.
     * @param item The item that we want the index of.
     * @return The index location of the item or -1 if the item isn't found.
     */
    public int indexOf(int item) {
        // TODO
    }
    
    /**
     * Removes the item at the index location.
     * @param index The index location to remove the item from.
     * @return The item removed from the index location.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public int removeIndex(int index) {
        // TODO
    }
    
    /**
     * Removes the first occurence of a specified item.
     * @item The item to be removed.
     * @return true is the item was found, false otherwise.
     */
    public boolean removeItem(int item) {
        // TODO
    }
    
    /**
     * Sets the value at index location to the specified item.
     * @param index The index location to update.
     * @param item The item to set index location to.
     * @throws IndexOutOfBoundsException if index is out of range.
     */
    public void set(int index, int item) {
       // TODO 
    }
    
    /**
     * Returns the size of this ArrayList.
     * @return The size of this ArrayList.
     */
    public int size() {
        // TODO
    }
}

Generics

• Oracle Tutorial on Generics
• Generics allow us to create objects of any type
• Generics can be bounded

Imagine you wanted to create a very simple data structure called a Box which only held one item. What if you wanted that one item to be any type? This would require multiple Box classes.

public class IntBox {
  private int item;
  public IntBox(int item) {
    this.item = item;
  }

  public int getItem() {
    return this.item;
  }

  public void setItem(int item) {
    this.item = item;
  }
}

public class DoubleBox {
  private double item;
  public DoubleBox(double item) {
    this.item = item;
  }

  public double getItem() {
    return this.item;
  }

  public void setItem(double item) {
    this.item = item;
  }
}

public class PersonBox {
  private Person item;
  public PersonBox(Person item) {
    this.item = item;
  }

  public Person getItem() {
    return this.item;
  }

  public void setItem(Person item) {
    this.item = item;
  }
}

Solution A (Incorrect)

We could make our box hold an Object, since everything is an Object.

public class Box {
  private Object item;
  public Box(Object item) {
    this.item = item;
  }

  public Object getItem() {
    return this.item;
  }

  public void setItem(Object item) {
    this.item = item;
  }
}

However, this would require that every time you get an item out of the Box, you would need to cast it to the correct type. This could potentially introduce a slue of new bugs.

Generics allow us to create a class that takes any type of object.

• We usually use E or T out of convention to represent a generic type

public class Box<T> {
  private T item;
  public Box(T item) {
    this.item = item;
  }

  public T getItem() {
    return this.item;
  }

  public void setItem(T item) {
    this.item = item;
  }
}

What if we wanted to bound the generic type, so that our Box class only accepted types that are a number?

public class Box<T extends Number> {
  private T item;
  public Box(T item) {
    this.item = item;
  }

  public T getItem() {
    return this.item;
  }

  public void setItem(T item) {
    this.item = item;
  }
}

Type Erasure

Type Erasure

• Replace all type parameters with bounds or Object
• Insert type casts to preserve type safety