#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>
#include<chrono>
#include<map>
using namespace std::chrono;
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);
}
void addedge(int u, int v)
{
	edge[hcnt].v = v;
	edge[hcnt].next = head[u];
	head[u] = hcnt++;
}

void bfs(int p,vector<int> pro) {
	memset(visit, 0, sizeof visit);
	queue<int> Q;
	Q.push(p);
	dep[p] = 0;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		if (!visit[u])
		{
			if (isroot[u])
			{
				if (dis[u].size() < N)
				{
					dis[u].resize(N);
					for (int i = 0; i < N; i++)
						dis[u][i] = inf;
				}
				for(int i = 0;i < N ; i++)
					for (int k = 0; k < pro.size(); k++)
						if (pro[k] == chaxun[i] && dep[u] < dis[u][i])
								dis[u][i] = dep[u];//更新标签
			}
			for (int i = head[u]; i != -1; i = edge[i].next)
			{
				int v = edge[i].v;
				if (!visit[v])
				{
					dep[v] = dep[u] + 1;
					Q.push(v);

				}
			}
			visit[u] = 1;
		}
		
	}
}
void bfsentry() {
	
	for (int i = 0; i < maxpoint; i++)
	{
		vector<int> temp = split(property[i],",");
		int flag = 0;
		for(int k=0;k<N;k++)
			for (int j = 0; j < temp.size(); j++)
				if (temp[j] == chaxun[k])
				{
					flag = 1;
					break;
				}
		if (flag == 1)//如果该点拥有查询属性
		{
			bfs(i, temp);
		}
		
	}
}
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 findparent()
{
	pa.clear();
	for (int p = 0; p < maxpoint; p++)
	{

		if (dis[p].size() == N) {
			int flag = 1;
			for (int i = 0; i < N; i++)
				if (dis[p][i] == inf)
				{
					flag = 0;
					break;
				}
			if (flag==1) {
				if (pa.size() == 0)
				{
					pa.push_back(p);
					continue;
				}
				int opflag = 0, firstflag = 1;
				vector<int>::iterator it = pa.begin();
				for (; it != pa.end(); it++)
				{
					int temp = isparent(p, *it);
					if (temp == 1)
					{
						if (firstflag == 1)
						{
							*it = p;
							opflag = 0;
						}
						else {
							pa.erase(it);
							it--;
						}
						opflag = 1;
					}
					else if (temp == -1)
					{
						opflag = 1;
						break;
					}
				}
				if (opflag == 0)//如果都没有支配或者被支配，加入新的祖宗集
					pa.push_back(p);
			}
		}
	}
	}
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;
	auto t1 = steady_clock::now();
	getedge("G:/作业/算法设计作业/大作业/Yago_small/edge.txt");
	cout << "开始构造属性" << endl;
	gettext("G:/作业/算法设计作业/大作业/Yago_small/node_keywords.txt");
	cout << "开始构造根节点数组" << endl;
	getroot("G:/作业/算法设计作业/大作业/placeid2coordYagoVB.txt");
	auto t2 = steady_clock::now();
	auto time1 = (t2 - t1).count() / 1e6;
	cout << "构造用时" << time1 << "ms" << endl;
	cout << "请输入查询属性的个数(不大于20个):";
	cin >> N;
	cout << "请输入查询属性(数字)，以空格分开(不大于20个):";
	for (int i = 0; i < N; i++)
		cin >> chaxun[i];

	cout << "开始对每个根节点进行bfs" << endl;
	t1 = steady_clock::now();
	bfsentry();
	cout << "语义地点构造完毕，开始在语义地点寻找skyline" << endl;
	findparent();
	t2 = steady_clock::now();
	time1 = (t2 - t1).count() / 1e6;
	cout << "寻找完毕，用时" << time1 << "ms,是skyline的点有" << pa.size() << "个，分别是：" << endl;

	for (int i = 0; i < pa.size(); i++)
		cout << pa[i] << " ";
	system("pause");
}