/*	wortstat.c -- Programm unter GPL, (c) RTC @ 2003			*/
/*	Programm zählt die Wörter in einem Text und sortiert sie in einem	*/
/*	binären Baum ein, welchen es dann ausgibt				*/
/*	Programm sollte mit "wortstat < textdatei" gestartet werden		*/


/* ---- Präprozessor-Direktiven -----------------------------------------------	*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_ZEICH 1000


/* ---- Struktur eines Knotens des binären Baumes deklarieren -----------------	*/
typedef struct bin_knoten{
	char *wort;
	int anzahl;
	struct bin_knoten *links;
	struct bin_knoten *rechts;
} BAUM_KNOTEN;

/* ---- Funktions-Prototypen --------------------------------------------------	*/
BAUM_KNOTEN *einordnen(char *wort, BAUM_KNOTEN *knoten);
void freigeben(BAUM_KNOTEN *knoten);
void ausgeben(BAUM_KNOTEN *knoten);
char *lower_wort(char *wort);


/* ---- main() ----------------------------------------------------------------	*/
int main(void){
	BAUM_KNOTEN *wurzel=NULL;
	char *trennzeich=" @¤µ\"!^°<>|§$%&/()=?`'}][{+-*~#'_.:,;\r\n\t\\0123456789", zeile[MAX_ZEICH], *wort;
	
	/* die einzelnen Zeilen einlesen und den binären Baum bearbeiten */
	while(fgets(zeile, 1000, stdin) != NULL){
		zeile[strlen(zeile)-1]='\0';
		/* wenn kein erstes Wort in der Zeile gefunden oder nur ein Buchstabe, dann mit nächster Zeile fortfahren */
		wort=strtok(zeile, trennzeich);
		if(wort==NULL || strlen(wort)==1)
			continue;
		/* das jeweilige Wort im binären Baum einordnen */
		wurzel=einordnen(wort, wurzel);
		while((wort=strtok(NULL, trennzeich)) != NULL){
			if(strlen(wort)==1)
				continue;
			einordnen(wort, wurzel);
		}
	}
	
	/* den sortierten binären Baum ausgeben */
	printf( "%15sWortstatistik zu einem Text\n"
		"%15s===========================\n\n", "", "");
	ausgeben(wurzel);
	printf("\n");

	/* Speicherplatz wieder frei geben und Programm beenden */
	freigeben(wurzel);
	return 0;
}


/* ---- einordnen() - Funktion zum Einordnen eines Wortes im binären Baum -----	*/
BAUM_KNOTEN *einordnen(char *wort, BAUM_KNOTEN *knoten){
	/* wenn kein aktueller Knoten vorhanden, dann lege einen an */
	wort=lower_wort(wort);
	if(knoten==NULL){
		/* zunächst Speicherplatz für einen ganzen Knoten reservieren */
		if((knoten=malloc(sizeof(BAUM_KNOTEN))) == NULL){
			fprintf(stderr, "Speicherplatzmangel...\n");
			exit(1);
		}
		/* jetzt die einzelnen Knotenvariablen initialisieren */
		if((knoten->wort=malloc(strlen(wort)+1)) == NULL){
			fprintf(stderr, "Speicherplatzmangel...\n");
			exit(2);
		}
		strcpy(knoten->wort, wort);
		knoten->anzahl=1;
		knoten->links=NULL;
		knoten->rechts=NULL;
	}
	/* rechts einordnen */
	else if(strncmp(knoten->wort, wort, strlen(wort)+1) < 0)
		knoten->rechts=einordnen(wort, knoten->rechts);
	/* links einordnen */
	else if(strncmp(knoten->wort, wort, strlen(wort)+1) > 0)
		knoten->links=einordnen(wort, knoten->links);
	/* Zähler für aktuelles Wort erhöhen */
	else if(strncmp(knoten->wort, wort, strlen(wort)+1) == 0)
		knoten->anzahl++;
		
	return knoten;
}

/* ---- freigeben() - gibt den Speicher des binären Baumes frei ---------------	*/
void freigeben(BAUM_KNOTEN *knoten){
	if(knoten!=NULL){
		/* zunächst alle linksseitigen Knoten freigeben */
		freigeben(knoten->links);
		/* nun alle rechtsseitigen Knoten freigeben */
		freigeben(knoten->rechts);
		/* zum Schluss den aktuellen Knoten freigeben */
		free(knoten);
	}
}

/* ---- ausgeben() - gibt die Wörter aller Knoten und ihre Anzahl aus ---------	*/
void ausgeben(BAUM_KNOTEN *knoten){
	if(knoten!=NULL){
		/* gib alle linken, dann den aktuellen, dann alle rechten Knoten aus */
		ausgeben(knoten->links);
		printf("%-25s:%5d\n", knoten->wort, knoten->anzahl);
		ausgeben(knoten->rechts);
	}
}

/* ---- lower_wort() - wandelt das gesamte Wort in Kleinbuchstaben um ---------	*/
char *lower_wort(char *wort){
	int i;
	for(i=0; i<strlen(wort); ++i)
		wort[i]=tolower(wort[i]);

	return wort;
}