#include "SeqList.h"
#include "SeqQueue.h"

const int MaxVertices = 10;
const int MaxWeight = 10000;

class AdjMWGraph
{
	private:
		SeqList Vertices;
		int Edge[MaxVertices][MaxVertices];
		int numOfEdges;
	public:
		AdjMWGraph(const int sz = MaxVertices);

		int GraphEmpty()const 
			{return Vertices.ListEmpty();}
		int NumOfVertices(void)
			{return Vertices.ListSize();}
		int NumOfEdges(void)
			{return numOfEdges;}
		VerT GetValue(const int i);
		int GetWeight(const int v1, const int v2);

		void InsertVertex(const VerT &vertex);
		void InsertEdge(const int v1, const int v2, int weight);
		void DeleteVertex(const int v);
		void DeleteEdge(const int v1, const int v2);

		int GetFirstNeighbor(const int v);
		int GetNextNeighbor(const int v1, const int v2);

		void DepthFirstSearch(const int v, int visited[], void visit(VerT item));
		void BroadFirstSearch(const int v, int visited[], void visit(VerT item));
		void DepthFirstSearch(void visit(VerT item));
		void BroadFirstSearch(void visit(VerT item));
};

AdjMWGraph::AdjMWGraph(const int sz)
{
	for(int i = 0; i < sz; i++)
		for(int j = 0; j < sz; j++)
		{
			if(i == j) Edge[i][j] = 0;
			else Edge[i][j] = MaxWeight;
		}
	numOfEdges = 0;
}

VerT AdjMWGraph::GetValue(const int i)
{
	if(i < 0 || i > Vertices.ListSize())
	{
		cerr << "參數(shù)i越界出錯!" << endl;
		exit(1);
	}
	return Vertices.GetData(i);
}

int AdjMWGraph::GetWeight(const int v1, const int v2)
{
	if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize())
	{
		cerr << "參數(shù)v1或v2越界出錯!" << endl;
		exit(1);
	}
	return Edge[v1][v2];
}

void AdjMWGraph::InsertVertex(const VerT &vertex)
{
	Vertices.Insert(vertex, Vertices.ListSize());
}

void AdjMWGraph::InsertEdge(const int v1, const int v2, int weight)
{
	if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize())
	{
		cerr << "參數(shù)v1或v2越界出錯!" << endl;
		exit(1);
	}
	Edge[v1][v2] = weight;
	numOfEdges++;
}

void AdjMWGraph::DeleteVertex(const int v)
{
	for(int i = 0; i < Vertices.ListSize(); i++)
		for(int j = 0; j < Vertices.ListSize(); j++)
			if((i == v || j == v) && i != j && Edge[i][j] > 0 && Edge[i][j] < MaxWeight) 
			{
				Edge[i][j] = MaxWeight;
				numOfEdges--;
			}
	Vertices.Delete(v);
}

void AdjMWGraph::DeleteEdge(const int v1, const int v2)
{
	if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize() || v1 == v2)
	{
		cerr << "參數(shù)v1或v2出錯!" << endl;
		exit(1);
	}
	Edge[v1][v2] = MaxWeight;
	numOfEdges--;
}

int AdjMWGraph::GetFirstNeighbor(const int v)
{
	if(v < 0 || v > Vertices.ListSize())
	{
		cerr << "參數(shù)v1越界出錯!" << endl;
		exit(1);
	}
	for(int col = 0; col <= Vertices.ListSize(); col++)
		if(Edge[v][col] > 0 && Edge[v][col] < MaxWeight) return col;
	return -1;
}

int AdjMWGraph::GetNextNeighbor(const int v1, const int v2)
{
	if(v1 < 0 || v1 > Vertices.ListSize() || v2 < 0 || v2 > Vertices.ListSize())
	{
		cerr << "參數(shù)v1或v2越界出錯!" << endl;
		exit(1);
	}
	for(int col = v2+1; col <= Vertices.ListSize(); col++)
		if(Edge[v1][col] > 0 && Edge[v1][col] < MaxWeight) return col;
	return -1;
}

void AdjMWGraph::DepthFirstSearch(void visit(VerT item))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(! visited[i]) DepthFirstSearch(i, visited, visit);
	delete []visited;
}

void AdjMWGraph::DepthFirstSearch(const int v, int visited[], void visit(VerT item))
{
	visit(GetValue(v));
	visited[v] = 1;

	int w = GetFirstNeighbor(v);
	while(w != -1)
	{
		if(! visited[w]) DepthFirstSearch(w, visited, visit);
		w = GetNextNeighbor(v, w);
	}
}

void AdjMWGraph::BroadFirstSearch(void visit(VerT item))
{
	int *visited = new int[NumOfVertices()];
	for(int i = 0; i < NumOfVertices(); i++) visited[i] = 0;
	for(i = 0; i < NumOfVertices(); i++)
		if(!visited[i]) BroadFirstSearch(i, visited, visit);
	delete []visited;
}

void AdjMWGraph::BroadFirstSearch(const int v, int visited[], void visit(VerT item))
{
	VerT u, w;
	SeqQueue queue;
	visit(GetValue(v));
	visited[v] = 1;
	queue.QInsert(v);
	while(!queue.QueueEmpty())
	{
		u = queue.QDelete();
		w = GetFirstNeighbor(u);
		while(w != -1)
		{
			if(!visited[w])
			{
				visit(GetValue(w));
				visited[w] = 1;
				queue.QInsert(w);
			}
			w = GetNextNeighbor(u, w);
		}
	}
}