#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tree.h"

char *sneed_strdup(char *s);
struct tnode *talloc(void);
int compare(char *w, struct tnode *p, int bar, int *found);

struct tnode *naddtree(struct tnode *p, char *w, int bar, int *found)
{
	int cond;

	if (p == NULL) {
		p = talloc();
		p->word = sneed_strdup(w);
		p->count = 1;
		p->match = *found;
		p->left = p->right = NULL;
	} else if ((cond = compare(w, p, bar, found)) == 0) {
		p->count++;
	} else if (cond < 0) {
		p->left = naddtree(p->left, w, bar, found);
	} else if (cond > 0) {
		p->right = naddtree(p->right, w, bar, found);
	}

	return p;
}

void ntreeprint(struct tnode *p)
{
	if (p != NULL) {
		ntreeprint(p->left);
		if (p->match)
			printf("%4d %s\n", p->count, p->word);
		ntreeprint(p->right);
	}
}

void treefree(struct tnode *p) {
	if (p != NULL) {
		treefree(p->left);
		treefree(p->right);
		free(p->word);
		free(p);
	}
}

struct tnode *talloc(void)
{
	return (struct tnode *) malloc(sizeof(struct tnode));
}

char *sneed_strdup(char *s)
{
	char *p;

	p = (char *) malloc(strlen(s) + 1);
	if (p != NULL)
		strcpy(p, s);

	return p;
}

int compare(char *w, struct tnode *p, int bar, int *found)
{
	int cond;

	if ((cond = strncmp(w, p->word, bar)) == 0)
		if ((cond = strcmp(w + bar, p->word + bar)) != 0)
			p->match = *found = YES;

	return cond;
}