// 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 <iostream.h>
#include <fstream.h>
#include <assert.h>
#include "mytask6.h"


ostream & operator<<(ostream &os, taskset::task const *t)			{
  return os << t->name;							}

///////////////////////// MEMBER FUNCTIONS ////////////////////////////

///////////////////////////// FOR TASKs ///////////////////////////////

// Constructor for a task with identifier given by "taskname"
// The number of unmet prerequisites is initially 0; the list
//   of postrequisites is initially empty.

taskset::task::task(const taskid taskname):task_stub(taskname)							{
  link=NULL;
  postreqlist=NULL;						}


// Increment the number of unmet prerequisites of a task

void taskset::task::incr_unmet()							{
  unmet++;								}

// Decrement the number of unmet prerequisites of a taskset::task

void taskset::task::decr_unmet()							{
  unmet--;								}


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

void taskset::task::decr_list_unmet()						{
  taskset::task *curr=postreqlist;
  while (curr)							{
    curr->main_entry->decr_unmet();
    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 taskset::task::add_constraint(taskset::task *c)					{
  taskset::task *t=new taskset::task(c->name);
  assert(t);
  t->link=postreqlist;
  postreqlist=t;
  t->main_entry=c;
  c->incr_unmet();							}


//////////////////////////// FOR TASKSETs //////////////////////////////

// Constructor for tasksets, which, given an input stream,
//   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.
// A taskset is ill-formed iff the input stream contains an
//   odd number of tasks.  This is represented by placing
//   a negative value in the "unmet" field of the header.

taskset::taskset(istream &istr)						{
  char pre[NAMELEN], post[NAMELEN];
  task *preptr,*postptr;
  theader=new task("dummy");
  assert(theader);
  theader->link=NULL;
  theader->unmet=0;
  istr>>pre;       // !!!
  if (istr.eof())                        			{
    cout << "empty input file" << endl;
    theader->unmet=-1;  // signal ill-formedness
    return;                                             }
    while (!istr.eof()) {  // !!!
//  while (istr>>pre)						{
    if (istr >> post)					{
      preptr=find(pre);
      if (!preptr)              // if the prereq. task is new,
	preptr=add_task(pre);   //  add it
      postptr=find(post);       // if the postreq. task is new,
      if (!postptr)             //  add it
	postptr=add_task(post);
      preptr->add_constraint(postptr);
      istr>>pre;  	 	}  // !!!
    else						{
      theader->unmet=-1;    // signal ill-formedness
      return;			 			}	}      }


// The destructor for tasksets must delete each task on the list,
//   and for each task must delete each of its postrequisite tasks.

taskset::~taskset() 							{
  delete theader;
  theader=0;
  }

// This destructor should not delete the main entry; it's part
//   of another linked structure.  The links are deleted by the taskset
//   destructor

taskset::task::~task()							{
    delete name;
    name=NULL;
    delete link;
    link=NULL;
    delete postreqlist;
    postreqlist=NULL;
    main_entry=NULL;                                                    }


// 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.

taskset::task *taskset::find(const taskid taskname) const					{
taskset::task *tcurr=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.

taskset::task *taskset::add_task(const taskid taskname)                                  {
  task *t=new task(taskname);
  assert(t);
  t->link=theader->link;
  theader->link=t;
  theader->unmet++;
  return t;								}


// returns TRUE iff the taskset is ill-formed

boolean taskset::bad()  						{
  return theader->unmet<0;                                              }


// Topologically sort a task set, using the algorithm described in
//   the top-level documentation.
// A counter keeps track of the number of tasks not included in
//   the output--if this counter is nonzero at the end of the
//   algorithm, then not all tasks have been included in the
//   output.

void taskset::topsort(ostream & os) 					{
  boolean done=FALSE;
  task *curr;
  int counter=theader->unmet;
  while (!done)							{
    // find task with no unmet prereqs
    curr=theader->link;
    while (curr && curr->unmet!=0)			   {
      curr=curr->link;					   }
    // if one exists
    if (curr)						      {
      os << curr << endl; // add it to the output stream
      curr->decr_unmet();  // and decrement its unmet count
      curr->decr_list_unmet();	// & that of all postreqs
      counter--;         // & the size of the set
							      }
    else                   // otherwise halt
      done=TRUE;                                            	}
   if (counter==0)
      os << "this ordering accounts for all tasks" << endl;
    else                                                        {
      os << "there is a cycle-- ";
      os << counter << " tasks are not included above" << endl; }
    os << endl;                                                            }