using System;
using System.Collections;

using CategoryTheory;

namespace MathGraph
{
	/// <summary>
	/// Digraph
	/// </summary>
	public class Digraph
	{
		
		/// <summary>
		/// The "in not a path" string
		/// </summary>
		static public readonly string NotPath = "This diagram is not a path";
		
		/// <summary>
		/// Vertices
		/// </summary>
		protected ArrayList vertices = new ArrayList();


		/// <summary>
		/// Constructor
		/// </summary>
		public Digraph()
		{
		}

		/// <summary>
		/// Transforms digraph
		/// </summary>
		/// <param name="vertTransformer">Vertex transformer</param>
		/// <param name="edgeTransformer">Edge transformer</param>
		public void Transform(ObjectTransformer vertTransformer, ObjectTransformer edgeTransformer)
		{
			foreach (DigraphVertex v in vertices)
			{
				v.Object = vertTransformer(v.Object);
				foreach (DigraphEdge edge in v.OutcomingEdges)
				{
					edge.Object = edgeTransformer(edge.Object);
				}
			}
		}

		/// <summary>
		/// Adds vertex to this digraph
		/// </summary>
		/// <param name="vertex">Vertex to add</param>
		public void AddVertex(DigraphVertex vertex)
		{
			if (vertices.Contains(vertex))
			{
				throw new Exception("Vertex already exists");
			}
			vertices.Add(vertex);
		}
		
		/// <summary>
		/// Removes vertex from this digraph
		/// </summary>
		/// <param name="vertex">Vertex to remove</param>
		public void RemoveVertex(DigraphVertex vertex)
		{
			vertices.Remove(vertex);
			vertex.RemoveObject();
		}
		
		/// <summary>
		/// Resets indexes if vetices
		/// </summary>
		public void Reset()
		{
			foreach (DigraphVertex v in vertices)
			{
				v.Index = -1;
			}
		}

		/// <summary>
		/// Loops of digraph
		/// </summary>
		public ArrayList Loops
		{
			get
			{
				ArrayList list = new ArrayList();
				Reset();
				foreach (DigraphVertex v in vertices)
				{
					v.GetLoops(list);
					Reset();
				}
				return list;
			}
		}

		/// <summary>
		/// Count of vertices
		/// </summary>
		public int Count
		{
			get
			{
				return vertices.Count;
			}
		}

		/// <summary>
		/// Access to i th vertex
		/// </summary>
		public DigraphVertex this[int i]
		{
			get
			{
				return vertices[i] as DigraphVertex;
			}
		}

		/// <summary>
		/// Digraph path. Throws exception if digraph is not a path
		/// </summary>
		public DigraphEdge[] Path
		{
			get
			{
				ArrayList e = new ArrayList();
				ArrayList v = new ArrayList();
				DigraphVertex current = null;
				foreach (DigraphVertex vertex in vertices)
				{
					if (vertex.IncomingEdges.Count == 0)
					{
						current = vertex;
						break;
					}
				}
				if (current == null)
				{
					throw new Exception(NotPath);
				}
				v.Add(current);
				while (current.OutcomingEdges.Count > 0)
				{
					if (current.OutcomingEdges.Count > 1)
					{
						throw new Exception(NotPath);
					}
					DigraphEdge edge = current.OutcomingEdges[0] as DigraphEdge;
					current = edge.Target;
					if ((current.IncomingEdges.Count > 1) | v.Contains(current))
					{
						throw new Exception(NotPath);
					}
					v.Add(current);
					e.Add(edge);
				}
				foreach (DigraphVertex vertex in vertices)
				{
					if (!v.Contains(vertex))
					{
						throw new Exception(NotPath);
					}
				}
				DigraphEdge[] path = new DigraphEdge[e.Count];
				for (int i = 0; i < path.Length; i++)
				{
					path[i] = e[i] as DigraphEdge;
				}
				return path;
			}
		}
	}

}

