/*******************************************************************************
*
* Project:      seft (search engine for text)
*
* File:         tst.c
*
* Author:       Owen de Kretser (oldk@cs.mu.oz.au)
*
* Organisation: Dept. of CS&SE, University of Melbourne
*
* Date:         April 1999
*
* Purpose:      ternary search tree functions
*
* Notes:        adapted from Bentley & Sedgewick
* 
*******************************************************************************/


/***** #includes **************************************************************/

#include "tst.h"
#include "util.h"


Tptr 
tst_insert(Tptr p, char *s, int index)
{   
    if (p == NULL) 
        {
        p = (Tptr) safe_malloc(sizeof(Tnode));
        p->splitchar = *s;
        p->lokid = p->eqkid = p->hikid = NULL;
        p->term_index = NOT_FOUND;
        }
    if (*s < p->splitchar)
        {
        p->lokid = tst_insert(p->lokid, s, index);
        }
    else if (*s == p->splitchar) 
        {
        if (*s == '\0')
            {
            p->term_index = index;
            }
        else
            {
            p->eqkid = tst_insert(p->eqkid, ++s, index);
            }
        } 
    else
        {
        p->hikid = tst_insert(p->hikid, s, index);
        }

    return (p);
}

void 
cleanup(Tptr p)
{   
    if (p) 
        {
		cleanup(p->lokid);
		if (p->splitchar) 
            {
            cleanup(p->eqkid);
            }
		cleanup(p->hikid);
		free(p);
        }
}

int 
tst_search(Tptr root,char *s)
{   
    Tptr p;
    p = root;
    while (p) 
        {
        if (*s < p->splitchar)
            {
            p = p->lokid;
            }
        else if (*s == p->splitchar)  
            {
            if (*s++ == 0)
                {
                return (p->term_index);
                }
            p = p->eqkid;
            } 
        else
            {
            p = p->hikid;
            }
        }

    return (NOT_FOUND);
}