// Read the TCS Genealogical Database file and display its tree structure
// using indentation, with names ordered by Ph.D. date.
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include "earlier.h"
using namespace std;

typedef string Name;
typedef string Year;
typedef string Place;
typedef map<string, string> PropertyMap;
typedef multiset<string, earlier> DateOrderedMset;
typedef map<string, DateOrderedMset> AcademicRelation;
typedef DateOrderedMset::iterator IterMset;
typedef AcademicRelation::iterator IterRel;

// 進入界面
void welcome()
{
	cout << "************ 樹狀顯示SIGACT 理論計算機科學家譜系圖*************\n";
}


// 獲取數據源文件句柄放于ifs參數
void getDataSource(ifstream& ifs)
{
	// 源數據文件名稱
	string file_name;
	// 輸入文件名稱
	cout << "請輸入包含族譜數據的文件名稱: " ;
	cin >> file_name;
	// 打開文件
	ifs.open(file_name.c_str());
	// 如果打開失敗，報告異常，退出
	if (!ifs.is_open()) 
	{
		cout << "異常：文件"<< file_name << "沒有找到 " 
			<< endl;
		exit(1);
	}
}

// 構造數據關系模型
void modelView(AcademicRelation& advisors, 
			   AcademicRelation& students,
			   ifstream& ifs)
{
	string name, advisor, place, year;
	// 析取數據源并建立合適結構
	while(ifs)
		// 如果未到文件末尾
	{
		// 忽略注釋
		if (ifs.peek() == '#')
		{
			getline(ifs,name,'\n');
			continue;
		}
		// 逐行讀取4個域
		getline(ifs, name, '\t');
		getline(ifs, advisor, '\t');
		getline(ifs, place, '\t');
		getline(ifs, year ,'\n');
			// 一行結束，間隔符為換行符
		// 構造博士畢業時間、地點屬性結構
		earlier::placeProp[name] = place;
		earlier::dateProp[name] = year;
		// 不確定的導師信息統一用"---"表示
		if (advisor == "?")
			advisor = "---";
		// 構造導師--學生關系結構
		students[advisor].insert(name);
		advisors[name].insert(advisor);
	}
	// 關閉源數據文件
	ifs.close();
}

// 構造族譜森林的根節點集合
// 沒有導師信息的科學家為根節點
DateOrderedMset& setupRootSet( AcademicRelation& advisors, 
							   AcademicRelation& students)
{
	// 初始化根節點集合為導師信息為"---"的學生
	DateOrderedMset& roots = students["---"];
	// 定義遍歷導師映射的迭代器
	IterRel iter_rel;
	// 定義遍歷各個學生對應導師集合的迭代器
	IterMset iter_set; 
	// 是否存在導師信息？
	bool existAdvisor;
	// 遍歷導師映射
	for (iter_rel = advisors.begin(); iter_rel != advisors.end(); ++iter_rel) 
	{
		existAdvisor = false;
		// 當前學生的導師集合容器開始迭代器
		IterMset iter_set_b = iter_rel->second.begin(); 
		// 當前學生的導師集合容器結束迭代器
		IterMset iter_set_e = iter_rel->second.end(); 
		for (iter_set = iter_set_b; iter_set != iter_set_e; ++iter_set)
		{
			// 如果該學生的導師為---（未知），則初始化時已經在根集合中
			// 如果該學生的導師在數據庫中查找出來，則該學生肯定不屬于根集合
			// 以上兩種情況下，將existAdvisor設為true，不予后續處理
			if (*iter_set == string("---") || 
				advisors.find(*iter_set) != advisors.end())
				existAdvisor = true;
		}
		// 如果不存在導師（信息）
		if (!existAdvisor) 
		{
			string first_advisor = *(iter_rel->second.begin());
			// 檢查它是否已經存在于根集合中:
			//   因為multiset roots是依據name的日期屬性排序
			//   因此這個find操作是線性時間復雜度
			//   對于當前問題規模，這不是一個麻煩 
			if ( find(roots.begin(), roots.end(), first_advisor)
				 == roots.end())
			roots.insert(first_advisor);
				// 如果不在根集合中，則插入根集合
		}
	}
	return roots;
}

// 打印以root_name為根的學術樹
// 以合適的縮進格式表示師承關系
// 顯示他（她）的所有后代師承
// 遞歸調用
void tree_view(const string& root_name, 
			   AcademicRelation& students,
			   PropertyMap& placeProp, 
			   PropertyMap& dateProp,
			   ostream& out,
			   int indentation_level = 0)
{
	// 根據縮進層次顯示合適的行縮進量
	for (int k = 0; k != indentation_level; ++k)
		out << "      ";
	// 打印學生的博士學位信息
	// 格式如： Brian Kernighan (Princeton 1969）
	out << root_name << " (" << placeProp[root_name] << " " 
		<< dateProp[root_name]<< ")" << endl;
	DateOrderedMset& L = students[root_name];
	DateOrderedMset::const_iterator j;
	// 打印該科學家的所有學生信息
	// 遍歷他的整個學生集合
	// 按照日期順序，并增加一層縮進
	for (j = L.begin(); j != L.end(); ++j)
		// 遞歸調用
		tree_view (*j, students, placeProp, dateProp, out,
					indentation_level+1);
}

// 顯示根節點集合代表的各棵樹
void forest_view(const DateOrderedMset& roots,
				 AcademicRelation& students)
{
	DateOrderedMset::const_iterator iter;
	//遍歷根節點集合，輸出各個根對應樹
	cout << "請選擇輸出SIGACT 理論計算機科學家譜系圖" << endl
		<< "1. 輸出到屏幕\n" << "2. 輸出到文件\n"
		<< "請輸入1或2選擇：";
	int selector;
	cin >> selector;
	if (selector == 1)
		// 輸出到屏幕
		for (iter = roots.begin(); iter != roots.end(); ++iter)	
		{
			tree_view(*iter, students, earlier::placeProp, earlier::dateProp, cout);
			system("pause");
			cout << endl;
		}
	else
		//輸出到文件
	{
		cout << "請給出輸出文件名" << endl;
		string viewName;
		cin >> viewName;
		ofstream ofs(viewName.c_str());
		cout << "文件創建中..." << endl;
		for (iter = roots.begin(); iter != roots.end(); ++iter)
			// 輸出到文件
			tree_view(*iter, students, earlier::placeProp, earlier::dateProp, ofs);
		// 關閉文件
		ofs.close();
		cout << "文件創建成功！" << endl;
	}	
}


int main()
{
	// 程序進入界面，說明程序功能
	welcome();
	// 獲取數據源文件句柄
	ifstream ifs;
	getDataSource(ifs);	 
	// 定義師生關系映射變量
	AcademicRelation advisors, students;
	// 從數據源構建各科學家關系和屬性
	modelView(advisors,students,ifs);
	// 初始化根節點集合為導師信息為"---"的學生
	DateOrderedMset roots = setupRootSet(advisors,students);
	// 顯示整個結果集合
	forest_view(roots,students);
	return 0;
}