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

typedef struct _treeentry {
    char				*word;
    int					count;
    char				c;  //0=black, 1=red
    struct _treeentry	*wr;
    struct _treeentry	*wl;
    struct _treeentry   *cr;
    struct _treeentry   *cl;
} TreeEntry;


void        WTree_Add(TreeEntry*,char*);
void        WTree_Destroy(TreeEntry*);
TreeEntry*  WTree_Find(TreeEntry*,char*);
void        WTree_Examine(TreeEntry*);
TreeEntry*  Tree_NewEntry(char* word);
void        CTree_Add(TreeEntry*);

#define ISNULL(v)       (!v)
#define ISNOTNULL(v)    (v)

static TreeEntry    *WTree_Root=NULL;
static TreeEntry    *CTree_Root=NULL;
static int          CTree_Count=0;

void _CTree_Add(TreeEntry*,TreeEntry*);
void _CTree_Build(TreeEntry*);
void _CTree_Display(TreeEntry*);

void DB_Create(void) {
}

void DB_Add(char *word) {
	if (!WTree_Root) {
        WTree_Root = Tree_NewEntry(word);
        return;
    }

    WTree_Add(WTree_Root,word);
}

TreeEntry* Tree_NewEntry(char* word) {
    TreeEntry* pEntry = (TreeEntry*)malloc(sizeof(TreeEntry));
    pEntry->word=word;
    pEntry->wl=NULL;
    pEntry->wr=NULL;
    pEntry->cl=NULL;
    pEntry->cr=NULL;
    pEntry->count=1;
    return pEntry;
}

void DB_Destroy(void) {
    if (!WTree_Root)
        return;
    WTree_Destroy(WTree_Root);
}

void WTree_Destroy(TreeEntry *root) {
    if (root->wr!=NULL)
        WTree_Destroy(root->wr);
    if (root->wl!=NULL)
        WTree_Destroy(root->wl);
    free(root);
}

TreeEntry* WTree_Find(TreeEntry *root,char* word) {
    if (!root)
        return NULL;
    int d = strcmp(word,root->word);
    if (d<0)
        return WTree_Find(root->wl,word);
    return WTree_Find(root->wr,word);
        
}

void CTree_Add(TreeEntry *newb) {
    if (ISNULL(CTree_Root)) {
        CTree_Root=newb;
        return;
    }

    _CTree_Add(CTree_Root,newb);
}

void _CTree_Add(TreeEntry *root,TreeEntry *node) {
    if (node->count < root->count) {
        if (ISNULL(root->cl)) {
            root->cl=node;
            return;
        }
        _CTree_Add(root->cl,node);
        return;
    }

    if (ISNULL(root->cr)) {
        root->cr=node;
        return;
    }

    _CTree_Add(root->cr,node);
}

void WTree_Add(TreeEntry *root,char* word) {
    int d = strcmp(word,root->word);
    if (d<0) {
        if (root->wl==NULL) {
            root->wl = Tree_NewEntry(word);
            return;
        }
        WTree_Add(root->wl,word);
        return;
    }

	if (d>0) {
		if (root->wr==NULL) {
			root->wr = Tree_NewEntry(word);
			return;
		}
		WTree_Add(root->wr,word);
		return;
	}

	root->count++;
}

void DB_DisplayResult(void) {
    _CTree_Build(WTree_Root);
    CTree_Count = 25;
    _CTree_Display(CTree_Root);
}

void _CTree_Display(TreeEntry* root) {
    if (ISNULL(root))
        return;
    _CTree_Display(root->cr);
    if (!CTree_Count)
        return;
    printf("%s    (%d)\n",root->word,root->count);
    if (--CTree_Count)
        _CTree_Display(root->cl);
}

void _CTree_Build(TreeEntry* root) {
    if (ISNULL(root))
        return;
    _CTree_Build(root->wl);
    CTree_Add(root);
    _CTree_Build(root->wr);
}