What is printed by the following code?
Stack<File> unsearched = new Stack<File>();
unsearched.push(new File("00"));
while (!unsearched.isEmpty()) {
File dir = unsearched.pop();
System.out.println(dir);
File[] children = dir.listFiles();
for (File child : children) {
if (child.isDirectory()) {
unsearched.push(child);
}
}
}
What if Stack were replaced with Queue, push with enqueue, and pop with dequeue?
We want to map keys to values: names to phone numbers (a phonebook), web addresses to IP addresses (DNS), terms to their definitions (dictionary), words to their pages of occurrence (index), etc. When someone feeds us a key, we can report back the associated value.
How might you support lookup where the keys are of type String and the value is of generic type T?
package lecture21;
public interface Map<K, V> {
V get(K key);
void add(K key, V value);
}
package lecture21;
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class NickMap<K, V> implements Map<K, V> {
private ArrayList<K> keys;
private ArrayList<V> values;
public NickMap() {
keys = new ArrayList<K>();
values = new ArrayList<V>();
}
@Override
public V get(K key) {
for (int i = 0; i < keys.size(); ++i) {
if (keys.get(i).equals(key)) {
return values.get(i);
}
}
throw new NoSuchElementException();
}
public boolean hasKey(K key) {
return keys.contains(key);
}
@Override
public void add(K key,
V value) {
if (hasKey(key)) {
throw new RuntimeException("Duplicate key, foobag!");
} else {
keys.add(key);
values.add(value);
}
}
}
package lecture21;
public class Fastmap<K, V> implements Map<K, V> {
private V[] values;
public Fastmap() {
values = (V[]) new Object[100];
}
@Override
public V get(K key) {
return values[key];
}
@Override
public void add(K key,
V value) {
values[key] = value;
}
public static void main(String[] args) {
Fastmap<Integer, String> ageToName = new Fastmap<Integer, String>();
ageToName.add(5, "Lewis");
ageToName.add(5, "Devin");
System.out.println(ageToName.get(5));
}
}
Comments