/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramm p08020300.c                                */
/* aus "C fuer Java-Programmierer", Hanser-Verlag              */
/*                                                             */
/* Demonstriert wird der Umgang mit doppelt verketteten Listen.*/
/***************************************************************/

#include <stdio.h>

typedef struct listenknoten_dop {
  int  wert;
  struct listenknoten_dop  *prev;
  struct listenknoten_dop  *next;
} listenknoten_dop;

int einfuegen_kopf_dop(listenknoten_dop **kopf, listenknoten_dop *einzufueg) {
 if ((einzufueg==NULL)||(kopf==NULL)) return -1;
 if (*kopf==NULL) {
    *kopf = einzufueg;
    (*kopf)->next = (*kopf)->prev = *kopf;
   }
  else {
    einzufueg->next = *kopf;
    einzufueg->prev = (*kopf)->prev;
    einzufueg->prev->next = einzufueg;
    einzufueg->next->prev = einzufueg;
    *kopf = einzufueg;
   }
 return 0;
}

int einfuegen_nach_dop(listenknoten_dop *nachdiesem, listenknoten_dop *einzufueg) {
 if ((nachdiesem==NULL)||(einzufueg==NULL)) return -1;
 einzufueg->next = nachdiesem->next;
 einzufueg->prev = nachdiesem;
 nachdiesem->next = einzufueg;
 einzufueg->next->prev = einzufueg;
 return 0;
}

int einfuegen_ende_dop(listenknoten_dop **kopf, listenknoten_dop *einzufueg) {
 if ((einzufueg==NULL)||(kopf==NULL)) return -1;
 if (*kopf==NULL) {
  *kopf = einzufueg;
  (*kopf)->next = (*kopf)->prev = *kopf;
 }
 else
  einfuegen_nach_dop((*kopf)->prev,einzufueg);
 return 0;
}

listenknoten_dop *entfernen_kopf_dop(listenknoten_dop **kopf) {
 listenknoten_dop *kopf_alt;
 if ((kopf==NULL)||(*kopf==NULL)) return NULL;
 kopf_alt = *kopf;
 if (*kopf==(*kopf)->next) {
   *kopf = NULL;
   return kopf_alt;
  }
 *kopf=(*kopf)->next;
 (*kopf)->prev = kopf_alt->prev;
 (*kopf)->prev->next = *kopf;
 return kopf_alt;
}

listenknoten_dop *entfernen_ende_dop(listenknoten_dop **kopf) {
 listenknoten_dop *ende_alt;
 if ((kopf==NULL)||(*kopf==NULL)) return NULL;
 if (*kopf==(*kopf)->next) {
   ende_alt = *kopf;
   *kopf = NULL;
   return ende_alt;
  }
 ende_alt=(*kopf)->prev;
 (*kopf)->prev = ende_alt->prev;
 (*kopf)->prev->next = *kopf;
 return ende_alt;
}

listenknoten_dop *entfernen_dop(listenknoten_dop **kopf, listenknoten_dop *auszufueg) {
 if ((kopf==NULL)||(auszufueg==NULL)||(*kopf==NULL)) return NULL;
 if (auszufueg->next==auszufueg) {
  *kopf=NULL;
  return auszufueg;
 }
 if (*kopf==auszufueg)
  *kopf=(*kopf)->next;
 auszufueg->next->prev = auszufueg->prev;
 auszufueg->prev->next = auszufueg->next;
 return auszufueg;
}

void durchlaufen_dop(listenknoten_dop *kopf) {
 listenknoten_dop *laufzeiger;
 if (kopf==NULL) { printf("-------------\nENDE\n-------------\n\n"); return; }
 laufzeiger = kopf;
 printf("-------------\n");
 do {
  printf("%d ",laufzeiger->wert);
  laufzeiger = laufzeiger->next;
 }
 while (laufzeiger!=kopf);
 printf("ENDE\n-------------\n\n");
}

