/*
 * Copyright (c) 2005-2006 Erik Tigerholm <eriktigerholm@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

namespace OpenTraffic.Model.Graph.Partioning
{
    using System;
    using System.Collections.Generic;
    using OpenTraffic.Collections;

    public class Partioning<TV, TE>
        where TV : Vertex
        where TE : GraphEdge<TV>
    {
        public Dictionary<int, int> partition { get; private set; }

        private Graph<TV, TE> source;
        private List<float> weights;
        private MultiGraph<TV, GraphEdge<TV>> graph;
        private Random rand;

        public Partioning(Graph<TV, TE> g, List<float> weights)
        {
            this.weights = weights;
            partition = new Dictionary<int, int>();
            this.source = g;
            this.graph = new MultiGraph<TV, GraphEdge<TV>>();
            rand = new System.Random(31);
        }

        private float CalculateCost()
        {
            float cost = 0;

            foreach (MultiVertex<TV> mv in graph.Nodes)
            {
                foreach (GraphEdge<MultiVertex<TV>> e in graph.AdjLinks[mv])
                {
                    if (e.Source.Id != e.Target.Id)
                    {
                        if (partition[e.Source.Id] != partition[e.Target.Id])
                        {
                            cost++;
                        }
                    }
                }
            }
            return cost;
        }

        private float CalculateGain(MultiVertex<TV> v)
        {
            float gain = 0;
            // Calculate gain  
            foreach (GraphEdge<MultiVertex<TV>> e in graph.AdjLinks[v])
            {
                if (e.Source.Id != e.Target.Id)
                {
                    gain += ((partition[e.Target.Id] == partition[e.Source.Id]) ? -1 : 1);
                }
            }
            foreach (GraphEdge<MultiVertex<TV>> e in graph.RevAdjLinks[v])
            {
                if (e.Source.Id != e.Target.Id)
                {

                    gain += ((partition[e.Target.Id] == partition[e.Source.Id]) ? -1 : 1);
                }
            }

            return gain;
        }

        private void Coarsen()
        {
            SortedDictionary<Int32, MultiVertex<TV>> randomVertexList = new SortedDictionary<Int32, MultiVertex<TV>>();

            //            LinkedList<MultiVertex<V>> list = new LinkedList<MultiVertex<V>>(graph.Nodes);
            foreach (MultiVertex<TV> n in graph.Nodes)
            {
                randomVertexList.Add(rand.Next(), n);
            }

            graph.NewPoint();
            foreach (KeyValuePair<int, MultiVertex<TV>> mx in randomVertexList)
            {
                bool stop = false;
                if (graph.Nodes.Contains(mx.Value))
                {
                    List<GraphEdge<MultiVertex<TV>>> adj = graph.AdjLinks[mx.Value];
                    if (adj.Count != 0)
                    {
                        for (int i = rand.Next(adj.Count - 1); i < adj.Count; i++)
                        {
                            MultiVertex<TV> n = adj[i].Target;
                            if (mx.Value.Id != n.Id && graph.Nodes.Contains(n))
                            {
                                graph.Join(mx.Value, n);
                                stop = true;
                                break;
                            }
                        }
                    }

                    adj = graph.RevAdjLinks[mx.Value];
                    if (!stop && adj.Count != 0)
                    {
                        for (int j = rand.Next(adj.Count - 1); j < adj.Count; j++)
                        {
                            MultiVertex<TV> n = adj[j].Source;
                            if (mx.Value.Id != n.Id && graph.Nodes.Contains(n))
                            {
                                graph.Join(mx.Value, n);
                                break;
                            }
                        }
                    }
                }
            }
        }

        private void MakePartition(float weight1)
        {
            MultiVertex<TV> startNode = null;
            // Just take the first;
            float maxWeight = 0;
            foreach (MultiVertex<TV> node in graph.Nodes)
            {
                startNode = node;
                partition.Add(node.Id, 0);
                maxWeight += node.Weight;

            }

            if (startNode != null)
            {
                partition[startNode.Id] = 1;

                float weight = startNode.Weight;


                List<MultiVertex<TV>> list = new List<MultiVertex<TV>>();
                list.Add(startNode);
                while (weight < maxWeight * weight1)
                {
                    // Dictionary<MultiVertex<TV>, bool> possibleVertexList = new Dictionary<MultiVertex<TV>, bool>();
                    MultiVertex<TV> v = null;
                    v = AddNeighboorVertexWithGreatestGain(list, v, false);
                    if (v == null)
                    {
                        v = AddNeighboorVertexWithGreatestGain(list, v, true);
                    }
                    if (v == null)
                    {
                        return;
                    }
                    partition[v.Id] = 1;
                    weight += v.Weight;
                    list.Add(v);
                }
            }
        }

        private MultiVertex<TV> AddNeighboorVertexWithGreatestGain(
            List<MultiVertex<TV>> list,
            MultiVertex<TV> v,
            bool reverse
            )
        {
            float maxGain = Int32.MinValue;
            // Add all vertexes connected and calculate their gain   

            foreach (MultiVertex<TV> mv in list)
            {
                List<GraphEdge<MultiVertex<TV>>> vList = reverse ? graph.RevAdjLinks[mv] : graph.AdjLinks[mv];
                foreach (GraphEdge<MultiVertex<TV>> edge in  vList)
                {

                    MultiVertex<TV> possibleVertex = reverse ? edge.Source : edge.Target;
                    if (partition[possibleVertex.Id] == 0)
                    {
                        float gain = this.CalculateGain(possibleVertex);
                        if (gain > maxGain)
                        {
                            maxGain = gain;
                            v = possibleVertex;
                        }
                    }
                }



            }
            return v;
        }

        private void BetterPartition(float weight1)
        {
            Dictionary<MultiVertex<TV>, float> dd1 = new Dictionary<MultiVertex<TV>, float>();
            Dictionary<MultiVertex<TV>, float> dd2 = new Dictionary<MultiVertex<TV>, float>();
            List<MultiVertex<TV>> clearList = new List<MultiVertex<TV>>();
            float weightNode1 = 0;
            float weightNode2 = 0;


            //Calculate initialized cost
            foreach (MultiVertex<TV> kv in graph.Nodes)
            {
                if (partition[kv.Id] == 0)
                {
                    weightNode1 += kv.Weight;
                    dd1.Add(kv, 1);
                }
                else
                {
                    weightNode2 += kv.Weight;
                    dd2.Add(kv, 1);
                }

            }
            // float maxWeight = weightNode1 + weightNode2;
            float startCost = CalculateCost();
            float maxCost = startCost;
            float gain = 0;


            // Change 50 nodes
            for (int i = 0; i < 50; i++)
            {
                Dictionary<MultiVertex<TV>, float> dd;
                if (weightNode1 * weight1 > weightNode2 * (1 - weight1))
                {
                    dd = dd1;
                }
                else
                {
                    dd = dd2;
                }
                if (dd.Count == 0) break;
                float localMaxGain = float.MinValue;
                MultiVertex<TV> v = null;
                foreach (KeyValuePair<MultiVertex<TV>, float> pmx in dd)
                {
                    float g = CalculateGain(pmx.Key);
                    if (g > localMaxGain)
                    {
                        v = pmx.Key;
                        localMaxGain = g;
                    }
                }
                gain += CalculateGain(v);
                float weightDiff = (partition[v.Id] == 0) ? v.Weight : -v.Weight; ;
                weightNode1 -= weightDiff;
                weightNode2 += weightDiff;
                ChangePartition(v);
                clearList.Add(v);
                System.Diagnostics.Debug.Assert(startCost - gain == CalculateCost());
                if ((startCost - gain) < maxCost)
                {
                    clearList.Clear();
                    maxCost = startCost - gain;
                }
                dd.Remove(v);
            }
            foreach (MultiVertex<TV> v in clearList)
            {
                ChangePartition(v);
            }
            System.Diagnostics.Debug.Assert(startCost >= CalculateCost());
        }

        private void ChangePartition(MultiVertex<TV> v)
        {
            partition[v.Id] = partition[v.Id] == 1 ? 0 : 1;
        }

        private static float Split(Dictionary<int, float> weights1, Dictionary<int, float> part1, Dictionary<int, float> part2)
        {
            TrafficHeap<float, int> list = new TrafficHeap<float, int>(weights1.Count);
            float tot = 0;
            float weight1 = 0;
            foreach (KeyValuePair<int, float> w in weights1)
            {
                tot += w.Value;
                list.Add(-w.Value, w.Key);
            }

            while (list.Count != 0)
            {
                int i = list.Pop().Value;
                if ((weights1[i] + weight1) <= (tot / 2))
                {
                    part1.Add(i, weights1[i]);
                    weight1 += weights1[i];
                }
                else
                {
                    part2.Add(i, weights1[i]);
                }
            }
            return weight1 / tot;

        }

        public void Run()
        {
            Dictionary<int, float> w = new Dictionary<int, float>();
            Dictionary<int, int> part = new Dictionary<int, int>();

            for (int i = 0; i < weights.Count; i++)
            {
                w.Add(i + 1, weights[i]);
            }


            foreach (TV node in source.Nodes)
            {
                part.Add(node.Id, 0);

            }
            Run(w, part, part, 0);
            partition = part;
        }

        private static void RenamePart(Dictionary<int, int> from, Dictionary<int, int> to, int fromv, int tov)
        {
            foreach (KeyValuePair<int, int> v in from)
            {
                if (v.Value == fromv)
                {
                    to[v.Key] = tov;
                }
            }
        }

        private void Run(Dictionary<int, float> weights1, Dictionary<int, int> part,
            Dictionary<int, int> result, int from) //List<float> weights) 
        {
            Dictionary<int, float> part1 = new Dictionary<int, float>();
            Dictionary<int, float> part2 = new Dictionary<int, float>();
            float weightFirstPart = Split(weights1, part1, part2);


            Dictionary<int, int> partition = RunBiPartition(part, from, 1 - weightFirstPart);
            if (part1.Count == 1)
            {
                foreach (KeyValuePair<int, float> k in part1)
                {
                    RenamePart(partition, result, 0, k.Key);
                }

            }
            if (part2.Count == 1)
            {
                foreach (KeyValuePair<int, float> k in part2)
                {
                    RenamePart(partition, result, 1, k.Key); //soap
                }

            }
            if (part1.Count > 1) Run(part1, partition, result, 0);
            if (part2.Count > 1) Run(part2, partition, result, 1);


            // If more than one element just call run one time more.
            // We dont not need to renamepart or anything. The child will take care of it
        }


        private Dictionary<int, int> RunBiPartition(Dictionary<int, int> part, int from, float weight1)
        {
           
            partition = new Dictionary<int, int>();

            this.graph = new MultiGraph<TV, GraphEdge<TV>>();
            Dictionary<int, MultiVertex<TV>> lookup = new Dictionary<int, MultiVertex<TV>>();
            foreach (TV n in source.Nodes)
            {
                if (part.ContainsKey(n.Id) && (part[n.Id] == from))
                {
                    MultiVertex<TV> mv = new MultiVertex<TV>(n);
                    lookup.Add(mv.Id, mv);
                    graph.Add(mv);

                }
            }
            foreach (TE n in source.Links)
            {
                if (part.ContainsKey(n.Target.Id) && part.ContainsKey(n.Source.Id) &&
                    (part[n.Source.Id] == from) && (part[n.Target.Id] == from))
                {

                    graph.Add(new GraphEdge<MultiVertex<TV>>(n.Id, lookup[n.Source.Id],
                        lookup[n.Target.Id], null));
                }
            }
            //           graph.ExportToLatex(8, 10, "c:\\temp\\stockholm_orig_" + (++i) + ".graph",null);
            while (this.graph.Nodes.Count > 100)
            {
                this.Coarsen();
                //            graph.ExportToLatex(8, 10, "c:\\temp\\stockholm_coarsen_" + (++i) + ".graph",null);
            }

            MakePartition(weight1);
            //          graph.ExportToLatex(8, 10, "c:\\temp\\stockholm_part_" + (++i) + ".graph",partition);

            //    this.BetterPartition(weight1);

            try
            {
                while (true)
                {
                    foreach (KeyValuePair<MultiVertex<TV>, MultiVertex<TV>> k
                        in graph.ReverseToNextPoint())
                    {
                        partition.Add(k.Value.Id, partition[k.Key.Id]);
                    }
                    //          this.BetterPartition(weight1);
                    //                graph.ExportToLatex(8, 10, "c:\\temp\\stockholm_expand_" + (++i) + ".graph", partition);
                }
            }
            catch (InvalidOperationException)
            {

            }
            return partition;
        }

    }
}