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


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


// task identifiers are just character strings

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


// 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:public taskset_stub					{
  private:
  class task:public task_stub					{
    friend taskset;
    friend ostream& operator<<(ostream&, const task *);
    private:
      task *postreqlist;    // without header
      task *link;
      task *main_entry;    // so postreq entries can point inside tasksets
      virtual void add_constraint(task *);  // arg is postreq ptr
      void incr_unmet();
      void decr_unmet();
      void decr_list_unmet();
    public:
      ~task();
      task(const taskid);					};
    // end of task
    task *theader;
    task *add_task(const taskid);  // returns ptr to new task
    task *find(const taskid) const;   // returns task or nil given name
  public:
    taskset(istream &);     // takes stream -- not necessarily from a file
   ~taskset();
    boolean bad();          // tests for ill-formed taskset
    void topsort(ostream &);					};
  // end of taskset