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

node *source;

extern node *currentnode;
extern int length;

node *APPEND_LETTER(activenode,letter)
node *activenode;
int letter;
{
   node *newactivenode,*varnode,*SPLIT(),*CREATE_NODE();

   if ((newactivenode=activenode->out[letter]) != UNDEFINED) {
      if (activenode->type[letter] == PRIMARY) return(newactivenode);
      else return(SPLIT(activenode,letter));
   }
   else {
      newactivenode = CREATE_NODE();
      activenode->out[letter] = newactivenode; activenode->type[letter] = PRIMARY;
      newactivenode->origin = activenode;
      newactivenode->last_letter = letter;
      newactivenode->depth = activenode->depth + 1;
      varnode = activenode->suf_pointer;
      while (varnode != UNDEFINED && varnode->out[letter]==UNDEFINED) {
         varnode->out[letter] = newactivenode; varnode->type[letter] = SECONDARY;
         varnode = varnode->suf_pointer;
      }
      SET_SUF_POINTER(newactivenode,
          (varnode == UNDEFINED) ? source
          : ((varnode->type[letter] == PRIMARY) ?
	     varnode->out[letter] : SPLIT(varnode,letter)));
      return(newactivenode);
   }
}

/* modified version: the second parameter is a and not targetnode
     because SPLIT is always called SPLIT(x,x->out[a]) */
node *SPLIT(originnode,a)
node *originnode; 
int a;
{
   node *targetnode,*newtargetnode,*n,*varnode,*CREATE_NODE();
   int appendedletter,c;

   targetnode = originnode->out[a];
   newtargetnode = CREATE_NODE();
   appendedletter = targetnode->last_letter;
   originnode->out[a] = newtargetnode; originnode->type[a] = PRIMARY;
   newtargetnode->origin = originnode;
   newtargetnode->last_letter = appendedletter;
   newtargetnode->depth = originnode->depth + 1;
/* additional instructions */
   if (currentnode == targetnode) 
      if (length<=newtargetnode->depth) currentnode=newtargetnode; 
/* end of additional instructions */
   for (c=0;c<MAXCHARS;c++)
      if ((n=targetnode->out[c]) != UNDEFINED) {
         newtargetnode->out[c] = n; newtargetnode->type[c] = SECONDARY;
      }

   SET_SUF_POINTER(newtargetnode,targetnode->suf_pointer);
   DELETE_SUF_POINTER(targetnode,targetnode->suf_pointer);
   SET_SUF_POINTER(targetnode,newtargetnode);
/* after this: */
/* targetnode has the suffix pointer to newtargetnode, */
/* targetnode is the only child of newtargetnode, */

   varnode = originnode->suf_pointer;
   while (varnode != UNDEFINED && varnode->type[appendedletter]==SECONDARY) {
      varnode->out[appendedletter] = newtargetnode;
      varnode = varnode->suf_pointer;
   }
   return(newtargetnode);
}

SET_SUF_POINTER(newchild, father)
     node *newchild, *father;
/* it is supposed that newchild does not have a suffix pointer, */
/* that is, does not belong to any child list. child is inserted */
/* in the father's list at the leftmost position */
{
   node *current_leftmost_child;
   if (father->child !=UNDEFINED)
     {
/* unnecessary test */
     if (father->number_of_children == 0 ) printf("problem5...\n");
/* end of unnecessary test */
     current_leftmost_child=father->child;
     newchild->right_neighbour = current_leftmost_child;
     current_leftmost_child->left_neighbour = newchild;
     }
   newchild->suf_pointer=father;
   father->child=newchild;
   father->number_of_children++;
}

DELETE_SUF_POINTER(oldchild, father)
     node *oldchild, *father;
{
   if (oldchild->left_neighbour==UNDEFINED)
      if (oldchild->right_neighbour != UNDEFINED)
                 /* oldchild is not the only child of father but is the leftmost one */
         {
/* unnecessary test */
         if (father->number_of_children <= 1) printf("problem6 ...\n");
/* end of unnecessary test */
         oldchild->right_neighbour->left_neighbour = UNDEFINED;
	 father->child = oldchild->right_neighbour;
	 oldchild->right_neighbour = UNDEFINED;
         }
      else
                 /* oldchild is the only child of father */
         {
/* unnecessary test */
         if (father->number_of_children != 1) printf("problem7 ...\n");
/* end of unnecessary test */
         father->child = UNDEFINED; 
         } 
   else
      if (oldchild->right_neighbour != UNDEFINED)
                 /* oldchild has both right and left neighbour */
         {
/* unnecessary test */
         if (father->number_of_children <= 1) printf("problem6 ...\n");
/* end of unnecessary test */
         oldchild->right_neighbour->left_neighbour = oldchild->left_neighbour;
         oldchild->left_neighbour->right_neighbour = oldchild->right_neighbour;
	 oldchild->left_neighbour = oldchild->right_neighbour = UNDEFINED;
         }
      else
                 /* oldchild is not the only child of father but is the rightmost one */
         {
/* unnecessary test */
         if (father->number_of_children <= 1) printf("problem6 ...\n");
/* end of unnecessary test */
         oldchild->left_neighbour->right_neighbour = UNDEFINED;
         oldchild->left_neighbour = UNDEFINED;
         }
   oldchild->suf_pointer=UNDEFINED;
   father->number_of_children--;
}


