// BloomFilter.java

public class BloomFilter {
    private boolean[] bits;
    private int size;

    // we use three different hash functions
    private int hash1(String input) {
        int value = 3;

        for (int i = 0; i < input.length(); i++) {
            value = value * input.charAt(i);
        }

        return Math.abs(value) % size;
    }

    private int hash2(String input) {
        int value = 0;

        for (int i = 0; i < input.length(); i++) {
            value = (value*28) + input.charAt(i);
        }
        return Math.abs(value) % size;
    }

    private int hash3(String input) {
        int value = 0;

        for (int i = 0; i < input.length(); i++) {
            if( i == 0){
                value = value + input.charAt(i);
            }
            else{
                value = value + (input.charAt(i) * input.charAt(i - 1));

            }
        }
        return Math.abs(value) % size;
    }

    // setup an empty filter
    public BloomFilter(int size) {
        this.size = size;
        bits = new boolean[size];
        for (int i = 0; i < size; i++) {
            bits[i] = false;
        }
    }

    // insert a String into the filter
    public void insert(String value) {
        // set all three positions
        bits[hash1(value)] = true;
        bits[hash2(value)] = true;
        bits[hash3(value)] = true;
    }

    // lookup an item
    public boolean lookup(String value) {
        return bits[hash1(value)] &&
            bits[hash2(value)] &&
            bits[hash3(value)];
    }
}