/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramme Nr. 61-63                                 */
/* der frueheren Vorlesung Datenverarbeitung                   */
/*                                                             */
/* Die Datei enthaelt eine Sammlung von Basisfunktionen        */
/* zur Arbeit mit doppelt verketteten Listen:                  */
/* - Einfuegen: vorn, hinten, an eine beliebige Stelle         */
/* - Ausfuegen                                                 */
/* - Durchlaufen mit Ausgabe                                   */
/* Die Listen sind zyklisch verkettet, d.h. der Nachfolger des */
/* letzten Elements ist das erste Element und der Vorgaenger   */
/* des ersten ist das letzte.                                  */
/*                                                             */
/* ACHTUNG: Die Datei enthaelt kein Hauptprogramm main() und   */
/* ist daher so nicht ausfuehrfaehig.                          */
/***************************************************************/

#include <stdio.h>

/* Typdefinition fuer die Elemente einer doppelt verketteten Liste */

typedef struct doplistelem {
  int                 wert;    /* Eintrag des Elements */
  struct doplistelem  *next;   /* Zeiger auf Nachfolger */
  struct doplistelem  *prev;   /* Zeiger auf Vorgaenger */
} doplistelem;

/* Variable fuer den Listenkopf = Zeiger auf das erste Listenelement */

doplistelem *dophead;

/* Funktion dopeinfueg(): fuegt nach einem bestimmten Listenelement ein
                          neues ein. */

int dopeinfueg(doplistelem *nachdiesem, doplistelem *einzufueg)
    /* nachdiesem: Element, nach dem eingefuegt werden soll
       einzufueg:  einzufügendes Element */
{
 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */
 if ((nachdiesem==NULL)||(einzufueg==NULL)) return -1;

 /* Einketten des neuen Elements */
 einzufueg->next = nachdiesem->next;
 einzufueg->prev = nachdiesem;
 nachdiesem->next->prev = einzufueg;
 nachdiesem->next = einzufueg;

 /* Rueckgabe des Codes 0 = ok */
 return 0;

}

/* Funktion dopneuerst(): fuegt ein neues erstes Listenelement ein. */

int dopneuerst(doplistelem **liste,doplistelem *einzufueg) {
    /* liste:      Liste, in die eingefuegt werden soll
       einzufueg:  einzufuegendes Element */

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
   Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */
 if ((einzufueg==NULL)||(liste==NULL)) return -1;

 /* Einketten des neuen Elements mit Aenderung von liste */
 if (*liste==NULL) {
  /* Liste war bisher leer => Listenkopf muss nun auf das einzufuegende
     Element zeigen, das (wegen der zyklischen Verkettung) sein eigener
     Vorgaenger und Nachfolger wird. */
  *liste = einzufueg;
  (*liste)->next = (*liste)->prev = *liste;
 }

 else {
  /* neues Element wird hinter den Vorgaenger des bisher ersten
     eingefuegt. Da die Verkettung zyklisch ist, kommt das neue
     Element also unmittelbar zwischen das bisher erste und das
     letzte */
  dopeinfueg((*liste)->prev,einzufueg);
  /* Listenkopf wird auf das neue Element verschoben */
  *liste = einzufueg;
 }

 /* Rueckgabe des Codes 0 = ok */
 return 0;
}

/* Funktion dopneuletzt(): fuegt ein neues letztes Listenelement ein. */

int dopneuletzt(doplistelem **liste,doplistelem *einzufueg) {
    /* liste:      Liste, in die eingefügt werden soll
       einzufueg:  einzufuegendes Element */

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */
 if ((einzufueg==NULL)||(liste==NULL)) return -1;

 if (*liste==NULL) {

 /* Falls Liste leer, Aenderung von liste */
  *liste = einzufueg;
  (*liste)->next = (*liste)->prev = *liste;
 }

 else

  /* Einketten des neuen Elements als Vorgaenger des ersten Listenelements.
     Wegen der zyklischen Verkettung wird es damit zum neuen letzten Listen-
     element. */
  dopeinfueg((*liste)->prev,einzufueg);

 /* Rueckgabe des Codes 0 = ok */
 return 0;
}

/* Funktion dopausfueg(): fuegt ein Element aus einer Liste aus. */

int dopausfueg(doplistelem **liste,doplistelem *auszufueg) {
    /* liste:      Liste, aus der ausgefuegt werden soll
       auszufueg:  auszufuegendes Element */

 /* Test, ob einer der beiden Parameter den Nullzeiger enthaelt.
    Wenn ja: Abbruch mit Rueckgabe des Fehlercodes -1 */
 if ((liste==NULL)||(auszufueg==NULL)) return -1;
 /* Test, ob Liste leer. Wenn ja: Fehler */
 if (*liste==NULL) return -1;

 if (auszufueg->next==auszufueg) {
  /* Falls das auszufuegende Element der einzige Listeneintrag ist
     (erkennbar daran, dass es - wegen der zyklischen Verkettung -
     sein eigener Nachfolger ist), wird die Liste jetzt leer. */
  *liste=NULL;
  return 0; /* okay */
 }

 if (*liste==auszufueg)
  /* Wenn das erste Element ausgefuegt werden soll, wird zunaechst
     der Listenkopf um ein Element nach hinten geschoben, damit er
     nach dem Ausfuegen nicht ins Leere verweist. */
  *liste=(*liste)->next;

 /* Ausketten des Elements: Der prev-Zeiger des Nachfolgers von auszufueg
    zeigt nicht mehr auf auszufueg, sondern auf dessen Vorgaenger.
    Analog wird mit dem next-Zeiger des Vorgaengers verfahren. */
 auszufueg->next->prev = auszufueg->prev;
 auszufueg->prev->next = auszufueg->next;

 return 0; /* okay */
 
}

/* Funktion dopdurchlauf(): durchlaeuft eine Liste von vorn nach hinten
                            und gibt dabei ihre Elemente aus. */

void dopdurchlauf(doplistelem *liste) {
 /* liste: zu durchlaufende Liste */
 doplistelem *hilfzeig;

 /* Liste leer? */
 if (liste==NULL) return;

 hilfzeig = liste;
 do {
  /* Schleife durch alle Listenelemente, beginnend vom Listenkopf */
  printf("%d ",hilfzeig->wert);
  hilfzeig = hilfzeig->next;
 }
 while (hilfzeig!=liste); /* bis (ueber die zyklische Verkettung)
                             der Listenkopf wieder erreicht wird */
 printf("\n");

}