using System;
using System.Collections;
using QCGM.Graphs2;
using QCGM.Boards;

namespace QCGM.Graphs2
{
	/// <summary>
	/// Summary description for DepthFirstSearch.
	/// </summary>
	public class BreadthFirstSearch
	{
		public const int Infinity = 16000;

		protected ArrayList Vertices;
		protected Graph2 G;
		protected Node2 s;
		public Node2 Start
		{
			get
			{
				return s;
			}
		}

		protected int time;
		public int Time
		{
			get
			{
				return time;
			}
			set
			{
				time = value;
			}
		}

		public Node2 GetNode(Tile t)
		{
			foreach(Node2 u in this.Vertices)
			{
				if(u.Tile == t)
				{
					return u;
				}
			}
			throw new Exception("Node not found!!!!");
		}

		public BreadthFirstSearch(Graph2 G)
		{
			this.G = G;
			BuildVertices();
		}

		protected void BuildVertices()
		{
			this.Vertices = new ArrayList();

			foreach(Node2 n in G.Nodes)
			{
				Vertices.Add(n);
			}
		}

		public void Perform(Node2 s)
		{
			ArrayList V = Vertices;
			this.s = s;
			V.Remove(s);
			
			foreach(Node2 u in V)
			{
				u.BFS_Color = BFSColors.White;
				u.BFS_d = Infinity;
				u.BFS_Pi = null;
			}

			s.BFS_Color = BFSColors.Gray;
			s.BFS_d = 0;
			s.BFS_Pi = null;

			SimpleQueue Q = new SimpleQueue();

			Q.Enqueue(s);
			while(Q.Count != 0)
			{
				Node2 u = Q.ExtractMin();
				for(int i=0; i < 4; i++)
				{
					if(u.Neighbors[i] != null)
					{
						Node2 v = u.Neighbors[i];

						if(v.BFS_Color == BFSColors.White)
						{
							v.BFS_Color = BFSColors.Gray;
							v.BFS_d = u.BFS_d + 1;
							v.BFS_Pi = u;
							Q.Enqueue(v);
						}
					}
				}
				u.BFS_Color = BFSColors.Black;
			}

			s.BFS_d = 0;
			s.BFS_Pi = null;
			V.Add(s);
		}

		/// <summary>
		/// Gathers the shortest path from node s to node v, or null if no such path exists.
		/// </summary>
		/// <param name="v">The destination node</param>
		/// <remarks>Perform method must be called before ShortestPath.</remarks>
		/// <returns>Returns the shortest path from node s to node v, or null if no path exists</returns>
		public ArrayList ShortestPath(Node2 v)
		{
			ArrayList L = new ArrayList();

			Node2 node = v;

			while(node != this.Start)
			{
				L.Add(node);
				node = node.BFS_Pi;
			}

			L.Add(Start);

			return L;
		}

		/// <summary>
		/// Obtains the weight (cost) to travel to node V from the start node
		/// </summary>
		/// <param name="v">the destination node</param>
		/// <returns>the cost of travel to v</returns>
		public int CostOfTravel(Node2 v)
		{
			if(this.Vertices.Contains(v))
			{
				return v.BFS_d;
			}
			else
			{
				throw new Exception("Not in this set baby!");
			}
		}


		/// <summary>
		/// Recursive algorithm to gather a path from source to destination!
		/// </summary>
		/// <param name="s">Source node</param>
		/// <param name="v">Destination node</param>
		/// <returns>The next node in the path from s to v, or null if no path exists</returns>
		private void Traverse(Node2 s, Node2 v, ref ArrayList l)
		{
			if(v == s)
			{
				l.Add(s);
				return;
			}
			else if(v.BFS_Pi == null)
			{
				l.Clear();
				return;
			}
			else
			{
				Traverse(s, v, ref l);
				l.Add(v);
			}
		}

		/// <summary>
		/// Recursive algorithm to gather the cost of travel from source to destination!
		/// </summary>
		/// <param name="s">Source node</param>
		/// <param name="v">Destination node</param>
		/// <param name="c">The cost of travel</param>
		private void Traverse(Node2 s, Node2 v, ref int c)
		{
			if(v == s)
			{
				return;
			}
			else if (v.BFS_Pi == null)
			{
				c = -1;
				return;
			}
			else
			{
				Traverse(s, v, ref c);
				c++;
			}
		}

		protected void Visit(Node2 u)
		{
			u.BFS_Color = BFSColors.Gray;

			time++;

			u.BFS_d = time;

			for(int i=0; i < 4; i++)
			{
				if(u.Neighbors[i] != null)
				{
					if(u.Neighbors[i].BFS_Color == BFSColors.White)
					{
						u.Neighbors[i].BFS_Pi = u;
						Visit(u.Neighbors[i]);
					}
				}

				u.BFS_Color = BFSColors.Black;
				u.BFS_F = time;
				time++;
			}
		}
	}

	public enum BFSColors { White, Gray, Black };
/*
	public class Vertex
	{
		Node2 n;

		private ArrayList adj;
		public ArrayList Adjacent
		{
			get
			{
				return adj;
			}
		}

		private int f;
		public int F
		{
			get
			{
				return f;
			}
			set
			{
				f = value;
			}
		}
		
		private int d;
		public int D
		{
			get
			{
				return d;
			}
			set
			{
				d = value;
			}
		}
		
		protected BFSColors color = BFSColors.White;
		
		public BFSColors Color
		{
			get
			{
				return this.color;
			}
			set
			{
				this.color = value;
			}
		}

		private Vertex pi;
		/// <summary>
		/// The predecessor Node
		/// </summary>
		public Vertex Pi
		{
			get
			{
				return pi;
			}
			set
			{
				pi = value;
			}
		}

		public Node2 Node
		{
			get
			{
				return n;
			}
		}

		public Vertex(Node2 n)
		{
			this.color = BFSColors.White;
			this.n = n;
			this.adj = new ArrayList();

			foreach(Node2 no in n.Neighbors)
			{
				adj.Add(no);
			}
		}
	}*/

	public interface IBreadthFirstSearchable
	{
		BFSColors BFS_Color
		{
			get;
			set;
		}

		int BFS_d
		{
			get;
			set;
		}

		Node2 BFS_Pi
		{
			get;
			set;
		}
	}
}
