// Übung zu Bäumen: Worte zählen (Grundversion + getFirst / getNext + remove)
// Rekursive Remove-Variante ohne Doppelpointer
//
// Aufruf: baum-delete-rec
//
// Klaus Kusche, 2018

#include <iostream>
#include <string>
// für isalpha
#include <cctype>

using namespace std;

// Klasse für einen Baumknoten
class Node
{
  public:
    // jeder darf das Wort und die Anzahl auslesen
    string getWord() const { return word; }
    int getCnt() const { return cnt; }
    
  // Der Rest von "Node" soll nur innerhalb von "Tree" verwendbar sein
  // wir machen daher alles andere privat (==> keiner kann darauf zugreifen)
  // und erklären Tree zum Freund (==> aber Tree darf alles)
  friend class Tree;
  // die Ausgabe-Operatoren müssen auch auf die Member zugreifen können,
  // gehören aber zu keiner Klasse
  // wir schreiben gleich zwei Ausgabe-Operatoren:
  // einen für ein Knoten-Objekt, der nur diesen einen Knoten ausgibt
  friend ostream &operator<<(ostream &outfile, const Node &nodeObj);
  // ... und einen für einen Knoten-Pointer,
  // der den gesamten (Teil-) Baum ab diesem Knoten ausgibt
  // (bzw. nichts ausgibt, wenn er als Pointer den nullptr bekommt)
  friend ostream &operator<<(ostream &outfile, const Node *node);

  private:
    // Normaler Konstruktor:
    // Im neuen Knoten wird das angegebene Wort gespeichert
    // und die Anzahl seiner Vorkommen auf 1 gesetzt
    // Bei Binärbäumen werden neue Knoten immer als Blätter eingefügt,
    // daher haben neue Knoten beim Anlegen nie Söhne
    Node(const string &w) : word(w), cnt(1), left(nullptr), right(nullptr) {}
    // Konstruktor zum Kopieren eines Baumes:
    // Alle Member-Werte werden als Parameter angegeben
    Node(const string &w, int c, Node *l, Node *r) :
      word(w), cnt(c), left(l), right(r) {}
    // Baumknoten soll man weder kopieren noch zuweisen können,
    // nur die Pointer darauf werden kopiert und zugewiesen
    Node(const Node &node) = delete;  
    Node &operator=(const Node &node) = delete;  

    // Achtung: Das remove ändert das Wort in einem Knoten nachträglich
    // ==> kein const mehr!
    string word;          // Nutzdaten: Ein Wort
    int cnt;              // ... und die Anzahl seiner Vorkommen
    Node *left, *right;   // Pointer auf die Söhne
};

// Klasse für einen Baum
class Tree
{
  // wir erlauben dem Ausgabe-Operator für Bäume den Zugriff auf "root"
  friend ostream &operator<<(ostream &outfile, const Tree &tree);

  public:
    // Konstruktor:
    // Ein neuer Baum hat noch keine Knoten
    Tree() : root(nullptr) {}
    // Copy-Konstruktor: Baum rekursiv kopieren (d.h. alle Knoten kopieren)
    Tree(const Tree &orig) : root(copyRec(orig.root)) {}
    // Destruktor: Alle Knoten des Baumes rekursiv löschen
    ~Tree() {
      delRec(root);
    }
    // Die Zuweisung ganzer Bäume (würde Kopieren erfordern) bleibt verboten
    Tree &operator=(const Tree &tree) = delete;

