/*========================================================================
        Copyright (C) 2006 by Geir-Tore Lindsve, Torbjørn Meistad 
        and Yngve Raudberget, hereby refered to as "the authors".
                        All rights reserved

    Permission is hereby granted, without written agreement and without
    license or royalty fees, to use, reproduce, prepare derivative
    works, distribute, and display this software and its documentation
    for NONCOMMERCIAL RESEARCH AND EDUCATIONAL PURPOSES, provided 
    that (1) the above copyright notice and the following two paragraphs 
    appear in all copies of the source code and (2) redistributions, 
    including without limitation binaries, reproduce these notices in 
    the supporting documentation. 

    IN NO EVENT SHALL THE AUTHORS, OR DISTRIBUTORS OF THIS SOFTWARE 
    BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, 
    OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE 
    AND ITS DOCUMENTATION, EVEN IF THE AUTHORS OR ANY OF THE ABOVE 
    PARTIES HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    THE AUTHORS SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING,
    BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
    FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
    ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO
    OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
    MODIFICATIONS.
========================================================================*/

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;

using Iesi.Collections;
using Casper.Exceptions;
using Casper.Data;

namespace Casper.Algorithm.VariableOrdering
{
    /// <summary>
    /// Class for supporting minimum width ordering.
    /// </summary>
    public class MinimumWidthOrder:IVariableOrdering
    {
        private ConstraintGraph cGraph;
        private ConstraintGraph cGraphLocal;
        private Boolean firstCallToCount = true;
        List<int> varOrder;
        private static int index;


        /// <summary>
        /// Initializes a new instance of the <see cref="T:MinimumWidthOrdering"/> class.
        /// </summary>
        /// <param name="cGraph">The constraint graph.</param>
        public MinimumWidthOrder(ConstraintGraph cGraph)
        {
            this.cGraphLocal = new ConstraintGraph();
            this.cGraph = cGraph;
            ICollection keys = cGraph.CGraph.Keys;
            IEnumerator keyenum = keys.GetEnumerator();

            //Create a local copy of constraintGraph.
            //this copy will be edited during the
            //creation of the minimum width variable ordering.
            while (keyenum.MoveNext())
            {
                Set interconnNodes = new HashedSet();
                AdjacencyList adjList = (AdjacencyList)cGraph.CGraph[keyenum.Current];
                interconnNodes.AddAll(adjList.Variables);
                AdjacencyList localList = new AdjacencyList();
                localList.Variables=interconnNodes;
                this.cGraphLocal.CGraph[keyenum.Current] = localList;
            }
            varOrder = new List<int>();
            try
            {
                GenerateMinWidthOrder();
            }
            catch (CasperException) { throw; }
        }

        /// <summary>
        /// Generates the minimum width order.
        /// </summary>
        private void GenerateMinWidthOrder()
        {
            Hashtable unSortedList = new Hashtable();
            try
            {
                ICollection keys = (ICollection)cGraph.CGraph.Keys;
                IEnumerator keyEnum = (IEnumerator)keys.GetEnumerator();
                while(keyEnum.MoveNext())
                {
                    if (!cGraphLocal.CGraph.Contains((int)keyEnum.Current))
                        continue;
                    AdjacencyList adjList = (AdjacencyList)cGraphLocal.CGraph[(int)keyEnum.Current];
                    
                    List<int> collisionList = (List<int>)unSortedList[adjList.VariableWidth];
                    if (collisionList == null)
                    {
                        collisionList = new List<int>();
                        unSortedList[adjList.VariableWidth] = collisionList;
                    }
                    collisionList.Add((int)keyEnum.Current);
                    collisionList.Sort();
                    
                }
                SortedList sortedList = new SortedList(unSortedList);
                ICollection SortedKeys = (ICollection)sortedList.Keys;
                IEnumerator ie = (IEnumerator)SortedKeys.GetEnumerator();
                ie.Reset();
                index = this.cGraphLocal.CGraph.Count - 1;
                if (firstCallToCount == true)
                {
                    for (int i = 0; i < cGraph.CGraph.Count; i++)
                        varOrder.Add(0);
                    firstCallToCount = false;
                }

                while (ie.MoveNext())
                {
                    List<int> varList = (List<int>)sortedList[(int)ie.Current];
                    varList.Sort();
                    for (int i = 0; i < varList.Count; i++)
                    {
                        //Remove current node and all the edges connected to it
                        //from the constraint graph.
                        removeNodeFromConstraintGraph(varList[i]);
                        if (index >= 0)
                        {
                            varOrder[index] = varList[i];
                            index--;
                        }
                        if (index >= 0)
                        {
                            //Continue generation of the min width ordering based on 
                            //the edited graph where the current node and all its edges 
                            //have been removed from the constraint graph.
                            GenerateMinWidthOrder();
                        }
                    }
                }
            }
            catch (Exception e) 
            {
                throw new CasperException("Error in minimum width ordering: ", e); 
            }
        }

        /// <summary>
        /// Removes the node from the constraint graph, also deleting all 
        /// edges that the node
        /// </summary>
        /// <param name="node">The node.</param>
        private void removeNodeFromConstraintGraph(int node)
        {
            this.cGraphLocal.CGraph.Remove(node);//removes the selected node from the graph.
            ICollection ic = (ICollection)cGraphLocal.CGraph.Keys;//.GetEnumerator();
            IEnumerator ie = ic.GetEnumerator();
            while (ie.MoveNext())
            {
                AdjacencyList adjList = (AdjacencyList)this.cGraphLocal.CGraph[(int)ie.Current];
                adjList.Variables.Remove(node);//removes all occurences of the removed node in 
                //other nodes adjacency list which is equal to removing the edges between the nodes; 
                //if a node is not in another nodes adjacency list then there is no edge between them.
                adjList.VariableWidth = adjList.Variables.Count;//should be moved into AdjacencyList
            }
        }

        /// <summary>
        /// Gets the next variable according to the minimum width ordering.
        /// </summary>
        /// <param name="numberInQueue">The number in queue.</param>
        /// <returns>The next variable in relation to the number in queue.</returns>
        public int GetNextVar(int numberInQueue)
        {
            return varOrder[numberInQueue];
        }
    }
}