// Graph Set up, printing, etc.
#include "graph.h"
#include <string.h>
#include <fstream>
#include <stdio.h>

using namespace std;

void graph::UserInput()
{
	Flush();
	uint EdgeNo = 0, VertexNo = 0;
	Type = Unknown;
	cout << "Please ensure: i) that the edges around each vertex are given in their correct\n";
	cout << "cyclic (anticlockwise) order; and ii) that the graph map you enter can be\n";
	cout << "realised by an orientation-preserving surface homeomorphism.\n";
	cout << "Results are undefined if these rules are broken.\n\n";
	cout << "Enter number of peripheral loops, edges and vertices: ";
	cin >> Punctures >> EdgeNo >> VertexNo;
	cout << '\n';
	if (!EdgeNo || !VertexNo) THROW("Graph must have at least one edge and vertex", 0);
	NextEdgeLabel = EdgeNo+1; NextVertexLabel = VertexNo+1;
	uint *EdgeStart = new uint[EdgeNo+1], *EdgeEnd = new uint[EdgeNo+1];
    uint i;
	for (i=1; i<=EdgeNo; i++) EdgeStart[i] = EdgeEnd[i] = 0;
	for (i=1; i<=VertexNo; i++)
	{
		vertex& Now = Vertices[i];
		Now.Edges.Flush();
		cout << "Vertex number " << i << ":\n";
		Now.Label = i;
		cout << "Image vertex: ";
		cin >> Now.Image;
		if (Now.Image<1 || Now.Image>VertexNo)
		{
			delete[] EdgeStart; delete[] EdgeEnd;
			THROW("Vertex label out of range",0);
		}
		cout << "Enter labels of edges at vertex in cyclic order, ending with 0:\n";
		long Image;
		uint j=1;
		do {
			cin >> Image;
			if (Image == 0) continue;
			if (Image > 0)
			{
				if (Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge label out of range",0);
				}
				if (EdgeStart[Image])
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge start already assigned",0);
				}
				EdgeStart[Image] = i;
				Now.Edges[j++] = Image;
			}
			else
			{
				if (-Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge label out of range",0);
				}
				if (EdgeEnd[-Image])
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge end already assigned",0);
				}
				EdgeEnd[-Image] = i;
				Now.Edges[j++] = Image;
			}
		} while (Image != 0);
	}
	for (i=1; i<=EdgeNo; i++)
	{
		if (!(EdgeStart[i] && EdgeEnd[i]))
		{
			delete[] EdgeStart; delete[] EdgeEnd;
			THROW("Ends of edge not resolved",0);
		}
		Edges[i].Start = EdgeStart[i];
		Edges[i].End = EdgeEnd[i];
	}
	for (i=1; i<=EdgeNo; i++)
	{
		edge& Now = Edges[i];
		Now.Image.Flush();
		cout << "Edge number " << i << " from " << Now.Start << " to " << Now.End <<":\n";
		Now.Label = i;
		if (Punctures)
		{
			int IsPeripheral;
			cout << "Enter 1 if peripheral, 0 otherwise: ";
			cin >> IsPeripheral;
			if (IsPeripheral)
			{
				Now.Type = Peripheral;
				cout << "Enter puncture which edge is about: ";
				cin >> Now.Puncture;
				if (Now.Puncture<1 || Now.Puncture>Punctures)
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Puncture out of range",0);
				}
			}
			else Now.Type = Main;
		}
		else Now.Type = Main;
		cout << "Enter labels of image edges, ending with 0:\n";
		long Image;
		uint j=1;
		do {
			cin >> Image;
			if (Image == 0) continue;
			if (Image > 0)
			{
				if (Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge label out of range",0);
				}
				Now.Image[j++] = Image;
			}
			else
			{
				if (-Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					THROW("Edge label out of range",0);
				}
				Now.Image[j++] = Image;
			}
		} while (Image != 0);
		(Now.Image).Tighten();
	}
	delete [] EdgeStart;
	delete [] EdgeEnd;
	OrientPeripheralEdges();
	if (!SanityCheck()) THROW("Insane graph map",0);
}

void graph::Set(braid& B)
{
	if (B.Size() < 3) THROW("Braid should have at least three strings",0);
	Flush();
	IdentityGraph(B.Size());
	for (uint i=1; i<=B.Length(); i++)
	{
		ActOn(B[i]);
		Tighten();
	}
	ReLabel();
}

