#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <libgen.h>
#include <glib.h>
#include <time.h>
#include "radix_tree.h"

/*
Usage:
radix_benchmark <words_list>

Compile with:
gcc -Wall -o radix_benchmark -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include radix_tree.c radix_benchmark.c -lglib-2.0 -lrt

20k english words:
http://www.puzzlers.org/pub/wordlists/pocket.txt
*/

static long start_time;

static gint sort_random(gconstpointer a, gconstpointer b) {
    return rand() - RAND_MAX / 2;
}

static void tree_insert(gpointer data, gpointer user_data) {
    RadixTree *tree = (RadixTree *) user_data;
    radix_tree_insert(tree, (char *) data, strdup((char *) data));
}

static void tree_lookup(gpointer data, gpointer user_data) {
    RadixTree *tree = (RadixTree *) user_data;
    char *value = (char *) radix_tree_lookup(tree, (char *) data);   
    if (!value)
        printf("[tree] Can't find key: %s\n", (char *) data);
    else if (strcmp(value, (char *) data))
        printf("[tree] Error: key '%s' has wrong value: '%s'\n", (char *) data, value);
}

static void tree_remove(gpointer data, gpointer user_data) {
    RadixTree *tree = (RadixTree *) user_data;
    radix_tree_remove(tree, (char *) data);
}

static void table_insert(gpointer data, gpointer user_data) {
    GHashTable * table = (GHashTable *) user_data;
    g_hash_table_insert(table, strdup((char *) data), strdup((char *) data));
}

static void table_lookup(gpointer data, gpointer user_data) {
    GHashTable * table = (GHashTable *) user_data;
    char *value = (char *) g_hash_table_lookup(table, (char *) data);
    if (!value)
        printf("[table] Can't find key: %s\n", (char *) data);
    else if (strcmp(value, (char *) data))
        printf("[table] Error: key '%s' has wrong value: '%s'\n", (char *) data, value);
}

static void table_remove(gpointer data, gpointer user_data) {
    GHashTable * table = (GHashTable *) user_data;
    g_hash_table_remove(table, (char *) data);
}

long time_ms(clockid_t clock) {
    struct timespec t;
    clock_gettime(clock, &t);
    return t.tv_sec * 1000LL + t.tv_nsec / 1000000LL;
}

void timing(const char *action) {
    if (action) {
        printf("%s in %ldms\n", action, time_ms(CLOCK_MONOTONIC) - start_time);
    }
    start_time = time_ms(CLOCK_MONOTONIC);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s <words_file> \n", basename(argv[0]));
        return 1;
    }

    GList *words = NULL;
    char line[512];
    FILE *fp = fopen(argv[1], "r");
    while (fgets(line, 512, fp)) {
        int len = strlen(line);
        if (line[len - 1] == '\n')
            line[len - 1] = '\0';
        words = g_list_append(words, strdup(line));
    }
    fclose(fp);
    printf("Read %d words from %s\n", g_list_length(words), argv[1]);

    RadixTree *tree = radix_tree_new(free);
    GHashTable *table = g_hash_table_new_full(g_str_hash, g_str_equal, free, free);

    words = g_list_sort(words, sort_random);
    timing(NULL);
    g_list_foreach(words, tree_insert, tree);
    timing("Inserted words into the radix tree");
    g_list_foreach(words, table_insert, table);
    timing("Inserted words into the hash table");

    //radix_tree_dump(tree, 1);

    words = g_list_sort(words, sort_random);
    timing(NULL);
    g_list_foreach(words, tree_lookup, tree);
    timing("Looked up all words from the radix tree");
    g_list_foreach(words, table_lookup, table);
    timing("Looked up all words from the hash table");

    words = g_list_sort(words, sort_random);
    timing(NULL);
    g_list_foreach(words, tree_remove, tree);
    timing("Removed all words from the radix tree");
    g_list_foreach(words, table_remove, table);
    timing("Removed all words from the hash table");

    //radix_tree_dump(tree, 1);

    radix_tree_destroy(tree);
    g_hash_table_destroy(table);

    return 0;
}