/*
 *	main.cpp
 */
#include <iostream.h>
#include "stdlib.h"
#include "stdio.h"
#include "math.h"

#define ZERO39 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" 

typedef struct  {
	int Node;
	int parentNode;
	char mask1[40];
	char mask2[40];
	int flag;
} CONNECTION;


char nameTbl[41][20] ={
	{"node0"},
	{"node1"},
	{"node2"},
	{"node3"},
	{"node4"},
	{"node5"},
	{"node6"},
	{"node7"},
	{"node8"},
	{"node9"},
	{"node10"},
	{"node11"},
	{"node12"},
	{"node13"},
	{"node14"},
	{"node15"},
	{"node16"},
	{"Dr. Lucy"},
	{"Kevin"},
	{"Cowling"},
	{"Attila"},
	{"Andrea"},
	{"Keshav"},
	{"Mr. Brain"},
	{"Davies"},
	{"Margaret"},
	{"Rae"},
	{"Prof. Excell"},
	{"Veena"},
	{"Harrison"},
	{"Hedges"},
	{"Mr. Karim"},
	{"Harel"},
	{"Gonde"},
	{"Morris"},
	{"Mark"},
	{"Goodliff"},
	{"Godfrey"},
	{"Castro"},
	{"Forbes"},
	{"Dr. Fretwell"}
};

CONNECTION connections[40]={
	{1,0,ZERO39,ZERO39,0},
	{2,1,ZERO39,ZERO39,0},
	{3,2,ZERO39,ZERO39,0},
	{4,3,ZERO39,ZERO39,0},
	{5,4,ZERO39,ZERO39,0},
	{6,5,ZERO39,ZERO39,0},
	{7,6,ZERO39,ZERO39,0},
	{8,7,ZERO39,ZERO39,0},
	{9,1,ZERO39,ZERO39,0},
	{10,9,ZERO39,ZERO39,0},
	{11,10,ZERO39,ZERO39,0},
	{12,11,ZERO39,ZERO39,0},
	{13,12,ZERO39,ZERO39,0},
	{14,13,ZERO39,ZERO39,0},
	{15,14,ZERO39,ZERO39,0},
	{16,15,ZERO39,ZERO39,0},
	{17,2,ZERO39,ZERO39,1},
	{18,2,ZERO39,ZERO39,1},
	{19,3,ZERO39,ZERO39,1},
	{20,3,ZERO39,ZERO39,1},
	{21,4,ZERO39,ZERO39,1},
	{22,4,ZERO39,ZERO39,1},
	{23,6,ZERO39,ZERO39,1},
	{24,6,ZERO39,ZERO39,1},
	{25,7,ZERO39,ZERO39,1},
	{26,7,ZERO39,ZERO39,1},
	{27,8,ZERO39,ZERO39,1},
	{28,8,ZERO39,ZERO39,1},
	{29,10,ZERO39,ZERO39,1},
	{30,10,ZERO39,ZERO39,1},
	{31,11,ZERO39,ZERO39,1},
	{32,11,ZERO39,ZERO39,1},
	{33,12,ZERO39,ZERO39,1},
	{34,12,ZERO39,ZERO39,1},
	{35,14,ZERO39,ZERO39,1},
	{36,14,ZERO39,ZERO39,1},
	{37,15,ZERO39,ZERO39,1},
	{38,15,ZERO39,ZERO39,1},
	{39,16,ZERO39,ZERO39,1},
	{40,16,ZERO39,ZERO39,1}
};

int coefficient[16][3]={
	{70,4,1},
	{24,6,9},
	{55,3,4},
	{49,3,5},
	{95,5,9},
	{44,9,3},
	{82,3,5},
	{39,2,1},
	{39,3,3},
	{49,4,6},
	{23,8,3},
	{43,4,9},
	{21,2,8},
	{39,3,8},
	{85,7,7},
	{32,5,9}
};

int hash(char* name,int coeff[3])  //hash function,ASCII碼的值乘以一個系數(shù)的和莫320(40*8)
{
	int i = 0;
	long value = 0;
	
	while(name[i] != '\0')
	{
		value += name[i]*coeff[i%3];
		i++;
	}
	
	value = (unsigned int)value%320;
	return value;
}

