/* titel: baum.c; Binaerbaum als Beispiel zu selbstreferentiellen Strukturen  */
#include <stdio.h>
#include <ctype.h>
#include <wctype.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
#define MAX_WORT      40
struct  node {
            char *wort;
            int  zahl;
            struct node *links;
            struct node *rechts;
};
typedef struct node knoten;

/* dcount zählt die paarweise verschiedenen Worte */
int dcount = 0;

/* lieswort liest aus einer Datei ein Wort der Laenge < lim in den Speicher,
   auf den s zeigt, und gibt 1 zurueck, falls es wirklich ein Wort gelesen hat,
   jedoch 0 im Fall zu grosser Wortlaenge oder am Dateiende. */

int lieswort_utf8(char *s, int lim) {
  /* static: Variablen bleiben nach Beendigung der Funktion bestehen */
  static int n=0;
  static wchar_t wline[2000], *wlp=wline;
  wchar_t w[lim], *wp = w;
  int max=lim-1;
  /* auf schon angefangener Zeile Wortanfang suchen */
  if (n>0) {
    while (*wlp && !iswalpha(*wlp)) wlp++;  /* naechsten Buchstaben suchen */
    if (!*wlp) n=0;                         /* Zeile zu Ende */
  }
  /* falls Zeile zu Ende: neue Zeile lesen und Wortanfang suchen */
  while (n==0) {
    char line[2000];
    if (!fgets(line,2000,stdin)) return 0;  /* Zeile lesen */
    n = mbstowcs(wline,line,2000);          /* Zeile konvertieren */
    wlp = wline;
    while (*wlp && !iswalpha(*wlp)) wlp++;  /* finde Wortanfang */
    if (!*wlp) n=0;                         /* Zeile zu Ende */
  }
  /* nun haben wir einen Wortanfang */
  while (iswalpha(*wlp) && max>0) {         /* Wort kopieren */
    *wp++=*wlp++; max--;
  }
  *wp = L'\0';                              /* Wortende markieren */
  if (max==0 || wcstombs(s,w,lim)==lim) {   /* nach UTF-8 konvertieren */
    printf("Error: Wort zu lang\n");
    return 0;
  }
  return 1;
}

/* suche  durchsucht den Baum auf das Vorkommen des Wortes w, traegt es
   gegebenenfalls lexikographisch richtig ein bzw. erhoeht dessen Zahl und
   gibt den Pointer auf seinen Knoten zurueck. Die c-Funktion strcmp
   (resp. strcoll) vergleicht zwei Zeichenketten lexikographisch mit
   Rueckgabe einer negativen Zahl, 0 oder einer positiven Zahl. */
knoten *suche(knoten *p, char *w) {
  int cond;
  if (p == NULL) {
    /* mit malloc Speicher für neuen Knoten reservieren. */
    p = (knoten *)malloc( sizeof( knoten ) ) ;
    p->wort = strdup(w);
    p->zahl = 1;
    p->links = p->rechts = NULL;
    dcount++;
  }
  else if ((cond = strcoll(w, p->wort)) == 0)
    p->zahl++;
  else if (cond < 0)
    p->links  = suche(p->links,  w);
  else p->rechts = suche(p->rechts, w);
  return p ;
}

/* inorder gibt den Unterbaum, auf den p zeigt, sortiert aus
   (rekursive Version!) */
void inorder(knoten *p) {
  if (p != NULL){
    inorder(p->links);
    printf("%4d %s\n", p->zahl, p->wort);
    inorder(p->rechts);
  }
}

/* main liest aus der Standard-Eingabe die Woerter und gibt sie lexikographisch
   sortiert mit Haeufigkeitsangabe auf die Standard-Ausgabe aus. */
int main() {
  knoten *baum=NULL;
  int  wcount=0;
  char wort[ MAX_WORT ];

  setlocale(LC_ALL, "de_DE.UTF-8");
  while ( lieswort_utf8( wort, MAX_WORT) ) {
    baum = suche( baum, wort );
    wcount++;
  }
  printf("%d Woerter gelesen, davon paarweise verschieden: %d\n", wcount, dcount);
  inorder( baum );
}