/*  pdnmesh - a 2D finite element solver
    Copyright (C) 2001-2005 Sarod Yatawatta <sarod@users.sf.net>  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  $Id: dag.c,v 1.13 2005/02/18 18:27:10 sarod Exp $
*/



/* Directed Acyclic Graph */

#include <stdio.h>
#include <stdlib.h>
#include "types.h"

/* sentinel for queue intialization */
static DAG_node_queue Dsentinel={NULL,NULL,NULL};
/* initialize DAG */
int
DAG_init(DAG_tree *t, int (*comp_INC)(const void *rec1,const void *rec2, const void *MM/* Mesh */),
								void (*print_record)(const void *rec))
{
	t->root=0;
	t->comp_INC=comp_INC;
	t->print_record=print_record;
	/* intialize the queue */
  t->sentinel=&Dsentinel;
  t->qhead=t->sentinel;
	t->qtail=t->sentinel;
	t->sentinel->next=t->sentinel->prev=0;
	return(DAG_STATUS_OK);
}

/* we return the dag node with piggyback data record */
/* because we need it for cross referencing */
void *
DAG_insert(DAG_tree *t, DAG_node *parent, void *rec) 
{
	 DAG_node_list *temp_list_node, *head,*tail;
		DAG_node_queue *temp_q;
   DAG_node *child;



    if ((child=(DAG_node *)malloc(sizeof(DAG_node)))==0) {
      fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
		  exit(1);
		 }
     child->rec=rec; 
		 /* we do not actually keep the data here */ 
		 /* because it will be kept in the balanced tree */
     child->list=0;

		 /* insert new node to queue because by default it will be a leaf */
		 	if ((temp_q=(DAG_node_queue *)malloc(sizeof(DAG_node_queue)))==0) {
		  fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
		  exit(1);
		 }
				/* insert it above the sentinel */
		temp_q->next=t->sentinel->next;
		if ( t->sentinel->next ) {
		t->sentinel->next->prev=temp_q;
	 }
		t->sentinel->next=temp_q;
		temp_q->prev=t->sentinel;
		temp_q->child=child;
		/* this is the empty queue case */
		if ( t->qhead == t->sentinel ) {
		t->qhead=temp_q;
		}

	 /* first handle empty DAG */
	 if (t->root==0) {
    		 t->root=child;
				 return((void*)child);
	 }

	 /* non - empty tree */
   /* first create the list node and the  dag	node pointing it */
			if ((temp_list_node=(DAG_node_list *)malloc(sizeof(DAG_node_list)))==0) {
		  fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
		  exit(1);
		 }
		 temp_list_node->next=0;
		 temp_list_node->child=child;

  if (parent->list==0) {
				parent->list=temp_list_node;
				return((void*)temp_list_node->child);
  }
	/* else implied */
  head=parent->list; 
  /* traverse parent list of children*/
	while (head){
				  tail=head;	
					head=head->next;
	}
  tail->next=temp_list_node;
	return((void*)temp_list_node->child);
}

/* add a cross link between two nodes */
void *
DAG_link(DAG_tree *t, DAG_node *parent, DAG_node *child) 
{
      DAG_node_list *temp_list_node, *head,*tail;
      /* first create the list node and the  dag	node pointing it */
			if ((temp_list_node=(DAG_node_list *)malloc(sizeof(DAG_node_list)))==0) {
		  fprintf(stderr,"%s: %d: no free memory",__FILE__,__LINE__);
		  exit(1);
		 }
		 temp_list_node->next=0;
		 temp_list_node->child=child;
  if (!parent) {
		fprintf(stderr,"%s: %d: error",__FILE__,__LINE__);
	  return(0);
	}
  if (parent->list==0) {
				parent->list=temp_list_node;
				return((void*)temp_list_node->child);
  }
	/* else implied */
  head=parent->list; 
  /* traverse parent list of children*/
	while (head){
				  tail=head;	
					head=head->next;
	}
  tail->next=temp_list_node;
	return((void*)temp_list_node->child);
}


