/* Beispiel-Programm zu binaeren Wurzel-Baeumen                            *
 *                                                                         *
 * C-Praktikum Matthias Gross, Fachhochschule Koeln                        *
 *                                                                         *
 * Das Programm CountWords zaehlt die in einem Text vorkommenden Woerter   *
 * und gibt das Ergebnis in alphabetischer Reihenfolge auf der Standard-   *
 * Ausgabe oder einem File aus                                             *
 *                                                                         *
 * Aufruf ueber: CountWor InFile [OutFile]                                 *
 *                                                                         *
 * ACHTUNG: Dieser C-Source stellt nur einige Beispiele zusammen und       *
 *          ist noch kein ausgereiftes Programm!!                          *
 *          Kommentare sind waehrend der Besprechung zu ergaenzen!!        */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MaxWordLen 100         /* Maximale verarbeitbare Wortlaenge        */

/* Unterschiedliche Typ-Definitionen fuer Knoten des Baumes und den Inhalt */

typedef
  struct STree_Node {
    void *Inhalt;
    STree_Node *Left;
    STree_Node *Right;
  } *Tree_Node;        /* Definition als Pointer */

typedef
  struct {
    int   Anz;
    char *Text;
  } WordAnz;             /* Definition als Struktur */
/*--- Globale Variablen ----------------------------------------------------*/

  FILE *InFile;          /* Input- und Output-File  */
  FILE *OutFile;

/*--- Funktionsprototypen --------------------------------------------------*/

int main(int argc, char *argv[]);/* Hauptprogramm */

int getword(FILE *stream, char *word, int limit);
                                 /* "parst" ein Wort */

void DoWithAll(Tree_Node p, void (*OFunc)(void *));
                               /* Fuehrt OFunc mit allen Knoten von p durch */

/*.....*/

/*--- Routinen zum Erzeugung von neuen Elementen ---------------------------*/

Tree_Node InitNewTree_Node(void)
{
  Tree_Node p;

  p = (Tree_Node) malloc(sizeof(STree_Node));
  if (p != NULL) {
    p->Inhalt = NULL;  /* Wurzel initialisieren */
    p->Left   = p->Right = NULL;
  }
  return p;
}

WordAnz *InitNewInhalt(char *Word)
{
  WordAnz *p;

  p = (WordAnz *) malloc(sizeof(WordAnz));
  if (p != NULL) {
    p->Anz  = 1;  /* Initialisieren */
    p->Text = (char *) malloc(strlen(Word)+1);
    if (p->Text != NULL)
      strcpy(p->Text, Word);
  }
  return p;
}

/*--- Beispiel Output von allen Knoten -------------------------------------*/

void OutputInhalt(WordAnz *Inhalt) /* Gibt Inhalt einmal aus. */
{
  fprintf(OutFile, "%6d mal %s\n", Inhalt->Anz, Inhalt->Text);
}

/*--- Routinen zur Baumbearbeitung (binaer, symmetrisch)--------------------*/

void DoWithAll(Tree_Node p, void (*OFunc)(void *))
{
  if (p != NULL) {
    DoWithAll(p->Left, OFunc);
    (*OFunc)(p->Inhalt);
    DoWithAll(p->Right, OFunc);
  }
}

Tree_Node addtree(Tree_Node p, char *Buffer) {

  int cond;

  if (p == NULL) {
    p = InitNewTree_Node();
    p->Inhalt = (void *) InitNewInhalt(Buffer);
  } else if ((cond=strcmp(Buffer, ((WordAnz *) p->Inhalt)->Text)) == 0)
    ((WordAnz *) p->Inhalt)->Anz++;
  else if (cond<0)
    p->Left = addtree(p->Left, Buffer);
  else
    p->Right= addtree(p->Right, Buffer);

  return p;
}

/*--- Sonstige Hilfsroutinen -----------------------------------------------*/

int getword(FILE *stream, char *word, int limit)

/* Routine liest ein "Wort" aus dem uebergebenen stream ein und gibt dieses
   nach word aus. Als Separator gelten zwischen 2 Woertern gelten alle
   nicht alphabetischen Zeichen.

   Input:  stream : Datenstrom, aus dem gelesen wird
           word   : Pointer auf den zurueckzugebenden String (Size limit+1)
           limit  : Maximale Anzahl an Zeichen, die word aufnehmen kann

   Output: getword: EOF oder erstes Zeichen von word
           word   : Eingelesenes neues Wort

   Vorsicht! Die Routine verwendet ungetc()
*/
{
  char *w = word;  /* Lokale Kopie des bergebenen Pointers anlegen */
  int   c;         /* Neues Zeichen                                 */

  while (isspace(c=getc(stream)))   /* Leerzeichen berlesen        */
    ;
  if (c != EOF)
    *w++ = c;                       /* EOF abspeichern              */
  if (!isalpha(c))                  /* Zeichen kein Wort-Beginn     */
     {
    *w = '\0';                      /* Falls EOF-> EOF\0 zurueck, sonst \0 */
    return c;
  }
  for ( ; --limit>0; w++)           /* Maximal limit Zeichen einlesen */
    if (!isalnum(*w=getc(stream)))  /* Alle alphanumerischen Zeichen einlesen */
    {
      ungetc(*w, stream);           /* Letztes Zeichen zurckstellen  */
      break;
    }
  *w = '\0';                        /* \0 Abschluss eintragen         */

  return word[0];
}

/*--- Hauptprogramm --------------------------------------------------------*/

int main(int argc, char *argv[]) /* Kopf mit Kommandozeilen-Auswertung       */
{
  Tree_Node CountTree = NULL;    /* Baum zur Aufnahme des Textes in Wortform */

  char word[MaxWordLen];         /* Zwischenspeicher beim Einlesen           */

/*-- Eingabe-Parameter verarbeiten -----------------------------------------*/

  if (argc<2 || argc>3) {        /* Gueltige Anzahl an Parametern ueberpruefen */
    printf("Falscher Aufruf!\n\n"
           "Programm starten mit COUNTWOR InFile [OutFile]\n\n");
    return 1;                    /* FehlerCode != 0 zurueckgeben an DOS      */
  }

  if ((InFile=fopen(argv[1], "r"))==NULL) {
    printf("Input-File-Name %s ist ungueltig oder die Datei laesst "
           "sich nicht oeffnen\n\n", argv[1]);
    return 2;                    /* Weiteren Fehlercode zurcklifern         */
  }
  if (argc == 2)                 /* Falls keine Angabe erfolgt, Ausgabe ber */
    OutFile = stdout;            /* StdOut abwickeln                         */
  else
    if ((OutFile=fopen(argv[2], "r"))==NULL) {
      printf("Output-File-Name %s ist ungueltig oder die Datei laesst "
             "sich nicht oeffnen\n\n", argv[2]);
      return 3;
    }

/*-- Eigentliches Hauptprogramm --------------------------------------------*/

  while (getword(InFile, word, MaxWordLen) != EOF)
                                          /* Gesamtes Input-File bearbeiten */
    if (isalpha(word[0]))        /* Nur Woerter zaehlen */
    {
      CountTree = addtree(CountTree, word);
    }

  DoWithAll(CountTree, (void (*)(void *))OutputInhalt); /* Alle W”rter ausgeben */

  return 0;                      /* Programm fehlerfrei beendet */
}