とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

理論計算機科学の系譜を表示するプログラム

STL―標準テンプレートライブラリによるC++プログラミング 第2版
辞書ファイル同様に必要な TCS-genealogy.txt を以下から入手する。
STL Tutorial Resources at Rensselaer -- Source Code for the Book's Example Programs
以下ソース。正直,だらだらしたコードで読んでらんない。正直,roots.insert 周りのforブロックは日本語でおkって感じだ。

// P273 ex18-01.cpp
#include<functional>
#include<string>
#include<map>
#include<set>
#include<iostream>
#include<fstream>
#include<algorithm>

typedef std::string Date;
typedef std::string Name;
typedef std::string Place;
typedef std::map<Date, Name> Name2Date;
typedef std::map<Place, Name> Name2Place;

struct Earlier
 : std::binary_function<std::string, std::string, bool>
{
 bool operator()(const std::string& name1, const std::string& name2)
 {
  return dates[name1] < dates[name2];
 }
 static Name2Date dates;
 static Name2Place places;
};
Name2Date Earlier::dates;
Name2Place Earlier::places;

typedef std::multiset<Date, Earlier> DateOrderdMset;
typedef std::map<Name, DateOrderdMset> RelationMap;

void OutputTree(const std::string& name, RelationMap& students,
                Name2Place& places, Name2Date& dates,
                int indentationLevel = 0)
{
 using std::cout;
 using std::endl;
 for(int i = 0; i != indentationLevel; ++i)cout << "    ";
 cout << name << " (" << places[name] << " " << dates[name] << ")" << endl;
 DateOrderdMset& l = students[name];
 for(DateOrderdMset::const_iterator j = l.begin(), end = l.end();
     j != end; ++j)
 {
  OutputTree(*j, students, places, dates, indentationLevel + 1);
 }
}

void GetChunk(std::istream& in, std::string& s, char terminator = '\t')
{
 s.clear();
 s.reserve(20);
 std::string::value_type ch;
 while(in.get(ch) && ch != terminator)
  s.insert(s.end(), ch);
}

int main()
{
 using std::cout;
 using std::flush;
 using std::endl;
 using std::string;
 using std::cin;
 using std::ifstream;
 using std::find;
 cout << "Displaying the SIGACT Theoretical Computer Science Genealogy\n"
  "First, enter the name of the file containing\n"
  "the genealogy data: " << flush;
 string fileName;
 cin >> fileName;
 ifstream ifs(fileName.c_str());
 if(!ifs.is_open()){
  cout << "Eh? Could not open file named " << fileName << endl;
  return 1;
 }

 RelationMap advisors, students;
 for(;;){
  string name, advisor, place, date;
  if(ifs.peek() == '#'){
   GetChunk(ifs, name, '\n');
   continue;
  }
  GetChunk(ifs, name);
  if(!ifs)break;
  GetChunk(ifs, advisor);
  GetChunk(ifs, place);
  GetChunk(ifs, date, '\n');

  Earlier::places[name] = place;
  Earlier::dates[name] = date;
  if(advisor == "?")advisor = "---";
  students[advisor].insert(name);
  advisors[name].insert(advisor);
 }

 DateOrderdMset& roots = students["---"];
 bool anyAdvisor;
 for(RelationMap::iterator i = advisors.begin(), end = advisors.end();
     i != end; ++i)
 {
  anyAdvisor = false;
  for(DateOrderdMset::iterator j = i->second.begin(), jend = i->second.end();
      j != jend; ++j)
  {
   if(*j == "---" || advisors.find(*j) != advisors.end())
    anyAdvisor = true;
  }
  if(!anyAdvisor){
   string firstAdvisor = *(i->second.begin());
   if(find(roots.begin(), roots.end(), firstAdvisor) == roots.end())
    roots.insert(firstAdvisor);
  }
 }

 for(DateOrderdMset::iterator j = roots.begin(), end = roots.end();
     j != end; ++j)
 {
  OutputTree(*j, students, Earlier::places, Earlier::dates);
 }
}