// Program to find all anagrams of a given word, using a dictionary
// read from a file
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef istream_iterator<string> string_input;


// 歡迎界面
void welcome()
{
	cout << "******************* 變位詞查找系統Version1******************\n"
		<< "在詞典中找出給定的字符串的所有變位詞" << endl;
}

// 讀入詞典文件,并對詞典單詞.進行詞典序排序
void readDict(vector<string> & dictionary)
{
	// 從用戶獲取文件名稱
	cout << "首先，請輸入詞典的文件名稱：" << endl;
	string dictionary_name; 
	cin >> dictionary_name;
	// 打開文件
	ifstream ifs(dictionary_name.c_str());
	// 讀入異常
	if (!ifs.is_open()) 
	{
		cerr << "異常：文件"<< dictionary_name 
			<< "沒有找到 " << endl;
		exit(1);
	}
	cout << "詞典讀入中 ..." << flush;
	// 將詞典文件內容讀入到字符串向量dictionary中
	copy(string_input(ifs), string_input(),
		back_inserter(dictionary));
	// 為便于后面的查找操作，對詞典排序
	sort(dictionary.begin(),dictionary.end());
	// 輸出詞典屬性
	cout << "詞典包含有 " 
		<< dictionary.size() << " 個單詞\n\n";
	// 關閉文件
	ifs.close();
}

// 獲取用戶單詞，查找變位詞并輸出
void analyseAnagram(const vector<string> & dictionary)
{
	cout << "請輸入單詞（或任意字母序列）" << endl;
	// 使用輸入流迭代器p接受用戶從標準輸入流cin輸入的字符串，
	// 直到用戶輸入流結束標志
	for (string_input p(cin); p != string_input(); ++p) 
	{
		cout << "查找輸入單詞的變位詞中..." << endl;
		string word = *p;
		// 對輸入word排序，以備進行全排列
		sort(word.begin(), word.end());
		// 記錄是否在詞典中查找變位詞成功
		bool found_one = false;

		do 
		{
			if (binary_search(dictionary.begin(),
					dictionary.end(),
					word))
			// 對詞典的詞條進行二分查找，如果查找成功，
			// 輸出該變位詞，設置found_one為true
			{
				cout << "  " << word ;
				found_one = true;
			}
		} while (next_permutation(word.begin(), word.end()));
			// 獲得按照詞典順序的下一個排列，如果成功，開始新一輪查找
		// 沒有找到的情形
		if (!found_one) 
			cout << "  抱歉，沒有找到變位詞\n";

		// 提示開始準備新的工作
		cout << "\n請輸入下一個單詞 " 
			<< "(或輸入end-of-file字符終止程序 ) \n"
			<< "<end-of-file字符在Windows平臺是Ctrl+Z，UNIX平臺是Ctrl+D>: " << endl;
	}
}
	



int main() 
{
	welcome();
	vector<string> dictionary;
	readDict(dictionary);
	analyseAnagram(dictionary);

	system("pause");
	return 0;
}