/*
	@ 后面可以进行打印输出，查看first集，follow集，action表，goto表，状态转化图 等等
	@ first、follow、action、goto、状态转化图均动态生成
	@ 输入：token.txt grammar.txt
	@ 文法开始符号为 P
 	@ @ 表示空字符串
 	@ 运行-命令行
 	g++ 试验二.cpp
 	a
*/

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<stack>
#include<cstdio>

using namespace std;
struct Symbol //文法符号
{
	string name; //符号名
	int type;    //0 终结符号 1 非终结符号
	friend bool operator== (Symbol s1,Symbol s2){ // 重载符号相等
		return s1.name==s2.name;
	}
	friend bool operator!= (Symbol s1,Symbol s2){ // 重载符号相等
		return s1.name!=s2.name;
	}
};
Symbol kong;// 空字符串

struct myHashFuc
{
	size_t operator()(const Symbol &key) const
	{
		return hash<string>()(key.name);
	}
};

struct ProductionExpression
{
	Symbol left;            // 产生式左部
	vector<vector<Symbol> > rights;  // 产生式右部
	// 左部可能有多个产生式，所以用两重vector来存储
};

struct Item // 项集中的一个项
{
	int wrapperidx; // 点对应exps 第一层的下标
	int expidx;     // 点对应exps 第二层的下标
	int pos;        // 点在产生式中的位置 (0 位最左边)
	Item(int w,int e,int p) : wrapperidx(w), expidx(e),pos(p){}
};

struct Direction
{
	int state;    // 转移到的方向
	string name;  // 接受的符号
	Direction(int s,string n) : state(s), name(n){}
};
struct Items // 项集
{
	int id;                     // 项集编号
	vector<Item> kernelItems;   // 项集中的内核项
	vector<Item> nonKernelItems;// 项集中的非内核项
	vector<Direction> directions;     //项集所指的其他项的下标
    // 重载相等运算符
    friend bool operator== (Items n1, Items n2) // 项集相等保证内核项相同即可
    {
        if (n1.kernelItems.size()!=n2.kernelItems.size()){
        	return false;
        }
        const int n = n1.kernelItems.size();
        vector<bool> visited(n,false);
        for (int i = 0;i<n;++i){
        	bool flag = false;
        	for (int j = 0;j<n;++j){
        		if (!visited[j] && n1.kernelItems[i].wrapperidx==n2.kernelItems[j].wrapperidx
        						&& n1.kernelItems[i].expidx==n2.kernelItems[j].expidx
        						&& n1.kernelItems[i].pos==n2.kernelItems[j].pos){
        			visited[j] = true;
        			flag = true;
        		}
        	}
        	if (!flag) return false;
        }
        return true;
    }
};

struct Act
{
	int type; // 0 移入 1规约
	int state;// 移入进入哪个状态 or 规约对应表达式的第一个编号
	int expidx; //规约对应表达式的第二个编号
};
/*
	@功能 求出items所有非内核项，并且为其赋值
	@参数 exps:所有生成式 items:内核项已经填好的项集
	@返回值 空
*/
void closeure(vector<ProductionExpression> &exps,Items &items){
	// 求出非内核项
	queue<Item> q; //访问队列
	unordered_set<string> visited; // 被访问过非终结符集合
	for(int i = 0;i<items.kernelItems.size();++i){
		q.push(items.kernelItems[i]);
	}
	while(!q.empty()){
		Item item = q.front();
		q.pop();
		int wrapperidx = item.wrapperidx;
		int expidx = item.expidx;
		int pos = item.pos;

		if (pos==exps[wrapperidx].rights[expidx].size()){
			// 点已经移动到了最后一个
			continue;
		}
		string name = exps[wrapperidx].rights[expidx][pos].name;
		if (visited.find(name)!=visited.end()){
			// 已经找了
			continue;
		}
		if (!isupper(name[0])){
			// 不是非终结符
			continue;
		}
		visited.insert(name);
		for(int j = 0; j < exps.size();++j){
			if (exps[j].left.name == name){
				for (int k = 0;k<exps[j].rights.size();++k){
					Item itemTmp(j,k,0);
					if (exps[j].rights[k][0].name=="@"){
						itemTmp.pos=1;
						items.kernelItems.push_back(itemTmp);  // 作为内核项
					}
					else{
						items.nonKernelItems.push_back(itemTmp);
					}
					q.push(itemTmp);
				}
				break;
			}
		}
	}
}
/*
	@功能 求出项集所有下一项（点的下一个符号）名称，放到names里面
	@参数 exps 所有生成式 items 所求项集 names 为符号名称
	@返回值 空
*/

