/*
	Radix tree library for storing text strings
*/

#include <stdio.h>
#include "radix.h"


static int do_insert();
static void do_dump();

#ifdef COMPRESSOR
static int do_compress();
static int next_code = 1;
#endif

/* Returns -1 on failure, and 0 on success (as an analyser) or the code */
/* assigned (as a compressor) */

int
r_insert(root, key)
struct r_node **root;
unsigned char *key;
{
	if(!key || !*key) {
		return -1; /* Failure */
	}
	return do_insert(root, key);
}

#ifndef COMPRESSOR
void
r_dump(root)
struct r_node *root;
{
	unsigned char buffer[4096];

	do_dump(root, buffer, 0);
}
#endif

#ifdef COMPRESSOR
int
r_compress(root, string)
struct r_node *root;
unsigned char **string;
{
	return do_compress(root, string);
}
#endif


static int
do_insert(curr, key)
struct r_node **curr;
unsigned char *key;
{
	int hi, lo, mid;


	if(!*key) {
		return 0; /* end of string, we're done */
	}

	/* Find the character 'key' points at in the current node */
	/* adding it in if necessary */

	/* Empty nodes are always allocated with room for one letter */
	if((*curr)->count == 0) {
		(**curr).letter[0].c = *key;
		(**curr).letter[0].child = NULL;
#ifdef COMPRESSOR
		(**curr).letter[0].code = 0;
#else
		(**curr).letter[0].count = 0;
#endif
		mid = 0;
		(*curr)->count = 1;
	} else {
		lo = 0;
		hi = (*curr)->count - 1;
		while(hi >= lo) {
			mid = ((hi - lo) >> 1) + lo;
			if((**curr).letter[mid].c == *key) {
				break;
			} else if((**curr).letter[mid].c < *key) {
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
		if(hi < lo) { /* We failed to find it, insert */
			struct r_node *tmp;

			tmp = (struct r_node *) realloc(*curr,
				sizeof(struct r_node) +
				(sizeof(struct r_letter) * (*curr)->count));
			if(!tmp) {
				return -1; /* Failure */
			}
			*curr = tmp;
			(*curr)->count += 1;
			if(lo + 1 < (*curr)->count) {
				bcopy(&((*curr)->letter[lo]),
					&((*curr)->letter[lo+1]),
					((*curr)->count - (lo + 1)) *
						sizeof(struct r_letter));
			}
			(*curr)->letter[lo].c = *key;
			(*curr)->letter[lo].child = NULL;
#ifdef COMPRESSOR
			(*curr)->letter[lo].code = 0;
#else
			(*curr)->letter[lo].count = 0;
#endif
			mid = lo;
		} else  {
		}
	}

	/* If we get here, mid is the index of the right character, so */
	/* update it and recurse as needed */

#ifndef COMPRESSOR
	(*curr)->letter[mid].count += 1;
#endif

	if(key[1] == '\0') {
#ifdef COMPRESSOR
		(*curr)->letter[mid].code = next_code;
		return next_code++; /* success */
#else
		return 0;
#endif
	}

	/* We have more string to go, so carry on */
	if((*curr)->letter[mid].child == NULL) {
		struct r_node *tmp;

		tmp = (struct r_node *) malloc(sizeof(struct r_node));
		if(!tmp) {
			return -1;
		}
		tmp->count = 0;
		(*curr)->letter[mid].child = tmp;
	}

	return do_insert(&((*curr)->letter[mid].child), key + 1);
}


#ifdef COMPRESSOR
static int
do_compress(curr, str)
struct r_node *curr;
unsigned char **str;
{
	int hi, lo, mid, code;

	if(!*str) {
		return 0; /* end of string, we're done */
	}

	/* Find the character 'key' points at in the current node */
	/* adding it in if necessary */

	if(curr == NULL || curr->count == 0) {
		/* Can't code the next letter, return 0 */
		return 0;
	}
	lo = 0;
	hi = curr->count - 1;
	while(hi >= lo) {
		mid = ((hi - lo) >> 1) + lo;
		if(curr->letter[mid].c == **str) {
			/* See if we can go further */

			(*str)++;
			code = do_compress(curr->letter[mid].child, str);
			if(code == 0) {
				if(curr->letter[mid].code){
					return curr->letter[mid].code;
				} else {
					(*str)--;
					return 0;
				}
			} else {
				return code;
			}
		} else if(curr->letter[mid].c < **str) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}

	/* Failed to code this letter, return 0 */

	return 0;
}
#endif

#ifndef COMPRESSOR
static void
do_dump(curr, buff, depth)
struct r_node *curr;
unsigned char *buff;
int depth;
{
	int	i;

	if(!curr)
		return;

	for(i = 0; i < curr->count; i++) {
		/* Emit the current string */
		buff[depth] = curr->letter[i].c;
		buff[depth + 1] = '\0';
#ifdef COMPRESSOR
		printf("%d '%s'\n", curr->letter[i].code, buff);
#else
		printf("%d '%s'\n", curr->letter[i].count, buff);
#endif

		/* Recurse to handle all extensions of this string too */

		do_dump(curr->letter[i].child, buff, depth + 1);
	}
}
#endif