void graph::Print(ostream& Out)
{
   FindTypes();
	Out << "Graph on surface with " << Punctures << " peripheral loops:\n";
	vertexiterator I(Vertices);
	do
	{
		(I++).Print(Out);
	} while (!I.AtOrigin());
	edgeiterator J(Edges);
	do
	{
		(J++).Print(Out);
	} while (!J.AtOrigin());
	switch(Type)
	{
		case fo:
			Out << "Finite order Isotopy class\n";
			break;

		case Reducible1:
			Out << "Reducible Isotopy class\n";
			Out << "The following main edges and their images constitute an invariant subgraph:\n";
			PrintReduction(Out);
			break;

		case Reducible2:
			Out << "Reducible Isotopy class\n";
			PrintGates(Out);
			break;

		case pA:
			Out << "Pseudo-Anosov Isotopy class\n";
			PrintGates(Out);
			break;
			
		default: ;
	}
}

graph::graph(braid &B)
{
	if (B.Size() < 3) THROW("Braid should have at least three strings",0);
	IdentityGraph(B.Size());
	for (uint i=1; i<=B.Length(); i++)
	{
		ActOn(B[i]);
		Tighten();
	}
	ReLabel();
}

void graph::IdentityGraph(uint n)
{
	Flush();
	Punctures = n;
	NextEdgeLabel = 2*n;
	NextVertexLabel = n;
	Type = Unknown;
	// Set up Vertices
    uint i;
	for (i=1; i<=n; i++)
	{
		vertex &Now = Vertices[i];
		Now.Edges.Flush();
		Now.Label = i;
		Now.Image = i;
		if (i==1)
		{
			Now.Edges[1] = 1;
			Now.Edges[2] = -1;
			Now.Edges[3] = n+1;
			continue;
		}
		if (i==n)
		{
			Now.Edges[1] = n;
			Now.Edges[2] = -long(n);
			Now.Edges[3] = -long(2*n-1);
			continue;
		}
		Now.Edges[1] = i;
		Now.Edges[2] = -long(i);
		Now.Edges[3] = i+n;
		Now.Edges[4] = -long(i+n-1);
	}
	// Set up Peripheral Edges
	for (i=1; i<=n; i++)
	{
		edge &Now = Edges[i];
		Now.Image.Flush();
		Now.Label = i;
		Now.Type = Peripheral;
		Now.Puncture = i;
		Now.Start = i;
		Now.End = i;
		Now.Image[1] = i;
	}
	// Set up Main Edges
	for (i=n+1; i<2*n; i++)
	{
		edge &Now = Edges[i];
		Now.Image.Flush();
		Now.Label = i;
		Now.Type = Main;
		Now.Start = i-n;
		Now.End = i-n+1;
		Now.Image[1] = i;
	}
}

void graph::ActOn(long Gen)
{
	intarray Temp;
	long n = long(Punctures);
	long i = (Gen>0) ? Gen : -Gen;
	VertexImageSwap(i, i+1);
	if (Gen == 1)
	{
		Temp[1] = -(n+1);
		Temp[2] = -1;
		Replace(n+1, Temp);
		Temp[1] = n+1;
		Temp[2] = n+2;
		Replace(n+2, Temp);
		return;
	}
	if (Gen == -1)
	{
		Temp[1] = -(n+1);
		Replace(n+1, Temp);
		Temp[1] = n+1;
		Temp[2] = 2;
		Temp[3] = n+2;
		Replace(n+2,Temp);
		return;
	}
	if (Gen == n-1)
	{
		Temp[1] = -(2*n-1);
		Replace(2*n-1, Temp);
		Temp[1] = 2*n-2;
		Temp[2] = n-1;
		Temp[3] = 2*n-1;
		Replace(2*n-2, Temp);
		return;
	}
	if (Gen == -(n-1))
	{
		Temp[1] = -n;
		Temp[2] = -(2*n-1);
		Replace(2*n-1, Temp);
		Temp[1] = 2*n-2;
		Temp[2] = 2*n-1;
		Replace(2*n-2, Temp);
		return;
	}
	if (Gen > 0)
	{
		Temp[1] = -(i+n);
		Temp[2] = -i;
		Replace(i+n, Temp);
		Temp[1] = i+n;
		Temp[2] = i+n+1;
		Replace(i+n+1, Temp);
		Temp[1] = (i+n-1);
		Temp[2] = i;
		Temp[3] = i+n;
		Replace(i+n-1, Temp);
		return;
	}
	if (Gen < 0)
	{
		Temp[1] = -(i+1);
		Temp[2] = -(i+n);
		Replace(i+n, Temp);
		Temp[1] = i+n-1;
		Temp[2] = i+n;
		Replace(i+n-1, Temp);
		Temp[1] = i+n;
		Temp[2] = i+1;
		Temp[3] = i+n+1;
		Replace(i+n+1, Temp);
		return;
	}
}

