package dataStructures1112;

/**
 * @author Ricardo Gaspar nº 35277 Ricardo Cruz nº 34951 Turno P8 Docente
 *         Armanda Rodrigues
 */
public class SepChainHashTable<K extends Comparable<K>, V> extends
		HashTable<K, V> {

	/**
	 * Número de série da versão.
	 */
	static final long serialVersionUID = 0L;

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

	/**
	 * Construtor da SepChainHashTable. Constrói a tabela de dispersão com a
	 * capacidade indicada.
	 * 
	 * @param capacity
	 *            Capacidade da tabela de dispersão.
	 */
	public SepChainHashTable(int capacity) {
		array = initialize(array, capacity);
		maxSize = capacity;
		currentSize = 0;
	}

	/**
	 * Construtor da SepChainHashTable. Constrói a tabela de dispersão com a
	 * capacidade definida por defeito.
	 */
	public SepChainHashTable() {
		this(DEFAULT_CAPACITY);
	}

	// Returns the hash value of the specified key.
	protected int hash(K key) {
		return Math.abs(key.hashCode()) % array.length;
	}

	// If there is an entry in the dictionary whose key is the specified key,
	// returns its value; otherwise, returns null.
	public V find(K key) {
		return array[this.hash(key)].find(key);
	}

	// If there is an entry in the dictionary whose key is the specified key,
	// replaces its value by the specified value and returns the old value;
	// otherwise, inserts the entry (key, value) and returns null.
	public V insert(K key, V value) {
		int index = 0;

		if (this.isFull())
			this.rehash();

		index = this.hash(key);
		V v = array[index].insert(key, value);

		if (v == null)
			currentSize++;

		return v;
	}

	// If there is an entry in the dictionary whose key is the specified key,
	// removes it from the dictionary and returns its value;
	// otherwise, returns null.
	public V remove(K key) {
		V v = array[this.hash(key)].remove(key);
		if (v != null) {
			currentSize--;
		}
		return v;
	}

	// Returns an iterator of the entries in the dictionary.
	public Iterator<Entry<K, V>> iterator() {
		return new SepChainHashTableIterator<K, V>(this.array);
	}

	/**
	 * Redimensiona a tabela de dispersão. Constrói uma nova tabela de
	 * dispersão, inicializa-a e copia todos os elementos da antiga para a nova.
	 */
	protected void rehash() {
		maxSize = maxSize * 2;
		Iterator<Entry<K, V>> it = this.iterator();
		this.array = initialize(array, maxSize);
		currentSize = 0;

		while (it.hasNext()) {
			Entry<K, V> e = it.next();
			this.insert(e.getKey(), e.getValue());
		}
	}
	
	private Dictionary<K,V>[] initialize (Dictionary <K,V>[] dic, int value){
		
		int arraySize = HashTable.nextPrime((int) (1.1 * (value)));
		dic = (Dictionary<K, V>[]) new Dictionary[arraySize];
		for (int i = 0; i < arraySize; i++)
			dic[i] = new OrderedDoublyLL<K, V>();
		return dic;
	}
	
}