package aufgabe_3;

import java.util.Arrays;

public class CoalescedHashTable {

	int[] ht; // eigentliche Hashtabelle
	int[] next; // Extrabereich zur Verkettung der Überläufer
	int n; // Anzahl der Datensätze in der Hashtabelle

	public CoalescedHashTable(int size) {
		if (size < 1) {
			System.err.println("Warning: The size of the hash table has to be greater than zero. Creating new hash table "
					+ "with the default size of 10.");
			size = 10;
		}

		n = 0;

		ht = new int[size];
		next = new int[size];

		for (int i = 0; i < size; i++) {
			ht[i] = -1;
			next[i] = -1;
		}
	}

	/**
	 * Diese Methode liefert den Hash-Wert für einen gegebenen Key.
	 *
	 * @param key
	 * Der Key, für den der Hash-Wert berechnet werden soll.
	 * @return
	 * Der Hash-Wert.
	 */
	private int hash(int key) {
		return key % ht.length;
	}

	/**
	 * Methode zum Einfügen in die Hash-Tabelle.
	 *
	 * @param entry
	 * Der Wert, der in die Tabelle eingefügt werden soll.
	 * @return
	 * <b>true</b>, wenn alles geklappt hat<br><b>false</b>, wenn die Tabelle voll ist
	 */
	public boolean insert(int entry) {

		// TODO implementieren Sie hier die Methode und passen Sie den Rückgabewert an
		if (entry < 0) {
			throw new IllegalArgumentException("Must be a positive Integer!");
		}


		int position = 0;

		position = hash(entry); // is position for insertion

		if (member(entry) == entry) {
				return false;
		}

		if (ht[position] == -1) { //if position is empty //or ht[position] == entry?

				 ht[position] = entry;   //insert entry into ht
				 return true;
		}
		else if (ht[position] != -1){
			int index = ht.length - 1;     //	else if position is occupied (value != -1)
			while (index >= 0 && ht[index] != -1) {
				index--;
			}
			//Verkettung
			if (index > -1 && next[position] == -1) {
			next[position] = index;
			ht[index] = entry; //put entry into first empty bucket from the end
			return true;
			} else if (index > -1 && next[position] != -1) { //if next position already occupied put to next emtpy position (pointer in next)
				next[index] = index;
				ht[index] = entry;
				return true;
			} else
			{
				return false;//index ht is full
			}
		} else {
			return false;
		}


	}

	/**
	 * Methode zum Suchen in der Hash-Tabelle
	 *
	 * @param entry
	 * Der Eintrag, der gesucht werden soll.
	 * @return
	 * Der Eintrag, wenn er in der Tabelle existiert, oder <b>-1</b>, wenn der Eintrag nicht existiert.
	 */
	public int member(int entry) {

		// TODO implementieren Sie hier die Methode und passen Sie den Rückgabewert an

// test if value already in data set
		for (int i = 0; i < ht.length; i++) {
			if (ht[i] == entry)
				return entry;

		}

		return -1;

	}

	@Override
	public String toString() {
		return "HashTable [ht=" + Arrays.toString(ht) + ", next=" + Arrays.toString(next) + "]";
	}
}