AlgoDat/Uebung08/RBTree.java

/**
 * Sparse Implementierung einer verkettete Liste
 */
public class RBTree {

    /**
     * Hilfsklasse, welche ein einzelnes Node repräsentiert.
     * 
     * @author Paul
     */
    private class Node {
        int index;
        double value;
        Node next;

        public Node(int index, double value, Node next) {
            this.index = index;
            this.value = value;
            this.next = next;
        }

    }

    // Standard Konstruktor mit einem leeren Vektor initialisieren
    private Node firstNode = null;
    private int length = 0;

    /**
     * Konstruktor mit Vektor länge 0
     * 
     * @author Elif
     */
    public RBTree() {
        this.firstNode = null;
        this.length = 0;
    }

    /**
     * Konstruktor mit Vektor länge n
     * 
     * @author Elif
     * @param n Vektor länge
     */
    public RBTree(int n) {
        this.firstNode = null;
        this.length = n;
    }

    /**
     * den value in index hinzufügen
     * - Aktualisieren des Wertes, wenn der firstNode an dem Index mit einem Wert
     * exisitiert
     * - Neuer firstNode mit neuem Wert hinzufügen, wenn der firstNode an dem Index
     * nicht existiert
     * 
     * @author Elif
     * @param index Stelle,w wo Vektor eingefügt werden soll
     * @param value wert, den wir übergeben
     */
    public void setElement(int index, double value) {
        // methode wird aufgerufen, falls index existiert = platz schaffen
        removeElement(index);

        int maxIndex = this.getLength() - 1;
        // 1. if: schauen, ob Index im erlaubten Bereich
        // 2. if: schauen, ob erster Knoten null ist und index von erstem knoten größer
        // als index, dann neuen knoten setzen
        if (index > maxIndex) {
            System.out.println("Fehler: Der Index " + index + " ist außerhalb des erlaubten Bereichs.");
            return;
        }

        if (this.firstNode == null || this.firstNode.index > index) {
            this.firstNode = new Node(index, value, this.firstNode);

        }
        // hilfsknoten erstellen
        // solange im index und gesuchten index nicht erreicht haben, gehen wir weiter
        Node now = this.firstNode;

        while (now.next != null && now.next.index < index) {
            now = now.next;
        }

        // gesuchte index gefunden
        if (now != null && now.index == index) {
            now.value = value;
            System.out.println("at index " + index + " set value " + value);
            // knoten den wir erstellen wollten existiert nicht, deshlab new node
        } else if (now.next == null || now.next.index > index) {
            now.next = new Node(index, value, now.next);
            System.out.println("at index " + index + " set value " + value);

        }

    }

    /**
     * return the Wert value of that index input das Index, und return den
     * entsprechenden Wert des Index
     * 
     * @author Paul
     * @param index Stelle, an der der Wert steht
     * @return double Wert des Elements
     */
    public double getElement(int index) {

        if (index < 0 || index >= this.length) { // für Testfall wenn Länge < index
            throw new IndexOutOfBoundsException("Index " + index + " ist außerhalb der Vektorlänge " + this.length
                    + ". Max. Index ist " + (this.length - 1));
        }

        Node now = this.firstNode;

        while (now != null) {
            if (now.index == index) {
                return now.value;
            }
            now = now.next;
        }

        return 0.0;
    }

    /**
     * entfernt Element nach Index
     * 
     * @author Leonhard
     * @param index Stelle des zu entferneden Elements
     */
    public void removeElement(int index) {
        // Anlegen der jetzigen und vorherigen Node
        Node now = this.firstNode;
        Node pre = null;

        // Wenn der momentane Node nicht Null ist und der gesuchte Index korrekt ist
        // ersetze den momentanen Node durch den nächsten
        if (now != null && now.index == index) {
            this.firstNode = now.next;
            return;
        }

        // Während wir momentan nicht bei Null sind und den Index nicht gefunden haben
        // setzte pre und now den nächsten Node weiter
        while (now != null && now.index != index) {
            pre = now;
            now = now.next;
        }

        // Wenn wir den Index gefunden haben und nicht bei Null sind
        // setze den nächsten Node auf den momentanen Node
        if (now != null && now.index == index) {
            pre.next = now.next;
            System.out.println("Node mit Wert: " + now.value + " am Index " + index + " gefunden und gelöscht.");
        } else {
            System.out.println("Keine Node am Index: " + index + " nicht gefunden!");
        }
    }

    /**
     * Gibt die Länge des Vektors aus
     * 
     * @author Leonhard
     * @return int Vektor Länge
     */
    public int getLength() {
        return RBTree.this.length;
    }

    /**
     * testen, ob other = this (nur vergleichen die Nicht-Null Elemente)
     * 
     * @author YC Terry
     * @param other Anderer Vektor, mit dem verglichen wird
     * @return boolean Wahrheitswert, ob Vektoren gleich sind
     */
    public boolean equals(RBTree other) {

        if (this.getLength() != other.getLength()) {

            return false;

        }

        Node thisnow = this.firstNode;
        Node othernow = other.firstNode;

        while (thisnow != null || othernow != null) {

            if (thisnow != null && othernow != null) {
                if (!(thisnow.index == othernow.index && thisnow.value == othernow.value)) {
                    return false;
                }

                thisnow = thisnow.next;
                othernow = othernow.next;

                // wenn die Anzahl der Positionen mit Nicht-Null-Elementen nicht übereinstimmen
                // = nicht identisch
            } else if ((thisnow != null && othernow == null) || (othernow != null && thisnow == null)) {

                return false;
            }

        }
        return true;
    }

    /**
     * to add two vectors together and renew (overwrite) the this.vector
     * 
     * @author YC Terry
     * @param other Anderer Vektor, der auf addiert wird
     */
    public void add(RBTree other) {

        Node thisnow = this.firstNode;
        Node othernow = other.firstNode;
        Node thispre = null;

        // Fall 0: 2 Vektoren mit unterschiedlichen Längen geht nicht!
        if (this.getLength() != other.getLength()) {

            System.out.println("Vektoren mit unterschiedlichen Längen können nicht zusammen addiert werden!!");
            System.out.println(
                    "Länge des controlVector: " + this.getLength() + " aber die von otherVector: " + other.getLength());
            return;

        }

        while (thisnow != null && othernow != null) {

            // Fall 1, gleicher Index, dann nur Werte zusammen addieren → update this Vektor
            if (thisnow.index == othernow.index) {
                thisnow.value += othernow.value; // overwrite the this. value
                thispre = thisnow;
                thisnow = thisnow.next;
                othernow = othernow.next;
            }

            // Fall 2: Der Index von othernow ist kleiner, füge diesen Knoten in this ein
            else if (othernow.index < thisnow.index) {

                Node newNode = new Node(othernow.index, othernow.value, thisnow);

                if (thispre == null) {
                    this.firstNode = newNode;
                } else {
                    thispre.next = newNode;
                }

                // this Vektor Zeiger und other Vektor Zeiger gehen weiter voran
                othernow = othernow.next;
                thispre = newNode;

                // Fall 3: Der Index von othernow > thisnow, 2 Zeiger gehen weiter
            } else if (othernow.index > thisnow.index) {

                thispre = thisnow;
                thisnow = thisnow.next;

            }

        }

    }
}