void graph::VertexImageSwap(uint i, uint j)
{
    uint k;
	for (k=1; k<=Punctures; k++)
	{
		if (Vertices[k].Image == i)
		{
			Vertices[k].Image = j;
			Edges[k].Image[1] = j;
		}
		else if (Vertices[k].Image == j)
		{
			Vertices[k].Image = i;
			Edges[k].Image[1] = i;
		}
	}
	for (k=1; k<Punctures; k++)
	{
		intarray& Im = Edges[Punctures+k].Image;
		for (uint l=1; long(l)<=Im.TopIndex(); l++)
		{
			if (Im[l] == long(i)) Im[l] = j;
			else if (Im[l] == long(j)) Im[l] = i;
			if (Im[l] == -long(i)) Im[l] = -long(j);
			else if (Im[l] == -long(j)) Im[l] = -long(i);
		}
	}
}

void graph::PrintTurns(ostream& Out)
{
	FindTurns();
	for (uint i=1; long(i)<=Turns.TopIndex(); i++) Out << Turns[i] << '\n';
}

void graph::PrintGates(ostream& Out)
{
	if (Type != pA && Type != Reducible2)
		THROW("Trying to print gates with unsuitable graph map", 1);
	for (uint i=1; i<=NumberVertices(); i++)
	{
		uint Label = Vertices[i].Label;
		Out << "Vertex " << Label << ":\nGates are: ";
		uint j=5; while (Reduction[j-3] || Reduction[j-2]!=long(Label) || Reduction[j-4]) j++;
		Out << '{';
		bool Finished = false;
		while (!Finished)
		{
			Out << Reduction[j];
			if (Reduction[++j]) Out << ", ";
			else
			{
				if (Reduction[++j]) Out << "}, {";
				else
				{
					Finished = true;
					Out << "}\n";
					j++;
				}
			}
		}
		Out << "Infinitesimal edges join ";
		bool First = true;
		for (j=1; long(j)<=Turns.TopIndex(); j++)
		{
			if (Turns[j].Level == Label)
			{
				if (First) First = false;
				else Out << ", ";
				Out << Turns[j].i << " to " << Turns[j].j;
			}
		}
		Out << '\n';
	}
}



