// Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.

namespace System.Data.Entity.Core.Mapping.Update.Internal
{
    using System.Collections.Generic;
    using System.Data.Entity.Utilities;
    using System.Globalization;
    using System.Linq;
    using System.Text;

    // <summary>
    // A directed graph class.
    // </summary>
    // <remarks>
    // Notes on language (in case you're familiar with one or the other convention):
    // node == vertex
    // arc == edge
    // predecessor == incoming
    // successor == outgoing
    // </remarks>
    // <typeparam name="TVertex"> Type of nodes in the graph </typeparam>
    internal class Graph<TVertex>
    {
        // <summary>
        // Initialize a new graph
        // </summary>
        // <param name="comparer"> Comparer used to determine if two node references are equivalent </param>
        internal Graph(IEqualityComparer<TVertex> comparer)
        {
            DebugCheck.NotNull(comparer);

            m_comparer = comparer;
            m_successorMap = new Dictionary<TVertex, HashSet<TVertex>>(comparer);
            m_predecessorCounts = new Dictionary<TVertex, int>(comparer);
            m_vertices = new HashSet<TVertex>(comparer);
        }

        // <summary>
        // Gets successors of the node (outgoing edges).
        // </summary>
        private readonly Dictionary<TVertex, HashSet<TVertex>> m_successorMap;

        // <summary>
        // Gets number of predecessors of the node.
        // </summary>
        private readonly Dictionary<TVertex, int> m_predecessorCounts;

        // <summary>
        // Gets the vertices that exist in the graph.
        // </summary>
        private readonly HashSet<TVertex> m_vertices;

        private readonly IEqualityComparer<TVertex> m_comparer;

        // <summary>
        // Returns the vertices of the graph.
        // </summary>
        internal IEnumerable<TVertex> Vertices
        {
            get { return m_vertices; }
        }

        // <summary>
        // Returns the edges of the graph in the form: [from, to]
        // </summary>
        internal IEnumerable<KeyValuePair<TVertex, TVertex>> Edges
        {
            get
            {
                foreach (var successors in m_successorMap)
                {
                    foreach (var vertex in successors.Value)
                    {
                        yield return new KeyValuePair<TVertex, TVertex>(successors.Key, vertex);
                    }
                }
            }
        }

        // <summary>
        // Adds a new node to the graph. Does nothing if the vertex already exists.
        // </summary>
        // <param name="vertex"> New node </param>
        internal void AddVertex(TVertex vertex)
        {
            m_vertices.Add(vertex);
        }

        // <summary>
        // Adds a new edge to the graph. NOTE: only adds edges for existing vertices.
        // </summary>
        // <param name="from"> Source node </param>
        // <param name="to"> Target node </param>
        internal void AddEdge(TVertex from, TVertex to)
        {
            // Add only edges relevant to the current graph vertices
            if (m_vertices.Contains(from)
                && m_vertices.Contains(to))
            {
                HashSet<TVertex> successors;
                if (!m_successorMap.TryGetValue(from, out successors))
                {
                    successors = new HashSet<TVertex>(m_comparer);
                    m_successorMap.Add(from, successors);
                }
                if (successors.Add(to))
                {
                    // If the edge does not already exist, increment the count of incoming edges (predecessors).
                    int predecessorCount;
                    if (!m_predecessorCounts.TryGetValue(to, out predecessorCount))
                    {
                        predecessorCount = 1;
                    }
                    else
                    {
                        ++predecessorCount;
                    }
                    m_predecessorCounts[to] = predecessorCount;
                }
            }
        }

        // <summary>
        // DESTRUCTIVE OPERATION: performing a sort modifies the graph
        // Performs topological sort on graph. Nodes with no remaining incoming edges are removed
        // in sort order (assumes elements implement IComparable(Of TVertex))
        // </summary>
        // <returns> true if the sort succeeds; false if it fails and there is a remainder </returns>
        internal bool TryTopologicalSort(out IEnumerable<TVertex> orderedVertices, out IEnumerable<TVertex> remainder)
        {
            // populate all predecessor-less nodes to root queue
            var rootsPriorityQueue = new SortedSet<TVertex>(Comparer<TVertex>.Default);

            foreach (var vertex in m_vertices)
            {
                int predecessorCount;
                if (!m_predecessorCounts.TryGetValue(vertex, out predecessorCount)
                    || 0 == predecessorCount)
                {
                    rootsPriorityQueue.Add(vertex);
                }
            }

            var result = new TVertex[m_vertices.Count];
            var resultCount = 0;

            // perform sort
            while (0 < rootsPriorityQueue.Count)
            {
                // get the vertex that is next in line in the secondary ordering
                var from = rootsPriorityQueue.Min;
                rootsPriorityQueue.Remove(from);

                // remove all outgoing edges (free all vertices that depend on 'from')
                HashSet<TVertex> toSet;
                if (m_successorMap.TryGetValue(from, out toSet))
                {
                    foreach (var to in toSet)
                    {
                        var predecessorCount = m_predecessorCounts[to] - 1;
                        m_predecessorCounts[to] = predecessorCount;
                        if (predecessorCount == 0)
                        {
                            // 'to' contains no incoming edges, so it is now a root
                            rootsPriorityQueue.Add(to);
                        }
                    }

                    // remove the entire successor set since it has been emptied
                    m_successorMap.Remove(from);
                }

                // add the freed vertex to the result and remove it from the graph
                result[resultCount++] = from;
                m_vertices.Remove(from);
            }

            // check that all elements were yielded
            if (m_vertices.Count == 0)
            {
                // all vertices were ordered
                orderedVertices = result;
                remainder = Enumerable.Empty<TVertex>();
                return true;
            }
            else
            {
                orderedVertices = result.Take(resultCount);
                remainder = m_vertices;
                return false;
            }
        }

        // <summary>
        // For debugging purposes.
        // </summary>
        public override string ToString()
        {
            var sb = new StringBuilder();

            foreach (var outgoingEdge in m_successorMap)
            {
                var first = true;

                sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}] --> ", outgoingEdge.Key);

                foreach (var vertex in outgoingEdge.Value)
                {
                    if (first)
                    {
                        first = false;
                    }
                    else
                    {
                        sb.Append(", ");
                    }
                    sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}]", vertex);
                }

                sb.Append("; ");
            }

            return sb.ToString();
        }
    }
}