int setMaskBit(char* mask,int num)//設(shè)置v向量，向量的大小為320，mask為某結(jié)點(diǎn)的v向量，num為0到319之間的數(shù)，將向量中的第num位設(shè)為1
{
	int maskByte,maskBit;
	char maskChar;

	if(num<0 || num>319)
		return 0;

	maskByte = num/8;
	maskBit = num%8;
	maskChar = 0x01<<(7-maskBit);

	mask[maskByte] |= maskChar;
	
	return 1;
}

int checkMaskBit(char* mask,int num)//檢查向量mask 的第num位是否為1
{
	int maskByte,maskBit;
	char maskChar;

	if(num<0 || num>319)
		return 0;

	maskByte = num/8;
	maskBit = num%8;
	maskChar = 0x01<<(7-maskBit);

	if(mask[maskByte]&maskChar)
		return 1;
	else
		return 0;
}

void updataMask(char* mask,char* name)//更新一全向量，哈稀函數(shù)的鍵值為name，選擇不同的coefficient可以得到不同的哈 稀函數(shù)
{
	int hashValue;

	hashValue = hash(name,coefficient[0]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[1]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[2]);
	setMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[3]);
	setMaskBit(mask,hashValue);
}

int isOffspring(int ancestor,int offspring)
{
	int retValue = 0;

	if(ancestor == offspring)
	{
		retValue = 1;
		return retValue;
	}

	for(int i = 0; i < 40; i++)
	{
		if(connections[i].parentNode == ancestor)//如果某個結(jié)點(diǎn)的父節(jié)點(diǎn)為祖先結(jié)點(diǎn)，，則檢查子結(jié)點(diǎn)是否為當(dāng)前結(jié)點(diǎn)的子女
			retValue = retValue || isOffspring(connections[i].Node,offspring);
	}

	return retValue;
}

void generateMask()
{

/*	for(int i = 0; i < 40; i++)
	{
		if(connections[i].parentNode == k)
			generateMask(connections[i].Node);
	}
*/
	for(int i=0; i<40; i++)
	{
		for(int j=0; j<41; j++)
		{
			if(isOffspring(connections[i].Node,j))
				updataMask(connections[i].mask2,nameTbl[j]);
			else
				updataMask(connections[i].mask1,nameTbl[j]);//為什么要有兩個mask
		}
	}
//	cout<<k<<endl;
}

int checkMask(char* mask, char* name)//檢查經(jīng)過哈稀映射各位置都為1
{
	int hashValue;
	int retValue = 1;

	hashValue = hash(name,coefficient[0]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[1]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[2]);
	retValue &= checkMaskBit(mask,hashValue);
	hashValue = hash(name,coefficient[3]);
	retValue &= checkMaskBit(mask,hashValue);	
	
	return retValue;
}

void queryPath(int srcNode,int dstNode)
{
	int nextNode;

	cout<<srcNode<<'\t';
	
	if(srcNode == dstNode)
		return;
	
	for(int i=0; i<40; i++)
	{
		if(connections[i].Node == srcNode)
			if(1 == checkMask(connections[i].mask1,nameTbl[dstNode]))
				nextNode = connections[i].parentNode;
		if(connections[i].parentNode == srcNode)
			if(1 == checkMask(connections[i].mask2,nameTbl[dstNode]))
				nextNode = connections[i].Node;
	}
	if(nextNode>-1 && nextNode<40)
		queryPath(nextNode,dstNode);
	else
		cout<<"ERROR !"<<endl;
}

void main()
{
	int currentNode;
	int targetNode;

	generateMask();
/*	for(int i = 0; i < 40; i++)
	{
		printf("mask1 of %d: ",connections[i].Node);

		for(int j=0; j<40; j++)
			printf("%2x",(unsigned char)connections[i].mask1[j]);

		printf("\n");
		printf("mask2 of %d: ",connections[i].Node);

		for(j=0; j<40; j++)
			printf("%2x",(unsigned char)connections[i].mask2[j]);
		printf("\n");
	}
*/
	cout<<"Please input the current node"<<endl;
	cin>>currentNode;
	cout<<"Please input the target node"<<endl;
	cin>>targetNode;
//	currentNode = 2;
//	targetNode = 39;

//	cout<<checkMask(connections[17].mask2,"Veena")<<endl;
	queryPath(currentNode,targetNode);

	cout<<endl;

//	cout<<hash("Morris",coefficient[0])<<endl;
//	cout<<hash("Morris",coefficient[1])<<endl;
//	cout<<hash("Morris",coefficient[2])<<endl;
//	cout<<hash("Morris",coefficient[3])<<endl;
}