// 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
//   represented as an instance of the class "taskset" is constructed
//   from the components of the pairs of the relation.

// The style and documentation of this program are intentionally
//   substandard.  In particular, there are no destructors, there
//   is no modularity, constant parameters are not labeled.  Also,
//   the output operator "<<" could have been overloaded for tasks,
//   but was not.

#include <stdlib.h>
#include <string.h>
#include <iostream.h>
#include <fstream.h>
#include <assert.h>

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

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


// task identifiers are just character strings

typedef char* taskid;


//////////////////////////// CLASSES ////////////////////////////////

// The "task" class has 5 data members -- 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 data member "main_entry" is used to point
//   from tasks that are members of postrequisite lists to corresponding
//   tasks in task sets.
// The constructor takes a task identifier (here, a character string)
//   as its sole argument.  Other member functions must be made accessible
//   to "taskset" objects.  These functions increment or decrement the
//   number of unmet prerequistes, add an element (or "constraint") to
//   the postrequisite list of a task, and decrement the number of
//   unmet prerequisites of each element of a postrequisite list.


class task							{
  friend class taskset;
  private:
    taskid name;
    int unmet;
    task *postreqlist;    // without header
    task *link;
    task *main_entry;    // so postreq entries can point inside tasksets
    void add_constraint(task *);  // arg is postreq ptr
    void incr_unmet();
    void decr_unmet();
    void decr_list_unmet();
  public:
    task(taskid);						    };

// An instance of the "taskset" class is represented as a headed linked
//   list of tasks.  The constructor takes an istream .  A public
//   "topsort" function applies to tasksets and adds the output
//   sequence of task identifiers to an output stream (ostream).  Both
//   istreams and ostreams are associated with files in this program,
//   but in principle need not be.
// The header keeps a count of the size of the set of tasks in its
//   "unmet" field.
// The "add_task" function creates and adds a task with a given identifier
//   to the set.  It returns a pointer to the new task.  The "find_task"
//   function finds the task with a given identifier, returning a pointer
//   to it (or NULL if none exists).  A "bad" predicate determines
//   whether a taskset is ill-formed (that is, whether the input file
//   from which it was constructed was ill-formed).


class taskset							{
  private:
    task *theader;
    task *add_task(taskid);  // returns ptr to new task
    task *find(taskid);   // returns task or nil given name
  public:
    taskset(istream &);     // takes stream -- not necessarily from a file
    boolean bad();          // tests for ill-formed taskset
    void topsort(ostream &);					};



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

task::task(taskid taskname)					{
  int len=strlen(taskname);
  name=new char[1+len];
  assert(name);
  strcpy(name,taskname);
  unmet=0;
  link=NULL;
  postreqlist=NULL;						}


// Increment the number of unmet prerequisites of a task

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

// Decrement the number of unmet prerequisites of a task

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


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

void task::decr_list_unmet(void)					{
  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 task::add_constraint(task *c)					{
  task *t=new 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;
  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);  	 	}
    else						{
      theader->unmet=-1;    // signal ill-formedness
      return;			 			}	}      }


// 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 *taskset::find(taskid taskname)					{
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.

task *taskset::add_task(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(void)						{
  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->name << 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;                                                            }



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

int main(void)                                                           {
ifstream istr;
taskset *s;
char filename[FILENMLEN];
    cout << "enter input file name:  ";
    cin >> filename;
    istr.open(filename);
    if (istr)					{
      s=new taskset(istr);
      if (!s->bad())
	s->topsort(cout);
      else
	cout << "ill-formed input" << endl;
      delete s;     				}
    else
      cout << "file not found" << endl;
  istr.close();
  return 0;                                                     	}