void getAllNames(vector<ProductionExpression> &exps,Items &items,vector<string> &names){
	for (int i = 0;i<items.kernelItems.size();++i){
		int wrapperidx = items.kernelItems[i].wrapperidx;
		int expidx = items.kernelItems[i].expidx;
		int pos = items.kernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		bool flag = false;
		for(int j = 0;j<names.size();++j){
			if (names[j] == exps[wrapperidx].rights[expidx][pos].name){
				flag = true;
				break;
			}
		}
		if (!flag){
			names.push_back(exps[wrapperidx].rights[expidx][pos].name);
		}
	}
	for (int i = 0;i<items.nonKernelItems.size();++i){
		int wrapperidx = items.nonKernelItems[i].wrapperidx;
		int expidx = items.nonKernelItems[i].expidx;
		int pos = items.nonKernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		bool flag = false;
		for(int j = 0;j<names.size();++j){
			if (names[j] == exps[wrapperidx].rights[expidx][pos].name){
				flag = true;
				break;
			}
		}
		if (!flag){
			names.push_back(exps[wrapperidx].rights[expidx][pos].name);
		}
	}
}

/*
	@功能 求出项集items接收到name符号进入的下一个项集
	@参数 exps 所有生成式 items 源项集 name 接收到的符号名称
	@返回值 下一个项集，已经包含所有内核项
*/
Items GoTo(vector<ProductionExpression> &exps,Items &items,string name){
	Items res;
	// vector<Item> kernelItems;
	for (int i = 0;i<items.kernelItems.size();++i){
		int wrapperidx = items.kernelItems[i].wrapperidx;
		int expidx = items.kernelItems[i].expidx;
		int pos = items.kernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx].size()==pos){// 点移动到了最后
			continue;
		}
		if (exps[wrapperidx].rights[expidx][pos].name == name){
			res.kernelItems.push_back(Item(wrapperidx,expidx,pos+1)); // 向右移动了一个单位
		}
	}
	for (int i = 0;i<items.nonKernelItems.size();++i){
		int wrapperidx = items.nonKernelItems[i].wrapperidx;
		int expidx = items.nonKernelItems[i].expidx;
		int pos = items.nonKernelItems[i].pos;
		if (exps[wrapperidx].rights[expidx][pos].name == name){
			res.kernelItems.push_back(Item(wrapperidx,expidx,pos+1)); // 向右移动了一个单位
		}
	}
	return res;
}

