/******************************************************************************

	二分木を利用した単語の出現頻度カウントプログラム（出力が深さつきの版）

******************************************************************************/

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

struct tnode {
	char *word;						/* 単語 */
	int count;						/* カウント */
	struct tnode *left;				/* 左の子へのポインタ */
	struct tnode *right;			/* 右の子へのポインタ */
};

typedef struct tnode Tnode;

#define BUFSIZE 1024	/* バッファの大きさ */

char *freadword(FILE *in);
Tnode *Tnode_add(Tnode* tp, char *s);
Tnode *Tnode_construct(char *s);
void Tnode_printtree(Tnode* tp, int depth);
void Tnode_print(Tnode *p);

int main(int argc, char *argv[]) {
	FILE *in;
	char *s;
	Tnode *root = NULL;

	if (argc != 2) {
		fprintf(stderr, "引数の数が違います.\n");
		return 1;
	}
	in = fopen(argv[1], "rt");
	if (in == NULL) {
		fprintf(stderr, "ファイル \"%s\" を開けません.\n", argv[1]);
		return 1;
	}

	while ((s = freadword(in)) != NULL) {	/* 単語を読み込んでは */
		root = Tnode_add(root, s);			/* 木につけ加える */
	}
	Tnode_printtree(root, 0);				/* 木の印字 */

	return 0;
}

/* in から読み込んだ次の単語を大文字にして返す。（いわゆる）日本語は不可 */
char *freadword(FILE *in) {
	static char buf[BUFSIZE+1] = "";
	static char *bufp = buf;				/* 次の word の先頭候補 */
	char *p;

	while (1) {
		while (!isalpha(*bufp) && *bufp != '\0') {	/* 非欧字をスキップ */
			bufp++;
		}
		if (*bufp == '\0') {				/* 行末まで単語がなかった */
			bufp = buf;
			if (fgets(buf, BUFSIZE, in) == NULL) {
				return NULL;				/* 読み込めなかった場合 */
			}
			continue;
		}
		p = bufp;
		while (isalpha(*bufp)) {			/* 単語の終わりの次を探す */
			*bufp = toupper(*bufp); bufp++;
		}
		if (*bufp == '\0') {     			/* 不完全行の場合は \n がなくて */
			*(bufp+1) = '\0';				/* すぐ \0 がくるので別処理 */
		}
		*bufp++ = '\0';						/* ++ は次の呼び出しに備えて */
		return p;
	}
}


/* 木 p 以下に s を“加える”。p が NULL 以外のときの返り値は p 自身 */
Tnode *Tnode_add(Tnode *p, char *s) {
	int result;

	if (p == NULL) {
		return Tnode_construct(s);
	} else {
		result = strcmp(s, p->word);
		if (result < 0) {						/* 小さければ左の部分木へ */
			p->left = Tnode_add(p->left, s);
		} else if (result > 0) {				/* 大きければ右の部分木へ */
			p->right = Tnode_add(p->right, s);
		} else {								/* 一致すればカウントを増す */
			p->count++;
		}
		return p;
	}
}


/* s から Tnode を構成 */
Tnode *Tnode_construct(char *s) {
	Tnode *p;

	if ((p = malloc(sizeof(Tnode))) == NULL) {
		return NULL;
	}
	if ((p->word = malloc(strlen(s)+1)) == NULL) {
		free(p); return NULL;
	}
	strcpy(p->word, s);
	p->count = 1;
    p->left = p->right = NULL;
	return p;
}


/* 木 p を印字。深さつき */
void Tnode_printtree(Tnode *p, int depth) {
	if (p == NULL) {
		return;
	}
	Tnode_printtree(p->left, depth + 1);
	printf("%2d ", depth);
	Tnode_print(p);
	Tnode_printtree(p->right, depth + 1);
}


/* p の指す Tnode を印字 */
void Tnode_print(Tnode *p) {
	printf("%4d %s\n", p->count, p->word);
}