// Übung zu Bäumen: Worte zählen (Version mit STL map)
//
// Aufruf: baum-map
//
// Klaus Kusche, 2018

#include <iostream>
#include <string>
// für isalpha
#include <cctype>
// für das map-Template
#include <map>

using namespace std;

// Grundsätzlich:
// Eine Map speichert Paare von Schlüsselwert + Nutzdaten:
// * Der Schlüsselwert ist das, nach dem gesucht und sortiert wird
//   (bei uns: Das Wort)
// * Zu jedem Schlüsselwert gehören Nutzdaten
//   (bei uns: Die Anzahl der Vorkommen dieses Wortes)
// Intern wird eine map als Baum gespeichert
//
// Technisch:
// * Das map-Template hat zwei Typ-Parameter: map<T1, T2>
//   T1 ist der Typ der Schlüsselwerte
//   T2 ist der Typ der Nutzdaten zu den Schlüsselwerten
// * Ein einzelnes Element einer map<T1, T2>
//   hat den vordefinierten Typ pair<const T1, T2>,
//   d.h. ein map-Iterator zeigt auf ein solches pair
// * Auf die beiden Member eines pair kann man mit first und second zugreifen

// Ausgabe-Operator für ein einzelnes Element
// Gibt "wort: anzahl" aus
template <typename T1, typename T2>
ostream &operator<<(ostream &outfile, const pair<const T1, T2> &p)
{
  outfile << p.first << ": " << p.second;
  return outfile;
}

// Ausgabe-Operator für eine ganze map
template <typename T1, typename T2>
ostream &operator<<(ostream &outfile, const map<T1, T2> &m)
{
  // Alte Schleifen-Variante:
  // it ist ein Iterator, der die map durchläuft
  //for (auto it = m.begin(); it != m.end(); ++it) {
  //  outfile << *it << endl; // gibt den Knoten aus, auf den der Iterator zeigt
  //}
  // Neue Schleifen-Variante:
  // i ist eine Referenz,
  // die der Reihe nach mit den einzelnen Baum-Elementen belegt wird
  // (d.h. mit dem Wert selbst, einem pair, keinem Pointer darauf!)
  for (auto &i : m) {
    outfile << i << endl;
  }
  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()
{
  map<string, int> tree;
  string str;

  // Worte lesen und zählen bzw. in der map speichern, bis kein Wort mehr kommt
  while (getword(str)) {
    // Händische, umständliche Variante:
    // it ist ein Iterator
    // sein Typ wird automatisch durch die Initialisierung festgelegt
    // Suche den String in der map
    auto it = tree.find(str);

    if (it == tree.end()) {
      // nicht gefunden ==> neues Paar erzeugen und einfügen
      // "pair<string,int>(str, 1)" ist ein Konstruktor-Aufruf
      // zur Erzeugung eines temporären pair-Objektes
      // (nicht dynamisch angelegt)
      tree.insert(pair<string,int>(str, 1));
    } else {
      // gefunden (it zeigt darauf) ==> Zähler erhöhen
      ++(it->second);
    }
    
    // Verbesserte Variante mit operator[]:
    // 1.) [] liefert bei einer map zu einem Schlüsselwert (bei uns: Wort)
    //     die dazugehörigen Nutzdaten (bei uns: Anzahl),
    //     und zwar als Referenz auf die Original-Nutzdaten in der map
    //     (d.h. wenn wir das Ergebnis von [] ändern,
    //     ändern wir die Daten in der map)
    // 2.) Ein noch nicht existierender Schlüsselwert in den [] bewirkt, 
    //     dass ein neues Element angelegt und in die map eingefügt wird!
    // 3.) Wenn [] ein neues Element anlegt und einfügt,
    //     und der Nutzdaten-Teil ist ein int,
    //     dann wird dieser automatisch auf 0 gesetzt.
    // ==> Egal, ob das Element alt oder neu ist,
    //     wir können in beiden Fällen einfach 1 dazuzählen!
    //++(tree[str]);
  }

  // map kopieren
  map<string, int> tree2 = tree;
  
  // Alle Einträge der kopierten map durchgehen (wieder mit Iterator)
  for (auto it = tree2.begin(); it != tree2.end(); ) {
    // Iterator merken und *vor* dem Löschen weiterzählen
    // (denn nach dem Löschen des Elementes ist der Iterator ja ungültig
    // bzw. zeigt ins Leere, und man könnte ihn nicht mehr weiterzählen)
    auto tmp = it;
    ++it;
    // entferne alle Einträge mit Nutzdaten == 1
    if (tmp->second == 1) {
      tree2.erase(tmp);
    }
  }

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