/**
     *  @file RList.java Listenverwaltung  in Form einer <b>doppelt
     *  verketteten Ringliste</b>.
     *
     *   <ul>
     *    <li> Jedes Listenelement m ist mit einer Referenz m.n auf den
     *          Nachfolger und einer Referenz  m.p auf den Vorgänger versehen
     *         (sog. doppelte Verkettung).
     *    <li> Jede Liste enthält immer ein sog. <b>Ankerelement</b>.
     *          Dieses  trägt niemals
     *          Nutzdaten (Komponente 'data' ist die null-Referenz).
     *    <li> Die leere Liste wird allein durch das Ankerelement
     *          repräsentiert, bei dem Nachfolger
     *          und Vorgänger auf sich selbst zeigen.
     *    <li> Bei einer nicht leeren Liste ist der Nachfolger
     *          des Ankerelementes der <b>Listenkopf</b>, d.h.
     *          das erste Nutzdaten tragende Element der Liste. Der
     *          Vorgänger des Ankerelementes ist das <b>letzte Element</b>
     *          der Liste. Umgekehrt hat der Listenkopf immer das
     *          Ankerelement als Vorgänger, und das letzte Element der
     *          Liste hat immer das Ankerelement als Nachfolger.
     *    </ul>
     *
     *  Der Vorteil einer doppelt verketteten Ringliste besteht darin,
     *  dass Einfüge- und Löschoperationen, sowie Konkatenation
     *   ohne spezielle Fallunterscheidungen
     *  "Liste leer/nicht leer", "Löschen des letzten Elementes" etc.
     *  auskommen.
     */

    /**
     *  Aus der Klasse Rlist werden einzelne Listenelemente instanziiert.
     *  Gleichzeitig repräsentiert das Ankerelement der Liste die
     *  gesamte Liste, denn vom Ankerelement aus lässt sich jedes
     *  Listenelement erreichen.
     */
    class Rlist<T extends Comparable<T>> {

        /** Jeder Listeneintrag hat ein Objekt vom Typ T als Nutzdaten.
         *  Das Ankerelement l der Liste ist durch die Bedingung
         *
         *  <code>l.data == null</code>
         *
         *  eindeutig gekennzeichnet.
         */
        private T data;

        /** Referenz auf das Nachfolger-Listenelement */
        private Rlist<T> n;

        /** Referenz auf das Vorgänger-Listenelement */
        private Rlist<T> p;

        /**
         *  Konstruktor Rlist() erzeugt eine neue leere
         *  Liste.
         *
         *  @return Korrekt initialisiertes Ankerelement und damit
         *           eine leere Liste, die allein durch das Ankerelement
         *           repräsentiert ist.
         */
        public Rlist() {
            data =  null;
            n = this;
            p = this;
        }



        /**
         *  Methode isEmpty() prüft, ob eine Liste
         *  leer ist.
         *
         *
         *  @return Gibt genau dann true zurück, wenn die Liste leer ist,
         *          d.h. wenn Vorgänger und Nachfolger wieder
         *          auf das Listenelement zeigen, auf dem empty()
         *          aufgerufen wird: Damit ist nachgewiesen, dass
         *          die Liste allein aus dem Ankerelement besteht.
         *
         */
        public boolean isEmpty() {

                return data == null && n == this && p == this;


        }


        /**
         *  Methode size() berechnet die Länge
         *  einer Liste. Das Ankerelement wird
         *  dabei <b>nicht</b> mit gezählt.
         *
         *  @return Anzahl der Listenelemente,
         *          abzüglich des Ankerelements.
         *
         *  @note Wegen der Ringverkettung kann die Methode auf ein
         *        beliebiges Listenelement aufgerufen werden.
         *        Die Zählung endet, wenn bei der Traversion der List wieder
         *        das Ursprungselement erreicht wurde.
         *
         */
        public int size() {

            int s = 0;
            Rlist<T> e = this;
            do {
                s++;
                e = e.n;
                e.p = e;
            } while (e != this);
            return s-1;
        }

        /**
         *  Methode clear() löscht den Listeninhalt, so dass
         *  die leere Liste zurück bleibt.
         *  Diese Methode darf nur auf das Ankerelement aufgerufen
         *  werden.
         *
         */
        public void clear() {

           if (data == null){
        	   p.n = p;
        	   n.p = n;
        	   n = this;
        	   p = this;
           }

        }

        /**
         * Methode add() fügt ein neues Listenelement
         * <b>hinter</b>  dem Element ein, auf welchem
         * die Methode aufgerufen wurde.
         *
         *  @param d Einzufügendes Nutzdatenobjekt.
         *
         *  @note Die Operation lässt sich ohne ein
         *        einziges if-statement realisieren.
         *
         *  @note add(null) ist nicht zulässig,
         *        weil ansonsten das Ankerelement nicht eindeutig
         *        bestimmbar wäre.
         *
         */
        public void add(T d) {

                Rlist<T> x = new Rlist<T>();
                x.data = d;
                x.n = this.n;
                this.n = x;
                x.p = this.p;
                this.p = x;


        }

        /**
         * Methode insert() fügt ein neues Listenelement
         * <b>vor</b> demjenigen ein, auf welchem die Operation
         * aufgerufen wird.
         *
         *  @param d Nutzdaten für das neu
         *         anzulegende Listenelement.
         *
         *  @note Die Operation lässt sich ohne ein
         *        einziges if-statement realisieren.
         *
         *  @note insert(null) ist nicht zulässig,
         *        weil ansonsten das Ankerelement nicht eindeutig
         *        bestimmbar wäre.
         */
        public void insert(T d) {



        }


        /**
         * Methode get() gibt den Inhalt (Nutzdaten) des
         * Listenelements zurück, auf dem die Operation
         * aufgerufen wird.
         *
         *  @return Referenz auf die Nutzdaten (kann null sein,
         *  falls es sich um das Ankerelement handelt)
         *
         */
        public T get() {
            return data;
        }

        /**
         * Methode next() gibt die Referenz auf
         * den Nachfolger des Listenelements l zurück,
         * auf dem die Methode aufgerufen wird.
         *
         *  @return Nachfolger l.n von l.
         *
         */
        public Rlist<T> next() {

        	return n;
        }

        /**
         * Methode prev() gibt die Referenz auf
         * den Vorgänger des Listenelements l zurück, auf dem
         * die Methode aufgerufen wird.
         *
         *  @return Vorgänger l.p von l.
         *
         */
        public Rlist<T> prev() {



            return p;
        }

        /**
         * Methode find() sucht nach einem Listenelement l,
         * welches ein vorgegebenes Nutzdatenelement enthält,
         * und gibt die Referenz auf dieses Element l zurück,
         * falls vorhanden.
         *
         *  @param d Nutzdatenobjekt, das unter den Listenelementen
         *           gesucht werden soll.
         *  @return null, falls d bei keinem Element als Nutzdaten
         *          eingetragen ist.
         *  @return Referenz auf das erste gefundene Listenelement sonst.
         *
         *  @note Zum Vergleich der Nutzdaten wird die Methode equals()
         *        verwendet.
         */
        public Rlist<T> find(T d) {



            return null;
        }



        /**
         * Methode remove() löscht das Listenelement aus der Liste,
         * auf welchem die Methode aufgerufen wurde.
         * Wirkungslos, wenn auf dem Ankerelement aufgerufen.
         *
         *
         *  @note Diese Operation benötigt eine if-Abfrage.
         *        Warum?
         */
        public void remove() {

           if (data != null){
        	   p.n = n;
        	   n.p = p;
        	   n = this;
        	   p = this;
           }

        }


        /**
         * Methode toString() gibt den Nutzdateninhalt der Liste als String zurück.
         *
         * Der String ist eine durch spitze Klammern eingefasste und durch Komma
         * separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
         * Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der
         * Methode toString() formatiert.
         * Beispielrückgabe: "<1, 2, 4, 3>"
         *
         *  Diese Methode darf nur auf das Ankerelement aufgerufen
         *  werden.
         *
         * @return Der String.
         */
        public String toString() {

        	String inhalt = "<";

           if (data == null){

        	   Rlist l = this;

        	  do {

        		  inhalt = inhalt + l.get() + ", ";
        		  l.next();

        	  } while (l.data != null);

           }

           inhalt = inhalt + ">";
           return inhalt;
        }


        /**
         * Methode equals() vergleicht zwei Listen auf
         * inhaltliche Gleichheit.
         *
         *  Diese Methode darf nur auf das Ankerelement aufgerufen
         *  werden.
         *
         *  @param o Referenz auf Ankerelement der zweiten Liste.
         *         Die Liste darf leer sein.
         *
         *  @return false, wenn o nicht vom Typ RList ist.
         *  @return false, wenn die Listen unterschiedliche Länge haben.
         *  @return false, wenn sich die Listen bei mindestens einem Element
         *           in den Nutzdaten unterscheiden.
         *  @return true, falls die Listen dieselbe Länge, dieselben
         *          Nutzdaten und dieselbe Sortierung besitzen.
         */
        @Override
        public boolean equals(Object o) {


	        	if (!(o instanceof Rlist)){
	        		return false;
	        	}

	        	Rlist lAux = (Rlist) o;
	            Rlist l = this;

	            if (data == null && lAux.data == null){

		            if (size() != lAux.size()){
		            	return false;
		            }

		            for (l = l.n, lAux = lAux.n; l.p.data == null; l = l.next(), lAux = lAux.next() ) {
		                if (! l.get().equals(lAux.get()) ){
		                	return false;
		                }
		            }

	            }
	            return true;
        }


        /**
         *  Methode addSorted() fügt das Element d in die Liste
         *  ein, so dass eine vorher aufsteigend sortierte Liste
         *  nach  Ausführung von addSorted() immer noch aufsteigend
         *  sortiert ist.
         *  Diese Methode darf nur auf das Ankerelement aufgerufen
         *  werden.
         *
         * @param d Das einzufügende Element.
         *
         * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
         */
        public void addSorted(T d) {



        }

        /**
         * Methode isSorted() überprüft, ob die Liste aufsteigend
         * sortiert ist. Diese Methode darf nur auf das
         * Ankerelement aufgerufen werden.
         *
         * @return Gibt genau dann true zurück, wenn die Liste sortiert ist.
         *
         * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
         */
        public boolean isSorted() {



            return false;
        }
    }