#include "fstream"
#include "iostream"
#include <vector>
#include <queue>

using namespace std;
	
char mark; //the mark is either v or f
struct face {
	int vertex[3];
	int faceId;
	bool visited;
	face(int a[3], int b, bool c) {
		for (int i=0; i<3; i++)
			vertex[i] = a[i];
		faceId = b;
		visited = c;
	}
};
vector<double*> vertexVec; // store the vertex info
vector<face> faceVec; //store the face info
	
int vcount=0; //counter for vertex;
int fcount=0; //counter for face
vector<face> *node; //the array that stores faceVecs which consist faces withs same vertices.

//read data file and build vertexVec, faceVec and node.
void readFile(char* FileName) {
	fstream file_op(FileName,ios::in);
	
	while(file_op >> mark) {
		if (mark == 'v'){
			double *temp = new double[3];
			for(int i=0; i<3; i++)	{			
				file_op >> temp[i];
			}
			vertexVec.push_back(temp);
			vcount++;
		}//vertexVec

		if (mark == 'f') {
			int *temp = new int[3];
			for(int i=0; i<3; i++)	{			
				file_op >> temp[i];			
			}
			
			faceVec.push_back(face(temp, fcount+1, false));
			fcount++;
		}//faceVec				
	}

	node = new vector<face>[vcount+1];

	for (int i=0; i<fcount; i++) {
		for(int j=0; j<3; j++)
			node[faceVec[i].vertex[j]].push_back(faceVec[i]);			
	}//node		
}

//write the vertex and face in the output file
void writeFile (char* FileName) {
	fstream file_op(FileName,ios::out);
	for (int i=0; i<vcount; i++){
		file_op << "Vertex " << i+1 << " " <<vertexVec[i][0] << " " << vertexVec[i][1] << " " << vertexVec[i][2] << endl;
	}
	for (int i=0; i<fcount; i++){
		file_op << "Face " << i+1 << " " <<faceVec[i].vertex[0] << " " << faceVec[i].vertex[1] << " " << faceVec[i].vertex[2] << endl;		
	}
}

//compare two faces to see if their orientation is consistant. If not, do swap and fix faceB.
void repair(face &faceA, face &faceB){
	int tmp;
	if ((faceB.vertex[0] == faceA.vertex[0] && faceB.vertex[1] == faceA.vertex[1])|| (faceB.vertex[0] == faceA.vertex[1] && faceB.vertex[1] == faceA.vertex[2])|| (faceB.vertex[0] == faceA.vertex[2] && faceB.vertex[1] == faceA.vertex[0]))	 
	{
		tmp = faceB.vertex[0];
    	faceB.vertex[0] = faceB.vertex[1];
	    faceB.vertex[1] = tmp;
	}
	if ((faceB.vertex[2] == faceA.vertex[0] && faceB.vertex[0] == faceA.vertex[1])|| (faceB.vertex[2] == faceA.vertex[1] && faceB.vertex[0] == faceA.vertex[2])|| (faceB.vertex[2] == faceA.vertex[2] && faceB.vertex[0] == faceA.vertex[0]))	 
	{
		tmp = faceB.vertex[0];
    	faceB.vertex[0] = faceB.vertex[2];
	    faceB.vertex[2] = tmp;
	}
    if ((faceB.vertex[1] == faceA.vertex[0] && faceB.vertex[2] == faceA.vertex[1])|| (faceB.vertex[1] == faceA.vertex[1] && faceB.vertex[2] == faceA.vertex[2])|| (faceB.vertex[1] == faceA.vertex[2] && faceB.vertex[2] == faceA.vertex[0]))	 
	{
		tmp = faceB.vertex[1];
    	faceB.vertex[1] = faceB.vertex[2];
	    faceB.vertex[2] = tmp;
	}

}

//construct a faceQueue. First we put a random face in the queue. Get the queue.front and search in the "node" we defined earlier to get 3 neighbors that shared 
//edges with the queue.front. If they are not visited before, check consistancy and put them in the queue. Keep going until the queue is empty.
//based on the data structure we have, the search for neighbors takes O(1). So the algorithm's complexity is O(n)
void queueConstruction2 () {
	queue<face> faceQueue;
	faceQueue.push(faceVec[0]);
	faceVec[0].visited = true;
	while (!faceQueue.empty()) {
		int temp[3];
		for (int i=0; i<3; i++){
			temp[i] = faceQueue.front().vertex[i];//temp stores the queue front face
		}
		for (int i=0; i<3; i++) {
			vector<face> tempVec = node[temp[i]];//get the faceVec that stores faces with the same vertex
			for (unsigned int j=0; j<tempVec.size(); j++)
				if ((temp[(i+1)%3] == tempVec[j].vertex[0]||temp[(i+1)%3] == tempVec[j].vertex[1]||temp[(i+1)%3] == tempVec[j].vertex[2]) && !faceVec[tempVec[j].faceId-1].visited){
					repair(faceQueue.front(), faceVec[tempVec[j].faceId-1]);
					faceVec[tempVec[j].faceId-1].visited = true;
					faceQueue.push(faceVec[tempVec[j].faceId-1]);
					break;
				}
		}
		faceQueue.pop();
				
	}
}

//the idea is the same as queueConstruction2(). the "node" data structure is not used. Instead, everytime we search for the neighbors, we scan the whole faceVec,
//the complexity of search is O(n). and the complexity of the algorithm is O(n^2);
void queueConstruction () {
	int count = 0; 
	queue<face> faceQueue;
	faceQueue.push(faceVec[0]);
	faceVec[0].visited = true;
	while (!faceQueue.empty()){

		for (unsigned int i=0; i<faceVec.size(); i++) {
			
				for (int k =0; k<3; k++)		
					if (faceVec[i].vertex[0] == faceQueue.front().vertex[k]||faceVec[i].vertex[1] == faceQueue.front().vertex[k]||faceVec[i].vertex[2] == faceQueue.front().vertex[k]) 
						count++;
				if (count == 2 && !faceVec[i].visited) {
					repair(faceQueue.front(), faceVec[i]);
					faceVec[i].visited = true;
					faceQueue.push(faceVec[i]);
					
				}
				count = 0;					
		}		
		faceQueue.pop();
	}
}


int main (int argc, char *argv[])
{
// 	if (argc!=3)
// 	{
// 		printf ("Usage: Projectname, inputfile, outputfile \n");
// 		return -1;
// 	}

	readFile("in.obj");
	queueConstruction2 ();
	writeFile("out.m");
}