node *LOAD_KEYWORD(v)
char v[];
{
   int i; 
   node *activenode;

   activenode=source;
   for (i=0;i<strlen(v);i++) {
      activenode = APPEND_LETTER(activenode,LET_TO_NUM(v[i]));
      activenode->prefix_degree++;
   }
   return activenode;
}

node *CREATE_NODE()
{
  node *newnode;
  int i;

  newnode = (node*) malloc(sizeof(node));
/*  printf("memory allocated, %d\n",sizeof(node)); */
  for(i=0;i<MAXCHARS;i++) newnode->out[i]=UNDEFINED;
  newnode->suf_pointer=newnode->origin=UNDEFINED;
  newnode->child=newnode->left_neighbour=newnode->right_neighbour=UNDEFINED;
  newnode->terminal=NULL;
  newnode->number_of_children=newnode->prefix_degree=0;
  newnode->depth=0;
  newnode->visited=NOT_YET;
  newnode->last_letter=-1;
  newnode->number=0;
  return newnode;
}

node *DELETE_LETTER(activenode)
node *activenode;
{
   node *newactivenode,*varnode,*suffixnode; 
   int deletedletter;

   newactivenode = activenode->origin;
   deletedletter = activenode->last_letter;
   if (activenode->prefix_degree>0 || 
       activenode->number_of_children > 1) return(newactivenode);
   else if (activenode->number_of_children==1) {
      MERGE(activenode,newactivenode,deletedletter);
      return(newactivenode);
   }
   else {
      newactivenode->out[deletedletter]=UNDEFINED;
/* additional instructions */
      if (currentnode==activenode) { 
         currentnode=activenode->suf_pointer; 
         length = currentnode->depth; 
       } 
/* end of additional instructions */
      varnode=newactivenode->suf_pointer;
      while (varnode!=UNDEFINED && varnode->type[deletedletter]==SECONDARY) {
/* unnecessary test */
         if (varnode->out[deletedletter] != activenode) printf("problem1 ...\n");
/* end of unnecessary test */
         varnode->out[deletedletter]=UNDEFINED;
         varnode = varnode->suf_pointer;
      }
      DELETE_SUF_POINTER(activenode,activenode->suf_pointer);
      DELETE_NODE(activenode);
      if (varnode != UNDEFINED) {
/* unnecessary test */
         if (varnode->type[deletedletter] != PRIMARY) printf("problem2 ...\n");
/* end of unnecessary test */
         suffixnode = varnode->out[deletedletter];
         if (suffixnode->prefix_degree==0 && suffixnode->number_of_children==1)
	    MERGE(suffixnode,varnode,deletedletter);
      }
      return(newactivenode);
   }
}

MERGE(targetnode,originnode,deletedletter)
/* targetnode must have one child */
node *targetnode,*originnode;
int deletedletter;
{
   node *newtargetnode,*varnode;

   newtargetnode = targetnode->child;
/* additional instructions */
   if (currentnode == targetnode) currentnode=newtargetnode;
/* end of additional instructions */
   originnode->out[deletedletter] = newtargetnode;
   originnode->type[deletedletter] = SECONDARY;
   varnode = originnode->suf_pointer;
   while (varnode!=UNDEFINED && varnode->type[deletedletter]==SECONDARY) {
      varnode->out[deletedletter] = newtargetnode;
      varnode = varnode->suf_pointer;
   }
/* unnecessary tests */
   if (varnode == UNDEFINED)  {
     if (targetnode->suf_pointer != source) printf("problem3 ...\n");
     }
   else 
     if (varnode->type[deletedletter] != PRIMARY) printf("problem4 ...\n");
/* end of unnecessary tests */

   DELETE_SUF_POINTER(newtargetnode,targetnode);
   SET_SUF_POINTER(newtargetnode,targetnode->suf_pointer);
   DELETE_SUF_POINTER(targetnode,targetnode->suf_pointer);
   DELETE_NODE(targetnode);
}

DELETE_NODE(nod)
/* it is supposed that no edges point to nod and that */
/* the suffix pointer of nod has been deleted */
     node *nod;
{
  free(nod);
}

UNLOAD_KEYWORD(terminalnode)
node *terminalnode;
{
   node *activenode;

   activenode = terminalnode;
   while (activenode != source) {
      activenode->prefix_degree--;
      activenode = DELETE_LETTER(activenode);
   }
}