/**
 *   File nn_tree.c
 *   This module is used to manage pointers (actually indexes in array objs[])
 *   as a binary tree (btree) structure.
 *   It can be easily re-used in other contexts because the only elements needed
 *   from "defines.h" are
 *   *  a "Qtype" enum for types
 *   *  a "QDobject" struct with the line of pointers:
 *                   int self ,elder  ,brother ,child;
 *          and the  int active;   flag 
 *   Array objs[] is known via globals.h
 *   It is the programmer's responsability to create, init and deletes elements
 *   in array objs.
 *   "elder" can be the father or a brother.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <signal.h>

#include "globals.h"
#include "nn_tree.h"


#ifdef DEBUG
int objs_max (void);

void print_objs (void)
{
  int i;
  for (i=0; i< objs_max (); i++) {
    int typ = objs[i].typ;
    if (typ >= 0) {
      printf ("obj: i=%3d s=%3d e=%3d b=%3d c=%3d  %30s\t id=%d\n" ,i
	      ,objs[i].self
	      ,objs[i].elder
	      ,objs[i].brother
	      ,objs[i].child
	      ,Qtype_name[objs[i].typ]
	      ,objs[i].id
	      );
    } else {
      printf ("obj: i=%3d e=%3d b=%3d c=%3d  typ=%d \t id=%d\n" ,i
	      ,objs[i].elder
	      ,objs[i].brother
	      ,objs[i].child
	      ,typ
	      ,objs[i].id
	      );
    }
  }
}

static void _print_tree (int i ,int depth)
{
  Qtype typ = objs[i].typ;
  char fmt[140];
  if (typ == Q_Undef) {
    printf ("_print_tree: i=%d depth=%d  Q_Undef\n" ,i ,depth);
    return;
  }
  sprintf (fmt ,"%%3d %%%ds %%-14s id=%%3d  i=%%3d e=%%3d b=%%3d c=%%3d layer=%%3d" ,3*depth+3);
  printf (fmt ,depth ," " ,Qtype_name[typ] ,objs[i].id ,i
	  ,objs[i].elder ,objs[i].brother ,objs[i].child ,objs[i].layer
	  );
    printf ("\t bb (%.3f %.3f %.3f %.3f)" 
	    ,objs[i].bb.xv1
	    ,objs[i].bb.yv1
	    ,objs[i].bb.xv2
	    ,objs[i].bb.yv2
	    );
  printf ("\n");
}
void print_tree (void) 
{
  nn_traverse_stop (FALSE);
  nn_traverse_child_first (0 ,_print_tree ,NULL);
}

static void _check_tree (int i ,int depth)
{
  Qtype typ = objs[i].typ;
  int e ,b ,c;
  if (i == 0) return;
  if (typ == Q_Undef) {
    fprintf (stderr ,"_print_tree: i=%d depth=%d  Q_Undef\n" ,i ,depth);
    return;
  } else { 
    if (objs[i].self != i) {
      fprintf (stderr ,"check_tree : objs[%d].self = %d  \n" ,i ,objs[i].self);
      return;
    }
    e = objs[i].elder;
    if (e < 0) {
      fprintf (stderr ,"check_tree : objs[%d].elder < 0 \n" ,i);
      return;
    }
    b = objs[e].brother;
    c = objs[e].child;
    if (b == c) {
      fprintf (stderr ,"check_tree : objs[%d].brother == objs[%d].child \n" ,e ,e);
      return;
    }
    if (c == i) {             /* "i" is child of "e" */
      if (objs[i].father_typ != objs[e].typ) {
	fprintf (stderr ,"check_tree : objs[%d].father_typ != objs[%d].typ \n" ,i ,e);
	return;
      }
      if (objs[i].father_id != objs[e].id) {
	fprintf (stderr ,"check_tree : objs[%d].father_id != objs[%d].id \n" ,i ,e);
	return;
      }
    } else if (b == i) {    /* "i" is brother of "e" */
      if (objs[i].father_typ != objs[e].father_typ) {
	fprintf (stderr ,"check_tree : father_typ != for brothers %d and %d \n" ,i ,e);
	return;
      }
      if (objs[i].father_id != objs[e].father_id) {
	fprintf (stderr ,"check_tree : father_id != for brothers %d and %d \n" ,i ,e);
	return;
      }
    } else {
      fprintf (stderr ,"check_tree : node %d: elder=%d ,e.brother=%d and e.child=%d \n" ,i ,e ,b ,c);
      return;
    }
  }
}
void check_tree (void)
{
  fprintf (stderr ,"\nCHECK TREE\n");
  nn_traverse_stop (FALSE);
  nn_traverse_child_first (0 ,_check_tree ,NULL);
  fprintf (stderr ,"Check tree ended\n");
}
#endif /* DEBUG */

