using System;
using System.Collections;
using QCGM.Graphs;
using QCGM.Graphs.Dijkstras;
using QCGM.Graphs2;
using System.Windows.Forms;


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

		protected ArrayList Vertices = new ArrayList();
		
		protected ArrayList Known = new ArrayList();

		protected Graph2 G;

		public Graph2 Graph
		{
			get
			{
				return G;
			}
		}

		protected Node2 s;
		public Node2 Start
		{
			get
			{
				return s;
			}
		}
		
		public Dijkstra()
		{
			// nothing
		}

		/// <summary>
		/// Initializes the source vertex for the search algorithm. After initialization, Pi[v] = Nil for all
		/// vertices, D[v] = Infinity for all vertices excluding "source".
		/// </summary>
		/// <param name="source"></param>
		/// <remarks>Omega(V)-time procedure</remarks>
		private void InitializeSingleSource(ref Node2 source)
		{
			for(int j=0; j < Vertices.Count; j++)
			{
				Node2 v = (Node2)Vertices[j];
					
				v.Dijkstra_d = Dijkstra.Infinity;
				v.Dijkstra_Pi = null;
				v.visited = false;
			}

			source.Dijkstra_d = 0;
			source.Dijkstra_Pi = null;

			;
		}

		/// <summary>
		/// This method performs a relaxation step on edge (u,v).
		/// 
		/// We test whether we can imporove the shortest path to v found so far by going through u and, if so,
		/// updating d[v] and pi[v]. A relaxation step may decrease teh value of the shortest-path estimate
		/// d[v] and update v's predecessor pi[v].
		/// </summary>
		/// <param name="u">Edge source vertex</param>
		/// <param name="v">Edge destination vertex</param>
		/// <param name="w">Search function, e.g. Depth-First Search, Breadth-First Search, etc.</param>
		//private void Relax(Node u, Node v, SearchMethod w)
		private void Relax(Node2 u, ref Node2 v, int w)
		{
			if (v.Dijkstra_d > (u.Dijkstra_d + w))
			{
				v.Dijkstra_d = (u.Dijkstra_d + w);
				v.Dijkstra_Pi = u;
			}
		}

		public void Perform(Graph2 G, ref Node2 source)
		{
			/// Build Vertices
			this.G = G;
			this.Vertices.Clear();
			foreach(Node2 n in G.Nodes)
			{
				this.Vertices.Add(n);
			}

			InitializeSingleSource(ref source);

			/*//foreach(Node2 n in this.
			if(u.Dijkstra_d != 10000)
			{
				int i = u.Dijkstra_d;
			}*/

			SimpleQueue Q = new SimpleQueue();

			this.Known.Clear();

			// Add all vertices in the Graph to the PQ.
			// Their priority is indicated by the d values of each vertex
			foreach(Node2 v in Vertices)
			{
				Q.Enqueue(v);
			}

			Node2 u;

			while(Q.Count > 0)
			{
				u = (Node2)Q.ExtractMin();

				this.Known.Add(u);

				if(u.Tile.X == 7 && u.Tile.Y == 8)
				{
					;
				}

				for(int i=0; i < 4; i++)
				{
					if(u.Neighbors[i] != null)
					{
						//Relax(u, ref u.Neighbors[i], u.Cost[i]);

						if (u.Neighbors[i].Dijkstra_d > (u.Dijkstra_d + u.Cost[i]))
						{
							u.Neighbors[i].Dijkstra_d = (u.Dijkstra_d + u.Cost[i]);
							u.Neighbors[i].Dijkstra_Pi = u;
						}
					}
				}
			}
		}

		/// <summary>
		/// Returns the cost associated with travelling from the source node (computed at the Perform method), to
		/// the destination node u.
		/// </summary>
		/// <param name="u">The destination node</param>
		/// <returns>The cost of travel from the starting Node to Node u.</returns>
		public int SmallestCostTo(Node2 u)
		{
			if(this.Known.Contains(u))
			{
				Node2 ud = (Node2)this.Known[Known.IndexOf(u)];
				return ud.Dijkstra_d;
				
			}
			else
			{
				throw new Exception ("Couldn't find it!");
			}
		}

		public ArrayList ShortestPathTo(Node2 u)
		{
			ArrayList l = new ArrayList();

			l.Add(u);
			
			while(u.Dijkstra_Pi != null)
			{
				l.Add(u.Dijkstra_Pi);
				u = u.Dijkstra_Pi;
			}

			return l;
		}
	}

	public interface IDijkstraSearchable
	{
		int Dijkstra_d
		{
			get;
			set;
		}

		Node2 Dijkstra_Pi
		{
			get;
			set;
		}
	}
}