    // zähle das Wort "word":
    // Wenn es schon im Baum vorhanden ist, erhöhe seinen Zähler um 1
    // sonst füge einen neuen Knoten für word in den Baum ein
    void count(const string &word) {
      if (root == nullptr) {
        // der Baum ist bisher leer
        // ==> neuen Knoten erzeugen, er wird neue Wurzel
        root = new Node(word);
      } else {
        Node *ptr;  // der Knoten, den wir uns gerade anschauen
        ptr = root; // oben mit der Wurzel anfangen
        for (;;) {  // und den Baum durchlaufen
          if (ptr->word < word) {
            // zu zählendes Wort muss rechts vom aktuellen Knoten sein
            if (ptr->right == nullptr) {
              // rechts gibt es noch keine Knoten
              // ==> neuen Knoten erzeugen
              // ... und rechts an den aktuellen Knoten hängen
              ptr->right = new Node(word);
              return;  // fertig!
            } else {
              // im nächsten Schleifendurchlauf beim rechten Sohn weitersuchen
              ptr = ptr->right;  
            }
          } else if (ptr->word > word) {
            // dasselbe für links
            if (ptr->left == nullptr) {
              ptr->left = new Node(word);
              return;
            } else {
              ptr = ptr->left;
            }
          } else {
            // ptr->word == word: Wort ist schon im Baum, ptr zeigt darauf
            // Zählerstand erhöhen
            ++(ptr->cnt);
            return;  // fertig!
          }
        } 
      }
    }

    // liefert einen Pointer auf den sortierordnungsmäßig kleinsten Knoten
    // im Baum (oder nullptr, wenn der Baum leer ist)
    Node *getFirst() const {
      if (root == nullptr) {
        return nullptr;
      }

      Node *nodePtr;
      // der sortierordnungsmäßig kleinste ist der am weitesten links
      // ==> gehe immer wieder nach links,
      //     bis der aktuelle Knoten keinen linken Sohn mehr hat:
      //     dann ist er der kleinste
      for (nodePtr = root; nodePtr->left != nullptr; nodePtr = nodePtr->left) {}
      return nodePtr;
    }

    // liefert einen Pointer auf den kleinsten Knoten im Baum,
    // der größer als das Wort "word" ist (d.h. auf den Nachfolger von word)
    // (oder nullptr, wenn es keinen Knoten größer word im Baum gibt)
    Node *getNext(const string &word) const {
      // Pointer auf den gesuchten Knoten:
      // Am Anfang kennen wir noch keinen Knoten größer Word
      Node *result = nullptr;
      // Pointer auf den aktuellen Knoten:
      // Wir beginnen oben im Baum
      Node *nodePtr = root;

      // Steige im Baum nach unten, bis du "unten rausfällst"
      while (nodePtr != nullptr) {
        if (nodePtr->word > word) {
          // der aktuelle Knoten ist größer Word:
          // Er ist ein Kandidat für das Ergebnis ==> merken
          result = nodePtr;
          // Aber es könnte Knoten links vom aktuellen Knoten geben,
          // die auch größer word, aber kleiner als der aktuelle Knoten sind
          // ==> links vom aktuellen Knoten weitersuchen
          nodePtr = nodePtr->left;
        } else {
          // der aktuelle Knoten ist kleinergleich word
          // ==> falls es überhaupt noch einen Knoten größer word gibt,
          // muss er rechts vom aktuellen Knoten sein
          nodePtr = nodePtr->right;
        }
      }

      // returniert den zuletzt gefundenen = kleinsten Knoten größer word
      // (oder den Anfangswert nullptr,
      // wenn die Schleife keinen Knoten größer word gefunden hat)
      return result;
    }

    // sucht und entfernt den Knoten mit dem Wort "word"
    // liefert dessen count wenn vorhanden
    // oder 0 wenn es keinen Knoten word gibt
    int remove(const string &word) {
      // rufe die rekursive Hilfsfunktion beginnend mit der Wurzel auf
      return removeRec(word, root);
    }

  private:
    Node *root;  // Zeiger auf die Wurzel (den obersten Knoten)

    // alle (rekursiven) Hilfsfunktionen
    // werden mit einem Pointer auf den zu bearbeitenden Teilbaum aufgerufen
    // ==> sie brauchen weder "root",
    // noch rufen sie eine Methode für den ganzen Baum auf
    // ==> sie brauchen kein "this"
    // ==> aus Performance-Gründen "static" deklarieren!

