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

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



// task identifiers are just character strings

typedef char * taskid;


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

// The "task_stub" class has 2 data members -- a task identifier "name"
//   and an integer representing the number of unmet prerequisites
// There are member functions to increment or decrement the
//   number of unmet prerequistes of a task, add an element (or "constraint") to
//   the postrequisite list of a task, and and to decrement the number of
//   unmet prerequisites of each task for which the given task
//   is a prerequisite.



class task_stub							{
  protected:
    taskid name;                     // name of task
    int unmet;                       // # of unmet prereqs
    virtual void incr_unmet()=0;
    virtual void decr_unmet()=0;
    virtual void decr_list_unmet()=0;
    task_stub(taskid taskname)
      {int len=strlen(taskname);
       name=new char[1+len];
       assert(name);
       strcpy(name,taskname);
       unmet=0;              }
						};


// In the "taskset_stub" 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_stub						{
  protected:
    virtual boolean bad(void)=0;         // tests for ill-formed taskset
    virtual void topsort(ostream &)=0;					};