/*
	@功能 求出first集合，放到first中
	@参数 exps 所有生成式 first集合(引用类型)
	@返回值 空
*/
void First(vector<ProductionExpression> &exps,unordered_map<Symbol,vector<Symbol>, myHashFuc > &first){
	for (int i = 0;i<exps.size();++i){// 终结符first初始化
		for(int j = 0;j<exps[i].rights.size();++j){
			for (int k = 0;k<exps[i].rights[j].size();++k){
				Symbol sym = exps[i].rights[j][k];
				if (sym.type==0&&find(first[sym].begin(),first[sym].end(),sym)==first[sym].end()){
					first[sym].push_back(sym);
				}
			}
		}
	}

	while(true){ // 遍历产生式
		bool flag = true;// 产生标记
		for(int i = 0;i<exps.size();++i){
			Symbol symLeft = exps[i].left;
			for (int j = 0;j<exps[i].rights.size();++j){
				bool kongFlag = true;
				for (int k = 0;k<exps[i].rights[j].size();++k){
					Symbol symRight = exps[i].rights[j][k];
					if (symRight.type == 0&&find(first[symLeft].begin(),first[symLeft].end(),symRight)==first[symLeft].end()&&kong!=symRight){
						//终结符
						first[symLeft].push_back(symRight);
						flag = false;
						kongFlag = false;
						break;
					}
					else if (kong!=symRight){
						for (int l = 0;l<first[symRight].size();++l){
							if (find(first[symLeft].begin(),first[symLeft].end(),first[symRight][l])==first[symLeft].end()&&kong!=first[symRight][l]&&kong!=first[symRight][l]){
								first[symLeft].push_back(first[symRight][l]);
								flag = false;
							}
						}
						if (find(first[symRight].begin(),first[symRight].end(),kong)==first[symRight].end()){
							kongFlag = false;
							break;
						}
					}
				}
				if (kongFlag&&find(first[symLeft].begin(),first[symLeft].end(),kong)==first[symLeft].end()){
					first[symLeft].push_back(kong);
					flag = false;
				}
			}
		}
		if (flag) break; // 没有一轮新加入的就算法结束
	}
}
/*
	@功能 求出Follow集 类比first
	@参数 类比first
	@返回值 空
*/
void Follow(vector<ProductionExpression> &exps,
			unordered_map<Symbol,vector<Symbol>, myHashFuc > &first,
			unordered_map<Symbol,vector<Symbol>, myHashFuc > &follow){
	while(true){ // 遍历产生式
		bool flag = true;// 产生标记
		for(int i = 0;i<exps.size();++i){
			Symbol symLeft = exps[i].left;
			for (int j = 0;j<exps[i].rights.size();++j){
				bool kongFlag = true;
				for (int k = exps[i].rights[j].size()-1;k>=0;--k){
					Symbol symRight = exps[i].rights[j][k];
					if (kongFlag){
						for(int l = 0;l<follow[symLeft].size();++l){
							if (find(follow[symRight].begin(),follow[symRight].end(),follow[symLeft][l])!=follow[symRight].end()){
								continue;
							}
							follow[symRight].push_back(follow[symLeft][l]);
							flag = false;
						}
						if (find(first[symRight].begin(),first[symRight].end(),kong)==first[symRight].end()){
							kongFlag = false;
						}
					}
					for (int l = k+1;l<exps[i].rights[j].size();++l){
						Symbol tmp = exps[i].rights[j][l];
						for (int l1 = 0;l1<first[tmp].size();++l1){
							if (kong==first[tmp][l1]){
								continue;
							}
							if (find(follow[symRight].begin(),follow[symRight].end(),first[tmp][l1])!=follow[symRight].end()){
								continue;
							}
							follow[symRight].push_back(first[tmp][l1]);
							flag = false;
						}
						if (find(first[tmp].begin(),first[tmp].end(),kong)==first[tmp].end()){
							break;
						}
					}
				}
			}
		}
		if (flag) break; // 没有一轮新加入的就算法结束
	}
}
/*
	@功能 求出action表和goto表
	@参数 exps 所有生成式 allItems 所有项集(集族) follow表 ACTION GOTO 引用类型直接对其赋值
	@返回值 空
*/
void action_goto(vector<ProductionExpression> &exps,
				 vector<Items> &allItems,
				 unordered_map<Symbol,vector<Symbol>, myHashFuc > &follow,
				 unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &ACTION,
				 unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &GOTO){
	for (int i = 0;i<allItems.size();++i){
		for (int j = 0;j<allItems[i].directions.size();++j){
			Symbol sym;
			sym.name = allItems[i].directions[j].name;
			if (!isupper(allItems[i].directions[j].name[0])){
				// cout<<i<<" "<<sym.name<<" "<<allItems[i].directions[j].state<<endl;
				sym.type = 0;
				ACTION[i][sym].type = 0;
				ACTION[i][sym].state = allItems[i].directions[j].state;
			}
			else{
				GOTO[i][sym].state = allItems[i].directions[j].state;
			}
		}
		for(int j = 0;j<allItems[i].kernelItems.size();++j){
			int wrapperidx = allItems[i].kernelItems[j].wrapperidx;
			int expidx = allItems[i].kernelItems[j].expidx;
			int pos = allItems[i].kernelItems[j].pos;
			if (exps[wrapperidx].rights[expidx].size()==pos){ // 点移动到了最后
				//可以规约了
				Symbol left = exps[wrapperidx].left;
				vector<Symbol> reduction = follow[left];
				for (int k = 0;k<reduction.size();++k){
					if (ACTION[i].find(reduction[k])!=ACTION[i].end()){
						int type = ACTION[i][reduction[k]].type;
						if (type==0) {
							cout<<i<<endl;
							cout<<reduction[k].name<<endl;
							cout<<"s-r crash!"<<endl;
							// exit(0);
						}
						else{
							// cout<<reduction[k]<<endl;
							cout<<3<<endl;
							cout<<"r-r crash!"<<endl;
							ACTION[i][reduction[k]].type = 1;
							ACTION[i][reduction[k]].state = wrapperidx; // else 如果选择匹配最近if的话 选择移入
							ACTION[i][reduction[k]].expidx = expidx;
							// exit(0);
						}
					}
					else{
						ACTION[i][reduction[k]].type = 1;
						ACTION[i][reduction[k]].state = wrapperidx; // else 如果选择匹配最近if的话 选择移入
						ACTION[i][reduction[k]].expidx = expidx;
					}
				}
			}
		}
	}
}
/*
	@功能 处理词法分析得到的token序列 打印产生式
	@参数 sym 传来的符号 ......
	@返回值 -1 处理错误 0 成功 1 归约 2 移入
*/
// -1 处理错误 0 成功 1 归约 2 移入
int Process(Symbol sym,
			vector<ProductionExpression> &exps,
			unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &ACTION,
			unordered_map<int,unordered_map<Symbol,Act,myHashFuc> > &GOTO,
			stack<Symbol> &symStack,
			stack<int> &stateStack){
	if (ACTION[stateStack.top()].find(sym)==ACTION[stateStack.top()].end()){
		// cout<<sym.name<<endl;
		cout<<sym.name<<" error1"<<endl;
		return -1;
	}
	else if (stateStack.top()==1&&stateStack.size()==2&&sym.name=="$"){ //"01"右边为栈顶
		// 成功识别
		cout<<sym.name<<" success"<<endl;
		return 0;
	}
	Act act = ACTION[stateStack.top()][sym];
	if (act.type==0){// 移入
		symStack.push(sym);
		stateStack.push(act.state);
		// cout<<sym.name<<"-shift"<<endl;
		// cout<<stateStack.top()<<endl;
		return 2;
	}
	else{  //规约
		int expressLen = exps[act.state].rights[act.expidx].size();
		if(exps[act.state].rights[act.expidx][0].name=="@") expressLen = 0;// 空式子不弹栈
		for (int i = 0;i<expressLen;++i){
			symStack.pop();
			stateStack.pop();
		}
		symStack.push(exps[act.state].left);
		if(GOTO[stateStack.top()].find(exps[act.state].left)==GOTO[stateStack.top()].end()){
			cout<<sym.name<<" error2"<<endl;
			return -1;
		}
		// cout<<sym.name<<"-reduction"<<endl;
		// cout<<exps[act.state].left.name<<"->";
		// for (int i = 0;i<exps[act.state].rights[act.expidx].size();++i){
		// 	cout<<exps[act.state].rights[act.expidx][i].name<<" ";
		// }
		// cout<<endl;
		stateStack.push(GOTO[stateStack.top()][exps[act.state].left].state);
		return 1;
	}
}
/*
	@功能 读文件 获取所有token
	@参数 syms 引用类型 读到的放到这个变量里面
	@返回值 空
*/
// void getSymbols(vector<Symbol> &syms){
// 	ifstream inf;
// 	inf.open("token.txt");
// 	string s;
// 	while(getline(inf,s)){
// 		Symbol sym;
// 		sym.type = 0;
// 		bool start = false;
// 		string s1,s2;
// 		for (int i = 0;i<s.size();++i){
// 			if (start){
// 				s2 += s[i];
// 			}
// 			else if (s[i]!=' '){
// 				s1 += s[i];
// 			}
// 			if (s[i]==' ') start = true;
// 		}
// 		if (s1=="id"||s1=="digits"){
// 			sym.name = s1;
// 		}
// 		else{
// 			sym.name = s2;
// 		}
// 		syms.push_back(sym);
// 	}
// }
void getSymbols(vector<Symbol> &syms){
	ifstream inf;
	inf.open("src.txt");
	string s;
	while(getline(inf,s)){
		Symbol sym;
		sym.type = 0;
		sym.name = s;
		syms.push_back(sym);
	}
	inf.close();
}
void printStack(stack<Symbol> &symStack,stack<int> &stateStack,string symName){
	stack<Symbol> tmp;
	stack<int> tmp2;
	const int size = symStack.size();
	string s = "Symbol:$ ";
	string s2 = "State:0 ";
	for(int i = 0;i<size;++i){
		tmp.push(symStack.top());
		tmp2.push(stateStack.top());
		symStack.pop();
		stateStack.pop();
	}// 栈顶第一个 栈顶第二个 。。。
	for (int i = 0;i<size;++i){
		s += tmp.top().name+" ";
		char c[8];
		sprintf(c,"%d",tmp2.top()); 
		string stmp2(c);
		s2 += stmp2+" ";
		symStack.push(tmp.top());
		stateStack.push(tmp2.top());
		tmp.pop();
		tmp2.pop();
	}
	cout<<s<<endl;
	cout<<s2<<endl;
	cout<<"next:"<<symName<<endl<<endl;
}