    // Hilfsfunktion für's Löschen:
    // Liefert einen Pointer auf den größten (äußerst rechten) Knoten
    // im Unterbaum beginnend bei node (node darf nicht nullptr sein!)
    static Node *maxNode(Node *node) {
      // gehe immer wieder nach rechts, bis es keinen rechten Sohn mehr gibt
      while (node->right != nullptr) {
        node = node->right;
      }
      return node;
    }

    // Rekursive Lösch-Funktion:
    // Lösche den Knoten word aus dem (Teil-) Baum,
    // auf dessen obersten Knoten ptr zeigt
    // Returnwert: Zählerstand cnt des gelöschten Knotens
    // oder 0, wenn es keinen Knoten word gibt
    //
    // Achtung:
    // Da sich der Baum beim Löschen ja ändert,
    // *speichert* die Funktion in ptr eventuell einen neuen Pointer
    // (auf die neue Wurzel des Teilbaumes)
    // Der Pointer ptr muss daher "by reference" übergeben werden!!!
    static int removeRec(const string &word, Node * &ptr) {
      if (ptr == nullptr) {
        // der zu durchsuchende Teilbaum ist leer ==> "nicht gefunden"
        return 0;
      } else if (ptr->word < word) {
        // der Knoten wort muss im rechten Unterbaum sein
        // == rekursiv dort herauslöschen
        return removeRec(word, ptr->right);
      } else if (ptr->word > word) {
        // dasselbe für den linken Unterbaum
        return removeRec(word, ptr->left);
      } else {
        // ptr->word == word, d.h. ptr zeigt auf den zu löschenden Knoten
        int retVal = ptr->cnt;  // cnt für den Returnwert merken
        if (ptr->left == nullptr) {
          // der zu löschende Knoten hat keinen linken Sohn
          // ==> ptr zeigt in Zukunft direkt auf seinen rechten Sohn
          // (und wenn rechts auch kein Sohn ist,
          // fällt der Teilbaum komplett weg, d.h. ptr wird der nullptr)
          Node *son = ptr->right;
          delete ptr;
          ptr = son;
        } else if (ptr->right == nullptr) {
          // der zu löschende Knoten hat einen linken, aber keinen rechten Sohn
          // ==> ptr zeigt in Zukunft direkt auf seinen linken Sohn
          Node *son = ptr->left;
          delete ptr;
          ptr = son;
        } else {
          // der "schwierige" Fall:
          // der zu löschende Knoten hat einen linken *und* einen rechten Sohn
          // er kann daher nicht aus dem Baum entfernt werden
          // sondern muss durch den Wert eines anderen Knotens ersetzt werden
          // wir nehmen dafür den größten Knoten des linken Unterbaumes
          // (wir könnten auch den kleinsten Knoten von rechts nehmen)
          Node *copyUp = maxNode(ptr->left);
          // alle seine Nutzdaten in den zu löschenden Knoten kopieren
          ptr->word = copyUp->word;
          ptr->cnt = copyUp->cnt;
          // und den heraufkopierten Knoten aus dem linken Unterbaum löschen
          removeRec(copyUp->word, ptr->left);
        }
        return retVal;
      }
    }

    // rekursive Baum-Kopier-Funktion:
    // liefert einen Pointer auf eine exakte Kopie
    // des Knotens ptr incl. seiner Unterbäume
    // liefert den nullptr, wenn ptr der nullptr ist
    static Node *copyRec(const Node *ptr) {
      if (ptr == nullptr) {
        // die Kopie eines leeren Teilbaumes ist ein leerer Baum
        return nullptr;
      } else {
        // die Kopie ist ein neuer Knoten mit denselben Nutzdaten,
        // an dem links und rechts Kopien der Unterbäume des Originals hängen
        return new Node(ptr->word, ptr->cnt,
                        copyRec(ptr->left), copyRec(ptr->right));
      }
    }

    // rekursive Baum-Lösch-Funktion:
    // löscht den Knoten node und alle Knoten in seinen Unterbäumen
    static void delRec(Node *node) {
      if (node != nullptr) {
        delRec(node->left);
        delRec(node->right);
        delete node;        // Knoten erst nach seinen Unterbäumen löschen!
      }
    }
};

