SequentialSearchST.java

Below is the syntax highlighted version of SequentialSearchST.java from §4.4 Symbol Tables.

/*************************************************************************
 *  Compilation:  javac SequentialSearchST.java
 *  Execution:    java SequentialSearchST
 *  
 *  Symbol table implementation with unordered array. Uses repeated
 *  doubling to resize the array.
 *
 *  % java UnorderedArrayST
 *  128.112.136.11
 *  208.216.181.15
 *  null
 *
 *************************************************************************/


import java.util.Iterator;
import java.util.NoSuchElementException;

// suppress unchecked warnings in Java 1.5.0_6 and later
@SuppressWarnings("unchecked")

public class SequentialSearchST<Key, Val> implements Iterable<Key> {
    private Key[] keys;   // symbol table keys
    private Val[] vals;   // symbol table values
    private int N = 0;    // number of elements in symbol table

    private static final int INIT_SIZE = 8;

    public SequentialSearchST() {
        keys = (Key[]) new Object[INIT_SIZE];
        vals = (Val[]) new Object[INIT_SIZE];
    }

    public boolean isEmpty() { return N == 0; }

    private void resize(int SIZE) {
        Key[] tempk = (Key[]) new Object[SIZE];
        Val[] tempv = (Val[]) new Object[SIZE];
        for (int i = 0; i < N; i++) tempk[i] = keys[i];
        for (int i = 0; i < N; i++) tempv[i] = vals[i];
        keys = tempk;
        vals = tempv;
    }


    public void put(Key key, Val val) {

        // to deal with duplicates
        remove(key);

        // double size of arrays if necessary
        if (N >= vals.length) resize(2*N);

        // add new key and value at the end of array
        vals[N] = val;
        keys[N] = key;
        N++;
    }

    // return value associated with given key (or null if no such key)
    public Val get(Key key) {
        for (int i = 0; i < N; i++)
            if (keys[i].equals(key)) return vals[i];
        return null;
    }

    // is the given key in the symbol table?
    public boolean contains(Key key) {
        return (get(key) != null);
    }

    // return number of elements
    public int size() { return N; }

    // remove given key and return associated value
    public void remove(Key key) {
        for (int i = 0; i < N; i++) {
            if (key.equals(keys[i])) {
                keys[i] = keys[N-1];
                vals[i] = vals[N-1];
                keys[N-1] = null;
                vals[N-1] = null;
                N--;
                return;
            }
        }
    } 


    public Iterator<Key> iterator() { return new ArrayIterator(); }

    // an iterator, doesn't implement remove() since it's optional
    private class ArrayIterator implements Iterator<Key> {
        private int i = 0;
        public boolean hasNext()  { return i < N;                               }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return keys[i++];
        }
    }



   /***********************************************************************
    * Test routine.
    **********************************************************************/
    public static void main(String[] args) {
        UnorderedArrayST<String, String> st = new UnorderedArrayST<String, String>();

        // insert some key-value pairs
        st.put("www.cs.princeton.edu", "128.112.136.11");
        st.put("www.princeton.edu",    "128.112.128.15");
        st.put("www.yale.edu",         "130.132.143.21");
        st.put("www.amazon.com",       "208.216.181.15");
        st.put("www.simpsons.com",     "209.052.165.60");

        // search for IP addresses given URL
        System.out.println(st.get("www.cs.princeton.edu"));
        System.out.println(st.get("www.amazon.com"));
        System.out.println(st.get("www.amazon.edu"));

    }

}