// Übung zu Listen: Sortierte doppelt verkettete Liste,
//                  einfügen / suchen / löschen / durchlaufen
//
// Aufruf: sorted-dbl-list
//
// Klaus Kusche, 2018

#include <iostream>

using namespace std;

// Klasse für ein einzelnes Element der Liste
// an sich würde eine Struktur statt einer Klasse genügen,
// aber eine Klasse hat einen schönen Konstruktor
class Elem
{
  // "Elem" soll nur innerhalb von "SortList" verwendbar sein
  // wir machen daher alles in Elem privat (==> keiner kann darauf zugreifen)
  // und erklären SortList zum Freund (==> aber SortList darf alles)
  friend class SortList;

  private:
    // Konstruktor:
    // Wir legen gleich beim Anlegen eines Elementes
    // seinen Wert und seine Nachbarn fest
    Elem(double v, Elem *n, Elem *p) : val(v), next(n), prev(p) {}

    const double val; // die Nutzdaten: Eine Kommazahl
                      // nach dem Anlegen (Konstruktor) nicht mehr änderbar
                      // denn das würde ja die Sortierung der Liste zerstören
    Elem *next;       // die Listen-Verkettung: Zeiger auf das nächste Element
    Elem *prev;       // die Listen-Verkettung: Zeiger auf das vorige Element
};

// Klasse für die sortierte Liste als Ganzes
class SortList
{
  public:
    // Konstruktor:
    // Eine neu angelegte Liste wird auf "leer" initialisiert
    // (kein erstes Element)
    SortList() : head(nullptr) {}

    // insert:
    // füge ein neues Element mit dem Wert val
    // an der richtigen Stelle in die sortierte Liste ein
    // die Such-Logik ist gleich wie bei der einfach verketteten Liste
    // nur beim eigentlichen Einfügen werden ein paar Pointer mehr gesetzt
    void insert(double val) {
      if ((head == nullptr) || (head->val >= val)) {
        // wenn die Liste noch ganz leer ist oder
        // wenn der neue Wert kleiner als der Wert des ersten Elementes ist:
        // füge ein neues Element als vorderstes Element in die Liste ein
        // sein Nachfolger ist das bisher erste Element
        // Vorgänger hat es keinen
        Elem *new_elem = new Elem(val, head, nullptr);
        // es wird der Vorgänger des bisherigen ersten Elementes,
        // falls es eines gab
        if (head != nullptr) {
          head->prev = new_elem;
        }
        // und es wird das neue erste Element
        head = new_elem;
      } else {
        // die Liste ist nicht leer,
        // und das neue Element gehört nicht als erstes,
        // sondern irgendwo mitten in die Liste (oder an ihr Ende),
        // d.h. an ein bestehendes Element angehängt

        // Vorgänger: Dieser Zeiger soll auf das Element zeigen,
        // an das wir das neue Element anhängen müssen
        // (mit einem Wert kleiner als der einzufügende Wert)
        Elem *prev = head;  // Am Anfang: Erstes Element
        // Nachfolger: Dieser Zeiger soll auf das Element
        // hinter dem neuen Element zeigen,
        // d.h. auf das Element, vor dem wir das neue Element einfügen müssen
        // (mit einem Wert größergleich dem einzufügenden Wert)
        Elem *next = prev->next;  // Am Anfang: Zweites Element (oder nullptr)
        // suche die richtige Stelle:
        // durchlaufe die Liste so,
        // dass prev und next immer auf zwei aufeinanderfolgende Elemente zeigen
        // bis es entweder kein next mehr gibt
        // (Ende der Liste, prev zeigt dann auf das letzte Element der Liste)
        // oder der Wert im Element next größergleich dem einzufügenden Wert ist
        while ((next != nullptr) && (next->val < val)) {
          prev = next;        // prev rutscht auf seinen Nachfolger
          next = prev->next;  // und next auf dessen Nachfolger
        }
        // erzeuge ein neues Element mit Wert val
        // und füge es hinter prev und vor next ein:
        // Der Nachfolger des neuen Elementes wird next
        // (also der bisherige Nachfolger von prev),
        // und sein Vorgänger wird prev
        // Das funktioniert sowohl mitten in der Liste
        // als auch an deren Ende (next ist in diesem Fall der nullptr)
        Elem *new_elem = new Elem(val, next, prev);
        // Das neue Element wird der Nachfolger von prev
        prev->next = new_elem;
        // und wenn es einen Nachfolger gibt,
        // ist das neue Element dessen Vorgänger
        if (next) {
          next->prev = new_elem;
        }
      }
    }

