#include "dict.h"


inline int compare_to_entry(char l, int t, int p, struct dictree* y) {
  int j;
  j = l - y->letter;
  if(j)
    return j;
  j = t - (int)(y->type);
  if(j)
    return j;
  j = p - (int)(y->parse);
  return j;
}


inline struct dictree* new_node(char c, struct alloc* mem) {
  struct dictree *xp;
  xp = szalloc(mem, sizeof(*xp));
  xp->letter = c;
  return xp;
}


struct dictree* include_in_tree(char* str, int n, DTYPE type, DTYPE parse, \
				struct dict* x) { 
  int i;
  struct dictree* p;

  i = dic_insert(str, n, type, parse, &p, x);
  if(!i) 
    return 0;
  return p;
}

int dic_insert(char* str, int n, DTYPE type, DTYPE parse, struct dictree** y,\
	       struct dict* x) {
  struct dictree **ap, *xp, *yp, *prev_yp, **root;
  char c;
  int i, j;
  struct alloc *mem;

  if(!n)
    n = strlen(str);

  root = &(x->root);
  mem = &(x->mem);

  // The following loop finds the path to the chain where a leaf with the 
  // entry of str might be present.
  // At the end of the loop ap is the address of the 'down' pointer of the
  // parent node of the first chain element. Thus, *ap is the address of 
  // the first chain element or zero if the chain is empty. 

  for(i = 0, ap = root; i < n - 1; i++, ap = &((*ap)->down)) 
    for(prev_yp = 0; ; prev_yp = yp) {
      if(!*ap) {
	*ap = new_node(str[i], mem);
	break;
      }
      else {
	yp = *ap;
	j = yp->letter - str[i];
	if(j < 0)
	  ap = &(yp->next); // no break, continue with next iteration
	else if(!j)
	  break;
	else {
	  xp = new_node(str[i], mem);
	  xp->next = yp;
	  if(prev_yp)
	    prev_yp->next = xp;
	  *ap = xp;
	  break;
	}
      }
    }

  // Insert the data of 'item' into the chain such that the tree nodes are in 
  // the right order. The code also ensures that the tree does not insert an 
  // element that is identical to an already existing element.

  for(yp = *ap, prev_yp = 0, j = 1; yp; yp = yp->next) {
    j = compare_to_entry(str[n-1], type, parse, yp); // line reached if yp != 0
    if(j <= 0) // j == 0 indicates that the element is already in the tree
      break;
    prev_yp = yp; // line reached if j > 0
  }
  if(!j) { // Note that j = 1 if *ap = 0 (see initialization of loop above)
    if(y) *y = yp;
    return 0; // element already in tree, so return 0
  }
  xp = new_node(str[n-1], mem); // line reached if new element needed
  xp->type = type;
  xp->parse = parse;
  if(prev_yp) { // insert element in between prev_yp and yp
    prev_yp->next = xp;
    xp->next = yp;
  }
  else  { // insert element in *ap 
    *ap = xp;
    xp->next = yp;
  }

  x->n += 1;
  if(x->maxlen <= n)
    x->maxlen = n + 1;

  if(y) *y = xp;
  return 1;
}


struct dictree* dic_lookup(char* entry, struct dictree *troot) {
  struct dictree *p, *yp;
  int i, j;
  char c;
  if(!entry) return 0;
  if(!entry[0]) return 0;
  if(!troot) return 0;

  for(i = 0, p = troot, c = entry[0]; c && p; p = yp->down) {
    for(yp = p; yp; yp = yp->next) 
      if(yp->letter >= c)
	break;
    if(!yp) return 0;
    if(yp->letter != c) return 0;
    i++;
    c = entry[i];
  }

  if(!yp->type) return 0;
  return yp;
}


struct sdict {
  struct dictree *d;
  int depth; // depth >= 0 (root has depth = 0)
};


inline void _place_in_stack(struct stk_alloc* s, struct dictree* d, int dp) {
  struct sdict *sd;
  if(!d)
    return;
  sd = (struct sdict*) stk_push(s);
  sd->d = d;
  sd->depth = dp; 
}

inline void _take_from_stack(struct stk_alloc* s, struct dictree** d, int *dp){
  struct sdict *sd;
  sd = (struct sdict*) stk_pop(s);
  *d = sd->d;
  *dp = sd->depth;
}

struct dictree* next_entry(char* str, struct dict* x) {
/* This function can be used to list all entries in 'x' in alphabetical
   order. The return value is the entry. The name of the entry is stored 
   in 'str'. When the function is called, 'str' should contain the name of
   the previous entry; 'str' should have room for x->maxlen characters. 
   For the first call, set str[0] = 0. When no more entries are found the 
   function returns 0.
 */

  static struct stk_alloc s;
  static int init = 1;
  int depth;
  struct dictree *node, *n2;

  if(init) { // if first time the function is called
    init = 0;
    init_stack(&s, 32, sizeof(struct sdict));
  }

  if(!str || !x) { // this indicates that the function should be reset
    freestack(&s); // no problem if called several times
    return 0;
  }

  if(is_stk_empty(&s) && str[0]) { // if there are no more entries
    freestack(&s); // no problem if called several times
    return 0; 
  }

  if(!str[0]) {  // then this is the first call
    node = x->root;
    if(!node)
      return 0; // nothing to do, the tree is empty
    depth = 0;
  }
  else 
    _take_from_stack(&s, &node, &depth); // take 'node' and 'depth' from stack
  str[depth] = node->letter;

  while(1) {

    // work on current node

    if(node->type) { // then an entry was found
      for(n2 = node->next; n2; n2 = n2->next) // skip identical entries
	if(n2->letter != node->letter)
	  break;
      _place_in_stack(&s, n2, depth);
      depth++;
      _place_in_stack(&s, node->down, depth);
      str[depth] = 0;
      return node;
    }

    // select next current node

    if(node->down) {
      _place_in_stack(&s, node->next, depth); //'next' will be considered later
      node = node->down;
      depth++;
    }
    else if(node->next)
      node = node->next;
    else {
      if(is_stk_empty(&s)) { // if there are no more entries in the stack
	freestack(&s); // no problem if called several times
	return 0; 
      }
      _take_from_stack(&s, &node, &depth);// take 'node' and 'depth' from stack
    }
    str[depth] = node->letter;
  }
  return 0;
}
