/* Aufgabe 42 Prakash Punnoor */

class Aufgabe42
{
	public static void main(String[] args)
	{
		int S[] = {534, 702, 105, 523, 959, 699, 821, 883, 842, 686, 658, 4, 20, 382, 570, 344};
		int S1[] = {4, 523, 20, 821, 686, 382, 344, 570};
		int S2[] = {525, 11, 733, 718, 349};
		
		hashtable ht = new hashtable(19);
		int i;
		
		for (i = 0; i < S.length; ++i)
			ht.insert(S[i]);
		ht.print();
		
		for (i = 0; i < S1.length; ++i)
			ht.delete(S1[i]);
		ht.print();
		
		for (i = 0; i < S2.length; ++i)
			ht.insert(S2[i]);
		ht.print();
		
		return;
	}
}

class hashtable
{
	private int T[];
	private int M;

	public hashtable(int size)
	{
		M = size;
		/* Machen wir uns das Leben nicht allzu schwer... */
		if (M < 1)
			M = 1;
		T = new int[M];
		/* Es werden nur nat. Zahlen eingefügt, also
		nutze -1 als unbelegt */
		for (int i = 0; i < M; ++i)
			T[i] = -1;
	}
	
	public boolean insert(int x)
	{
		int hash = h(x) + M;/* mod funkt nicht mit neg. Zahlen */
		int pos;
		
		/* Wir suchen max M Mal nach freien Platz*/
		for (int i = 0; i < M; ++i) {
			pos = sigma(hash, i);
			if (T[pos] == -1) {
				T[pos] = x;
				return true;
			}
		}
		return false;
	}
	
	/* liefert Pos von x in T oder -1 wenn nicht gefunden */
	public int find(int x)
	{
		int hash = h(x) + M;
		int pos;
		
		for (int i = 0; i < M; ++i) {
			pos = sigma(hash, i);
			if (T[pos] == x) 
				return pos;
		}
		return -1;
	}
	
	/* Die Idee ist, die Situation auf Skript p125 zu vermeiden,
	indem man bis zur nächsten freien Stelle alle verschiebbaren
	Elemente in Richtung Löschstelle verschiebt. Die kostet max O(n),
	macht aber find schneller */
	public boolean delete(int x)
	{
		int pos = find(x);
		
		/* Element nicht gefunden */
		if (pos == -1)
			return false;
		
		/* das nächste zu betrachtende Element */
		int j = pos + 1;
		j %= M;
		/* Umorganisieren der Tabelle */
		for (int i = 1; i < M; ++i) {
			if (T[j] == -1)
				break; /* Wir sind fertig */
			
			int hash = h(T[j]);
			if (hash != j) {
				/* Element könnte verschiebbar sein, überprüfe ob freie Pos
				nach dem hash liegt, nur dann geht es. Im linearen Sondierungsfall
 				wäre es ganz einfach, doch im allg, müßte man s_inv betrachen,
 				was wir machen */
				if (s_inv(hash, pos) < s_inv(hash, j)) {
					T[pos] = T[j];
					pos = j;
				}
			}
			++j;
			j %= M;
		}
		T[pos] = -1;
		return true;
	}
	
	public void print()
	{
		System.out.print(T[0]);
		for (int i = 1; i < M; ++i)
			System.out.print(", " + T[i]);
		System.out.println("");
	}
	
	/* Hashfunktion */
	private int h(int x) { return x % M; }
	
	/* Funktion für Sondierungsfolge sigma */
	private int s(int t) { return -t; }
	
	/* Sondierungsfolge */
	private int sigma(int hash, int t) { return (hash - s(t)) % M; }
	
	/* Inverse Fkt zu obigen s, i.a, schwierig anzugeben...*/
	private int s_inv(int hash, int pos) { return (M + pos - hash) % M; }
}