void nn_init_node (int i ,Qtype typ)
{
  objs[i].typ     = typ;
  objs[i].self    = i;
  objs[i].elder   = -1;
  objs[i].brother = -1;
  objs[i].child   = -1;
}

void nn_get_link_info (int i ,int *links)
{
  links[0] = objs[i].elder;
  links[1] = objs[i].brother;
  links[2] = objs[i].child;
  links[3] = objs[i].self;
}
void nn_set_link_info (int i ,int *links)
{
  objs[i].elder   = links[0];
  objs[i].brother = links[1];
  objs[i].child   = links[2];
  objs[i].self    = links[3];
}

/**
 * get the father (is not the elder if "i" is a brother)
 */
int nn_get_father (int i) 
{
  int f = objs[i].elder;
  if (f >= 0) {
    while (objs[f].brother == i) {
      i = f;
      f = objs[i].elder;
      if (f < 0) return f;
    }
    return f;
  } else {
    return -1;
  }
}

void nn_set_father (int i)
{
  int f = nn_get_father (i);
  if (f >= 0) {
    objs[i].father_typ = objs[f].typ;
    objs[i].father_id  = objs[f].id;
  } else {
    objs[i].father_typ = Q_Undef;
    objs[i].father_id  = -1;
  }
}

int nn_get_last_brother (int i)
{
  int b ,lb;
  if (i >= 0) {
    b = lb = objs[i].brother;
    while (b > 0) {
      lb = b;
      b = objs[b].brother;
    }
    return lb;
  }
  return -1;   /* failed */
}

/**
 * nn_insert_brother : insert "b" as brother before "i"
 *    if "i" was the first child, insert as elder brother,
 *    i.e. as child of father
 */
void nn_insert_brother (int i ,int b)
{
  int e = objs[i].elder; 
  if (objs[e].brother == i) {
    objs[e].brother  = b;
  } else {
    objs[e].child    = b;
  }
  objs[b].self       = b;
  objs[b].elder      = e;
  objs[b].brother    = i;
  objs[i].elder      = b;
  nn_set_father (b);
}
/**
 * nn_insert_brother_after : insert "b" as brother after "i"
 */
void nn_insert_brother_after (int i ,int b)
{
  int ob = objs[i].brother; 
  objs[i].brother    = b;
  objs[b].self       = b;
  objs[b].elder      = i;
  objs[b].brother    = ob;
  if (ob >= 0) objs[ob].elder  = b;
  nn_set_father (b);
}

/**
 * nn_append_brother : append "b" as youngest (i.e. last) brother of elder
 */
void nn_append_brother (int elder ,int b)
{
  int youngest = elder;
  int i = objs[elder].brother;
  while (i >= 0) {
    youngest = i;
    i = objs[i].brother;
  }
  objs[youngest].brother = b;
  objs[b].elder      = youngest;
  objs[b].self       = b;
  nn_set_father (b);
}

/**
 * nn_insert_child : insert "c" as first child of elder  
 */
void nn_insert_child (int elder  ,int c)
{
  int oc = objs[elder].child;
  if (oc >= 0) {
    objs[oc].elder  = c;
    objs[c].brother = oc;
  }
  objs[elder].child = c;
  objs[c].elder      = elder ;
  objs[c].self       = c;
  objs[c].father_typ = objs[elder].typ;
  objs[c].father_id  = objs[elder].id;
}

/**
 * nn_append_child :  append "c" after the last child
 */
