﻿namespace Graphs.Algorithms
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Contracts;
    using Graphs.Algorithms.Components;
    using Graphs.Algorithms.Components.Contracts;
    using Graphs.Components.Contracts;
    using Graphs.Algorithms.Common;

    /// <summary>
    /// Finds the minimal spanning tree of the provided undirected graph using Prim's algorithm.
    /// NOTE: The algorithm might perform better than Kruskal with the current graph architecture
    /// as it is more memory efficient.
    /// </summary>
    /// <typeparam name="T">IComparable generic type</typeparam>
    public sealed class Prim<T> : AlgorithmCore<T>, IMinimalSpanningTree<T>
        where T : IComparable
    {
        public Prim()
        {
        }

        public Graph<T> FindMST()
        {
            Graph<T> tree = new Graph<T>();
            ISet<INode<T>> nodes = new HashSet<INode<T>>();
            INode<T> startNode = this.Graph.Nodes.FirstOrDefault();
            
            startNode.IsVisited = true;
            nodes.Add(startNode);

            while (nodes.Count < this.Graph.Nodes.Count)
            {
                IDualEdge<T> minEdge = this.FindMinimalEdge(nodes);

                this.CloneEdge(tree, minEdge);

                minEdge.SecondNode.IsVisited = true;
                nodes.Add(minEdge.SecondNode);
            }

            this.UnvisitAllNodes();

            return tree;
        }

        private IDualEdge<T> FindMinimalEdge(ISet<INode<T>> nodes)
        {
            IDualEdge<T> minEdge = null;
            bool isSet = false;

            foreach (INode<T> node in nodes)
            {
                foreach (IEdge<T> edge in node.AdjacentEdges)
                {
                    if ((!isSet && !edge.Node.IsVisited) ||
                        (minEdge != null && edge.Weight < minEdge.Weight && !edge.Node.IsVisited))
                    {
                        minEdge = new DualEdge<T>(node, edge.Node, edge.Weight);
                        isSet = true;
                    }
                }
            }

            return minEdge;
        }

        private void CloneEdge(Graph<T> tree, IDualEdge<T> edge)
        {
            INode<T> firstNode = this.CloneNodeIfNonExistant(tree, edge.FirstNode);
            INode<T> secondNode = this.CloneNodeIfNonExistant(tree, edge.SecondNode);

            firstNode.UndirectedConnection(secondNode, edge.Weight);
        }

        private INode<T> CloneNodeIfNonExistant(Graph<T> tree, INode<T> node)
        {
            INode<T> newNode = tree.FindNode(node.Value);

            if (newNode == null)
            {
                newNode = (INode<T>)node.Clone();
                tree.AddNode(newNode);
            }

            return newNode;
        }
    }
}
