/* This program implements the topological sort algorithm.  The prerequisite
     relation is assumed to be stored explicitly in a file as a list of
     task names, each occupying a single line.  The set of tasks is
     assumed to be stored implicitly.  Its explicit representation as
     an instance of the class "taskset" is constructed from the
     components of the pairs of the relation.
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <io.h>
#include <assert.h>

typedef int boolean;
#define TRUE 1
#define FALSE 0

#define NAMELEN 32             /* the maximum length of a task name */
#define FILENMLEN 64           /*   and a file name */

typedef char * taskid;

/* The type for tasks.  Tasks have 5 fields -- a task identifier "name",
     an integer representing the number of unmet prerequisites, a link
     field so that it may appear on linked lists, and a pointer to a
     "postrequisite list" -- the list of tasks for which a given instance
     is a prerequisite.  The 5th field "main_entry" is used to point
     from tasks that are members of postrequisite lists to corresponding
     tasks in task sets.
*/

typedef struct task							{
    taskid name;
    struct task *postreqlist;    /* without header */
    int unmet;
    struct task *link;
    struct task *main_entry;  						}
task  ;


/* The type for sets of tasks is "taskset".  These sets are represented
     as headed linked lists of tasks.
   The list header keeps track of the number of elements in the set
     by means of its "unmet" field.
*/

typedef struct 								{
    task *theader;                                                      }
taskset;


/*///////////////////// FUNCTIONS FOR TASKS //////////////////////////*/


/* Initialize a task with identifier given by "taskname" by copying
     this taskname to the "name" field.
   The number of unmet prerequisites is initially 0; the list
     of postrequisites is initially empty.
*/

void init_task(task *t, taskid taskname)			{
  int len=strlen(taskname);
  t->name=(char *) malloc(len+1);
  strcpy(t->name,taskname);
  t->unmet=0;
  t->link=NULL;
  t->postreqlist=NULL;						}


/* free the space associated with a task */

void delete_task(task *t)						{
  free(t->name);							}


/* Increment the number of unmet prerequisites of a task */

void incr_unmet(task *t)						{
  t->unmet++;								}


/* Decrement the number of unmet prerequisites of a task */

void decr_unmet(task *t)						{
  t->unmet--;								}


/* Decrement the number of unmet prerequisites for each task
     on the list of postrequisites of the current task
*/

void decr_list_unmet(task *t)						{
  task *curr=t->postreqlist;
  while (curr)							{
    decr_unmet(curr->main_entry);
    curr=curr->link;					        }	}


/* Add a prerequisite/postrequisite constraint by adding a new
     element to the postrequisite list of the prerequisite task,
     and pointing from this new element to the task "c" in the
     taskset.  Here "c" is the postrequisite and the implicit
     argument is the prerequisite.
*/

void add_constraint(task *pre, task *post)				{
  task *tt;
  tt=(task *) malloc(sizeof(task));
  init_task(tt,post->name);
  tt->link=pre->postreqlist;
  pre->postreqlist=tt;
  tt->main_entry=post;
  incr_unmet(post);							}


/*////////////////////// FUNCTIONS FOR TASKSETS ///////////////////////*/

/* Find a task in a set of tasks, by traversing the list representing
     the set until a task name matching the given name is found.
     If there's no match, return an empty pointer.  Otherwise, return
     a pointer to the task.
*/

task *find(taskset *ts, taskid taskname)				{
task *tcurr=ts->theader;
  while (tcurr && strcmp(tcurr->name,taskname)!=0)
    tcurr=tcurr->link;
  if (tcurr)
    return tcurr;
  else
    return NULL;                                                        }


/* Add a task with a given name to a task set by creating a new task
     with the given name and then inserting the new task to the front
     of the headed list representing the task set.
*/

task *add_task(taskset *ts, taskid taskname)                            {
  task *t;
  t=(task *) malloc(sizeof(task));
  init_task(t,taskname);
  assert(t);
  t->link=ts->theader->link;
  ts->theader->link=t;
  ts->theader->unmet++;
  return t;								}


