Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

SortedList.java

text/x-java SortedList.java — 20.1 KB

Dateiinhalt

import java.util.Arrays;

/**
 * Implementiert den abtrakten Datentyp der sortierten, einfach verketteten
 * Liste ganzzahliger Werte
 */
public class SortedList {

    /**
     * Eine Exception für undefinierte Werte (z.B. bei Zugriff auf die leere
     * Liste)
     */
    public static class UndefinedValueException extends Exception {
        public UndefinedValueException() {
        }
    }

    /**
     * Ein Knoten für eine einfach verkettete Liste ganzzahliger Werte
     */
    public static class ListNode {
        // der Wert dieses Knotens
        public int value;

        // Zeiger auf den Nachfolger
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }

        /**
         * Gibt zurück, ob es einen nachfolgenden Knoten gibt.
         *
         * @return true, falls es einen nachfolgenden Knoten gibt.
         */
        public boolean hasNext() {
            return this.next != null;
        }

        @Override
        public String toString() {
            return String.format("%3d ", this.value);
        }
    }

    // der erste Knoten der sortierten Liste
    private ListNode headNode;

    public SortedList() {
        this.headNode = null;
    }

    /**
     * Konstruktor, der anhand eines Arrays die sortierte Liste erstellt.
     *
     * @param values
     *          Array, aus dem die sortierte Liste erstellt werden soll
     */
    public SortedList(int[] values) {
        this();
        insertAll(values);
    }

    /**
     * Fügt alle Werte des Arrays in die Liste ein.
     *
     * @param values
     *          Array, dessen Werte in die Liste eingefügt werden sollen
     */
    public void insertAll(int[] values) {
        for (int value : values) {
            insert(value);
        }
    }

    /**
     * Gibt zurück, ob die Liste leer ist.
     *
     * @return true, falls die Liste leer ist
     */
    public boolean isEmpty() {
        return this.headNode == null;
    }

    /**
     * Erstellt einen neuen Knoten mit Wert value und fügt ihn so in die Liste
     * ein, dass die Sortierung erhalten bleibt. Duplikate können also direkt vor
     * oder nach einem beliebigen Knoten mit identischem Wert eingefügt werden.
     *
     * @param value
     *          der in die Liste einzufügende Wert
     */
    public void insert(int value) {
        // TODO Code hier einfügen
    }

    /**
     * Entfernt den ersten Knoten (headNode) aus der sortierten Liste und liefert
     * dessen Wert zurück. Der Wert entspricht also dem Minimum der Liste. Falls
     * die Liste leer ist, soll stattdessen eine UndefinedValueException geworfen
     * werden. Der headNode wird auf den Nachfolger des entfernten Knotens
     * gesetzt.
     *
     * @return der Wert des ersten Knotens der Liste
     *
     * @throws UndefinedValueException
     *           Es wird diese Exception geworfen, falls die Liste leer ist.
     *
     */
    public int removeFirst() throws UndefinedValueException {
        // TODO Code hier einfügen

        throw new UndefinedValueException();
    }

    /**
     * Gibt die Länge der Liste zurück oder 0, falls die Liste leer ist. Um die
     * volle Punkzahl zu erhalten, soll die Laufzeit Ihrer Lösung in O(1) liegen.
     *
     * @return Länge der Liste oder 0, falls die Liste leer ist
     */
    public int getLength() {
        // TODO Code hier einfügen

        return 0;
    }

    /**
     * Gibt den k-größten Wert der Liste zurück (ohne ihn zu entfernen), falls er
     * existiert und die Liste nicht leer ist. Ansonsten wird eine
     * UndefinedValueException geworfen. Die Indexierung beginnt bei 1 und das
     * k-größte Element ist das (n-k)-te Element der sortierten Liste.
     * Beispielsweise ist der Wert 4 in der Liste [0,1,1,4,4,6] sowohl das zweit-
     * als auch das drittgrößte Element.
     *
     * @param k
     *          Der k-größte Wert, beginnend bei 1
     * @return der k-größte Wert der Liste oder UndefinedValueException, falls der
     *         Wert nicht existiert
     *
     * @throws UndefinedValueException
     *           Es wird diese Exception geworfen, falls der k-größte Wert nicht
     *           existiert oder die Liste leer ist.
     */
    public int getKLargest(int k) throws UndefinedValueException {
        // TODO Code hier einfügen

        throw new UndefinedValueException();
    }

    /**
     * Gibt den Median der Liste zurück (ohne ihn zu entfernen). Falls die Anzahl
     * der Knoten in der Liste ungerade ist, so ist der Median definiert als der
     * Wert des Knotens, der an mittlerer Stelle steht. Wenn die Liste hingegen
     * eine gerade Anzahl von Knoten enthält, ist der Median der Wert des rechten
     * der beiden mittleren Knoten. Für eine leere Liste soll die
     * Methode eine UndefinedValueException werfen.
     *
     * @return der Median der Liste
     *
     * @throws UndefinedValueException
     *           Es wird diese Exception geworfen, falls die Liste leer ist.
     */
    public double getMedian() throws UndefinedValueException {
        // TODO Code hier einfügen

        throw new UndefinedValueException();
    }

    /**
     * Fügt alle Knoten der übergebenen Liste otherSortedList sortiert in die
     * Liste ein. Die übergebene Liste otherSortedList darf dabei beliebig
     * verändert werden. Um die volle Punkzahl zu erhalten, soll die Laufzeit
     * Ihrer Lösung in O(m+n) liegen, wobei m und n die Längen der beiden Listen
     * sind.
     *
     * @param otherSortedList
     *          die übergebene Liste, die in diese Liste eingefügt werden soll
     */
    public void merge(SortedList otherSortedList) {
        // TODO Code hier einfügen
    }

    /**
     * Hilfsmethode, die zurückgibt, ob die beiden Listen identisch sind.
     */
    @Override
    public boolean equals(Object obj) {
        SortedList s2 = (SortedList) obj;
        if ((this.isEmpty()) != (s2.isEmpty())) {
            return false;
        }

        ListNode head1 = this.headNode;
        ListNode head2 = s2.headNode;

        while (head1 != null && head2 != null) {
            if (head1.value != head2.value) {
                return false;
            }
            if (head1.hasNext() != head2.hasNext()) {
                return false;
            }
            if (head1.hasNext()) {
                head1 = head1.next;
            } else {
                break;
            }
            if (head2.hasNext()) {
                head2 = head2.next;
            } else {
                break;
            }
        }
        return true;
    }

    /**
     * Hilfsmethode zum Überprüfen der Referenzen in den Testfällen
     */
    public boolean checkReferences() {
        ListNode sorted = this.headNode;
        while (sorted != null && sorted.next != null) {
            // prüfe, ob die Elemente sortiert sind
            if (sorted.value > sorted.next.value) {
                return false;
            }
            sorted = sorted.next;
        }
        return true;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode sorted  = this.headNode;
        sb.append("[");
        while (sorted != null) {
            sb.append(sorted.toString());

            if (sorted.hasNext()) {
                sb.append("-->");
            }
            sorted = sorted.next;
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * Testläufe
     */
    public static void main(String[] argv) {
        System.out.println("Einfügen testen (insert)");
        {
            SortedList s = new SortedList(new int[] {5, 3, 1, 2, 4});
            print("SortedList([5, 3, 1, 2, 4])", s);
            checkAndPrint("Sortiert eingefügt ", !s.isEmpty() && s.headNode.value == 1);
            checkAndPrint("Verlinkung OK", !s.isEmpty() && s.checkReferences());

            SortedList s2 = new SortedList(new int[] {5, 4, 3, 2, 1});
            print("SortedList([5, 4, 3, 2, 1])", s2);
            checkAndPrint("Sortiert eingefügt ", s2.headNode != null && s2.headNode.value == 1);
            checkAndPrint("Verlinkung OK", !s2.isEmpty() && s2.checkReferences());
            checkAndPrint("Listen korrekt && identisch", !s.isEmpty() && !s2.isEmpty() && s.equals(s2));

            SortedList s3 = new SortedList(new int[] {1, 2, 3, 4, 5});
            print("SortedList([1, 2, 3, 4, 5])", s3);
            checkAndPrint("Verlinkung OK", !s3.isEmpty() && s3.checkReferences());
            checkAndPrint("Listen identisch", !s3.isEmpty() && s2.equals(s3));
            checkAndPrint("Listen identisch", !s3.isEmpty() && s3.equals(s));

            SortedList s4 = new SortedList(new int[] {1, 2, 2, 4, 5});
            print("SortedList([1, 2, 2, 4, 5])", s4);
            checkAndPrint("Verlinkung OK", !s4.isEmpty() && s4.checkReferences());
            checkAndPrint("Listen nicht identisch", !s4.isEmpty() && !s.equals(s4));
        }

        System.out.println("\nMinimum entfernen testen (removeFirst)");
        {
            SortedList s = new SortedList(new int[] {5, 3, 1, 2, 4});
            print("SortedList([5, 3, 1, 2, 4])", s);
            for (int i = 1; i <= 5; i++) {
                try {
                    int returned = s.removeFirst();
                    print("removeFirst()", s);
                    checkAndPrint(returned + " als Minimum zurückgegeben (erwartet: " + i + ")", returned == i);
                    checkAndPrint("Verlinkung OK", s.checkReferences());
                } catch (UndefinedValueException e) {
                    checkAndPrint("UndefinedValueException als Minimum zurückgegeben (erwartet: " + i + ")", false);
                }
            }
        }

        System.out.println("\nLänge bestimmen (getLength)");
        {
            SortedList s = new SortedList();
            print("SortedList()", s);
            int returned = s.getLength();
            int expected = 0;
            checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected);

            s.insert(1);
            print("insert(1)", s);
            returned = s.getLength();
            expected = 1;
            checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected);

            try {
                expected = 0;
                s.removeFirst();
                print("removeFirst()", s);
                returned = s.getLength();
                checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected);
                checkAndPrint("Verlinkung OK", s.checkReferences());

            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Länge zurückgegeben (erwartet: " + expected + ")", false);
            }
        }

        System.out.println("\nMedian zurückgeben (getMedian)");
        {
            SortedList s = new SortedList(new int[] {13, 10, 5, 4, 2, 20, 21});
            print("SortedList([13, 10, 5, 4, 2, 20, 21])", s);

            double expected = 10.0;
            try {
                double returned = s.getMedian();
                checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")",
                              returned == expected);
            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false);
            }

            s = new SortedList(new int[] {1, 5, 4});
            print("SortedList([1, 5, 4])", s);
            expected = 4.0;
            try {
                double returned = s.getMedian();
                checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")",
                              returned == expected);
            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false);
            }

            s = new SortedList(new int[] {1, 5});
            print("SortedList([1, 5])", s);
            expected = 5.0;
            try {
                double returned = s.getMedian();
                checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")",
                              returned == expected);
            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false);
            }

            s = new SortedList(new int[] {1});
            print("SortedList([1])", s);
            expected = 1.0;
            try {
                double returned = s.getMedian();
                checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")",
                              returned == expected);
            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false);
            }

            s = new SortedList(new int[] {1, 5, 2, 3});
            print("SortedList([1, 5, 2, 3])", s);
            expected = 3;
            try {
                double returned = s.getMedian();
                checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")",
                              returned == expected);
            } catch (UndefinedValueException e) {
                checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false);
            }
        }

        System.out.println("\nK-größtes Element ausgeben (getKLargest)");
        {
            SortedList s1 = new SortedList(new int[] {5, 2, 3, 4, 1});
            print("SortedList([5, 2, 3, 4, 1])", s1);
            for (int k = 1; k <= 5; k++) {
                int expected = (5 - k + 1);
                try {
                    int returned = s1.getKLargest(k);
                    checkAndPrint(returned + " als " + k + "-größten Wert zurückgegeben (erwartet: " + expected + ")",
                                  returned == expected);
                } catch (UndefinedValueException e) {
                    checkAndPrint("UndefinedValueException als " + k
                                      + "-größten Wert zurückgegeben (erwartet: " + expected + ")",
                                  false);
                }
            }

            int returned = 0;
            try {
                returned = s1.getKLargest(0);
                checkAndPrint(returned + " als 0-größten Wert zurückgegeben (erwartet: UndefinedValueException )",
                              false);
            } catch (UndefinedValueException e) {
                checkAndPrint(
                    "UndefinedValueException als 0-größten Wert zurückgegeben (erwartet: UndefinedValueException )",
                    true);
            }

            try {
                returned = s1.getKLargest(6);
                checkAndPrint(returned + " als 6-größten Wert zurückgegeben (erwartet: UndefinedValueException)",
                              false);
            } catch (UndefinedValueException e) {
                checkAndPrint(
                    "UndefinedValueException als 6-größten Wert zurückgegeben (erwartet: UndefinedValueException)",
                    true);
            }
        }

        System.out.println("\nListen verschmelzen (merge)");
        {
            int[] elementsS1 = new int[] {1, 5};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {2, 4};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 4);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }

        {
            int[] elementsS1 = new int[] {2, 5};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {1, 3};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 4);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }

        {
            int[] elementsS1 = new int[] {2, 4, 6, 10, 11};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {1};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 6);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }

        {
            int[] elementsS1 = new int[] {1};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {2, 4, 6, 10, 11};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 6);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }

        {
            int[] elementsS1 = new int[] {};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {2, 4, 6, 10, 11};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 5);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }

        {
            int[] elementsS1 = new int[] {2, 4, 6, 10, 11};
            SortedList s1    = new SortedList(elementsS1);
            print("SortedList(" + Arrays.toString(elementsS1) + ")", s1);

            int[] elementsS2 = new int[] {};
            SortedList s2    = new SortedList(elementsS2);
            print("SortedList(" + Arrays.toString(elementsS2) + ")", s2);

            s1.merge(s2);
            print("merge()", s1);
            checkAndPrint("Merge OK", s1.getLength() == 5);
            checkAndPrint("Verlinkung OK", s1.checkReferences());

            SortedList s3 = new SortedList(elementsS1);
            s3.insertAll(elementsS2);
            checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3));
        }
    }

    private static void print(String message, SortedList sortedList) {
        System.out.println("  " + message + ": " + sortedList.toString());
    }

    private static boolean checkAndPrint(String message, boolean correct) {
        System.out.println("    " + (correct ? "PASS:" : "FAIL:") + " " + message);
        assert (correct);
        return correct;
    }
}