#include <stdlib.h>
#include <limits.h>
#include <assert.h>

#include "radix256_tree.h"

static int byte_value(char c) {
    return c - CHAR_MIN;
}

struct radix256_tree {
    union {
	int is_key;
	struct radix256_tree * stack_link;
    };
    struct radix256_tree * next[256];
};

struct radix256_tree * radix256_tree_new () {		/* constructor */
    return calloc(1, sizeof(struct radix256_tree));
}

void radix256_tree_delete (struct radix256_tree * t) {
    assert(t);
    struct radix256_tree * stack = 0;
    for (;;) {
	for (int i = 0; i < 256; ++i) {
	    if (t->next[i]) {
		t->next[i]->stack_link = stack; /* push */
		stack = t->next[i];
	    }
	}
	free(t);
			
	if (!stack)
	    return;

	t = stack;		/* pop */
	stack = t->stack_link;
    }
}

/* insert the string defined by begin and end in tree t */
int radix256_tree_add (struct radix256_tree * t,
		       const char * begin, const char * end) {
    assert(t);
    for (; begin != end; ++begin) {
	unsigned int c = byte_value(*begin);
	if (t->next[c])
	    t = t->next[c];
	else {
	    struct radix256_tree * new_branch = radix256_tree_new();
	    if (!new_branch)
		return 0;
	    struct radix256_tree * bt = new_branch;
	    while (++begin != end) {
		unsigned int bc = byte_value(*begin);
		bt->next[bc] = radix256_tree_new();
		if (!bt->next[bc]) {
		    radix256_tree_delete(new_branch);
		    return 0;
		}
		bt = bt->next[bc];
	    }
	    bt->is_key = 1;
	    t->next[c] = new_branch;
	    return 1;
	}
    }
    t->is_key = 1;
    return 1;
}

/* return true iff the string defined by begin and end is in tree t */
int radix256_tree_find (struct radix256_tree * t,
			const char * begin, const char * end) {
    assert(t);
    for (; begin != end; ++begin) {
	t = t->next[byte_value(*begin)];
	if (!t)
	    return 0;
    }
    return t->is_key;
}