CS 245 Lecture 13 – Generics and Maps
Agenda
- what ?s
- midterm – next Tuesday
- interfaces
- inheritance (overriding, augmenting)
- binary search
- informal computational complexity (linear vs. quadratic vs. linearithmic, etc.)
- growable arrays
- recursion
- code tracing
- code writing
- conceptual knowledge (not APIs)
- code reuse?
- making ArrayList reusable
- making ArrayList generic
- the map abstract data type
TODO
- Read Core Java, chapter 12 through section 12.6 (Restrictions and Limitations). 1/4 sheet.
Think About This
We’ve talked about polymorphism (writing code in terms of a supertype) as a way to promote code reuse. Why do this? Why not do this?
Code
OurrayList.java
package lecture13;
public class OurrayList {
private Object[] items;
private int itemCount;
public OurrayList(int initialCapacity) {
items = new Object[initialCapacity];
itemCount = 0;
}
public OurrayList() {
this(10);
}
public int size() {
return itemCount;
}
public Object get(int i) {
if (i < 0 || i >= itemCount) {
throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
}
return items[i];
}
public void add(Object s) {
// Are we full?
if (itemCount == items.length) {
Object[] moreItems = new Object[2 * items.length];
for (int i = 0; i < items.length; ++i) {
moreItems[i] = items[i];
}
items = moreItems;
}
items[itemCount] = s;
++itemCount;
}
public void remove(int i) {
--itemCount;
for (int j = i; j < itemCount; ++j) {
items[j] = items[j + 1];
}
items[itemCount] = null;
}
public int indexOf(Object s) {
for (int i = 0; i < itemCount; ++i) {
if (items[i].equals(s)) {
return i;
}
}
return -1;
// throw new NoSuchElementException();
}
public void remove(Object s) {
int i = indexOf(s);
if (i >= 0) {
remove(i);
}
}
public String toString() {
String s = "[";
if (size() > 0) {
s += items[0];
for (int i = 1; i < size(); ++i) {
s += ", " + items[i];
}
}
return s + "]";
}
public static void main(String[] args) {
OurrayList l = new OurrayList(1);
l.add("Alice");
l.add("Bob");
l.add("Carol");
l.add("Moon Unit");
System.out.println(l);
// This shouldn't be allowed!
l.add(new StackOverflowError());
l.remove(0);
System.out.println(l);
String head = (String) l.get(0);
System.out.println(head);
}
}
OurrayListGeneric.java
package lecture13;
public class OurrayListGeneric<T> {
private T[] items;
private int itemCount;
public OurrayListGeneric(int initialCapacity) {
items = (T[]) new Object[initialCapacity];
itemCount = 0;
}
public OurrayListGeneric() {
this(10);
}
public int size() {
return itemCount;
}
public T get(int i) {
if (i < 0 || i >= itemCount) {
throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
}
return items[i];
}
public void add(T s) {
// Are we full?
if (itemCount == items.length) {
T[] moreItems = (T[]) new Object[2 * items.length];
for (int i = 0; i < items.length; ++i) {
moreItems[i] = items[i];
}
items = moreItems;
}
items[itemCount] = s;
++itemCount;
}
public void remove(int i) {
--itemCount;
for (int j = i; j < itemCount; ++j) {
items[j] = items[j + 1];
}
items[itemCount] = null;
}
public int indexOf(T s) {
for (int i = 0; i < itemCount; ++i) {
if (items[i].equals(s)) {
return i;
}
}
return -1;
// throw new NoSuchElementException();
}
public void remove(T s) {
int i = indexOf(s);
if (i >= 0) {
remove(i);
}
}
public String toString() {
String s = "[";
if (size() > 0) {
s += items[0];
for (int i = 1; i < size(); ++i) {
s += ", " + items[i];
}
}
return s + "]";
}
public static void main(String[] args) {
OurrayListGeneric<String> l = new OurrayListGeneric<String>(1);
l.add("Alice");
l.add("Bob");
l.add("Carol");
l.add("Moon Unit");
System.out.println(l);
// This isn't allowed!
// l.add(new StackOverflowError());
l.remove(0);
System.out.println(l);
String head = l.get(0);
System.out.println(head);
}
}
Map.java
package lecture13;
public interface Map<K, V> {
boolean hasKey(K key);
V get(K key);
void remove(K key);
void add(K key, V value);
}
TwoListsMap.java
package lecture13;
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class TwoListsMap<K, V> implements Map<K, V> {
private ArrayList<K> keys;
private ArrayList<V> values;
public TwoListsMap() {
keys = new ArrayList<K>();
values = new ArrayList<V>();
}
@Override
public boolean hasKey(K key) {
return keys.contains(key);
}
@Override
public V get(K key) {
int indexOfKey = keys.indexOf(key);
if (indexOfKey < 0) {
throw new NoSuchElementException("No value for key " + key);
} else {
return values.get(indexOfKey);
}
}
@Override
public void remove(K key) {
if (hasKey(key)) {
int indexOfKey = keys.indexOf(key);
values.remove(indexOfKey);
keys.remove(indexOfKey);
}
}
@Override
public void add(K key,
V value) {
int indexOfKey = keys.indexOf(key);
if (indexOfKey >= 0) {
// Throw an exception or update the existing record? Let's update!
values.set(indexOfKey, value);
} else {
keys.add(key);
values.add(value);
}
}
}
StateQuiz.java
package lecture13;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class StateQuiz {
public static void main(String[] args) throws FileNotFoundException {
TwoListsMap<String, String> statesToCapitals = new TwoListsMap<String, String>();
ArrayList<String> justTheStates = new ArrayList<String>();
// statesToCapitals.add("Wisconsin", "Rhinelander");
// System.out.println(statesToCapitals.get("Wisconsin"));
Scanner in = new Scanner(new File("/Users/johnch/Desktop/states.txt"));
while (in.hasNextLine()) {
String line = in.nextLine();
String[] fields = line.split(",");
justTheStates.add(fields[0]);
statesToCapitals.add(fields[0], fields[1]);
}
in.close();
in = new Scanner(System.in);
Collections.shuffle(justTheStates);
for (int i = 0; i < justTheStates.size(); ++i) {
String state = justTheStates.get(i);
System.out.print("What's the capital of " + state + "? ");
String capital = in.nextLine();
String expectedCapital = statesToCapitals.get(state);
if (expectedCapital.equals(capital)) {
System.out.println("Wow! You are a founding father/mother!");
} else {
System.out.println("No, that's the capital of Puerto Rico.");
}
}
}
}
Haiku
Sure, one size fits all
It sells with a 1/2″ wrench
One size gives all fits
It sells with a 1/2″ wrench
One size gives all fits