/*
* R-way-trie
* Word Frequency Statistics
* NOTE: to use  visualize， you need install graphviz before。
* qcliu 2015/06/10
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define R 255
#define TRUE 1
#define FALSE 0

static int node_num;

struct node* ROOT;

typedef struct node
{
    int num;//the node number, only for dot
    int value;//the ASCII
    int frequecy;
    char* s;//if it's a world, this is the world
    struct node* child[R];
}Node;

static void throwException(char* info)
{
    printf("%s\n", info);
    exit(0);
}

static Node* newNode(int value)
{
    node_num++;

    Node* node = (Node*)malloc(sizeof(Node));
    node->num = node_num;
    node->value = value;
    node->frequecy = 0;
    node->s = NULL;
    int i;
    for (i=0; i<R; i++)
      node->child[i] = NULL;

    return node;
}


static char* openFile(char** argv)
{
    FILE* cfd;
    char* data;
    int file_len;

    cfd = fopen(argv[1], "r");
    if (cfd == NULL)
      throwException("NoFileInput");

    fseek(cfd, 0L, SEEK_END);
    file_len = ftell(cfd);
    fseek(cfd, 0L, SEEK_SET);
    data = (char*)malloc(file_len+1);
    if (fread(data, sizeof(char), file_len, cfd) != file_len)
      throwException("freed error");

    data[file_len] = -1;

    fclose(cfd);

    return data;

}

static char* recursiveCreate(Node* curr, Node* next, char* start ,char* data)
{
    if (*data<65||*data>122||(*data>90&&*data<97))
    {
        //a~z, A~Z
        //find a world

        if (curr != ROOT)
        {//如果curr为ROOT，说明遇到了连续的非字母，所以不是单词，直接跳过。

            curr->frequecy+=1;
            if (curr->s == NULL)
            {
                int len = data-start;
                char* world = (char*)malloc(len+1);
                world[len] = '\0';
                memcpy(world, start, len);
                curr->s = world;
            }
        }

        data++;
        return data;
    }

    else
    {//如果孩子中缺少这个字母，则创建新节点。
        if (curr->child[*data] == NULL)
        {
            next = newNode(*data);
            curr->child[*data] = next;
        }
        else
        {
            next = curr->child[*data];
        }
    }

    curr = next;
    data++;

    return recursiveCreate(curr, next, start, data);

}


static void printNode(Node* node, FILE* fp)
{
    if (node->frequecy == 0)
      fprintf(fp, "node%d[label=\"%c\"];\n", node->num, node->value);
    else
      fprintf(fp, "node%d[label=\"%c\\n%s\\nfrequecy=%d\"];\n",
                  node->num, node->value, node->s, node->frequecy);

}

static void printEdge(Node* parent, Node* curr, FILE* fp)
{
    fprintf(fp, "node%d->node%d;\n", parent->num, curr->num);
}

static void DFS(Node* parent,Node* curr,  FILE* fp)
{
    if (curr == NULL)
      return;


    printNode(curr, fp);
    printEdge(parent, curr, fp);



    int i;
    for (i=0; i<R; i++)
    {
        DFS(curr, curr->child[i], fp);
    }
}

static void visualize(Node* ROOT)
{
    FILE* fp;

    fp = fopen("trie.dot", "a");
    fprintf(fp, "digraph{\n");

    fprintf(fp, "node%d[label=\"ROOT\"];\n", ROOT->num);

    int i;
    for (i=0; i<R; i++)
      DFS(ROOT, ROOT->child[i], fp);

    fprintf(fp, "}\n");

    fclose(fp);

    system("dot -Tsvg trie.dot -o trie.svg");
    system("rm trie.dot");
}

int main(int argc, char** argv)
{
    char* data = openFile(argv);

    //初始化ROOT
    ROOT = newNode(0);
    Node* curr = ROOT;
    Node* next = ROOT;

    while (*data != -1)
    {
        //every loop create a world, so it's always begin at ROOT

        curr = ROOT;
        data = recursiveCreate(curr, next, data, data);
    }

    //绘图
    visualize(ROOT);
}