/* Initialize a taskset, given a pointer to an uninitialized taskset
     and a file containing the list of prerequisites.  The function
     creates a header for the list of tasks, then reads pairs
     of tasknames, includes them in the list of tasks if they
     are not there already, and then puts the prerequiste/
     postrequisite pair on the postrequisite list of the
     prerequisite task.
   It returns TRUE or FALSE depending on whether the taskset was
     correctly initialized.  So far the only way initialization
     can be incorrect is if there is an odd number of tasks in
     the file.
*/

boolean init_taskset(taskset *ts, FILE *fp)				   {
  char pre[NAMELEN], post[NAMELEN];
  task *preptr,*postptr,*theader;
  theader=(task *) malloc(sizeof(task));
  init_task(theader,"dummy");
  ts->theader=theader;
  while (fscanf(fp,"%s",&pre)!=EOF)				{
    if (fscanf(fp,"%s",&post)==EOF)   			{
      printf("ill-formed input--odd number of tasks\n");
      ts->theader->link=NULL;
      return FALSE;					}
    preptr=find(ts,pre);
    if (!preptr)              /* if the prereq, task is new, */
      preptr=add_task(ts,pre);             /*  add it */
    postptr=find(ts,post);   /* if the postreq. task is new, */
    if (!postptr)                       /*  add it */
      postptr=add_task(ts,post);
    add_constraint(preptr,postptr);				}
  return TRUE;							  	}


/* free the space associated with a taskset           */

void delete_taskset(taskset* ts) 						{
  task *curr=ts->theader;
  task *temp,*pcurr,*ptemp;
  while (curr)							{
    temp=curr->link;
    pcurr=curr->postreqlist;
    while (pcurr) 					{
      ptemp=pcurr->link;
      delete_task(pcurr);
      free(pcurr);
      pcurr=ptemp;					}
    delete_task(curr);
    free(curr);
    curr=temp;							}
}


/* Topologically sort a task set, using the algorithm described in
     the top-level documentation.  An error message is returned
     if there is a cycle; this condition is checked by initializing
     a counter to the size of the taskset, decrementing it when
     each task is output, and then checking whether it's 0
     when the algorithm terminates.
*/

void topsort(taskset *ts /* ,FILE *fp */)					{
  boolean done=FALSE;
  task *curr;
  int counter=ts->theader->unmet;
  while (!done)							{
    curr=ts->theader->link;
    while (curr && curr->unmet!=0)			   {
      curr=curr->link;					   }
    if (curr)						   {
      printf("%s\n",curr->name);    /* output task */
      decr_unmet(curr);  /* and decrement its unmet count */
      decr_list_unmet(curr);	/* & that of all postreqs*/
      counter--;           /* and the taskset counter */   }
    else                   /* otherwise halt */
      done=TRUE;                                            	}
    if (counter==0)
      printf("this ordering accounts for all tasks\n");
    else                                                        {
      printf("there's a cycle--");
      printf("%3d tasks are not included above\n",counter);     }	}


/*/////////////////////// MAIN PROGRAM ////////////////////////*/

/* The main program merely creates an input stream given a file,
     constructs a taskset given the input stream,
     and topologically sorts the taskset to standard output if the
     input file is well formed (i.e., if the "init_taskset" function
     returns TRUE .  If the file is not found, an error message is
     printed.
*/

int main(void)                                                           {
FILE *fp;
taskset *s;
char filename[FILENMLEN];
  printf("enter input file name:  ");
  scanf("%s",&filename);
  fp=fopen(filename,"r");
  if (fp)					                {
    s=(taskset *) malloc(sizeof(taskset));
    if (init_taskset(s,fp))               	   	{
      topsort(s);
      delete_taskset(s);
      fclose(fp);             			   	}     	}
  else
    printf("file not found\n");
  return 0;                                                     	}