/***********************************************************************
 *               Copyright (C) 1995 Joe English
 *                   Freely redistributable
 ***********************************************************************
 *
 * ctrie.c,v 1.6 1998/11/10 01:44:01 jenglish Exp
 *
 * Author: 	Joe English
 * Created: 	12 Jan 1995
 * Description:	Character Trie implementation.
 *		CTries may be used as a general-purpose
 *		string->value map type, and for prefix matching.
 * Implementation:
 *		A CTrieNode represents a prefix of a string;
 *		all keys which share the same prefix are
 *		stored as children of the node; children
 *		are kept in a binary search tree.
 *		%%% Could also use balanced binary tree;
 *		%%% could also keep track of child density,
 *		%%% switch from tree to array if it gets too dense.
 *
 * 1998/11/10 01:44:01
 * 1.6
 * 
 */

#include <stdlib.h>

#include "project.h"
#include "ctrie.h"

struct CTrieNode
{
    CTrieNode	parent;		/* link to parent node */
    CTrieNode	children;	/* top of child search tree */
    CTrieNode	left;		/* left node of sibling search tree */
    CTrieNode	right;		/* right node of sibling search tree */
    void	*value;		/* value ptr. */
    char	ch;		/* character at this node */
    unsigned	hasval;		/* flag: 1 if value is set for this node */
};

struct CTrie
{
    CTrieNode	epsilon;	/* key of empty string */
    /* Others? */
};

/*
 * CTrieNode allocator:
 * Just use malloc/free; nodes are not often freed.
 *
 * Hmm... per-trie freelist, linked by 'left' pointer,
 * store list of chunks 'right' pointer,
 * free all chunks when trie is destroyed?
 */

static CTrieNode ctnalloc(void)
{
    return (CTrieNode)malloc(sizeof(struct CTrieNode));
}

static void ctnfree(CTrieNode n)
{
    STOMPON(n->parent)
    STOMPON(n->children)
    STOMPON(n->left)
    STOMPON(n->right)
    STOMPON(n->value)

    free(n);
}

static CTrieNode ctncreate(CTrieNode parent, char ch)
{
    CTrieNode ctn = ctnalloc();

    ctn->parent	= parent;
    ctn->ch = ch;
    ctn->left = ctn->right = ctn->children = 0;
    ctn->value = 0;
    ctn->hasval = 0;

    return ctn;
}

/*+++ Prefix matching routines:
 * findch : find child node with given char
 * lookupch : find child node with given char, insert if it does not exist.
 */

CTrieNode ctrie_findch(CTrieNode ctn, char ch)
{
    ctn = ctn->children;
    while (ctn && ctn->ch != ch)
    {
	if (ctn->ch < ch)
	    ctn = ctn->left;
	else
	    ctn = ctn->right;
    }
    return ctn;
}

CTrieNode ctrie_lookupch(CTrieNode ctn, char ch)
{
    CTrieNode p = ctn->children;

    if (!p)
    { /* first child */
	ctn->children = p = ctncreate(ctn, ch);
	return p;
    }

    while (p->ch != ch)
    {
	if (p->ch < ch)
	{
	    if (p->left)
		p = p->left;
	    else
		return p->left = ctncreate(ctn,ch);
	}
	else
	{
	    if (p->right)
		p = p->right;
	    else
		return p->right = ctncreate(ctn,ch);
	}
    }
    return p;
}

/*+++ Get and set values for a node:
 */

void *ctrie_getvalue(CTrieNode ctn)
{
    return ctn->value;
}

void ctrie_setvalue(CTrieNode ctn, void *val)
{
    ctn->value = val;
    ctn->hasval = 1;
}

int ctrie_hasvalue(CTrieNode ctn)
{
    return ctn->hasval;
}

/*+++ Retrieve key from a node:
 */
int ctrie_keylen(CTrieNode ctn)
{
    int len = 1;

    while (ctn->parent)
    {
	ctn = ctn->parent;
	++len;
    }
    /* ASSERT: ctn->parent == NULL ==> ctn is epsilon node. */
    /* %%% Check this, it's off by one */

    return len;
}

int ctrie_getkey(CTrieNode ctn, char *buf, int buflen)
{
    int i = ctrie_keylen(ctn) + 1;

    if (i > buflen)
	return 0;
    buf[i--] = '\0';
    while (ctn->parent)
    {
	buf[i--] = ctn->ch;
	ctn = ctn->parent;
    }
    ASSERT(i==0, "Oops! Miscounted.");
    return 1;
}

CTrie ctrie_create (void)
{
    CTrie ct = malloc(sizeof(*ct));
    ct->epsilon = ctncreate(0,0);

    return ct;
}

/* %%% Need value destructors. */
static void ctndestroy(CTrieNode ctn)
{
    CTrieNode childptr = ctn->children;

    /* destroy all children: */
    while (childptr)
    {
	CTrieNode tmp;
	/* Rotate and flatten: */
	while (childptr->left)
	{
	    tmp = childptr->left;
	    childptr->left = tmp->right;
	    tmp->right = childptr;
	    childptr = tmp;
	}
	tmp = childptr;
	childptr = childptr->right;
	ctndestroy(tmp);
    }

    ctnfree(ctn);
}

void ctrie_destroy(CTrie ct)
{
    ctndestroy(ct->epsilon);
    ct->epsilon = 0;
    free(ct);
}

/*
 * Inquiry and lookup:
 */
CTrieNode ctrie_root(CTrie ct)
{
    return ct->epsilon;
}

CTrieNode ctrie_find(CTrie ct, const char *key)
{
    CTrieNode ctn = ct->epsilon;
    while (ctn && *key)
	ctn = ctrie_findch(ctn, *key++);
    return ctn;
}

CTrieNode ctrie_lookup(CTrie ct, const char *key)
{
    CTrieNode ctn = ct->epsilon;
    while (*key) {
	ctn = ctrie_lookupch(ctn, *key++);
	ASSERT(ctn, "ctrie_lookupch must return new node");
    }
    return ctn;
}

int ctrie_haskey(CTrie ct, const char *key)
{
    CTrieNode ctn = ctrie_find(ct, key);
    return ctn && ctn->hasval;
}

void *ctrie_get(CTrie ct, const char *key)
{
    CTrieNode ctn = ctrie_find(ct, key);
    if (!ctn)
	return 0;
    ASSERT(ctn->hasval || ctn->value == 0, "Internal inconsistency.");
    return ctn->value;
}

void *ctrie_unset(CTrie ct, const char *key)
{
    void *oldval;

    CTrieNode ctn = ctrie_find(ct, key);
    if (!ctn)
	return 0;
    oldval = ctn->value;
    ctn->value = 0;
    return oldval;
}

void ctrie_set(CTrie ct, const char *key, void *value)
{
    CTrieNode ctn = ctrie_lookup(ct, key);
    ASSERT(ctn, "ctrie_lookup must always return something")
    ctrie_setvalue(ctn, value);
}

/*
 * Iterator:
 */
static void ctrie_traverse(CTrieNode ctn, CTrieNodeProc p, void *closure)
{
    if (!ctn) return;
    if (ctn->hasval)
	(*p)(ctn,closure);
    ctrie_traverse(ctn->left, p, closure);
    ctrie_traverse(ctn->right, p, closure);
    ctrie_traverse(ctn->children, p, closure);
}

void ctrie_foreach(CTrie ct, CTrieNodeProc p, void *closure)
{
    ctrie_traverse(ct->epsilon,p,closure);
}