// Übung zu Listen: Sortierte einfach verkettete Liste,
//                  einfügen / löschen / durchlaufen
// Mit selbstgeschriebenen Template-Klassen
//
// Aufruf: sorted-list-templ
//
// Klaus Kusche, 2018

#include <iostream>
#include <string>

using namespace std;

template <typename T>
class SortList;

// 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
template <typename T>
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<T>;

  private:
    // Konstruktor:
    // Wir legen gleich beim Anlegen eines Elementes
    // seinen Wert und seinen Nachfolger fest
    Elem(T v, Elem *n) : val(v), next(n) {}

    const T val;      // die Nutzdaten: Ein Wert vom Typ T
                      // 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
template <typename T>
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(T 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
        head = new Elem<T>(val, head);
      } 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<T> *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<T> *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:
        // Das neue Element wird der Nachfolger von prev
        // und der Nachfolger des neuen Elementes wird next
        // (also der bisherige Nachfolger von prev)
        // Das funktioniert sowohl mitten in der Liste
        // als auch an deren Ende (next ist in diesem Fall der nullptr)
        prev->next = new Elem<T>(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(T val) {
      if ((head == nullptr) || (head->val > val)) {
        // Fall 1: Die Liste ist leer,
        // oder das erste Listenelement ist schon größer als val
        // ==> val nicht gefunden
        return false;
      } else if (head->val == val) {
        // Fall 2: Das erste Element der Liste hat Wert val, lösche es
        Elem<T> *tmp = head; // tmp zeigt auf das zu löschende Element
        head = tmp->next;    // dessen Nachfolger wird neues erstes Element
        delete tmp;          // Speicher des zu löschenden Elementes freigeben
        return true;
      } else {
        // Das zu löschende Element ist sicher nicht das erste
        // ==> Wir müssen die Liste durchsuchen
        // Schleife wie bei "insert":
        // stelle prev auf das Element vor dem zu löschenden
        // (d.h. auf das letzte Element mit Wert kleiner val)
        // und next auf das zu löschende Element
        // (d.h. auf das erste Element mit Wert val oder größer)
        Elem<T> *prev = head;
        Elem<T> *next = prev->next;
        while ((next != nullptr) && (next->val < val)) {
          prev = next;
          next = prev->next;
        }
        if ((next == nullptr) || (next->val > val)) {
          // Fall 3: Es gibt kein Element mit Wert val
          // (weil wir entweder am Ende der Liste angekommen sind,
          // oder weil das Element prev kleiner val
          // und das Element next größer val ist)
          return false;
        } else {
          // Fall 4: Hauptfall:
          // next zeigt auf das zu löschende Element (Element mit Wert val),
          // und prev zeigt auf das Element unmittelbar davor
          //
          // "Überspringe" next in der Liste,
          // d.h. der bisherige Nachfolger von next
          // wird der neue Nachfolger von prev
          prev->next = 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<T> *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<T> *head; // Zeiger auf das erste (kleinste) Element
                   // einen Zeiger auf das letzte Element brauchen wir nicht
};

int main()
{
//  double val;
//  SortList<double> list;
  string val;
  SortList<string> list;

  while (cin >> val) {
//    if (val > 0) {
    if (val[0] != '-') {
      // positiver Wert bzw. String ohne '-' am Anfang: Einfügen
      list.insert(val);
//    } else if (val < 0) {
    } else if (val.length() > 1) {
      // negativer Wert bzw. String mit '-' am Anfang:
      // Entsprechenden positiven Wert bzw. String ohne '-' rauslöschen
//      if (list.remove(-val)) {
      if (list.remove(val.substr(1))) {
        cout << val << " removed" << endl;
      } else {
        cout << val << " not found" << endl;
      }
    } else {
      // Wert 0 bzw. nur "-": Schleife verlassen
      break;
    }
    // nach jeder Listen-Änderung: Liste ausgeben
    list.output();
  }

  return 0;
}