//  Instructor's implementation of the SearchTable ADT.

import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

public abstract class SearchTable {

    public static SearchTable empty () {
	return new SearchTableEmpty();
    }

    public static SearchTable insert (SearchTable t, int k, int n) {
	return new SearchTableInsert (t, k, n);
    }

    public static boolean containsKey (SearchTable t, int k) {
	return t.containsKeyMethod (k);
    }

    public static int lookupKey (SearchTable t, int k) {
	return t.lookupKeyMethod (k);
    }

    public static SeqInt keys (SearchTable t) {
	SortedSet keyset = new TreeSet();
	t.keysMethod (keyset);
	SeqInt s = SeqInt.empty();
	for (Iterator i = keyset.iterator(); i.hasNext(); ) {
	    SeqInt s1 = SeqInt.singleton (((Integer) i.next()).intValue());
	    s = SeqInt.concat (s, s1);
	}
	return s;
    }

    //  Private stuff.

    abstract boolean containsKeyMethod (int k);

    abstract int lookupKeyMethod (int k);

    //  Adds a SearchTable's keys to the given SortedSet.

    abstract void keysMethod (SortedSet s);

    private static class SearchTableEmpty extends SearchTable {

	SearchTableEmpty () { }

	boolean containsKeyMethod (int k) { return false; }

	int lookupKeyMethod (int k) {
	    throw new IllegalArgumentException (makeErrorMsg (k));
	}

	void keysMethod (SortedSet s) { }

	private static String makeErrorMsg (int k) {
	    return "lookupKey (t, " + k + "): second argument not found";
	}

    }

    private static class SearchTableInsert extends SearchTable {

	private SearchTable t;              // the rest of the table
	private int k;                      // the key for one entry
	private int n;                      // the value for this key

	SearchTableInsert (SearchTable t, int k, int n) {
	    this.t = t;
	    this.k = k;
	    this.n = n;
	}

	boolean containsKeyMethod (int k0) {
	    if (k == k0)
		return true;
	    else return containsKey (t, k0);
	}

	int lookupKeyMethod (int k0) {
	    if (k == k0)
		return n;
	    else return lookupKey (t, k0);
	}

	void keysMethod (SortedSet s) {
	    s.add (new Integer (k));
	    t.keysMethod (s);
	}

    }

}