/** 
 * Implementiert den abstrakten Datentyp eines binären Min-Heaps für 
 * natürliche Zahlen aus {0, ..., n-1}
 */
public class MinHeap {

    /** 
     * Implementiert einen Eintrag des binären Min-Heaps
     */
    public static class Entry {
        /// Schlüssel des Eintrags
        public int key;
        /// Wert des Eintrags
        public int value;
        
        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
        
        public int getKey() { return key; }
        public int getValue() { return value; }
        public void setKey(int key) { this.key = key; }
        public void setValue(int value) { this.value = value; }

        @Override
        public String toString() {
            return "" + key + ":" + value;
        }
    }

    /**
     * Eine Exception, die geworfen wird wenn ein Heap-Eintrag
     * mit einem falschen Wert hinzugefügt werden soll, oder
     * ein nicht existierender Eintrag geändert werden soll.
     */
    public static class BadValueException extends Exception {
        public BadValueException() {
        }
    }

    /// Das heapgeordnete Array
    Entry[] heap;
    /// Der benutzte Platz im Array heap
    int used;
    /// Größe des Heap
    int n;
    
    public MinHeap(int n) {
        this.n = n;
        heap = new Entry[n];
        used = 0;
    }

    /** 
     * @return true, wenn der Heap leer ist
     */
    public boolean isEmpty() {
        return (used == 0);
    }

    /** 
     * Fügt ein neues Tupel (key, value) dem Heap hinzu 
     * und stellt die Heap-Eigenschaften wieder her
     *
     * @param key 
     *            Der Schlüssel des neuen Tupels
     *
     * @param value 
     *            Der Wert des neuen Tupels
     * 
     * @throws BadValueException
     *            Wenn der Wert ausserhalb des zulässigen Bereichs liegt
     *            oder ein Tupel mit diesem Wert bereits im Heap
     *            existiert
     */
    public void add(int key, int value) throws BadValueException {
        // TODO: Code hier einfügen
    }

    /** 
     * Ändert den Schlüssel eines Tupels im Heap
     * und stellt die Heap-Eigenschaften wieder her
     * 
     * @param newKey 
     *           Der neue Schlüssel des Tupels
     * @param value 
     *           Der Wert des zu ändernden Tupels
     * @throws BadValueException
     *           Wenn kein Tupel mit diesem Wert im Heap existiert
     */
    public void update(int newKey, int value) throws BadValueException {
        // TODO: Code hier einfügen
    }

    @Override
    public String toString() {
        String s = "";
        for(int i = 0; i < n; i++) {
            s = s + (heap[i] == null ? "   " : heap[i]) + " ";
        }
        return s;
    }

    
    /**
     * Methoden zum Testen der Funktion des Heaps
     */
    public class TestFailedException extends Exception {
        public TestFailedException() {
        }
    }
    
    public void checkFormConstraint() throws TestFailedException {
        for(int i = 0; i < used; i++) {
            if (heap[i] == null) {
                throw new TestFailedException();
            }
        }
        for(int i = used; i < n; i++) {
            if (heap[i] != null) {
                throw new TestFailedException();
            }
        }
    }

    public void checkHeapConstraint(int i) throws TestFailedException {

        int left = 2*(i+1) - 1;
        int right = 2*(i+1);

        if (left < used) {
            if (heap[left].getKey() < heap[i].getKey()) {
                throw new TestFailedException();
            }
            else {
                checkHeapConstraint(left);
            }
        }

        if (right < used) {
            if (heap[right].getKey() < heap[i].getKey()) {
                throw new TestFailedException();
            }
            else {
                checkHeapConstraint(right);
            }
        }
    }

    public void checkConstraints() {
        try {
            checkFormConstraint();
        } catch (TestFailedException e) {
            System.out.println("FAIL: Form-Constraint verletzt");
        }

        try {
            checkHeapConstraint(0);
        } catch (TestFailedException e) {
            System.out.println("FAIL: Heap-Constraint verletzt");
        }
    }

    public void checkSize(int s) {
        if (used != s) {
            System.out.println("FAIL: Nicht die richtige Anzahl Einträge");
        }
    }

  
    public static void main(String[] args) throws Exception {
        int s = 0;
        MinHeap h = new MinHeap(4); 
        h.checkConstraints(); h.checkSize(s);

        System.out.print("add(8, 1)    -> ");
        h.add(8, 1); h.checkConstraints(); h.checkSize(++s);
        System.out.println(h);

        System.out.print("add(7, 2)    -> ");
        h.add(7, 2); h.checkConstraints(); h.checkSize(++s);
        System.out.println(h);

        System.out.print("add(5, 0)    -> "); 
        h.add(5, 0); h.checkConstraints(); h.checkSize(++s);
        System.out.println(h);
        
        System.out.print("update(3, 2) -> ");
        h.update(3, 2); h.checkConstraints(); h.checkSize(s);
        System.out.println(h);

        System.out.print("add(4, 3)    -> ");
        h.add(4, 3); h.checkConstraints(); h.checkSize(++s);
        System.out.println(h);

        System.out.print("update(9, 2) -> ");
        h.update(9, 2); h.checkConstraints(); h.checkSize(s);
        System.out.println(h);

        System.out.print("update(9, 3) -> ");
        h.update(9, 3); h.checkConstraints(); h.checkSize(s);
        System.out.println(h);

        try {
            System.out.print("add(1, 10) -> ");
            h.add(1, 10);
            System.out.println("FAIL: Keine Exception geworfen!");
        } catch (BadValueException e) {
            System.out.println("OK: Exception geworfen!");
        }

        try {
            System.out.print("add(1, -1) -> ");
            h.add(1, -1);
            System.out.println("FAIL: Keine Exception geworfen!");
        } catch (BadValueException e) {
            System.out.println("OK: Exception geworfen!");
        }

        try {
            System.out.print("add(1, 0) -> ");
            h.add(1, 0);
            System.out.println("FAIL: Keine Exception geworfen!");
        } catch (BadValueException e) {
            System.out.println("OK: Exception geworfen!");
        }
        
        try {
            System.out.print("update(1, 7) -> ");
            h.update(1, 7);
            System.out.println("FAIL: Keine Exception geworfen!");
        } catch (BadValueException e) {
            System.out.println("OK: Exception geworfen!");
        }
    }
}