// This is the test program for Assignment 5, CS 146,
//   Section 6, Spring 2001, SJSU.  The "main" function
//   assumes an implementation of a "relation" class
//   template with methods "clear", "insert_pair", 
//   "size", "transitive_closure", and "related", 
//   as well as a 0-argument constructor, a copy 
//   constructor, and a version of the << operator.??


#include "relation.h"
#pragma warning(disable : 4786)
#include <string>
#include <iostream>


// an enumerated type for regions of greater NYC

enum region 
{manhattan,bronx,brooklyn,queens,richmond,
upstate,connecticut,long_island,new_jersey,san_rafael};


// synonyms for ugly type names

typedef pair<region,region> regionpair;
typedef pair<string,string> stringpair;
typedef pair<int,int> intpair;


// This overwritten version of the << operator is needed
//   due to a weakness in C++ -- elements of the enumerated
//   type are not available for I/O.

ostream& operator<<(ostream& os, const region s)  {
string names[]=
{"manhattan","bronx","brooklyn","queens","richmond",
"upstate","connecticut","long_island","new_jersey"};
	os << names[s];
	return os;                                        }


// The "main" function tests the "transitive_closure"
//   and other methods of a "relation" class template.

int main()                                 {

// the "ancestor" relation is the transitive closure
//   of the "parent" relation

  relation<string> parent;
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  parent.insert_pair("Henry II","Richard");
  parent.insert_pair("Henry II","John");
  parent.insert_pair("John","Henry III");
  parent.insert_pair("Henry III","Edward I");
  parent.insert_pair("Edward I","Edward II");
  parent.insert_pair("Edward II","Edward III");
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  parent.make_relation();
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  parent.transitive_closure();
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  parent.transitive_closure();
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  cout << endl;
  parent.clear();
  cout << "size = " << parent.get_size() << endl;
  cout << parent << endl;
  cout << endl;
  cout << endl << endl;


// The transitive closure of the adjacency relation
//   is a useful accessibility relation
  
  relation<region> adjacent;
  adjacent.insert_pair(upstate,upstate);
  adjacent.insert_pair(connecticut,connecticut);
  adjacent.insert_pair(bronx,bronx);
  adjacent.insert_pair(manhattan,manhattan);
  adjacent.insert_pair(new_jersey,new_jersey);
  adjacent.insert_pair(richmond,richmond);
  adjacent.insert_pair(brooklyn,brooklyn);
  adjacent.insert_pair(queens,queens);
  adjacent.insert_pair(long_island,long_island);

  adjacent.insert_pair(upstate,connecticut);
  adjacent.insert_pair(connecticut,upstate);
  adjacent.insert_pair(upstate,bronx);
  adjacent.insert_pair(bronx,upstate);
  adjacent.insert_pair(upstate,new_jersey);
  adjacent.insert_pair(new_jersey,upstate);
  adjacent.insert_pair(brooklyn,queens);
  adjacent.insert_pair(queens,brooklyn);
  adjacent.insert_pair(queens,long_island);
  adjacent.insert_pair(long_island,queens);
  adjacent.transitive_closure();
  adjacent.make_relation();
  
  // since the transitive_closure method is destructive,
  //   and we want to reuse the "adjacent" relation
  //   after applying this method to it, we make a copy
  //   of this relation
  // Note that since "make_relation" has been called
  //   on the "adjacent" relation, it needn't be 
  //   called on "a2".

  relation<region> a2=relation<region>(adjacent);

  a2.insert_pair(manhattan,brooklyn);
  a2.insert_pair(brooklyn,manhattan);
  a2.insert_pair(richmond,san_rafael);
  a2.insert_pair(san_rafael,richmond);

  cout << "size = " << adjacent.get_size() << endl;
  cout << adjacent << endl;
  cout << endl;
  adjacent.transitive_closure();
  adjacent.make_relation();
  cout << "size = " << adjacent.get_size() << endl;
  cout << adjacent << endl;
  cout << endl;

  cout << "size = " << a2.get_size() << endl;
  cout << a2 << endl;
  cout << endl;
  a2.transitive_closure();
  cout << "size = " << a2.get_size() << endl;
  cout << a2 << endl;
  cout << endl;
  cout << endl << endl;


// A language may be defined in terms of a grammar
//   by means of the transitive closure of a 
//   "rewritable" relation, where the rewriting is 
//   controlled in a simple way by the grammar
// In this example, the grammar allows rewriting of
//   S by NP VP
//   NP by Det N
//   VP by V NP
//   Det by "the" or "a"
//   N by "dog" or "cat"
//   V by "chased"
// Any string of words that is related to S in the
//   transitive closure is a string of the language

  relation<string> rewritable;
  rewritable.insert_pair(
	  "S","NP VP");
  rewritable.insert_pair(
	  "NP VP", "Det N VP");
  rewritable.insert_pair(
	  "Det N VP", "Det N V NP");
  rewritable.insert_pair(
	  "Det N V NP", "Det N V Det N");
  rewritable.insert_pair(
	  "Det N V Det N", "the N V Det N");
  rewritable.insert_pair(
	  "the N V Det N", "the dog V Det N");
  rewritable.insert_pair(
	  "the dog V Det N","the dog chased Det N");
  rewritable.insert_pair(
      "the dog chased Det N","the dog chased a N");
  rewritable.insert_pair(
	  "the dog chased a N","the dog chased a cat");
  rewritable.make_relation();
  cout << "size = " << rewritable.get_size() << endl;
  cout << rewritable << endl;
  rewritable.transitive_closure();
  cout << "size = " << rewritable.get_size() << endl;
  cout << rewritable << endl;
  cout << rewritable.related("S", "the dog chased a cat") << endl;
  cout << endl;
  rewritable.clear();


// The "modulo n" relation is the transitive closure
//   of the "differs by n" relation on integers.

  relation<int> differs_by_10;
  differs_by_10.insert_pair(1,11);
  differs_by_10.insert_pair(30,40);
  differs_by_10.insert_pair(10,20);
  differs_by_10.insert_pair(50,60);
  differs_by_10.insert_pair(20,30);
  differs_by_10.insert_pair(40,50);
  differs_by_10.insert_pair(60,70);
  differs_by_10.make_relation();

  cout << "size = " << differs_by_10.get_size() << endl;
  cout << differs_by_10 << endl;
  differs_by_10.transitive_closure();
  cout << "size = " << differs_by_10.get_size() << endl;
  cout << differs_by_10 << endl;

  cout << differs_by_10.related(10,60) << endl;
  cout << differs_by_10.related(1,60) << endl;
  cout << endl;
  differs_by_10.clear();
  cout << endl << endl;


// The transitive closure of a prerequisite
//   relation determines when one task is
//   an indirect prerequisite of another.
// No task should be related to itself by
//   the transitive closure relation!
// The given relation is a simplified 
//   version of the prerequisites among
//   courses required for the SJSU BSCS.

  relation<int> pq;
  pq.insert_pair( 46,146);
  pq.insert_pair( 46,140);
  pq.insert_pair(140,147);
  pq.insert_pair(147,149);
  pq.insert_pair( 46,145);
  pq.insert_pair( 31,146);
  pq.insert_pair( 42, 46);
  pq.insert_pair( 42,147);
  pq.insert_pair( 42,154);
  pq.insert_pair(146,160);
  cout << pq.related(147,149) << " " << endl;
  pq.make_relation();
  cout << pq.related(147,149) << " " << endl;
  cout << pq.related(148,147) << " " << endl;

  pq.transitive_closure();
  cout << "size = " << pq.get_size() << endl;
  cout << pq << endl;
  cout << endl;

  cout << pq.related(31,31) << " ";
  cout << pq.related(42,42) << " ";
  cout << pq.related(46,46) << " ";
  cout << pq.related(140,140) << " ";
  cout << pq.related(145,145) << " ";
  cout << pq.related(146,146) << " ";
  cout << pq.related(147,147) << " ";
  cout << pq.related(149,149) << " ";
  cout << pq.related(154,154) << " ";
  cout << pq.related(160,160) << " ";
  cout << endl;
  pq.clear();

  return 0;                                }