package dataStructures;

/**
 * @author Ricardo Gaspar Nr. 35277
 * @author Hugo Ant�nio Nr. 34334 Turno P2 Docente Vasco Amaral
 */
public class SepChainHashTable<K extends Comparable<K>, V> extends
		HashTable<K, V> {

	static final long serialVersionUID = 0L;

	// The array of dictionaries.
	protected Dictionary<K, V>[] table;

	public SepChainHashTable(int capacity) {
		initialize(capacity);

	}

	public SepChainHashTable() {
		this(DEFAULT_CAPACITY);
	}

	/**
	 * Returns the hash value of the specified key.
	 * 
	 * @param key
	 *            The specified key.
	 * @return hash value of the specified key.
	 */
	protected int hash(K key) {
		return Math.abs(key.hashCode()) % table.length;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.HashTable#find(java.lang.Object)
	 */
	public V find(K key) {
		return table[this.hash(key)].find(key);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.HashTable#insert(java.lang.Object, java.lang.Object)
	 */
	public V insert(K key, V value) {

		if (this.isFull())
			this.reHash();
		V resultValue = table[hash(key)].insert(key, value); // hash(key) � a
																// posi��o
		// Caso o tenha adicionado uma nova entrada
		if (resultValue == null)
			currentSize++;

		return resultValue;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.HashTable#remove(java.lang.Object)
	 */
	public V remove(K key) {

		if (this.isEmpty())
			return null;
		V resultValue = table[hash(key)].remove(key); // hash(key) � a
		// posi��o
		// Caso o tenha adicionado uma nova entrada
		if (resultValue != null)
			currentSize--;

		return resultValue;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see dataStructures.HashTable#iterator()
	 */
	public Iterator<Entry<K, V>> iterator() {

		return new SepChainHashTableIterator<K, V>(this.table);
	}

	/**
	 * Cria uma nova HashTable, com o dobro da capacidade. Copia os dados da
	 * antiga e insere-os na nova. 
	 */
	protected void reHash() {

		// Criar o iterador de entries existentes na tabela inicial
		// Assim � poss�vel iterar a tabela antiga
		Iterator<Entry<K, V>> it = this.iterator();
		//Aumentar a dimens�o da tabela
		initialize(maxSize * 2);
		while (it.hasNext()) {
			Entry<K, V> entry = it.next();
			this.insert(entry.getKey(), entry.getValue());
		}

	}

	/**
	 * Inicializa e redimensiona a HashTable existente para um tamanho dado.
	 * 
	 * @param newMaxSize
	 *            Novo tamanho da HashTable
	 */
	private void  initialize(int newMaxSize) {

		int arraySize = HashTable.nextPrime((int) (1.1 * newMaxSize));
		// Afectar a vari�vel correspondente � tabela existente com uma nova tabela
		// Compiler gives a warning.
		table = (Dictionary<K, V>[]) new Dictionary[arraySize];
		for (int i = 0; i < arraySize; i++)
			table[i] = new OrderedDoublyLL<K, V>();

		maxSize = newMaxSize;
		currentSize = 0;

	}

}