using System;
using System.Collections;
using QCGM.Graphs;

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

		protected ArrayList Vertices;
		protected Graph G;
		protected Node s;
		public Node Start
		{
			get
			{
				return s;
			}
		}

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

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

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

			foreach(Graphs.Node n in G.Nodes)
			{
				Vertices.Add(new Vertex(n));
			}
		}

		public void Perform(Node s)
		{
			ArrayList V = Vertices;
			this.s = s;
			V.Remove(s);
			
			foreach(Node 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;

			PriorityQueue Q = new PriorityQueue();

			Q.Enqueue(s, s.BFS_d);
			while(Q.Count != 0)
			{
				Node u = (Node)Q.Dequeue();
				foreach(Node v in u.Neighbors)
				{
					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, v.BFS_d);
					}
				}
				u.BFS_Color = BFSColors.Black;
			}
		}

		/// <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(Node v)
		{
			ArrayList L = new ArrayList();

			Traverse(s, v, ref L);

			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(Node v)
		{
			int i = 0;
			Traverse(s, v, ref i);
			return i;
		}


		/// <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(Node s, Node 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(Node s, Node 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(Vertex u)
		{
			u.Color = BFSColors.Gray;

			time++;

			u.D = time;

			foreach(Vertex v in u.Adjacent)
			{
				if(v.Color == BFSColors.White)
				{
					v.Pi = u;
					Visit(v);
				}
			}

			u.Color = BFSColors.Black;
			u.F = time;
			time++;
		}
	}

	public enum BFSColors { White, Gray, Black };

	public class Vertex
	{
		Node 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 QCGM.Graphs.Node Node
		{
			get
			{
				return n;
			}
		}

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

			foreach(Node no in n.Neighbors)
			{
				adj.Add(no);
			}
		}
	}

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

		int BFS_d
		{
			get;
			set;
		}

		Node BFS_Pi
		{
			get;
			set;
		}
	}

}