#pragma warn -lvc
void graph::ReLabel()
{
	FindTypes();
	uint ENo = NumberEdges(), VNo = NumberVertices();
	long *OldLabel = new long[ENo+1];
	uint i=1;
	//Start with peripheral edges about punctures in ascending order
    uint j;
	for (j=1; j<=Punctures; j++)
		for (uint k=1; k<=ENo; k++)
			if (Edges[k].Type == Peripheral && Edges[k].Puncture == j)
				OldLabel[i++] = Edges[k].Label;
	//Next preperipheral edges
	for (j=1; j<=ENo; j++)
		if (Edges[j].Type == Preperipheral) OldLabel[i++] = Edges[j].Label;
	//Finally main edges
	for (j=1; j<=ENo; j++)
		if (Edges[j].Type == Main) OldLabel[i++] = Edges[j].Label;
	//Error check
	if (i != ENo+1)
	{
		delete[] OldLabel;
		THROW("Something very wrong in ReLabel",1);
	}
	//Change edge labels
	for (i=1; i<=ENo; i++)
	{
		j=1; while (Edges[i].Label != OldLabel[j]) j++;
		Edges[i].Label = j;
	}
	//Change edge images
	for (i=1; i<=ENo; i++)
	{
		intarray& Now = Edges[i].Image;
		for (j=1; long(j)<=Now.TopIndex(); j++)
		{
			long Find = (Now[j]>0) ? Now[j] : -Now[j];
			long k=1; while (Find != OldLabel[k]) k++;
			Now[j] = (Now[j]>0) ? k : -k;
		}
	}
	//Change edges round vertices
	for (i=1; i<=VNo; i++)
	{
		intarray& Now = Vertices[i].Edges;
		for (j=1; long(j)<=Now.TopIndex(); j++)
		{
			long Find = (Now[j]>0) ? Now[j] : -Now[j];
			long k=1; while (Find != OldLabel[k]) k++;
			Now[j] = (Now[j]>0) ? k : -k;
		}
	}
	//Change reduction
	if (Type == Reducible1) for (i=1; long(i)<=Reduction.TopIndex(); i++)
	{
		j=1; while (Reduction[i] != OldLabel[j]) j++;
		Reduction[i] = j;
	}
	//Change edge indices
	edgelist Copy = Edges;
	for (i=1; i<=ENo; i++)
	{
		uint j=1; while (Copy[j].Label != long(i)) j++;
		Edges[i] = Copy[j];
	}

	//Relabel Vertices
	for (uint k=1; k<=VNo; k++)
	{
		uint OldVLabel = Vertices[k].Label;
		if (OldVLabel == k) continue;
		Vertices[k].Label = k;
		for (j=1; j<=ENo; j++)
		{
			if (Edges[j].Start == OldVLabel) Edges[j].Start = k;
			if (Edges[j].End == OldVLabel) Edges[j].End = k;
		}
		for (j=1; j<=VNo; j++) if (Vertices[j].Image == OldVLabel) Vertices[j].Image = k;
	}
	NextEdgeLabel = ENo+1;
	NextVertexLabel = VNo+1;
	delete[] OldLabel;
}

#pragma warn .lvc

void graph::Save(char* Filename, const char*)
{
	ofstream File;
	if (!strrchr(Filename, '.')) strcat(Filename, ".grm");
	File.open(Filename);
	if (!File) THROW("Cannot open file for writing",3);
	ReLabel();
	File << Punctures << " " << NumberEdges() << " " << NumberVertices() << '\n';
    uint i;
	for (i=1; i<=NumberVertices(); i++)
	{
		vertex& Now = Vertices[i];
		File << Now.Image << '\n';
		for (uint j=1; long(j)<=Now.Edges.TopIndex(); j++) File << Now.Edges[j] << " ";
		File << 0 << '\n';
	}
	for (i=1; i<=NumberEdges(); i++)
	{
		edge& Now = Edges[i];
		if (Punctures)
		{
			if (Now.Type == Peripheral) File << 1 << " " << Now.Puncture << '\n';
			else File << 0 << '\n';
		}
		for (uint j=1; long(j)<=Now.Image.TopIndex(); j++) File << Now.Image[j] << " ";
		File << 0 << '\n';
	}
    File <<  Type << '\n';
	File.close();
}