void nn_append_child (int elder  ,int c)
{
  int oc = objs[elder].child;
  if (oc < 0) {
    nn_insert_child (elder  ,c);
  } else {
    nn_append_brother (oc ,c);
  }
}

/**
 * nn_insert_typed_brother :  insert "b" as a brother of "elder"
 *     if type of elder is "typ" ,search the last brother
 *                       with "typ" and append after him
 *     else insert "b" as first brother of elder 
 *    Used to add Q_Graph  links
 */
void nn_insert_typed_brother (Qtype typ ,int elder ,int b)
{
  int cb = objs[elder].brother;   /* cb: current brother */
  while (cb >= 0) {
    if (objs[cb].typ != typ) {
      nn_insert_brother (cb ,b);
      return;
    }
    cb = objs[cb].brother;
  }
  nn_insert_brother (elder ,b);
}

/**
 *  nn_append_typed_brother : append "b" as brother of "elder"
 *                            If elder has no brother, create the first one.
 *                            Else traverse the branch until the current typ
 *                            is different from typ(elder) or typ(b)
 *                            and then append "b".
 */
void nn_append_typed_brother (int elder ,int b)
{
  int ocb = -1;
  int cb = objs[elder].brother;
  if (cb < 0) {
    nn_insert_brother_after (elder ,b);
  } else {
    Qtype etyp = objs[elder].typ;
    Qtype btyp = objs[b].typ;
    while (cb >= 0) {
      if (objs[cb].typ == etyp || objs[cb].typ == btyp) {
	ocb = cb;
	cb = objs[cb].brother;
      } else {
	break;
      }
    }
    if (cb < 0) {
      nn_insert_brother_after (ocb ,b);
    } else {
      nn_insert_brother (cb ,b);
    }
  }
}


/**
 * nn_append_typed_child :  append "c" after the last child of elder having
 *      type "typ". If no child exist, insert as 1st child.
 */
void nn_append_typed_child (Qtype typ ,int elder  ,int c)
{
  int cc = objs[elder].child;             /* cc: current child */
  if (cc < 0) {
    nn_insert_child (elder  ,c);
  } else {
    int brother = cc;                     /* will be a brother ? */
    int i = objs[cc].brother;             /* looks forward */
    int styp = -1;                        /* init to detect if same typ */
    while (i >= 0) {
      if (objs[i].typ == typ) styp = i;   /* yes i is of same typ */
      i = objs[i].brother;                /* looks forward */
    }
    i = (styp < 0) ? brother : styp;      /* if <0, no obj of same typ found,  */
    nn_append_brother (i ,c);
  }
}


/**
 * nn_move_child : prune "c" and append to elder with nn_append_typed_child
 */
void nn_move_as_child (int elder ,int c)
{
  int typ = objs[c].typ;
  nn_prune (c);
  nn_append_typed_child (typ ,elder ,c);
}


/* internal */

static int stop_trav = FALSE;
void nn_traverse_stop (int swt)
{
  stop_trav = swt;
}
static void _nn_traverse_child_first (int i
				      ,void (*f1) (int i ,int depth)
				      ,void (*f2) (int i ,int depth)
				      ,void (*f3) (int i ,int depth)
				      ,int *depth ,int *count)
{
  int next;
  (*count)++;
  if (*count > 500) {
    fprintf (stderr ,"_nn_traverse_child_first: ERROR count > 500\n");
    stop_trav = TRUE;
    return;
  }
  if (*depth > 100) {
    fprintf (stderr ,"_nn_traverse_child_first: ERROR depth > 100\n");
#ifdef DEBUG
    fprintf (stderr ,"_nn_traverse_child_first: i = %d\n" ,i);
    check_tree ();
    print_objs ();
#endif /* DEBUG */
    stop_trav = TRUE;
    return;
  }
  if (i < 0 || stop_trav) return;   /* stop_trav inutile ? */
  if (f1 != NULL) f1 (i ,*depth);
  if (!stop_trav) {
    next = objs[i].child;
    if (next == i) {
      fprintf (stderr ,"_nn_traverse_child_first: ERROR child=i=%d\n" ,i);
      stop_trav = TRUE;
      return;
    }
    if (next > 0) {
      (*depth)++;
      _nn_traverse_child_first (next ,f1 ,f2 ,f3 ,depth ,count);
      (*depth)--;
    }
  }
  if (f2 != NULL) f2 (i ,*depth);
  stop_trav = FALSE;
  next = objs[i].brother;
  if (next == i) {
    fprintf (stderr ,"_nn_traverse_child_first: ERROR brother=i=%d\n" ,i);
    stop_trav = TRUE;
    return;
  }
  if (next > 0) _nn_traverse_child_first (next ,f1 ,f2 ,f3 ,depth ,count);
  if (f3 != NULL) f3 (i ,*depth);
}

