// Übung zu Listen: Sortierte einfach verkettete Liste,
//                  einfügen / löschen / durchlaufen
//                  Version mit "Pointer auf Pointer"
//
// Aufruf: sorted-list-dblptr
//
// 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 seinen Nachfolger fest
    Elem(double v, Elem *n) : val(v), next(n) {}

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

// 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
    void insert(double val) {
      // richtige Stelle zum Einfügen suchen:
      // wir wollen next auf dasjenige Element der Liste zeigen lassen,
      // vor dem das neue Element eingefügt gehört
      // gehört das neue Element ganz ans Ende der Liste,
      // oder war die Liste bisher komplett leer,
      // dann soll next auf den nullptr gesetzt werden
      // (das macht aber für den Code nach der Schleife keinen Unterschied)
      Elem *next;
      // ptrptr zeigt immer auf den Pointer,
      // der auf das Element next zeigt
      // am Anfang zeigt ptrptr daher auf den head-Pointer,
      // und dann immer auf den next-Pointer in dem Element vor next
      Elem **ptrptr = &head;
      for (;;) {
        // next ist das Element, auf das der Pointer zeigt,
        // der dort gespeichert ist, wo ptrptr hinzeigt
        next = *ptrptr;
        // wenn es kein next mehr gibt,
        // oder wenn der Wert des Elementes next größergleich val ist,
        // sind wir an der richtigen Stelle: Suchschleife verlassen
        if ((next == nullptr) || (next->val >= val)) break;
        // sonst rücke in der Liste eins weiter:
        // lass ptrptr auf den next-Pointer im Element next zeigen
        ptrptr = &(next->next);
      }
      // erzeuge ein neues Element mit Wert val
      // und hänge es vor next in die Liste:
      // der Nachfolger des neuen Elementes ist next,
      // und den Pointer, der bisher auf next gezeigt hat
      // (das kann der head-Pointer sein,
      // wenn wir das neue Element vor dem ersten Element einfügen,
      // oder der next-Pointer des Vorgängers von next)
      // lassen wir jetzt auf das neu erzeugte Element zeigen
      *ptrptr = new Elem(val, next);
    }

    // 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) {
      // Suchschleife wie bei insert
      Elem *next;
      Elem **ptrptr = &head;
      for (;;) {
        next = *ptrptr;
        if ((next == nullptr) || (next->val >= val)) break;
        ptrptr = &(next->next);
      }
      if ((next == nullptr) || (next->val > val)) {
        // Es gibt kein Element mit Wert val
        // (weil wir entweder am Ende der Liste angekommen sind
        // bzw. die Liste komplett leer ist,
        // oder weil das Element next größer val ist)
        return false;
      } else {
        // next zeigt auf das zu löschende Element (Element mit Wert val)
        // ptrptr zeigt auf den Pointer, der auf das zu löschende Element zeigt
        // (das kann entweder head sein,
        // wenn das zu löschende Element das erste Element in der Liste ist,
        // oder der next-Pointer im Element unmittelbar vor dem zu löschenden,
        // wenn das zu löschende Elememt mitten in der Liste oder am Ende ist)
        // 
        // "Überspringe" next in der Liste,
        // d.h. speichere in dem Pointer, der bisher auf next zeigt,
        // einen Pointer auf den Nachfolger von next
        *ptrptr = next->next;
        delete next;  // Freigeben des entfernten Elementes nicht vergessen!
        return true;
      }
    }

    // output:
    // gib alle Elemente der Liste der Reihe nach aus, und auch ihre Anzahl
    // (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;
}