#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>
#include <time.h>
using namespace std;
const int maxpoint = 1e+7;
const int maxedge = 1e+6;
const int inf = 99999999;

struct e
{
	int v, next;//无权值，指向的点，下一条边的地址
}edge[maxedge];
vector<int> pa;
string property[maxpoint];
bool isroot[maxpoint], visit[maxpoint];
int head[maxpoint], dep[maxpoint],chaxun[20];//查询数组
int hcnt,N;//N为查询属性的个数
vector<int> dis[maxpoint];
vector<int> split(const string& str, const string& pattern)
{
	vector<int> res;
	if (str == "")
		return res;
	//在字符串末尾也加入分隔符，方便截取最后一段
	string strs = str + pattern;
	size_t pos = strs.find(pattern);

	while (pos != strs.npos)
	{
		string temp = strs.substr(0, pos);
		if (temp == "")
			return res;
		res.push_back(stoi(temp));
		//去掉已分割的字符串,在剩下的字符串中进行分割
		strs = strs.substr(pos + 1, strs.size());
		pos = strs.find(pattern);
	}
	return res;
}//字符串分割所用到的
void init() {
	hcnt = 0;
	memset(isroot,0, sizeof isroot);
	memset(head, -1, sizeof head);
	memset(dep, -1, sizeof dep);
	memset(visit, -1, sizeof visit);
}
void addedge(int u,int v)
{
	edge[hcnt].v = v;
	edge[hcnt].next = head[u];
	head[u] = hcnt++;
}

int isparent(int p1, int p2)
{
	int t1 = 0, t2 = 0, equ = 0;
	for (int i = 0; i < N; i++)
	{
		if (dis[p1][i] > dis[p2][i])
			t1++;
		if (dis[p1][i] > dis[p2][i])
			t2++;
		else {
			equ++;
			t1++;
			t2++;
		}
	}
	if (t1 == N && equ != N)
		return 1;
	if (t2 == N && equ != N)
		return -1;
	else  return 0;
}
void bfs(int root) {
	queue<int> Q;
	Q.push(root);
	visit[root] = 1;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		vector<int> prop = split(property[u],",");//进行分割
		for(int j=0;j<N;j++)
		for (int i = 0; i < prop.size(); i++)
			if (prop[i]==chaxun[j]&&dep[u]<dis[root][j])
				dis[root][j] = dep[u];
		int flag = 0;
		for (int i = 0; i < N; i++)//检测还有没有必要继续往深处走
			if (dis[root][i] == inf)
				flag = 1;
		if (flag == 1)//如果需要往深处走
		{
			for (int i = head[u]; i != -1; i = edge[i].next)
			{
				int v = edge[i].v;
				if (visit[v]==0)
				{
					dep[v] = dep[u]+1;
					Q.push(v); 
					visit[v] = 1;
				}
			}
		}
	}
}
void bfsentry() {
	pa.clear();
	for (int i = 0; i < maxpoint; i++)
	{
		if (isroot[i])
		{
			dis[i].resize(N);//建立dis数组
			for (int j = 0; j < N; j++)
				dis[i][j] = inf;
			dep[i] = 0;
			bfs(i);
			int flag = 1;
			for (int j = 0; j < N; j++)
				if (dis[i][j] == inf)
				{
					flag = 0;
					break;
				}
			if (flag == 1)
			{
				if (pa.size() == 0)
					pa.push_back(i);
				else {
					int opflag = 0, firstflag = 1;
					vector<int>::iterator it = pa.begin();
					for (; it != pa.end(); it++)
					{
						int temp = isparent(i, *it);
						if (temp == 1)
						{
							if (firstflag == 1)
							{
								*it = i;
								opflag = 0;
							}
							else {
								pa.erase(it);
								it--;
							}
							opflag = 1;
						}
						else if (temp == -1)
						{
							opflag = 1;
							break;
						}
					}
					if (opflag == 0)//如果都没有支配或者被支配，加入新的祖宗集
						pa.push_back(i);
				}
			}
			dis[i].clear();
		}
	}
}

void processpoint(string o) {
	int index = o.find_first_of(":");
	int srcpoint = stoi(o.substr(0, index));
	property[srcpoint] = o.substr(index + 1, o.length());
}
void processroot(string o) {
	int index = o.find_first_of(":");
	int srcpoint = stoi(o.substr(0, index));
	isroot[srcpoint]=true;
}
void processedge(string o)
{
	int index = o.find_first_of(" ");
	int srcpoint = stoi(o.substr(0, index));
	string edg = o.substr(index + 1, o.length());
	vector<int> pointto = split(edg, ",");
	for (int i = 0; i < pointto.size(); i++)
		addedge(srcpoint, pointto[i]);
}
void getedge(string path) {
	fstream file(path);//读取文件
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{	
				processedge(got);
			}
		}
	}
}
void gettext(string path)
{
	fstream file(path);//读取文件
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{
				processpoint(got);
			}
		}
	}
}
void getroot(string path)
{
	fstream file(path);//读取文件
	if (file.is_open())
	{
		while (!file.eof())
		{
			string got;
			getline(file, got);
			if (!got.empty())
			{
				processroot(got);
			}
		}
	}

}
int main()
{
	cout << "正在初始化" << endl;
	init();
	cout << "开始构造边" << endl;
	clock_t t1 =clock();
	getedge("G:/作业/算法设计作业/大作业/Yago/edge.txt");
	cout << "开始构造属性" << endl;
	gettext("G:/作业/算法设计作业/大作业/Yago/node_keywords.txt");
	cout << "开始构造根节点数组" << endl;
	getroot("G:/作业/算法设计作业/大作业/placeid2coordYagoVB.txt");
	clock_t t2 = clock();
	double time1 = (double)(t2 - t1)/ (CLOCKS_PER_SEC*20);
	cout << "构造用时" << time1 << "ms" << endl;
	cout << "请输入查询属性的个数(不大于20个):";
	cin >> N;

	cout << "请输入查询属性(数字)，以空格分开(不大于20个):";
	for (int i = 0; i < N; i++)
		cin >> chaxun[i];

	cout << "开始对每个根节点进行bfs并寻找skyline" << endl;
	t1 = clock();
	bfsentry();
	t2 = clock();
	time1 = (double)(t2 - t1) / (CLOCKS_PER_SEC * 20);
//	cout << "语义地点构造完毕，开始在语义地点寻找skyline" << endl;
//	findparent();

	cout << "寻找完毕，用时"<<time1<<"ms,是skyline的点有"<<pa.size()<<"个，分别是："<< endl;
	
	for (int i = 0; i < pa.size(); i++)
		cout << pa[i] << " ";
	system("pause");
}