public class LinearStringHash extends StringHash {
    private int N;
    private Entry[] table;

    public LinearStringHash(int n) {
        N = firstPrimeBiggerThan((int)1.5 * n);
        table = new Entry[N];
        for (int i = 0; i < N; i++) {
            table[i] = new Entry();
        }
        //System.out.println("N = "+N);
    }

    private int h(String s) {
        int k = 0;

        for (int i = 0; i < s.length(); i++) {
            k = (k*256 + s.charAt(i))%N;
        }

        return k;
    }

    public void clear(int nKeysExpected) {
        N = firstPrimeBiggerThan((int)1.5 * nKeysExpected);
        table = new Entry[N];
        for (int i = 0; i < N; i++) {
            table[i] = new Entry();
        }
        //System.out.println("N = "+N);
    }

    public void insert(String key)
    throws Error {
        //System.out.println(" *** inserting ["+key+"]");
        if (!contains(key)) {
            int i;
            int loc = h(key);

            for (i = 0; i < N && table[loc].isOccupied(); i++) {
                loc = (loc+1)%N;
            }

            if (i < N) {
                //System.out.println("  ** after "+i+" searches, will insert at location "+loc+", current contents: ["+table[loc].string()+"]");
                table[loc].insertEntry(key);
                //System.out.println("   * inserted ["+table[loc].string()+"]");
            }
            else {
                //System.out.println("   * could not insert ["+key+"], table full");
                //throw new Error("table is full!");
            }
        }
        else {
            //System.out.println("   * could not insert ["+key+"], already inserted");
        }
    }

    public boolean contains(String key) {
        int loc = h(key);

        //System.out.println(" *** looking for ["+key+"]");
        for (int i = 0; i < N && !table[loc].isEmpty(); i++) {
            if (table[loc].isOccupied()) {
                nComparisons++;
                if (table[loc].equals(key)) {
                    //System.out.println("   * found ["+table[loc].string()+"]");
                    return true;
                }
            }
            loc = (loc+1)%N;
        }

        //System.out.println("   * ["+key+"] not found");

        return false;
    }

    public String delete(String key) {
        int loc = h(key);

        for (int i = 0; i < N && !table[loc].isEmpty(); i++) {
            if (table[loc].isOccupied()) {
                nComparisons++;
                if (table[loc].equals(key)) {
                    //System.out.println(" *** deleting ["+table[loc].string()+"]");
                    return table[loc].deleteEntry();
                }
            }
            loc = (loc+1)%N;
        }

        return null;
    }