#include<iostream>
#include<vector>
#include<fstream>
#include<string>
#include<queue>
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];
int isroot[maxpoint];
int head[maxpoint], dep[maxpoint],chaxun[20],visit[maxpoint];//查询数组
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, maxpoint);
	memset(head, -1, maxpoint);
	memset(dep, -1, maxpoint);
	memset(visit, -1, maxpoint);
}
void addedge(int u,int v)
{
	edge[hcnt].v = v;
	edge[hcnt].next = head[u];
	head[u] = hcnt++;
}

void bfs(int root) {
	queue<int> Q;
	Q.push(root);
	while (!Q.empty()) {
		int u = Q.front();
		visit[u] = 1;
		Q.pop();
		if (!isroot[u])//如果该点不是root，进行属性检测，如果是root，直接继续
		{
			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])
				{
					dep[v] = dep[u + 1];
					Q.push(v); 
				}
			}
		}
	}
}
void bfsentry() {
	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 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 i = 0; i < maxpoint; i++)//对点集进行遍历
		{
			if (!isroot[i])
				continue;
			if (pa.size() == 0)
			{
				pa.push_back(i);
				continue;
			}
			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);
		
	}
}
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()
{
	init();
	cout << "开始构造边" << endl;
	getedge("G:/作业/算法设计作业/大作业/Yago_small/edge.txt");
	cout << "开始构造属性" << endl;
	gettext("G:/作业/算法设计作业/大作业/Yago_small/node_keywords.txt");
	cout << "开始构造根节点数组" << endl;
	getroot("G:/作业/算法设计作业/大作业/placeid2coordYagoVB.txt");
	cout << "请输入查询属性的个数(不大于20个):";
	cin >> N;

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

	cout << "正在初始化" << endl;
	init();

	cout << "开始对每个根节点进行bfs" << endl;
	bfsentry();

	cout << "语义地点构造完毕，开始在语义地点寻找skyline" << endl;
	findparent();

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

	system("pause");
}