/**
 *  nn_traverse_child_first :  walk the tree from node "start" in
 *    a "child first" scheme and call f1  at each node during
 *    the forward (start -> leaves) part of the walk (if f1 is not NULL)
 *    and f3 during the backward part (leaves -> nodes)
 */
void nn_traverse_child_first   (int start
				,void (*f1) (int i ,int depth)
				,void (*f3) (int i ,int depth))
{
  static int depth;
  static int count;
  if (start >= 0) {
    depth = 0;
    count = 0;
    stop_trav = FALSE;
    _nn_traverse_child_first (start ,f1 ,NULL ,f3 ,&depth ,&count);
  }
}

void nn_traverse_with_middle   (int start
				,void (*f1) (int i ,int depth)
				,void (*f2) (int i ,int depth)
				,void (*f3) (int i ,int depth))
{
  static int depth;
  static int count;
  if (start >= 0) {
    depth = 0;
    count = 0;
    stop_trav = FALSE;
    _nn_traverse_child_first (start ,f1 ,f2 ,f3 ,&depth ,&count);
  }
}

/**
 *  Prune node i
 *  note that nn_prune does not manage father_typ and father_id
 * and is incompatible with nn_insert_brother
 */
void nn_prune (int i)
{
  int oe = objs[i].elder;
  if (oe == ORPHAN) return;
  int b = objs[i].brother;
  if (b >= 0)  objs[b].elder = oe;
  if (objs[oe].brother == i) {
    objs[oe].brother = objs[i].brother;
  } else {
    objs[oe].child = objs[i].brother;
  }
  objs[i].elder   = ORPHAN;
  objs[i].brother = -1;      /* no more brother */
}

 /**
 *  Swap nodes i1 and i2 in the tree
 */
void nn_swap_nodes (int i1 ,int i2)
 {
   int l1[4] ,l2[4];
   QDobject obj;
   if (i1 == i2) return;
   /* save link info */
   nn_get_link_info (i1 ,l1);
   nn_get_link_info (i2 ,l2);
   /* swap objs elements */
   memcpy (&obj      ,&objs[i1] ,sizeof (QDobject));
   memcpy (&objs[i1] ,&objs[i2] ,sizeof (QDobject));
   memcpy (&objs[i2] ,&obj      ,sizeof (QDobject));
   /* restore link info */
   nn_set_link_info (i1 ,l1);
   nn_set_link_info (i2 ,l2);
 }

/**
 *  nn_kill_node : remove node "i" and all is descendants
 *                 leaving empty slots in objs
 */
void nn_kill_node (int i ,int depth)
{
  nn_prune (i);
  //22  nn_free (objs[i].data2);  /*  Assume that it does not need further free(); */
  objs[i].typ     = Q_Undef;
  objs[i].elder   = -1;
  objs[i].brother = -1;
  objs[i].child   = -1;
  objs[i].active  =  0;
  objs[i].id      = -1;
}


void nn_kill_branch (int i)
{
  nn_traverse_stop (FALSE);
  nn_traverse_child_first (objs[i].child ,NULL ,nn_kill_node);
  nn_kill_node (i ,0);

}

void nn_kill_youngers (int i)
{
  nn_traverse_stop (FALSE);
  nn_traverse_child_first (objs[i].child   ,NULL ,nn_kill_node);
  nn_traverse_stop (FALSE);
  nn_traverse_child_first (objs[i].brother ,NULL ,nn_kill_node);
}