int main(int argc, char const *argv[])
{
	ifstream inf;
	inf.open(argv[2]); //文法文件
	string s;
	vector<ProductionExpression> exps; // 所有的产生式子
	/*
		1.文法预处理
	*/
	ProductionExpression expStart;     // 增广文法
	vector<Symbol> rightStart;         //
	Symbol symStart;
	symStart.name = argv[1];               // 开始符号 增广文法
	symStart.type = 1;
	rightStart.push_back(symStart);
	expStart.rights.push_back(rightStart);
	expStart.left.name = "EE";
	expStart.left.type = 1;
	exps.push_back(expStart);

	while(getline(inf,s)){
		bool first = true; // 第一个字符为左部 标记一番
		int p1 = 0,p2 = 0; // 设置双指针找到子串
		int leftidx = -1;  // 产生式的下标
		vector<Symbol> expright;// 产生式右部
		for (int i = 0;i<s.size();++i){
			if (s[i]==' '){
				p2 = i;
				if (first){
					string left = s.substr(p1,p2-p1);
					if (!isupper(left[0])){
						cout<<"error : left is not upper symbol! failed"<<endl;
						exit(0);
					}
					// 找到一样的左部
					for(int j = 0; j < exps.size();++j){
						if (exps[j].left.name == left){
							leftidx = j;
							break;
						}
					}
					if (leftidx == -1){
						leftidx = exps.size();
						ProductionExpression exp;
						exp.left.name = left;
						exp.left.type = 1;
						exps.push_back(exp);
					}
					first = false;
				}
				else{
					Symbol sym;
					sym.name = s.substr(p1,p2-p1);
					sym.type = int(isupper(sym.name[0]));
					if (sym.name=="|"){
						exps[leftidx].rights.push_back(expright);
						expright.clear();
					}
					else{
						expright.push_back(sym);
					}
				}
				p1 = p2+1;
			}
			else if (i ==  s.size()-1){ // grammar.txt 产生式最后一个符号不为|
				p2 = i;
				Symbol sym;
				sym.name = s.substr(p1,p2-p1+1);
				sym.type = int(isupper(sym.name[0]));
				expright.push_back(sym);
				exps[leftidx].rights.push_back(expright);
			}
		}
	}
	inf.close();

	// 输出符合预期
	for(int i = 0;i<exps.size();++i){
		cout<<exps[i].left.name<<"->";
		for (int j = 0;j<exps[i].rights.size();++j){
			for (int k = 0;k<exps[i].rights[j].size();++k){
				cout<< exps[i].rights[j][k].name <<" ";
			}
			cout<<"|";
		}
		cout<<endl;
	}
	/*
		2. 求闭包 生成项集转化图
		需要用到前面计算结果 exps; // 所有的产生式子
		产生状态转换图 allItems
	*/
	kong.name = "@";
	kong.type = 0;
	vector<Items> allItems;// 集族

	// 最开始的一项
	Items items0;

	Item itemStart(0,0,0);
	items0.kernelItems.push_back(itemStart);

	closeure(exps,items0);  // 获取第1项的 非内核项
	items0.id = 0;          // 第一项的编号为0
	queue<Items> Qitems;    //所有项集
	Qitems.push(items0);
	allItems.push_back(items0);
	int count = 1;
	while(!Qitems.empty()){
		Items items = Qitems.front();
		Qitems.pop();
		vector<string> names;         // 所有的符号名字
		getAllNames(exps,items,names);// 获取第1项 所有点的下一项符号名字
		for (int i = 0;i<names.size();++i){
			if (names[i]=="@") continue;
			Items items2 = GoTo(exps,items,names[i]);
			bool flag = false;
			for (int j = 0; j<allItems.size();++j ){
				if (allItems[j]==items2){
					flag = true;
					allItems[items.id].directions.push_back(Direction(allItems[j].id,names[i]));
					break;
				}
			}
			if (!flag){
				closeure(exps,items2);
				items2.id = count++;  // 序号 也是allItems 下标
				Qitems.push(items2);
				allItems[items.id].directions.push_back(Direction(items2.id,names[i]));
				allItems.push_back(items2);
			}
		}
	}
/*
	3. 求出first集合和follow集合
*/
	unordered_map<Symbol,vector<Symbol>, myHashFuc > first;
	unordered_map<Symbol,vector<Symbol>, myHashFuc > follow;
	Symbol end;                        //初始化follow集
	end.name = "$";
	end.type = 0;
	follow[expStart.left].push_back(end); // 开始符号的follow集为"$"
	First(exps,first);
	Follow(exps,first,follow);
/*
	4. action表和goto表
*/
	unordered_map<int,unordered_map<Symbol,Act, myHashFuc> > ACTION;
	unordered_map<int,unordered_map<Symbol,Act, myHashFuc> > GOTO;
	action_goto(exps,allItems,follow,ACTION,GOTO); // 产生action表和goto表

/*
	5. 入栈处理和出栈处理
*/

	stack<Symbol> symStack;// 符号栈
	stack<int> stateStack; // 状态栈
	stateStack.push(0);    // 初始状
	string flags(argv[3]);
	if (flags=="make"){
		vector<Symbol> syms;
		getSymbols(syms);   // 获取所有符号
		// for (int i = 0;i<syms.size();++i){
		// 	while(Process(syms[i],exps,ACTION,GOTO,symStack,stateStack)==1);
		// }

		cout<<endl;
		for (int i = 0;i<syms.size();++i){
			printStack(symStack,stateStack ,syms[i].name);
			while(Process(syms[i],exps,ACTION,GOTO,symStack,stateStack)==1){
				printStack(symStack,stateStack ,syms[i].name);
			}
		}
	}
	// 产生action表和goto表 符合预期
	cout<<endl;
	cout<<"action"<<endl;
	for (auto& [k,v]:ACTION){
		for (auto& [k2,v2]:v){
			if (v2.type==0){
				cout<<k<<" "<<k2.name<<" s"<<v2.state<<endl;
			}
			else{
				int id = 0;
				for(int i = 0;i<v2.state;++i){
					id += exps[i].rights.size();
				}
				id += v2.expidx;
				cout<<k<<" "<<k2.name<<" r"<<id<<endl;
			}
			// cout<<k<<" "<<k2.name<<" "<<v2.state<<" "<<v2.type<<endl;
		}
	}
	cout<<endl;

	cout<<"goto"<<endl;
	for (auto& [k,v]:GOTO){
		for (auto& [k2,v2]:v){
			cout<<k<<" "<<k2.name<<" "<<v2.state<<endl;
		}
	}
	cout<<endl;
	cout<<"first"<<endl;
	// first集合和follow集合符合预期
	for (auto& [k,v]:first){
		cout<<k.name<<":";
		for (int i=0;i<first[k].size();++i){
			cout<<first[k][i].name<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	// follow 集合
	cout<<"follow"<<endl;
	for (auto& [k,v]:follow){
		cout<<k.name<<":";
		for (int i=0;i<follow[k].size();++i){
			cout<<follow[k][i].name<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
	cout<<"graph"<<endl;

	// 状态转化图 符合预期
	for (int i = 0;i<allItems.size();++i){
		cout<<"items:"<<allItems[i].id<<endl;
		for (int j = 0;j<allItems[i].kernelItems.size();++j){
			int wrapperidx = allItems[i].kernelItems[j].wrapperidx;
			int expidx = allItems[i].kernelItems[j].expidx;
			int pos = allItems[i].kernelItems[j].pos;
			cout<<exps[wrapperidx].left.name<<" -> ";
			for (int j = 0;j<=exps[wrapperidx].rights[expidx].size();++j){
				if (j==pos){
					cout<<". ";
				}
				if (j==exps[wrapperidx].rights[expidx].size()) continue;
				cout<<exps[wrapperidx].rights[expidx][j].name<<" ";
			}
			cout<<endl;
		}
		for (int j = 0;j<allItems[i].nonKernelItems.size();++j){
			int wrapperidx = allItems[i].nonKernelItems[j].wrapperidx;
			int expidx = allItems[i].nonKernelItems[j].expidx;
			int pos = allItems[i].nonKernelItems[j].pos;
			cout<<exps[wrapperidx].left.name<<" -> ";
			for (int j = 0;j<=exps[wrapperidx].rights[expidx].size();++j){
				if (j==pos){
					cout<<". ";
				}
				if (j==exps[wrapperidx].rights[expidx].size()) continue;
				cout<<exps[wrapperidx].rights[expidx][j].name<<" ";
			}
			cout<<endl;
		}
		cout<<"directions:"<<endl;
		for(int j = 0;j<allItems[i].directions.size();++j){
			cout<<allItems[i].directions[j].name<<":"<<allItems[i].directions[j].state<<" ";
		}
		cout<<endl<<endl;
	}

	// // 符合预期
	// for (int i = 0;i<names.size();++i){
	// 	cout<<names[i]<<endl;
	// }
	// // 符合预期
	// for (int i = 0;i<items0.nonKernelItems.size();++i){
	// 	cout<<items0.nonKernelItems[i].wrapperidx<<" "<<items0.nonKernelItems[i].expidx<<" "<<items0.nonKernelItems[i].pos<<endl;
	// }

	return 0;
}