/*========================================================================
        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 Iesi.Collections;
using System.Text;

using Casper.Data;
using Casper.Algorithm;
using Casper.Algorithm.VariableOrdering;
using Casper.Exceptions;

namespace Casper
{
    /// <summary>
    /// The interface of the Casper library. This class supports searching
    /// for valid domains, and reducing domains based on user selected domain values,
    /// using the CSP algorithm "Select value forward checking", and "Generalized look ahead".
    /// </summary>
    public class Csp
    {
        private List<CasperVarDom> casperVarDoms;
        private CSPExpressions expressions;
        private Boolean omitTestOnSingleValuedDomains = false;
        private Hashtable varIDToVarListIndex;
        private ConstraintGraph cGraph;
        private CspVariableOrdering variableOrdering = CspVariableOrdering.vo_static;
        private GeneralizedLookahead lookahead;

        /// <summary>
        /// Delegate used to present status for which 
        /// variable is currently searched for valid domains.
        /// </summary>
        /// <param name="currentlyRunVar"></param>
        public delegate void StatusChanged(int currentlyRunVar);

        /// <summary>
        /// Initializes a new instance of the <see cref="T:Csp"/> class.
        /// The default Implementation of <see cref="T:IConsistent"></see> is used.
        /// </summary>
        /// <param name="expressions">The expressions.</param>
        /// <param name="casperVarDoms">The list with variables/domains.</param>
        public Csp(CSPExpressions expressions, List<CasperVarDom> casperVarDoms)
        {
            this.expressions = expressions;
            this.casperVarDoms = casperVarDoms;
            varIDToVarListIndex = new Hashtable();
            for (int i = 0; i < casperVarDoms.Count; i++)
            {
                varIDToVarListIndex[casperVarDoms[i].VarID] = i;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="T:Csp"/> class.
        /// <see cref="T:CasperVarDom"></see> objects must be added
        /// afterwards, to use the "valid domains" methods. The default
        /// implementation of <see cref="T:IConsistent"></see> is used.
        /// </summary>
        /// <param name="expressions">The expressions.</param>
        public Csp(CSPExpressions expressions)
        {
            this.expressions = expressions;
            casperVarDoms = new List<CasperVarDom>();
            varIDToVarListIndex = new Hashtable();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="T:Csp"/> class.
        /// <see cref="T:CasperVarDom"></see> objects must be added,
        /// and a consistent implementation of <see cref="T:IConsitent"></see>
        /// must be set afterwards, to use the "valid domains" methods.
        /// </summary>
        public Csp()
        {
            casperVarDoms = new List<CasperVarDom>();
            varIDToVarListIndex = new Hashtable();
        }

        /// <summary>
        /// Gets or sets the constraint graph.
        /// </summary>
        /// <value>The constraint graph.</value>
        public ConstraintGraph CGraph
        {
            get { return cGraph; }
            set { cGraph = value; }
        }

        /// <summary>
        /// Gets the variable ordering.
        /// </summary>
        public CspVariableOrdering VariableOrdering
        {
            get { return variableOrdering; }
        }

        /// <summary>
        /// Sets the variable ordering, if 
        /// <see cref="T:GeneralizedLookahead"> </see>object is initialized.
        /// </summary>
        /// <param name="varorder">The varorder.</param>
        public void SetVariableOrdering(CspVariableOrdering varorder)
        {
            variableOrdering = varorder;
            if (lookahead != null) lookahead.VariableOrdering = varorder;
        }

        /// <summary>
        /// Gets or sets the expressions.
        /// </summary>
        /// <value>The expressions.</value>
        public CSPExpressions Expressions
        {
            get { return expressions; }
            set { expressions = value; }
        }

        /// <summary>
        /// Gets the variable and domain list.
        /// </summary>
        public List<CasperVarDom> CasperVarDoms
        {
            get { return casperVarDoms; }
        }

        /// <summary>
        /// Gets or sets a value indicating whether single
        /// valued domains should be omited.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if single valued domains should be omited; otherwise, <c>false</c>.
        /// </value>
        public Boolean OmitTestOnSingleValuedDomains
        {
            get { return omitTestOnSingleValuedDomains; }
            set { omitTestOnSingleValuedDomains = value; }
        }

        /// <summary>
        /// Event to present search status.
        /// </summary>
        public event StatusChanged StatusChangedEvent;

        /// <summary>
        /// Adds a new variable and domain to the problem.
        /// </summary>
        /// <param name="vardom">The new variable and domain</param>
        /// <returns>The index "vardom" is placed on.</returns>
        public int AddCasperVarDom(CasperVarDom vardom)
        {
            casperVarDoms.Add(vardom);
            varIDToVarListIndex[vardom.VarID] = casperVarDoms.Count - 1;
            return casperVarDoms.Count - 1;
        }

        /// <summary>
        /// This method reduces the domain list of "var" to 
        /// only consist of "domainVal" and runs the 
        /// <see cref="ValidDomains()"></see> method.
        /// </summary>
        /// <param name="var"></param>
        /// <param name="domainVal"></param>
        /// <returns></returns>
        ///<exception cref="T:Casper.Exceptions.CasperException"></exception>
        public List<CasperVarDom> ValidDomainsUserChoice(CasperVarDom var, int domainVal){
            List<int> tempList = new List<int>();
            tempList.Add(domainVal);
            var.DomainValues = tempList;
            try
            {
                return ValidDomains();
            }
            catch (CasperException e) 
            {
                throw new CasperException("Valid Domains with user choice could not be run", e);
            }
        }

        /// <summary>
        /// This method runs the forward checking algorithm in the 
        /// <see cref="T:GeneralizedLookahead"/> class. If 
        /// the data field omitTestOnSIgnleDomains is set to true, 
        /// one valued domain variables are jumped over. 
        /// </summary>
        /// <returns>List of variables with valid domains or null if no solution exists</returns>
        ///<exception cref="T:Casper.Exceptions.CasperException"></exception>
        public List<CasperVarDom> ValidDomains()
        {
            lookahead = new GeneralizedLookahead(this.expressions, variableOrdering, CGraph);
            foreach (CasperVarDom cVarDom in casperVarDoms)
            {
                if(StatusChangedEvent!=null)
                    StatusChangedEvent(cVarDom.VarID);
                List<int> validDomains = new List<int>();
                List<int> dValues = cVarDom.DomainValues;

                if (omitTestOnSingleValuedDomains && cVarDom.DomainValues.Count == 1) continue;

                foreach (int domainValue in dValues)
                {
                    if (cVarDom.ValidValues.Contains(domainValue))
                    {
                        validDomains.Add(domainValue);
                        continue;
                    }
                    List<int> reducedTestDom = new List<int>();
                    reducedTestDom.Add(domainValue);
                    cVarDom.DomainValues = reducedTestDom;

                    List<LookAheadVarDom> validDomainValues;
                    try
                    {
                        validDomainValues = lookahead.LookAhead(casperVarDoms);
                    }
                    catch (CasperException e)
                    {
                        throw new CasperException("Valid domains could not be run.", e);
                    }
                    if (validDomainValues != null)
                    {
                        for (int i = 0; i < validDomainValues.Count; i++)
                        {
                            LookAheadVarDom var = validDomainValues[i];
                            if (var.VarID == cVarDom.VarID)
                                validDomains.Add(domainValue);
                            else
                            {
                                int index = (int)varIDToVarListIndex[var.VarID];
                                CasperVarDom cvar = casperVarDoms[index];
                                cvar.ValidValues.Add(var.SelectedValue);
                            }
                        }
                    }
                }
                cVarDom.DomainValues = validDomains;
                if (validDomains.Count == 0)
                {
                    casperVarDoms = null;
                    return null;
                }
            }
            CleanUp();
            return casperVarDoms;
        }

        /// <summary>
        /// Internal method for cleaning up before
        /// starting a new valid domains search.
        /// </summary>
        private void CleanUp()
        {
            foreach (CasperVarDom vardom in casperVarDoms)
            {
                vardom.ValidValues.Clear();
            }
        }
    }
}