/***************************************************************/
/* Prof. Dr. Carsten Vogt                                      */
/* FH Koeln, Fak. 07 / Nachrichtentechnik                      */
/* http://www.nt.fh-koeln.de/vogt                              */
/*                                                             */
/* Beispielprogramm p08050100.c                                */
/* aus "C fuer Java-Programmierer", Hanser-Verlag              */
/*                                                             */
/* Demonstriert wird der Realisierung von Mengen durch doppelt */
/* verkettete Listen.                                          */
/***************************************************************/

#include <stdio.h>
#include <stdlib.h>

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

int einfuegen(listenknoten_dop **kopf, int wert) {
 listenknoten_dop *einzufueg = (listenknoten_dop *) malloc(sizeof(listenknoten_dop));
 einzufueg->wert = wert;
 if (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_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;
}

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;
}

listenknoten_dop *copy(listenknoten_dop *kn) {
 listenknoten_dop *kn_neu = (listenknoten_dop *) malloc(sizeof(listenknoten_dop));
 kn_neu->wert = kn->wert;
 kn_neu->next = kn_neu->prev = NULL;
 return kn_neu;
}

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

void init(listenknoten_dop **menge_a,listenknoten_dop **menge_b) {
 listenknoten_dop *hilf;
 while (*menge_a!=NULL) {
   hilf = entfernen_kopf_dop(menge_a);
   free(hilf);     
  }
 while (*menge_b!=NULL) {
   hilf = entfernen_kopf_dop(menge_b);
   free(hilf);     
  }
 einfuegen(menge_a,5);
 einfuegen(menge_a,4);
 einfuegen(menge_a,3);
 einfuegen(menge_a,2);
 einfuegen(menge_a,1);
 einfuegen(menge_b,8);
 einfuegen(menge_b,7);
 einfuegen(menge_b,6);
 einfuegen(menge_b,5);
 einfuegen(menge_b,4);
 einfuegen(menge_b,3);
 printf("Menge A: ");
 ausgabe(*menge_a);
 printf("Menge B: ");
 ausgabe(*menge_b);
}

int addAll(listenknoten_dop **a, listenknoten_dop *b) {
 listenknoten_dop *hilfliste = NULL,
                  *laufzeiger;
 if (a==NULL)
  return -1;
 if (b==NULL)
  return 0;
 laufzeiger = b;
 do {
  if (suchen_dop(*a,laufzeiger->wert)==NULL)
   einfuegen_ende_dop(&hilfliste,copy(laufzeiger));
  laufzeiger = laufzeiger->next;
 } while (laufzeiger!=b);
 do {
  laufzeiger = entfernen_kopf_dop(&hilfliste);
  einfuegen_ende_dop(a,laufzeiger);
 } while (hilfliste!=NULL);
 return 0;
}

int removeAll(listenknoten_dop **a, listenknoten_dop *b) {
 listenknoten_dop *laufzeiger, *zuentfernen;
 if (a==NULL)
  return -1;
 if (b==NULL)
  return 0;
 laufzeiger = b;
 do {
  zuentfernen = suchen_dop(*a,laufzeiger->wert);
  if (zuentfernen!=NULL) {
    entfernen_dop(a,zuentfernen);
    free(zuentfernen);
   }
  laufzeiger = laufzeiger->next;
 } while (laufzeiger!=b);
 return 0;
}

int retainAll(listenknoten_dop **a, listenknoten_dop *b) {
 listenknoten_dop *hilfliste = NULL,
                  *laufzeiger, *hilfzeiger;
 if (a==NULL)
  return -1;
 laufzeiger = b;
 if (laufzeiger!=NULL)
  do {
   hilfzeiger = suchen_dop(*a,laufzeiger->wert);
   if (hilfzeiger!=NULL) {
     entfernen_dop(a,hilfzeiger);
     einfuegen_ende_dop(&hilfliste,hilfzeiger);
    }
   laufzeiger = laufzeiger->next;
  } while (laufzeiger!=b);
 while (*a!=NULL) {
   hilfzeiger=entfernen_kopf_dop(a);
   free(hilfzeiger);
  }
 *a = hilfliste;
 return 0;
}

int main(void) {

 listenknoten_dop *menge_a = NULL, *menge_b = NULL;

 int wahl, errcode;

 init(&menge_a,&menge_b);

 do {

  do {

   printf("\nBitte Funktion auswaehlen:\n\n");
   printf("( 1 )  Mengeninhalt ausgeben\n");
   printf("( 2 )  Vereinigungsmenge bilden: A = A vereinigt mit B\n");
   printf("( 3 )  Differenzmenge bilden: A = A ohne B\n");
   printf("( 4 )  Schnittmenge bilden: A = A geschnitten mit B\n");
   printf("( 5 )  Reset\n");
   printf("( 0 )  Programmende\n");

   scanf("%d",&wahl);

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

  printf("\n");

  switch(wahl) {

   case 1:

    printf("Menge A: ");
    ausgabe(menge_a);
    printf("Menge B: ");
    ausgabe(menge_b);

    break;

   case 2:

    errcode = addAll(&menge_a,menge_b);
    if (errcode==0)
      printf("Vereinigungsmenge in Menge A gebildet\n");
     else
      printf("\nFehler\n");

    break;

   case 3:

    errcode = removeAll(&menge_a,menge_b);
    if (errcode==0)
      printf("Differenzmenge in Menge A gebildet\n");
     else
      printf("\nFehler\n");

    break;

   case 4:

    errcode = retainAll(&menge_a,menge_b);
    if (errcode==0)
      printf("Schnittmenge in Menge A gebildet\n");
     else
      printf("\nFehler\n");

    break;

   case 5:

    init(&menge_a,&menge_b);
    break;

  }

 } while (wahl!=0);

}