/*
 * Sehr einfache Implementierung einer Hash-Tabelle zur
 * Demonstration der Grundprinzipien. Folgende Einschränkungen
 *	- Inhalt beliebig (Template), aber Schlüssel nur int
 * 	- keine Dynamik, d.h
 *	- Bucket-Überlaufbehandlung durch lineares Sondieren
 *	- Keine Hash-Table-Überlaufbehandlung! Endlosschleife
 *	  bei insert() möglich
 *	- Probleme für einige nicht-Pointer Typparameter T der
 *	  Hash-Tabelle (erfordert ggf. Copy und Default-Konstruktor)
 */

#include <iostream>
#include <climits>
using namespace std;

#define HASHTABLE_SIZE 1021
#define NO_KEY INT_MIN

class Student {

	public:
		Student(int mn, char* n) {
			matrnr = mn;
		       	name = n;
		}
		int matrnr;
		char* name;
		
};

template <class T>
class HashTable;

template <class T>
class HashEntry {

	friend class HashTable<T>;

	private:
		HashEntry() {
			key = NO_KEY;
			element = NULL;
		}
		HashEntry(int k, T e) {
			key = k;
			element = e;
		}
		int key;
		T element;
};

template <class T>
class HashTable {

	public:
		HashTable();
		T search(int key); 
		void insert(int key, T object);
	private:
		int hashfunction(int key) {return key%HASHTABLE_SIZE;}
		HashEntry<T> table[HASHTABLE_SIZE];
};

template <class T>
HashTable<T>::HashTable() {
	for(int i=0;i < HASHTABLE_SIZE; i++) {
		table[i].key = NO_KEY;
		table[i].element = NULL;
	}		
}


template <class T>
T HashTable<T>::search(int k) {
	int hash = hashfunction(k);
	while (table[hash].key != k && table[hash].key != NO_KEY) hash=(hash++)%HASHTABLE_SIZE; // lineares Sondieren 
	return table[hash].element;
}

template <class T>
void HashTable<T>::insert(int k, T el) {
	int hash = hashfunction(k);
	while (table[hash].key != k && table[hash].key != NO_KEY) hash=(hash++)%HASHTABLE_SIZE; // lineares Sondieren
	table[hash].key = k;
	table[hash].element = el; 
}


int main() {
	Student* s1 = new Student(123456,"Müller");
	Student* s2 = new Student(153555,"Schmidt");
	Student* s3 = new Student(173602,"Schulze");
	Student* s4 = new Student(177884,"Meier");
	HashTable<Student*> tb;
	tb.insert(s1->matrnr,s1);
	tb.insert(s2->matrnr,s2);
	tb.insert(s3->matrnr,s3);
	tb.insert(s4->matrnr,s4);
	Student* s5 = tb.search(123456);
	if (s5 == NULL)
		cout << "Kein Student gefunden!" << endl;
	else
		cout << "Student: " << s5->name << " MatrNr: " << s5->matrnr << endl; 
	return 0;
}