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

namespace QCGM.Graphs2
{
	/// <summary>
	/// Summary description for Dijkstra2.
	/// </summary>
	public class Dijkstra2
	{
		public const int Infinity = 14000;

		public ArrayList S = new ArrayList();

		public Dijkstra2(Graph2 G, Node2 source)
		{
			S.Clear();
			SimpleQueue Q = new SimpleQueue();
			
			if(G.Contains(source) == false)
			{
				throw new Exception("Graph does not contain source vertex. Cannot do it");
			}
			
			foreach(Node2 n in G.Nodes)
			{
				n.Dijkstra_d = Infinity;
				n.Dijkstra_Pi = null;
				Q.Enqueue(n);
			}
			source.Dijkstra_d = 0;

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

				S.Add(u);

				for(int i=0; i < 4; i++)
				{
					if(u.Neighbors[i] != null)
					{
						int b = u.Dijkstra_d + u.Cost[i];
						if(u.Neighbors[i].Dijkstra_d > b)
						{
							u.Neighbors[i].Dijkstra_d = b;
							u.Dijkstra_Pi = u;
						}
					}
				}
			}
		}

		public Node2 GetNode(Tile t)
		{
			foreach(Node2 u in S)
			{
				if(u.Tile == t)
				{
					return u;
				}
			}
			throw new Exception("Not'd found'd!");
		}

		public int GetShortestCostTo(Node2 n)
		{
			foreach(Node2 u in this.S)
			{
				if(u == n)
				{
					return u.Dijkstra_d;
				}
			}

			throw new Exception("Not found - I didn't find it!");
		}
	}
}