/* returns node pointer where data is found */
/* assertion - nodes at same level cover disjoint regions */
/* nodes at higher level cover same region as nodes at lower level */
void *
DAG_find(DAG_tree *t, void *datarec, const void *MM/* Mesh */)
{
	/* note- datarec need not be the type rec */
  DAG_node *parent;
	DAG_node_list *head;
	/* empty tree */
	if (t->root==0) {
			return(0);
	}

  /* next a special check for root data */
  if (!t->comp_INC((void *)t->root->rec,(void *)datarec,MM))
			 return(0);
  /* if root record is not including data, no need to check any further */ 

	/* loop till we reach the leaves of DAG */
	parent=t->root;
	do {
	head=parent->list;
	while (head && (!t->comp_INC((void*)head->child->rec,(void *)datarec,MM))) {
			head=head->next;
	}
	/* if we are here, either head==0, or Inclusion function works */
	if (head==0) {
			return((void*)parent);
	} else {
			parent=head->child;
	}
	} while (parent);

	/* we will not get here, hopefully */
	return(0);

}

/* local visit */	
static void
visit_node(DAG_tree *t,DAG_node *parent)
{
	DAG_node_list *head;
  t->print_record(parent->rec);
  /* traverse child list */
  head=parent->list;
  /* traverse parent list of children*/
	while (head){
					visit_node(t,head->child);
					head=head->next;
	}
}
/* traverse and print */
void 
DAG_traverse(DAG_tree *t)
{
	/* empty tree */
	if (!t->root) {
	visit_node(t,t->root);
	}
}

/* traverse the leaf list and prune it */
/* that is, remove nodes that are not leaves */
/* returns the next leaf node data pointer */
void *
DAG_traverse_prune_list(DAG_tree *t)
{
		DAG_node_queue *temp;
 /* empty - impossible */
	if ( !t->sentinel  )
				return(0);
	/* tail==(sentinel)==head - empty */
	if ( (t->qhead==t->sentinel) && (t->qtail==t->sentinel ) ){
				return(0);
	}
 /* we have reached the  end of our traversal */
/* (tail)-(*)-(*)-(*).....(*)-(sentinel)==head */
	/* change this to */
/* (tail)==(sentinel)-(*)-(*)-(*).....(*)-(head) */
	if (t->qhead == t->sentinel ) {
					/* move sentinel to tail */
     temp=t->sentinel;
					t->qhead=t->qhead->prev;
					t->qhead->next=0;
					temp->next=t->qtail;
					t->qtail->prev=temp;
					t->qtail=temp;
					t->qtail->prev=0;
					return(0);
	}

	/* normal case */
/* (tail)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(head)*/
	while (t->qhead != t->sentinel ) {
	/* get the next node from queue */
	temp=t->qhead;
	t->qhead=temp->prev;
	if ( t->qhead ) {
   t->qhead->next=0;
	}
 /* check if this is a leaf */
 if ( !temp->child->list ) {
						/* insert this back at the tail 
							*  and return its record value */
       temp->next=t->qtail;
							temp->prev=0;
							if ( t->qtail ) {
													t->qtail->prev =temp;
							}
							t->qtail=temp;
							return(temp->child->rec);
	} else {
				/* this is not a leaf, so remove it from the queue */
#ifdef DEBUG
				printf("DAG pruning\n");
#endif
				free(temp);
				/* get another node from queue */
 }
 }
	
/* if we reach here, queue does not have a leaf */
	return(0);

}

/* reset queue for a new traversal */
void
DAG_traverse_list_reset(DAG_tree *t)
{
  /* empty - impossible */
	if ( t->sentinel  ) {

				/* move the sentinel down to the tail of the queue */
				if ((t->qhead !=t->sentinel)&&(t->qtail !=t->sentinel)) {
									/* sentinel in the middle */
									t->sentinel->prev->next=t->sentinel->next;
									t->sentinel->next->prev=t->sentinel->prev;
									/* move down */
									t->qtail->prev=t->sentinel;
									t->sentinel->prev=0;
									t->sentinel->next=t->qtail;
									t->qtail=t->sentinel;
				} else if ((t->qhead ==t->sentinel) &&(t->qtail !=t->sentinel) ) {
												/* sentinel at head, bring to bottom */
									t->sentinel->prev->next=0;
									t->qhead=t->sentinel->prev;
          /* move down */
									t->qtail->prev=t->sentinel;
									t->sentinel->prev=0;
									t->sentinel->next=t->qtail;
									t->qtail=t->sentinel;
				}

	}
}


