//  Objektorientiertes Telefonlisten-Programm
//
//  mit generischen Listenklassen
//
//  Jens Gelhar 03.02.91


#include <stream.h>
#include <string.h>


// * * * abstrakter Datentyp "Listenelement" * * *

class Listenelement
{ private:
    Listenelement *next, *prev;       // Vorgänger und Nachfolger

    virtual int compare(const Listenelement*) const = 0;
    // vergleicht Objekt "*this" mit einem anderen Listenelement
    // und gibt -1, 0 oder +1 zurück (wie bei "strcmp")

    virtual void ausgabe() const = 0;
    // Ein Listenelement ausgeben

    virtual ~Listenelement()
     { }
    // virtuieller Destruktor - hier nur ein Dummy, kann aber
    // in abgeleiteten Klassen überdeckt werden

  protected:
    // kleine Extras: abgeleitete Klassen dürfen "next" und "prev"
    // auslesen:
    Listenelement *getnext() const
      { return next; }
    Listenelement *getprev() const
      { return prev; }

  friend class Liste;     // Diese später deklarierte Klasse
                          // braucht Zugriff auf private Member
};


// * * * generischer Datentyp "Liste" * * *

class Liste
{ private:
    Listenelement *anfang, *ende;  // erstes und letztes Element
                                   // der Liste
  protected:
    void insert(Listenelement *neu);
    // sucht eine geeignete Position für das Element "*neu" und
    // hängt es in die Liste ein

  public:
    Liste();          // Konstruktor zur Initialisierung
    ~Liste();         // Destruktor (löscht alle
                      // Listenelemente)
    void ausgabe();   // gibt die ganze Liste aus

    Listenelement *suchen(Listenelement *);
    // sucht ein Element, das dem Argument-Element "entspricht"
    // (was immer das in einer konkreten Liste heißen mag -
    // jedenfalls ein Element, bei dem "compare" Null liefert)
    // oder Null, wenn kein solches element existiert.

    void loeschen(Listenelement*);
    // hängt ein Element aus der Liste aus und löscht es
    // mit "delete"
};

Liste::Liste()
 { anfang = 0;
   ende = 0;
 }


Liste::~Liste()
 {
   Listenelement *p = anfang;

   while(p)
     { Listenelement *hilf = p;
       p=p->next;
       delete hilf;
     }
 }


void Liste::ausgabe()
  { for(Listenelement *l = anfang; l; l = l->next)
      l->ausgabe();
  }

Listenelement *Liste::suchen(Listenelement *e1)
  { for(Listenelement *e2 = anfang;
        e2 && e2->compare(e1);
        e2 = e2->next);
    return e2;
  }


void Liste::insert(Listenelement *neu)
  {
    // Position suchen:
    Listenelement *pos = anfang;
    while (pos && neu->compare(pos) > 0)
      pos = pos->next;

    // Element an Position "pos" in Liste einfügen
    // (prinzipiell genau wie in der ersten Programmversion)

    if (pos == 0)
    // Sonderfall: Anfügen an das Ende der Liste
    {
      Listenelement *alt = ende;    // altes Listenende

      if (alt != 0)
      // allgemeiner Unter-Fall: wirklich anhängen
      {
        alt->next = neu;
        neu->prev = alt;
        neu->next = 0;
        ende = neu;
      }
      else
      // spezieller Spezialfall: Liste ist noch leer
      { neu->next = 0;
        neu->prev = 0;
        anfang = neu;
        ende = neu;
      }
    }
    else
    if (pos->prev == 0)
    // Sonderfall: Neues Element an Listenanfang hängen
    {
      pos->prev = neu;
      neu->next = pos;
      neu->prev = 0;
      anfang = neu;
    }
    else
    // allgemeiner Fall: Element in Liste einhängen
    {
      Listenelement *vor = pos->prev;
      // "neu" zwischen "vor" und "pos" einhängen:
      vor->next = neu;
      neu->prev = vor;
      neu->next = pos;
      pos->prev = neu;
    }
  }


void Liste::loeschen(Listenelement *E)
  // Löscht das Element, auf das "E" zeigt, aus der Liste
  {
   // Vorgänger unf Nachfolger des zu löschenden Elements
   Listenelement *vor = E->prev, *nach = E->next;

   if (vor)
   // Element hat Vorgänger: Dann dessen Nachfolger umsetzen
     vor->next = nach;
   else
   // kein Vorgänger: Dann Listenanfang aktualisieren
     anfang = nach;

   if (nach)
   // Element hat Nachfolger: Dann dessen Vorgänger verändern
     nach->prev = vor;
   else
   // kein Nachfolger, also Listenende anpassen
     ende = vor;

   delete(E);
  }



// * * * spezieller Datentyp "Eintrag" * * *

class Eintrag : public Listenelement
 { public:
     char name[30];                // Name und...
     char nummer[20];              // Telefonnummer

     // Konstruktor:
     Eintrag(const char *neuname, const char *neunummer);

     // Funktionen, die virtuelle Funktionen der Basisklasse
     // definieren:
     int compare(const Listenelement*) const;
     void ausgabe() const;
 };


Eintrag::Eintrag(const char *neuname, const char *neunummer)
  : name(neuname),
    nummer(neunummer)
  { }


int Eintrag::compare(const Listenelement* that) const
 {
   Eintrag *that2 = (Eintrag*) that;
   return strcmp(this->name, that2->name);
 }


void Eintrag::ausgabe() const
 {  cout << name << ": " << nummer << "\n"; }


// * * * spezieller Datentyp "Telefonbuch" * * *

class Telefonbuch : private Liste
 { public:
     // Neues Element erzeugen und einfügen:
     Eintrag *insert(const char *, const char *);

     // Element anhand des Namens suchen:
     Eintrag *suchen(const char *);

     // zwei Funktionen werden öffentlich vererbt:
     Liste::ausgabe;
     Liste::loeschen;
 };


Eintrag* Telefonbuch::insert(const char *neuname, const char *neunummer)
 {
   // neues Element erzeugen:
   Eintrag *neu = new Eintrag (neuname, neunummer);

   if (!neu) return 0;           // kein Speicher frei!

   // Element in Liste einhängen:
   Liste::insert(neu);

   // Fertig, Zeiger auf neues Element zurückgeben:
   return neu;
 }


Eintrag *Telefonbuch::suchen(const char *name)
 {
   Eintrag dummy(name,"");
   return (Eintrag*) Liste::suchen(&dummy);
 };


// * * *  Hauptprogram  * * *

void main()
 {
   // Eine Liste wird deklariert und initialisiert:

   Telefonbuch t;

   // Ein paar Beispieldaten werden eingefügt:

   t.insert("Harley-Davidson", "001-414/342-4680");
   t.insert("Boris Becker", "0815/4711");
   t.insert("James Bond", "007/26731");
   t.insert("Maxon", "06196/481813");
   t.insert("Zaphod Beeblebrox", "00042/08154242");
   t.insert("Luxemburg", "00352");
   t.insert("Queensr\0377che", "795069");
   t.insert("Fishbone", "4676152");

   // Ein Datensatz wird gesucht und ggf. gelöscht:

   Eintrag *e = t.suchen("Maxon");
   if (e)
     t.loeschen(e);
   else
     cout << "Name nicht gefunden!\n";

   // restliche Liste ausgeben:
   t.ausgabe();

   // Löschen der Liste geschieht automatisch durch Destruktor-Aufruf
 }