void graph::Load(char* Filename, bool Sanity)
{
	ifstream File;
	if (!strrchr(Filename, '.')) strcat(Filename, ".grm");
	File.open(Filename);
	if (!File) THROW("Cannot open file for reading",0);
	Flush();
	uint EdgeNo = 0, VertexNo = 0;
	File >> Punctures >> EdgeNo >> VertexNo;
	NextEdgeLabel = EdgeNo+1; NextVertexLabel = VertexNo+1;
	uint *EdgeStart = new uint[EdgeNo+1], *EdgeEnd = new uint[EdgeNo+1];
    uint i;
	for (i=1; i<=EdgeNo; i++) EdgeStart[i] = EdgeEnd[i] = 0;
	for (i=1; i<=VertexNo; i++)
	{
		vertex& Now = Vertices[i];
		Now.Edges.Flush();
		Now.Label = i;
		File >> Now.Image;
		if (Now.Image<1 || Now.Image>VertexNo)
		{
			delete[] EdgeStart; delete[] EdgeEnd;
			File.close();
			THROW("Vertex label out of range",0);
		}
		long Image;
		uint j=1;
		do {
			File >> Image;
			if (Image == 0) continue;
			if (Image > 0)
			{
				if (Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge label out of range",0);
				}
				if (EdgeStart[Image])
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge start already assigned",0);
				}
				EdgeStart[Image] = i;
				Now.Edges[j++] = Image;
			}
			else
			{
				if (-Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge label out of range",0);
				}
				if (EdgeEnd[-Image])
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge end already assigned",0);
				}
				EdgeEnd[-Image] = i;
				Now.Edges[j++] = Image;
			}
		} while (Image != 0);
	}
	for (i=1; i<=EdgeNo; i++)
	{
		if (!(EdgeStart[i] && EdgeEnd[i]))
		{
			delete[] EdgeStart; delete[] EdgeEnd;
			File.close();
			THROW("Ends of edge not resolved",0);
		}
		Edges[i].Start = EdgeStart[i];
		Edges[i].End = EdgeEnd[i];
	}
	for (i=1; i<=EdgeNo; i++)
	{
		edge& Now = Edges[i];
		Now.Image.Flush();
		Now.Label = i;
		if (Punctures)
		{
			int IsPeripheral;
			File >> IsPeripheral;
			if (IsPeripheral)
			{
				Now.Type = Peripheral;
				File >> Now.Puncture;
				if (Now.Puncture<1 || Now.Puncture>Punctures)
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Puncture out of range",0);
				}
			}
			else Now.Type = Main;
		}
		else Now.Type = Main;
		long Image;
		uint j=1;
		do {
			File >> Image;
			if (Image == 0) continue;
			if (Image > 0)
			{
				if (Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge label out of range",0);
				}
				Now.Image[j++] = Image;
			}
			else
			{
				if (-Image > long(EdgeNo))
				{
					delete[] EdgeStart; delete[] EdgeEnd;
					File.close();
					THROW("Edge label out of range",0);
				}
				Now.Image[j++] = Image;
			}
		} while (Image != 0);
		(Now.Image).Tighten();
	}
	delete[] EdgeStart;
	delete[] EdgeEnd;
	int graphtype;
        if (!File.eof()) {File >> graphtype; Type=static_cast<thurstontype>(graphtype);}
	File.close();
		OrientPeripheralEdges();
	if (Sanity && !SanityCheck()) THROW("Insane graph map",0);
}


bool graph::SanityCheck()
{
   uint i;
	for (i=1; i<=NumberEdges(); i++)
	{
		edge& Now = Edges[i];
		for (uint j=1; long(j)<=Now.Image.TopIndex(); j++)
		{
			if (j==1)
				if (Vertices[FindVertex(Now.Start)].Image != From(Now.Image[1])) return false;
			if (j>1) if (From(Now.Image[j]) != To(Now.Image[j-1])) return false;
			if (long(j)==Now.Image.TopIndex())
				if (Vertices[FindVertex(Now.End)].Image != To(Now.Image[j])) return false;
		}
	}
	for (i=1; i<=NumberVertices(); i++)
	{
		vertex& Now = Vertices[i];
		for (uint j=1; long(j)<=Now.Edges.TopIndex(); j++)
			if (From(Now.Edges[j]) != Now.Label) return false;
	}
	return true;
}

void graph::OrientPeripheralEdges()
{
	if (!Punctures) return;
	for (uint i=1; i<=NumberVertices(); i++)
	{
		vertex& Now = Vertices[i];
		if (!OnP(Now.Label)) continue;
		//Consider peripheral edges at Now
		for (uint j=1, k=2; long(j)<=Now.Edges.TopIndex(); j++, k++)
		{
			if (!IsPeripheral(Now.Edges[j])) continue;
			if (long(j)==Now.Edges.TopIndex()) k=1;
			if ((Now.Edges[j]>0 && !IsPeripheral(Now.Edges[k])) ||
				 (Now.Edges[j]<0 && IsPeripheral(Now.Edges[k])))
			{
				//Alter orientation of peripheral edge
				long Label = (Now.Edges[j]>0) ? Now.Edges[j] : -Now.Edges[j];
				edge& ToChange = Edges[FindEdge(Label)];
				uint Temp = ToChange.Start; ToChange.Start = ToChange.End; ToChange.End = Temp;
				ToChange.Image.Invert();
				for (uint l=1; l<=NumberVertices(); l++)
				{
					for (uint m=1; long(m)<=Vertices[l].Edges.TopIndex(); m++)
					{
						if (Vertices[l].Edges[m] == Label) Vertices[l].Edges[m] = -Label;
						else if (Vertices[l].Edges[m] == -Label) Vertices[l].Edges[m] = Label;
					}
				}
				intarray L(2,1); L[1] = -Label;
				Replace(Label, L);
			}
		}
	}
}