/* local free */	
static void
free_node(DAG_tree *t,DAG_node *parent)
{
	DAG_node_list *head;
	/* BIG NOTE: we do not free the record here
	 * it has to be freed using the RBT */
  /* t->print_record(parent->rec); */
  if ( parent ) {
  /* traverse child list */
  head=parent->list;
  /* free parent list of children*/
	while (head){
					free_node(t,head->child);
					head=head->next;
	}
	/* free itself */
	free(parent);
	}
}

/* BIG NOTE: we do not free the record here
* it has to be freed using the RBT */
/* free DAG */
void 
DAG_free(DAG_tree *t)
{
DAG_node_queue *temp;
	/* free tree */
	if (!t->root) {
	free_node(t,t->root);
	}

	/* free queue */
	if ( (t->qhead!=t->qtail) ){
		/* normal case */
/* (tail)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(head)*/
	temp=t->qhead;
	t->qhead=temp->prev;
	while (temp ) {
   if (temp!=t->sentinel) {free(temp);}
		temp=t->qhead;
		if ( temp )
	   t->qhead=temp->prev;
  }
	}
}



/* reset queue for a new reverse-traversal */
void
DAG_reverse_traverse_list_reset(DAG_tree *t)
{
  /* empty - impossible */
	if ( t->sentinel  ) {

				/* move the sentinel up to the head of the queue */
				if ((t->qhead !=t->sentinel)&&(t->qtail !=t->sentinel)) {
									/* sentinel in the middle */
									t->sentinel->prev->next=t->sentinel->next;
									t->sentinel->next->prev=t->sentinel->prev;
									/* move up */
									t->qhead->next=t->sentinel;
									t->sentinel->next=0;
									t->sentinel->prev=t->qhead;
									t->qhead=t->sentinel;
				} else if ((t->qtail==t->sentinel) &&(t->qhead !=t->sentinel) ) {
												/* sentinel at tail, bring to top*/
									t->sentinel->next->prev=0;
									t->qtail=t->sentinel->next;
          /* move up */
									t->qhead->next=t->sentinel;
									t->sentinel->next=0;
									t->sentinel->prev=t->qhead;
									t->qhead=t->sentinel;
				}

	}
}


/* reverse-traverse the leaf list and prune it */
/* that is, remove nodes that are not leaves */
/* returns the next leaf node data pointer */
/* note: reverse traverse is needed when we do not want to consider 
 * triangles created while traversing the list.
 * these new triangles will be considered in the next traversal of
 * the list. this is the difference between 
 * reverse and normal traversals. the reason being, new triangles
 * are always inserted before the sentinel. so (head)-*-*-(sentinel)
 * part gets new triangles, not the (sentinel)-*-(tail) part
 */
void *
DAG_reverse_traverse_prune_list(DAG_tree *t)
{
		DAG_node_queue *temp;
 /* empty - impossible */
	if ( !t->sentinel  )
				return(0);
	/* tail==(sentinel)==head - empty */
	if ( (t->qhead==t->sentinel) && (t->qtail==t->sentinel ) ){
				return(0);
	}
 /* we have reached the  end of our traversal */
/* (head)-(*)-(*)-(*).....(*)-(sentinel)==tail*/
	/* change this to */
/* (head)==(sentinel)-(*)-(*)-(*).....(*)-(tail) */
	if (t->qtail== t->sentinel ) {
					/* move sentinel to head */
     temp=t->sentinel;
					t->qtail=t->qtail->next;
					t->qtail->prev=0;
					temp->prev=t->qhead;
					t->qhead->next=temp;
					t->qhead=temp;
					t->qhead->next=0;
					return(0);
	}

	/* normal case */
/* (head)-(*)-(*)-(*).....(*)-(sentinel)-(*)-(*)-(*).....(*)-(tail)*/
	while (t->qtail != t->sentinel ) {
	/* get the next node from queue (tail) */
	temp=t->qtail;
	t->qtail=temp->next;
	if ( t->qtail) {
   t->qtail->prev=0;
	}
 /* check if this is a leaf */
 if ( !temp->child->list ) {
						/* insert this back at the head 
							*  and return its record value */
       temp->prev=t->qhead;
							temp->next=0;
							if ( t->qhead) {
													t->qhead->next=temp;
							}
							t->qhead=temp;
							return(temp->child->rec);
	} else {
				/* this is not a leaf, so remove it from the queue */
#ifdef DEBUG
				printf("DAG pruning\n");
#endif
				free(temp);
				/* get another node from queue */
 }
 }
	
/* if we reach here, queue does not have a leaf */
	return(0);

}