/*========================================================================
        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;
using Casper.Algorithm.VariableOrdering;

namespace Casper.Algorithm
{
    /// <summary>
    /// Implementation of "Generalized lookahead" with "Select value forward checking".   
    /// </summary>
    public class GeneralizedLookahead
    {
        /// <summary>
        /// Constant which represent the minimum width variable ordering.
        /// </summary>
        public const int MINWIDTHORDER = 1;
        /// <summary>
        /// Constant which represent ascending variable ordering.
        /// </summary>
        public const int ASCENDINGORDER = 0;

        private LookaheadVariables vars;
        private Consistent consistent;
        private Hashtable allRemovedValues;
        private Hashtable affectedVariables;
        private Hashtable assignedVars;
        private CspVariableOrdering variableOrdering;
        private ConstraintGraph cGraph;

        /// <summary>
        /// Initializes a new instance of the <see cref="T:GeneralizedLookahead"/> class.
        /// </summary>
        /// <param name="expressions">The expressions.</param>
        /// <param name="variableOrdering">The variable ordering.</param>
        /// <param name="cGraph">The constraint graph.</param>
        public GeneralizedLookahead(CSPExpressions expressions, CspVariableOrdering variableOrdering, ConstraintGraph cGraph)
        {
            this.consistent = new Consistent(expressions);
            this.variableOrdering = variableOrdering;
            this.cGraph = cGraph;
        }

        /// <summary>
        /// Gets or sets the variables.
        /// </summary>
        /// <value>The variables.</value>
        internal LookaheadVariables Vars
        {
            get { return vars; }
            set { vars = value; }
        }

        /// <summary>
        /// Adds a variable to the hashtable over assigned variables.
        /// </summary>
        /// <param name="var">The variable.</param>
        private void AddVarToAssignedVars(LookAheadVarDom var)
        {
            this.assignedVars.Add(var.VarID, var);
        }

        /// <summary>
        /// Removes a variable from the hashtable over assigned variables.
        /// </summary>
        /// <param name="var">The variable.</param>
        internal void RemoveVarFromAssignedVars(LookAheadVarDom var)
        {
            this.assignedVars.Remove(var.VarID);
        }

        /// <summary>
        /// Gets or sets the variable ordering.
        /// </summary>
        /// <value>The variable ordering.</value>
        public CspVariableOrdering VariableOrdering
        {
            get { return variableOrdering; }
            set { variableOrdering = value; }
        }
        
        /// <summary>
        /// The Generalized Lookahead routine from Dechter page 133
        /// </summary>
        /// <param name="varDoms">List of CasperVarDom objects, with variable and domain data</param>
        /// <returns>List of objects implementing the IConsistentVar interface</returns>
        /// <exception cref="T:Casper.Exceptions.CasperException"></exception>
        public List<LookAheadVarDom> LookAhead(List<CasperVarDom> varDoms)
        {
            List<LookAheadVarDom> prevAssign = new List<LookAheadVarDom>();

            this.allRemovedValues = new Hashtable();
            this.affectedVariables = new Hashtable();
            this.assignedVars = new Hashtable();

            vars = MakeLookAheadVarDoms(varDoms, variableOrdering, cGraph);
            int i = 0;

            LookAheadVarDom varDom = vars.GetVar(0);
            int? selectedValue = null;

            while (varDom != null)
            {
                try
                {
                    selectedValue = SelectValue(varDom, i);
                }
                catch (CasperException) { throw; }
                if (selectedValue == null) //backtrack
                {
                    if (prevAssign.Count > 0)
                    {
                        RemoveVarFromAssignedVars(prevAssign[prevAssign.Count - 1]);
                        prevAssign.RemoveAt(prevAssign.Count - 1);
                    }
                    i--;
                    if (i < 0) return null; //no solutions found
                    BacktrackDomains(vars.GetVar(i));
                }
                else //step forward
                {
                    prevAssign.Add(varDom);
                    AddVarToAssignedVars(varDom);
                    i++;
                }
                varDom = vars.GetVar(i);
            }
            return prevAssign;
        }

        /// <summary>
        /// Implementation of Select Value Forward Checking from Dechter page 134
        /// Internal method used by the LookAhead method
        /// </summary>
        /// <param name="var">Variable to be checked</param>
        /// <param name="i">The index "var" has in the variable list</param>
        /// <returns><c>Selected value</c> if a value could be selected; otherwise <c>null</c>.</returns>
        /// <exception cref="T:Casper.Exceptions.CasperException"></exception>
        public int? SelectValue(LookAheadVarDom var, int i)//current domain will keep track of removed values
        {
            var.GetNextValue(true);
            AddVarToAssignedVars(var);
            while (var.SelectedValue != null)
            {
                if (i > 0)
                {
                    LookAheadVarDom prev = vars.GetVar(i - 1);
                    Remove(var, prev);
                }
                var.AddToRemoved((int)var.SelectedValue);
                Boolean emptyDomain;
                try
                {
                    emptyDomain = ForwardCheck(var, i);//checks for consistency with other variables
                }
                catch (CasperException) { throw; }
                if (!emptyDomain)
                {
                    var.UpdateDomainWithRemoved();
                    RemoveVarFromAssignedVars(var);
                    return var.SelectedValue;
                }
                var.GetNextValue(false);
            }
            var.UpdateDomainWithRemoved();
            RemoveVarFromAssignedVars(var);
            return null;
        }

        /// <summary>
        /// Loops through future variables with respect to the current variable.
        /// This method checks if one of the future variables' domains is empty
        /// with the current assignment.
        /// </summary>
        /// <param name="currentVar">The variable we are currently investigating.</param>
        /// <param name="i">The index "currentVar" has in the variable list</param>
        /// <returns><c>true</c> if a following domain becomes empty; otherwise <c>false</c>.</returns>
        /// <exception cref="T:Casper.Exceptions.CasperException"></exception>
        public Boolean ForwardCheck(LookAheadVarDom currentVar, int i)
        {
            int k = i + 1;
            LookAheadVarDom nextVar = vars.GetVar(k);

            while (nextVar != null)
            {
                int domainSize;
                AddVarToAssignedVars(nextVar);
                try
                {
                    domainSize = PruneNextDomain(currentVar, nextVar);
                }
                catch (CasperException) { throw; }
                RemoveVarFromAssignedVars(nextVar);

                if (domainSize == 0)//the assignment of currentVar is not consistent with nextVar
                {
                    BacktrackDomains(currentVar);
                    return true;
                }
                k++;
                nextVar = vars.GetVar(k);
            }
            return false;
        }

        /// <summary>
        /// Checks each domain value for the future variables domains in forwardCheck
        /// Here we do the actual consistency check with the provided 
        /// consistency implementation.
        /// </summary>
        /// <param name="currentVar">Currently checked variable</param>
        /// <param name="nextVar">The variable and domain the method runs consistency check on</param>
        /// <returns>The domain size of "nextVar" after consistency check</returns>
        /// <exception cref="T:Casper.Exceptions.CasperException"></exception>
        public int PruneNextDomain(LookAheadVarDom currentVar, LookAheadVarDom nextVar)
        {
            try
            {
                nextVar.GetNextValue(true);
                while ((nextVar.SelectedValue) != null)
                {
                    if (!this.consistent.IsConsistent(assignedVars, currentVar, nextVar))
                    {
                        Remove(nextVar, currentVar);
                        nextVar.AddToRemoved((int)nextVar.SelectedValue);
                    }
                    nextVar.GetNextValue(false);
                }
                nextVar.UpdateDomainWithRemoved();
                return nextVar.DomainSize();
            }
            catch (CasperException) { throw; }
        }

        /// <summary>
        /// Updates the AllRemovedValues-structure with the removed value of 
        /// variable "victim" caused by variable "villain".
        /// </summary>
        /// <param name="victim">The victim.</param>
        /// <param name="villain">The villain.</param>
        public void Remove(LookAheadVarDom victim, LookAheadVarDom villain)
        {
            HybridSet victimsOfVillain = (HybridSet)affectedVariables[villain];
            if (victimsOfVillain == null)
            {
                victimsOfVillain = new HybridSet();
                affectedVariables[villain] = victimsOfVillain;
            }
            victimsOfVillain.Add(victim);//updates the affectedVariables structure with the current victim

            RemovedValues removedValues = (RemovedValues)allRemovedValues[victim];
            if (removedValues == null)
            {
                removedValues = new RemovedValues();
                allRemovedValues[victim] = removedValues;
            }
            removedValues.Insert((int)victim.SelectedValue, villain);
        }

        /// <summary>
        /// This method backtracks the changes the variable
        /// "villain" executed on the other variables' domains.
        /// </summary>
        /// <param name="villain">The villain.</param>
        public void BacktrackDomains(LookAheadVarDom villain)//inserts values back into the value list
        {
            Set victims = (HybridSet)affectedVariables[villain];
            foreach (LookAheadVarDom victim in victims)
            {
                RemovedValues removedValuesVictim = (RemovedValues)allRemovedValues[victim];
                HybridSet tempSet = (HybridSet)removedValuesVictim.RemValStructure[villain];
                if (tempSet != null)
                        victim.ResetDomain(tempSet);

                removedValuesVictim.Remove(villain);
            }
            affectedVariables[villain] = null;
        }

        /// <summary>
        /// Method for making LookAheadVar objects from CasperVarDom objects,
        /// for internal use in this class. Different variable orderings can
        /// be made with the constraint graph.
        /// </summary>
        /// <param name="casperVarDoms">List of "CasperVarDom" objects.</param>
        /// <param name="varOrder">The var order.</param>
        /// <param name="Graph">The constraint graph.</param>
        /// <returns>The variables.</returns>
        /// <exception cref="T:Casper.Exceptions.CasperException"></exception>
        public LookaheadVariables MakeLookAheadVarDoms(List<CasperVarDom> casperVarDoms, CspVariableOrdering varOrder, ConstraintGraph Graph)
        {
            try
            {
                LookaheadVariables lAheadVars = new LookaheadVariables(varOrder, cGraph);
            
                foreach (CasperVarDom cVarDom in casperVarDoms)
                {
                    List<int> domVals = cVarDom.DomainValues;
                    Set lAheadDoms = new HybridSet();

                    foreach (int domVal in domVals)
                    {
                        lAheadDoms.Add(domVal);
                    }
                    lAheadVars.VarDoms.Add(cVarDom.VarID,new LookAheadVarDom(cVarDom.VarID, lAheadDoms));
                }
                return lAheadVars;
            }
            catch (CasperException) { throw; }
        }
    }
}