/*
 *
 * Copyright (c) 1996 Rensselaer Polytechnic Institute
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Rensselaer Polytechnic Institute makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

// Read the TCS Genealogical Database file and display its tree structure
//   using indentation, with names ordered by Ph.D date.
#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <vector.h>
#include <map.h>
#include <multiset.h>
#include <algo.h>
#include <bstring.h>

// Define a type of map from strings to strings,
// ordered by alphabetic ordering of the keys.
typedef map<string, string, less<string> > data_map;

// Define a function object to compare persons in the database
// based on their associated dates.
// It includes static data members: dates and places.
struct earlier {
  bool operator()(const string& name1, const string& name2) const {
    return dates[name1] < dates[name2];
  }
  static data_map dates;
      // dates[name] holds year in which Ph.D degree was granted to name
  static data_map places;
      // places[name] holds institution that granted Ph.D
};

data_map earlier::dates;
data_map earlier::places;

// Define a type of multiset containing strings ordered by
// dates associated with names in the dates map.
typedef multiset<string, earlier> date_ordered_mset;

// Define a type of map from strings to date_ordered_msets
// ordered by alphabetic ordering of the keys;
typedef map<string, date_ordered_mset, less<string> >
        relation_map;

void output_tree(const string& name, relation_map& students,
		 data_map& places, data_map& dates,
		 int indentation_level = 0)
  // Output the tree rooted at name in the students map
{
  for (int k = 0; k != indentation_level; ++k)
    cout << "      ";
  cout << name << " (" << places[name] << " " << dates[name]
       << ")" << endl;
  date_ordered_mset& L = students[name];
  date_ordered_mset::const_iterator j;
  for (j = L.begin(); j != L.end(); ++j)
    output_tree(*j, students, places, dates, indentation_level + 1);
}

void get_chunk(istream& in, string& s, char terminator = '\t')
   // Get a string consisting of all the characters up to next terminator
{
   vector<char> v;
   v.reserve(20);
   char ch;
   in.get(ch);
   if (in.eof()) return;
   while (ch != terminator) {
     v.push_back(ch);
     in.get(ch);
   }
   s = v;
}

int main()
{
  ifstream ifs("TCS-genealogy.txt");

  string name, advisor, place, date;

  relation_map advisors, students;

  // Scan the theory-database file and build the maps
  while (true) {
    get_chunk(ifs, name);
    if (ifs.eof()) break;
    get_chunk(ifs, advisor);
    get_chunk(ifs, place);
    get_chunk(ifs, date, '\n');
    earlier::places[name] = place;
    earlier::dates[name] = date;
    if (advisor == "?")
       advisor = "---";
    students[advisor].insert(name);
    advisors[name].insert(advisor);
  }

  // Check for persons whose advisors have no advisor in the database
  //   and add an entry for each of them
  relation_map::iterator i;
  date_ordered_mset::iterator j;
  bool any_advisor;
  date_ordered_mset& roots = students["---"];
  for (i = advisors.begin(); i != advisors.end(); ++i) {
       any_advisor = false;
       for (j = (*i).second.begin(); j != (*i).second.end(); ++j) {
         if (*j == string("---") || advisors.find(*j) != advisors.end())
            any_advisor = true;
       }
       if (!any_advisor) {
          // None found, so insert the first advisor as a student of "---"
          string first_advisor = *((*i).second.begin());
          // Check if it is already there:
          //   must do linear search with generic find, since multiset is
          //   ordered based on dates rather than names (but the multiset
          //   size is not big enough for this to be a problem)
          if (find(roots.begin(), roots.end(), first_advisor)
                == roots.end())
            roots.insert(first_advisor);
       }
  }

  // Finally, output all the trees rooted at "---"
  for (j = roots.begin(); j != roots.end(); ++j)
       output_tree(*j, students, earlier::places, earlier::dates);
}