/*
 * Copyright (c) 2012 Philipp Meinen <philipp@bind.ch>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the Software
 * is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH
 * THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

package ch.bind.philib.util;

import java.util.Arrays;

import ch.bind.philib.util.ClusteredIndex.Entry;

// TODO: round tablesize up (2^x) and use bitmasks
// TODO: strengthen hashcodes through an avalanche phase
public final class ClusteredHashIndex<K, T extends Entry<K>> implements ClusteredIndex<K, T> {

	private final Entry<K>[] table;

	@SuppressWarnings("unchecked")
	public ClusteredHashIndex(int capacity) {
		table = new Entry[capacity];
	}

	@Override
	public boolean add(final T entry) {
		assert (entry != null && entry.getNextIndexEntry() == null && entry.getKey() != null);

		final K key = entry.getKey();
		final int hash = key.hashCode();
		final int position = hashPosition(hash);

		Entry<K> scanNow = table[position];
		if (scanNow == null) {
			table[position] = entry;
			return true;
		} else {
			Entry<K> scanPrev = null;
			while (scanNow != null) {
				K nowKey = scanNow.getKey();
				if (hash == nowKey.hashCode() && key.equals(nowKey)) {
					// key is already in the table
					return false;
				}
				scanPrev = scanNow;
				scanNow = scanNow.getNextIndexEntry();
			}
			assert (scanPrev != null);
			scanPrev.setNextIndexEntry(entry);
			return true;
		}
	}

	@Override
	public boolean remove(final T entry) {
		assert (entry != null);

		final K key = entry.getKey();
		final int hash = key.hashCode();
		final int position = hashPosition(hash);

		Entry<K> scanPrev = null;
		Entry<K> scanNow = table[position];
		while (scanNow != null && scanNow != entry) {
			scanPrev = scanNow;
			scanNow = scanNow.getNextIndexEntry();
		}
		if (scanNow != null) {
			assert (hash == scanNow.getKey().hashCode() && key.equals(scanNow.getKey()));
			if (scanPrev == null) {
				// first entry in the table
				table[position] = scanNow.getNextIndexEntry();
			} else {
				// there are entries before this one
				scanPrev.setNextIndexEntry(scanNow.getNextIndexEntry());
			}
			return true; // entry found and removed
		}
		return false; // entry not found
	}

	// returns null if a pair does not exist
	@Override
	@SuppressWarnings("unchecked")
	public T get(final K key) {
		assert (key != null);

		final int hash = key.hashCode();
		final int position = hashPosition(hash);

		Entry<K> entry = table[position];
		while (entry != null) {
			K entryKey = entry.getKey();
			if (hash == entryKey.hashCode() && key.equals(entryKey)) {
				return (T) entry;
			}
			entry = entry.getNextIndexEntry();
		}
		return null;
	}

	private int hashPosition(int hash) {
		int p = hash % table.length;
		return Math.abs(p);
	}

	@Override
	public void clear() {
		Arrays.fill(table, null);
	}
}

@@ -1947,25 +1947,17 @@
 rue;%0A%09%09%7D
- else %7B%0A%09
+%0A
 %09%09Entry%3C
@@ -1982,39 +1982,16 @@
 ;%0A%09%09
-%09while (scanNow != null)
+do
  %7B%0A%09%09%09
-%09
 K no
@@ -2015,17 +2015,16 @@
 tKey();%0A
-%09
 %09%09%09if (h
@@ -2077,17 +2077,16 @@
 ) %7B%0A%09%09%09%09
-%09
 // key i
@@ -2108,17 +2108,16 @@
 e table%0A
-%09
 %09%09%09%09retu
@@ -2129,20 +2129,18 @@
 lse;%0A%09%09%09
-%09
 %7D%0A
-%09
 %09%09%09scanP
@@ -2154,17 +2154,16 @@
 canNow;%0A
-%09
 %09%09%09scanN
@@ -2198,20 +2198,43 @@
 ry();%0A%09%09
-%09%7D%0A%09
+%7D while (scanNow != null);%0A
 %09%09assert
@@ -2254,17 +2254,16 @@
  null);%0A
-%09
 %09%09scanPr
@@ -2291,17 +2291,16 @@
 entry);%0A
-%09
 %09%09return
@@ -2306,20 +2306,16 @@
 n true;%0A
-%09%09%7D%0A
 %09%7D%0A%0A%09@Ov

improve loop conditions