/*
 * trie.c
 *
 * This program contains all the trie procedures/functions that may be
 * used in other programs.  The functions revolve arround the trie structure,
 * which is dynamically implemented.  Each struct has a character value,
 * an end flag, and an array pointing to other characters.  It can be used
 * to store lists and then search them selectively.
 *
 * CS 282 - Shamim
 * Craig Kelley - Feb 1995
 * revised - March 9, 1995
 */

#include "trie.h"

/* This procedure inserts characters from the *line into a trie, and it
 * creates nodes as it is necessary--
 * The end flag is raised on the last character, and newlines are thrown
 * out.
 */

extern void insert_trie(node_ptr trie, char *line) {

   while ((*line != '\n') && (*line != 0))  /* line terminated? */
      if (trie -> children[*line]) {	    /* does char exist already? */
	 trie = (trie -> children[*line]);
	 line++;
      }
      else {			/* we must create a new node */
	 (trie -> children[*line]) = new_node(*line); 
	 trie = (trie -> children[*line]);
	 line++;
      }
   (trie -> end) = 1;		            /* end reached, put up flag */
}

/* traverse_trie will go through the trie and search for *query
 * and when it finds it, it will return the pointer to the last character
 * of the search string.  Otherwise, it returns zero if it can't find
 * the query.
 */

static node_ptr traverse_trie(node_ptr trie, char *query) {

   while ((*query != '\n') && (*query != 0))   /* if not at end, search more */
      if (trie -> children[*query]) {       /* does the next letter exist? */
	 trie = (trie -> children[*query]);
	 query++;
      }
      else                                  /* no match for next character */
	 return (node_ptr) 0;               /* failed to find, return */
   return trie;
}

/* follow_trie will place the first occurance of the first line, starting at
 * the trie pointer, into the *line argument.  NOTE: it will place the
 * character in the starting point (trie -> value) at the beginning, so
 * if you do not desire this character be sure to skip the first letter.
 * It is guaranteed that *line will be null-terminated.
 */

static void follow_trie(node_ptr trie, char *line) {

   int i=0;

   *line = (trie -> value);	/* place current value at the end of line */
   line++;                      /* increment our pointer in line */
   if(trie -> end) 		/* if were at the end */
      *line = 0;		/* terminate the line*/

   else				/* if we're not at the end, find children */
      while(++i <= NCHARS)
	 if (trie -> children[i]) {
	    follow_trie((trie -> children[i]), line);
	    break;		/* we're not interested in more children */
	 }
}


/* This procedure searches the trie for a line (*query) and then follows
 * the trie until it completes the query.  If it is not found, a null string
 * is returned.  The completion will be returned in *line.
 */

extern int output_trie(node_ptr trie, char *query, char *line) {

   int i=0;			/* for/while loop */
   *line = 0;
   
   if(*query)			/* is there something to search for? */
      if(trie = traverse_trie(trie,query)){ /* get to the end of *query */
	 while (++i <= NCHARS)	/* search for alive children */
	    if (trie -> children[i]) {
	       follow_trie((trie -> children[i]),line);
	       break;		/* don't find anymore children */
	    }
      }
      else return 0;		/* couldn't find query */
   return 1;
}

/* New_node will simply create and initialize a new node.  As part of the
 * initialization, memory is allocated, the end flag is set to false, each
 * child is set to zero, and the value that new_node receives is placed in
 * the value of this new node.  The reference of this node is returned to 
 * the caller.
 */

extern node_ptr new_node(char value) {

   int i;
   node_ptr baby;

   baby = malloc(sizeof (trie_node));	/* get memory */
   for(i=0; i <= NCHARS; ++i)	/* cycle through children and set to 0 */
       (baby -> children[i]) = (node_ptr) 0;
   (baby -> value) = value;	/* assign current value to this child */
   (baby -> end) = 0;

   return baby;
}

/* This procedure will dismantle the trie and set the memory free.  It
 * will free the trie that is passed into it, and all of it's children
 * (if any).  NOTE: it will not remove any reference to the passed-in trie
 * by it's parents.
 */
	    
extern void free_trie(node_ptr trie) {

   int i;			/* for loop */

   while (i <= NCHARS) {	/* search for living children */
      if (trie -> children[i])	/* if it's alive, follow it and kill more */
	 free_trie (trie -> children[i]);
      i++;
   }
      
   free(trie);			/* after search, kill current child */
}

/* This procedure will print out the tree to stdout with the prefix
 * given (*query).  You MUST pass an empty string of MAXLENGTH as the
 * last argument (null terminated).
 */

extern void printt(node_ptr trie, char *query, char *prefix) {
   int i;                                   /* for while loops */
   char prefix_copy[MAXLENGTH];             /* for children */
   
   if ((*query != '\n') && (*query != 0))   /* if not at end, search more */
      if (trie -> children[*query]) {
	 prefix = strncat(prefix, &(trie -> value), 1);
	 printt((trie -> children[*query]), (query + 1), prefix);
      }
      else                                 /* no match for next character */
	 return;                           /* failed to find, return */
   else {                                  /* found prefix, print out now */
      prefix = strncat(prefix, &(trie -> value), 1);
      if (trie -> end)                      /* if we're at the end of a */
	 printf("%s\n", prefix);            /* line, print it out */
      i = 0;
      while (++i <= NCHARS)                 /* scan children for more data */
         if (trie -> children[i]) {
	    strcpy(prefix_copy, prefix);    /* send a copy of prefix */
	    printt((trie -> children[i]), query, prefix_copy);
	 }
      }
   }