class MyData {

    String  k; // Schluesselwert
    boolean b; // Nutzdaten
    float   f; // Nutzdaten

}

// Datentyp fuer Listen zur Hash-Bucket-Verwaltung
class Link {

    MyData data;
    Link   next;

}


public class MyHashS {


    static final int m = 5; // Primzahl fuer Arraygroesse
    static Link[] a = new Link[m]; // Hash-Array

    static int h(String key) {
 
        int aux = 0;


        // Beispiel : "ABCDEF"
        // 

        for ( int iCnt=0; iCnt< key.length(); iCnt++ )
	    aux = ((aux * 256 + (int)(key.charAt(iCnt))))%m;

	return aux;

    }

    static void insertIntoHashtable(String k, boolean b, float f) {

        // erzeuge neuen Listeneintrag
	Link x  = new Link();

        // Nutzdaten eintragen:
        x.data = new MyData();
        x.data.k = k;
        x.data.b = b;
        x.data.f = f;
      
        // Das neue Hash-Bucket x wird 
        // das ERSTE Listenelement der Liste
        // von Has-Buckets, die im Array unter
        // Index h(k) beginnt.
        x.next = a[h(k)];

        a[h(k)] = x;

        System.out.println("Insert key " + k +
                           " at index " + h(k));


    }

    // wir nehmen an, dass k Primärschluessel ist
    // findInList() bricht ab, sobald der erste
    // k-Wert gefunden wurde.
    static MyData findInList(String k, Link list) {

	if ( list == null ) {
	    return null;
	}
        else if ( list.data.k.equals(k) ) {
            return list.data;
	}
        else {
            return findInList(k,list.next);
	}

    }

    static Link deleteInList(String k, Link list) {

        // Hilfsvariable fuer Vorgaenger des zu loeschenden Eintrags
	Link prev = list;
        int  bucketCnt = 0;
		
	if ( list != null ) {
 
	    if ( list.data.k.equals(k) ) {
	        // Fall 1: zu loeschendes Element ist gleich
	        // der Kopf der Liste.
		System.out.println("Delete key " + k +
				   " at index " + h(k) +
				   " bucket No. " + bucketCnt);
		list = list.next;
	    }
	    else {
                // Fall 2: zu loeschendes Element - falls es existiert -
                // liegt hinter dem Listenkopf
		bucketCnt++;
		while ( prev.next != null && !prev.next.data.k.equals(k) ) {
		    System.out.println("Non-matching key " + prev.next.data.k +
				       " at index " + h(k) +
				       " bucket No. " + bucketCnt);
		    prev = prev.next;
		    bucketCnt++;
		}
		// Wenn der Eintrag gefunden wurde, ist
		// er durch prev.next referenziert. Dieses
		// Listenelement ist also zu loeschen
		if ( prev.next != null ) {
		    System.out.println("Delete key " + k +
				       " at index " + h(k) +
				       " bucket No. " + bucketCnt);
		    prev = prev.next.next;
		}
	    }

	} 

	return list;

    }

    static MyData findInHashTable(String k) {

        // Suche in der Liste, auf die Array-Element
        // mit Index h(k) zeigt:
	return findInList(k,a[h(k)]);

    }

    static void deleteInHashTable(String k) {
 
	a[h(k)] = deleteInList(k,a[h(k)]);

    }

    static void printResult(String k,MyData d) {

        if ( d != null ) 
          System.out.println("Key "+k+"  returns (" + 
			     d.k + "," + d.b + "," + d.f + ")");
        else 
	  System.out.println("Key "+k+"  returns null");

    }



    public static void main(String[] args) { 

        MyData d;

	insertIntoHashtable("jan",true,3.45f);
	insertIntoHashtable("240",true,4.45f);
	insertIntoHashtable("Johannes",true,3.55f); 
	insertIntoHashtable("Cornelia",true,3.45f); 
	
        System.out.println("*** Nach den Insert-Operationen:");
        printResult("jan",findInHashTable("jan"));
        printResult("240",findInHashTable("240"));
        printResult("blurps",findInHashTable("blurps"));
        printResult("Johannes",findInHashTable("Johannes"));
        printResult("Cornelia",findInHashTable("Cornelia"));

        System.out.println("*** Loesch-Operationen:");
        deleteInHashTable("jan");
        deleteInHashTable("Cornelia");
        deleteInHashTable("xyz");

        
        System.out.println("*** Nach den Delete-Operationen:");
        printResult("jan",findInHashTable("jan"));
        printResult("240",findInHashTable("240"));
        printResult("blurps",findInHashTable("blurps"));
        printResult("Johannes",findInHashTable("Johannes"));
        printResult("Cornelia",findInHashTable("Cornelia"));
 
    }

}