// Ausgabe-Operator für den einzelnen Knoten nodeObj (*kein* Pointer):
// Gibt "wort: anzahl" aus
ostream &operator<<(ostream &outfile, const Node &nodeObj)
{
  outfile << nodeObj.word << ": " << nodeObj.cnt;
  return outfile;
}

// Ausgabe-Operator für den (Teil-) Baum mit Wurzel node:
// Zeilenweise, sortierte Ausgabe des gesamten Baumes
ostream &operator<<(ostream &outfile, const Node *node)
{
  if (node != nullptr) {  // bei nullptr: Nicht zugreifen, nichts ausgeben!
    // Ausgabe in sortierter Reihenfolge:
    // Zuerst rekursiv den linken Unterbaum
    outfile << node->left;
    // ... dann die Wurzel unseres Teilbaumes (Achtung: Nicht den Pointer!) ...
    outfile << *node << endl;
    // ... und dann rekursiv den rechten Unterbaum
    outfile << node->right;
  }
  return outfile;
}

// Ausgabe-Operator für ein Tree-Objekt
ostream &operator<<(ostream &outfile, const Tree &tree)
{
  // Ausgabe für die Wurzel aufrufen
  outfile << tree.root;
  return outfile;
}

// Hilfsfunktion für main:
// Lies ein Wort (= Folge von Buchstaben) und speichere es in str
// Returnwert true bei Erfolg, false bei Dateiende oder Fehler
bool getword(string &str)
{
  char c;

  str.clear();             // str auf leer setzen
  while (cin.get(c)) {     // zeichenweise lesen bis EOF oder Fehler
    if (isalpha(c)) {      // Das Zeichen c ist ein Buchstabe (a bis z, A bis Z)
      str += c;            // ==> hänge den Buchstaben an das Ergebnis-Wort an
    } else {               // c ist kein Buchstabe
      if (!str.empty()) {  // wir hatten davor schon Buchstaben
                           // ==> das aktuelle Zeichen ist das Ende des Wortes
        return true;       // bisher gelesenes Wort zurückgeben, Erfolg
      }
      // else: Gelesenes Zeichen ist Nicht-Buchstabe *vor* dem zu lesenden Wort
      // ==> Zeichen ignorieren, weiterlesen bis ein Buchstabe kommt
    }
  }
  // Hierher kommen wir nur bei EOF oder Fehler
  // Wenn davor schon Buchstaben gelesen wurden ==> Erfolg
  // Wenn das Ergebnis noch leer ist ==> Fehler
  return !str.empty();
}

int main()
{
  Tree tree;
  string str;

  // Worte lesen und zählen bzw. im Baum speichern, bis kein Wort mehr kommt
  while (getword(str)) {
    tree.count(str);
  }

  // Baum kopieren
  Tree tree2 = tree;
  
  // Alle Einträge des kopierten Baumes durchgehen:
  // Beginne mit dem kleinsten und gehe nach jeder Ausgabe zum nächstgrößeren,
  // bis es keinen nächsten mehr gibt (oder gleich am Anfang keinen kleinsten)
  for (Node *nodePtr = tree2.getFirst();
       nodePtr != nullptr;
       nodePtr = tree2.getNext(str)) {
    // zuerst den String für das nächste getNext merken,
    // denn nach dem remove wäre der String auch weg!
    str = nodePtr->getWord();
    // entferne alle Einträge mit count == 1
    if (nodePtr->getCnt() == 1) {
      int cnt = tree2.remove(str);
      if (cnt != 1) {
        // Der gelöschte Knoten muss Zählerstand 1 gehabt haben,
        // sonst stimmt irgendetwas nicht!
        cout << "Remove von " << str << " ging schief: " << cnt << endl;
      }
    }
  }

  // Beide Bäume ausgeben
  cout << tree << endl << tree2 << endl;
  
  return 0;
}