/**
 *  Ternary Search Tree (TST) ANSI C implementation
 *  Copyright (C) 2010 Matous Jan Fialka, <http://mjf.cz/>
 *  Released under the terms of The MIT License
 */

#include <stdlib.h>

#ifndef NULL
#define NULL ((void *)0)
#endif

#define nil NULL

typedef struct tstnode tstnode;

struct tstnode {
	char key;
	tstnode *left;
	tstnode *middle;
	tstnode *right;
	void *value;
};

tstnode *
tst_create_node(char key)
{
	tstnode *node;

	node = (tstnode *) malloc(sizeof(tstnode));
	if(node) {
		node->key = key;
		node->left = nil;
		node->middle = nil;
		node->right = nil;
		node->value = nil;
	}
	return node;
}

void
tst_insert(tstnode ** node, char *string, void *value)
{
	int comparison;
	tstnode *current;

	while((current = *node)) {
		comparison = *string - current->key;
		if(!comparison) {
			if(!*string++) {
				return;
			}
			node = &(current->middle);
		} else {
			if(comparison < 0) {
				node = &(current->left);
			} else {
				node = &(current->right);
			}
		}
	}
	while(1) {
		current = *node = tst_create_node(*string);
		if(!*string++) {
			current->middle = (tstnode *) value;
			return;
		}
		node = &(current->middle);
	}
	return;
}

tstnode *
tst_search(tstnode * node, char *string)
{
	int comparison;

	while(node) {
		comparison = *string - node->key;
		if(comparison < 0) {
			node = node->left;
		} else {
			if(!comparison) {
				if(!*string++) {
					return (tstnode *) node->middle;
				}
				node = node->middle;
			} else {
				node = node->right;
			}
		}
	}
	return nil;
}