listenknoten_dop *suchen_dop(listenknoten_dop *kopf, int gesuchter_wert) {
 listenknoten_dop *laufzeiger;
 if (kopf==NULL)
  return NULL;
 laufzeiger = kopf;
 while (laufzeiger->next!=kopf&&laufzeiger->wert!=gesuchter_wert)
  laufzeiger = laufzeiger->next;
 if (laufzeiger->wert==gesuchter_wert)
   return laufzeiger;
  else
   return NULL;
}

int main(void) {

 listenknoten_dop *kopf_dop = NULL;

 listenknoten_dop *neu, *nachdiesem, *auszufuegen, *result;

 int wahl, wahl2, neuer_wert, gesuchter_wert, errcode;

 do {

  do {

   printf("\nBitte Funktion auswaehlen:\n\n");
   printf("( 1 )  Listeninhalt ausgeben\n");
   printf("( 2 )  Eintrag einfuegen\n");
   printf("( 3 )  Eintrag entfernen\n");
   printf("( 0 )  Programmende\n");

   scanf("%d",&wahl);

  } while (wahl<0 || wahl>3);

  printf("\n");

  switch(wahl) {

   case 1:

    durchlaufen_dop(kopf_dop);

    break;

   case 2:

    printf("Wert des neuen Eintrags: ");
    scanf("%d",&neuer_wert);

    neu = (listenknoten_dop *) malloc(sizeof(listenknoten_dop));
    neu->wert = neuer_wert;
    neu->prev = neu->next = NULL;

    printf("\nWohin einfuegen?\n\n");
    printf("( 1 )  Listenkopf\n");
    printf("( 2 )  Listenende\n");
    printf("( 3 )  nach einem bestimmten Eintrag\n");

    scanf("%d",&wahl2);

    switch(wahl2) {

     case 1: errcode = einfuegen_kopf_dop(&kopf_dop,neu);
             if (errcode!=0) printf("FEHLER\n");
             break;

     case 2: errcode = einfuegen_ende_dop(&kopf_dop,neu);
             if (errcode!=0) printf("FEHLER\n");
             break;

     case 3: printf("\nNach welchem Wert einfuegen? ");
             scanf("%d",&gesuchter_wert);
             nachdiesem = suchen_dop(kopf_dop,gesuchter_wert);
             if (nachdiesem!=NULL) {
                errcode = einfuegen_nach_dop(nachdiesem,neu);
                if (errcode!=0) printf("FEHLER\n");
               }
              else
               printf("\nEintrag nicht vorhanden\n");
             break;

     }

    break;

   case 3:

    printf("\nWelchen Knoten entfernen?\n\n");
    printf("( 1 )  Listenkopf\n");
    printf("( 2 )  Listenende\n");
    printf("( 3 )  Knoten mit bestimmtem Wert\n");

    scanf("%d",&wahl2);

    switch(wahl2) {

     case 1: result = entfernen_kopf_dop(&kopf_dop);
             if (result!=NULL)
               printf("Entfernt: %d\n",result->wert);
              else
               printf("FEHLER\n");
             break;

     case 2: result = entfernen_ende_dop(&kopf_dop);
             if (result!=NULL)
               printf("Entfernt: %d\n",result->wert);
              else
               printf("FEHLER\n");
             break;

     case 3: printf("Wert des zu entfernenden Knotens: ");
             scanf("%d",&gesuchter_wert);
             auszufuegen = suchen_dop(kopf_dop,gesuchter_wert);
             if (auszufuegen!=NULL) {
               result = entfernen_dop(&kopf_dop,auszufuegen);
               if (result!=NULL)
                printf("Entfernt: %d\n",result->wert);
               else printf("FEHLER\n");
              }
              else
               printf("\nEINTRAG NICHT VORHANDEN\n");

     }

    break;
    
  }

 } while (wahl!=0);

 return 0;

}