public class LarsenSearch extends SumSearch {

	private float loadFactor;

	public LarsenSearch(float loadFactor) {
		this.loadFactor = loadFactor;
	}

	@Override
	protected int search(long[] l, long[] m) {
		long[] hashtable = buildHashtable(m);

		int found = 0;
		for (int i = 0; i < l.length; i++) {
			long a = l[i];
			for (int j = i; j < l.length; j++) {
				long b = l[j];
				long sum = a + b;
				boolean hit = search(sum, hashtable);
				if (hit) ++found;
			}
		}
		return found;
	}

	private long[] buildHashtable(long[] m) {
		long[] hashtable = new long[(int) (m.length / loadFactor)];
		for (int i = 0; i < m.length; i++) {
			insert(m[i], hashtable);
		}
		return hashtable;
	}

	/**
	 * Insert with linear probing.
	 */
	private void insert(long x, long[] hashtable) {
		int i = (int) (x % hashtable.length);
		while (hashtable[i] != 0) {
			i = (i + 1) % hashtable.length;
		}
		hashtable[i] = x;
	}

	private boolean search(long x, long[] hashtable) {
		int i = (int) (x % hashtable.length);
		while (hashtable[i] != 0) {
			if (hashtable[i] == x) return true;
			i = (i + 1) % hashtable.length;
		}
		return false;
	}

	@Override
	public String toString() {
		return getClass().getName() + " loadFactor=" + loadFactor;
	}

}