    // find:
    // Suche das Element mit dem Wert val
    // (bzw. bei mehreren Elementen mit Wert val: das erste davon)
    // Returnwert: Pointer auf das gefundene Element
    //             oder nullptr, wenn es kein Element mit dem Wert val gibt
    Elem *find(double val) {
      Elem *pos;
      // durchlaufe die Liste:
      for (pos = head;         // beginne beim ersten Listen-Element
           pos != nullptr;     // wiederhole, solange du ein Element hast
           pos = pos->next) {  // geh am Ende eines jeden Schleifendurchlaufes
                               // zum Nachfolger des aktuellen Elementes
        if (pos->val > val) {  // Wert im aktuellen Element ist schon zu groß
          return nullptr;      // ==> gesuchter Wert kommt nicht vor
        }
        if (pos->val == val) { // gefunden!
          return pos;
        }
      }
      // Liste bis zum Ende durchlaufen, nichts gefunden
      return nullptr;
    }
    
    // remove:
    // lösche das Element mit dem Wert val aus der Liste
    // (bzw. bei mehreren Elementen mit Wert val: das erste davon)
    // Returnwert true: Element mit val gefunden und gelöscht
    // Returnwert false: Die Liste enthält kein Element mit Wert val
    bool remove(double val) {
      // Element suchen
      Elem *pos = find(val);
      if (pos == nullptr) return false;
      // Entferne Element pos aus der Liste:
      // next-Zeiger vom Vorgänger auf das Element hinter pos zeigen lassen
      // bzw. wenn pos das erste Element ist:
      // head-Zeiger auf das Element hinter pos zeigen lassen
      if (head == pos) {
        head = pos->next;
      } else {
        pos->prev->next = pos->next;
      }
      // und falls pos einen Nachfolger hatte:
      // Der Vorgänger von pos wird dessen neuer Vorgänger
      if (pos->next != nullptr) {
        pos->next->prev = pos->prev;
      }
      delete pos;   // Entferntes Element freigeben
      return true;
    }

    // output:
    // gib alle Elemente der Liste der Reihe nach aus, und auch ihre Anzahl
    // ident zum Code der einfach verketteten Liste
    // (wenn's ganz schön sein soll,
    // sollte stattdessen eigentlich ein Ausgabe-Operator programmiert werden)
    void output() {
      int cnt = 0;  // Zähler für Anzahl der Elemente
      Elem *pos;    // Zeiger auf aktuell auszugebendes Element
      // typische Listen-Durchlauf-Schleife
      for (pos = head;         // beginne beim ersten Listen-Element
           pos != nullptr;     // wiederhole, solange du ein Element hast
           pos = pos->next) {  // geh am Ende eines jeden Schleifendurchlaufes
                               // zum Nachfolger des aktuellen Elementes
        cout << pos->val << " ";  // gib den Wert des aktuellen Elementes aus
        ++cnt;                    // und zähle das Element
      }
      cout << "(" << cnt << " elements)" << endl;
    }

  private:
    Elem *head;  // Zeiger auf das erste (kleinste) Element
                 // einen Zeiger auf das letzte Element brauchen wir nicht
};

int main()
{
  double val;
  SortList list;

  while (cin >> val) {
    if (val > 0) {
      // positiver Wert: Einfügen
      list.insert(val);
    } else if (val < 0) {
      // negativer Wert: Entsprechenden positiven Wert rauslöschen
      if (list.remove(-val)) {
        cout << val << " removed" << endl;
      } else {
        cout << val << " not found" << endl;
      }
    } else {
      // Wert 0: Schleife verlassen
      break;
    }
    // nach jeder Listen-Änderung: Liste ausgeben
    list.output();
  }

  return 0;
}