    001package net.sf.cpsolver.ifs.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Comparator;
    006import java.util.HashSet;
    007import java.util.HashMap;
    008import java.util.List;
    009import java.util.Locale;
    010import java.util.Map;
    011import java.util.Set;
    012import java.util.TreeSet;
    013
    014import net.sf.cpsolver.ifs.criteria.Criterion;
    015import net.sf.cpsolver.ifs.solver.Solver;
    016import net.sf.cpsolver.ifs.util.ToolBox;
    017
    018/**
    019 * Generic model (definition of a problem). <br>
    020 * <br>
    021 * It consists of variables and constraints. It has also capability of
    022 * memorizing the current and the best ever found assignment. <br>
    023 * <br>
    024 * Example usage:<br>
    025 * <ul>
    026 * <code>
    027 * MyModel model = new MyModel();<br>
    028 * Variable a = new MyVariable("A");<br>
    029 * model.addVariable(a);<br>
    030 * Variable b = new MyVariable("B");<br>
    031 * model.addVariable(b);<br>
    032 * Variable c = new MyVariable("C");<br>
    033 * model.addVariable(c);<br>
    034 * Constraint constr = MyConstraint("all-different");<br>
    035 * model.addConstraint(constr);<br>
    036 * constr.addVariable(a);<br>
    037 * constr.addVariable(b);<br>
    038 * constr.addVariable(c);<br>
    039 * solver.setInitialSolution(model);
    040 * </code>
    041 * </ul>
    042 *
    043 * @see Variable
    044 * @see Constraint
    045 * @see net.sf.cpsolver.ifs.solution.Solution
    046 * @see net.sf.cpsolver.ifs.solver.Solver
    047 *
    048 * @version IFS 1.2 (Iterative Forward Search)<br>
    049 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    050 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    051 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    052 * <br>
    053 *          This library is free software; you can redistribute it and/or modify
    054 *          it under the terms of the GNU Lesser General Public License as
    055 *          published by the Free Software Foundation; either version 3 of the
    056 *          License, or (at your option) any later version. <br>
    057 * <br>
    058 *          This library is distributed in the hope that it will be useful, but
    059 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    060 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    061 *          Lesser General Public License for more details. <br>
    062 * <br>
    063 *          You should have received a copy of the GNU Lesser General Public
    064 *          License along with this library; if not see
    065 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    066 */
    067
    068public class Model<V extends Variable<V, T>, T extends Value<V, T>> {
    069    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Model.class);
    070    protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",
    071            new java.text.DecimalFormatSymbols(Locale.US));
    072    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
    073            new java.text.DecimalFormatSymbols(Locale.US));
    074    protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00",
    075            new java.text.DecimalFormatSymbols(Locale.US));
    076
    077    private List<V> iVariables = new ArrayList<V>();
    078    private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
    079    private List<GlobalConstraint<V, T>> iGlobalConstraints = new ArrayList<GlobalConstraint<V, T>>();
    080    protected Collection<V> iUnassignedVariables = new HashSet<V>();
    081    protected Collection<V> iAssignedVariables = new HashSet<V>();
    082    private Collection<V> iVariablesWithInitialValueCache = null;
    083    protected Collection<V> iPerturbVariables = null;
    084
    085    private List<ModelListener<V, T>> iModelListeners = new ArrayList<ModelListener<V, T>>();
    086    private List<InfoProvider<V>> iInfoProviders = new ArrayList<InfoProvider<V>>();
    087    private HashMap<String, Criterion<V, T>> iCriteria = new HashMap<String, Criterion<V,T>>();
    088
    089    private int iBestUnassignedVariables = -1;
    090    private int iBestPerturbations = 0;
    091    private int iNrAssignedVariables = 0;
    092
    093    /** Constructor */
    094    public Model() {
    095    }
    096
    097    /** The list of variables in the model */
    098    public List<V> variables() {
    099        return iVariables;
    100    }
    101
    102    /** The number of variables in the model */
    103    public int countVariables() {
    104        return iVariables.size();
    105    }
    106
    107    /** Adds a variable to the model */
    108    @SuppressWarnings("unchecked")
    109    public void addVariable(V variable) {
    110        variable.setModel(this);
    111        iVariables.add(variable);
    112        if (variable instanceof InfoProvider<?>)
    113            iInfoProviders.add((InfoProvider<V>) variable);
    114        if (variable.getAssignment() == null) {
    115            if (iUnassignedVariables != null)
    116                iUnassignedVariables.add(variable);
    117        } else {
    118            if (iAssignedVariables != null)
    119                iAssignedVariables.add(variable);
    120            iNrAssignedVariables++;
    121        }
    122        if (variable.getAssignment() != null)
    123            variable.assign(0L, variable.getAssignment());
    124        for (ModelListener<V, T> listener : iModelListeners)
    125            listener.variableAdded(variable);
    126        invalidateVariablesWithInitialValueCache();
    127    }
    128
    129    /** Removes a variable from the model */
    130    public void removeVariable(V variable) {
    131        variable.setModel(null);
    132        iVariables.remove(variable);
    133        if (variable instanceof InfoProvider<?>)
    134            iInfoProviders.remove(variable);
    135        if (iUnassignedVariables != null && iUnassignedVariables.contains(variable))
    136            iUnassignedVariables.remove(variable);
    137        if (iAssignedVariables != null && iAssignedVariables.contains(variable))
    138            iAssignedVariables.remove(variable);
    139        if (variable.getAssignment() != null)
    140            iNrAssignedVariables--;
    141        for (ModelListener<V, T> listener : iModelListeners)
    142            listener.variableRemoved(variable);
    143        invalidateVariablesWithInitialValueCache();
    144    }
    145
    146    /** The list of constraints in the model */
    147    public List<Constraint<V, T>> constraints() {
    148        return iConstraints;
    149    }
    150
    151    /** The number of constraints in the model */
    152    public int countConstraints() {
    153        return iConstraints.size();
    154    }
    155
    156    /** Adds a constraint to the model */
    157    @SuppressWarnings("unchecked")
    158    public void addConstraint(Constraint<V, T> constraint) {
    159        constraint.setModel(this);
    160        iConstraints.add(constraint);
    161        if (constraint instanceof InfoProvider<?>)
    162            iInfoProviders.add((InfoProvider<V>) constraint);
    163        for (ModelListener<V, T> listener : iModelListeners)
    164            listener.constraintAdded(constraint);
    165    }
    166
    167    /** Removes a constraint from the model */
    168    public void removeConstraint(Constraint<V, T> constraint) {
    169        constraint.setModel(null);
    170        iConstraints.remove(constraint);
    171        if (constraint instanceof InfoProvider<?>)
    172            iInfoProviders.remove(constraint);
    173        for (ModelListener<V, T> listener : iModelListeners)
    174            listener.constraintRemoved(constraint);
    175    }
    176
    177    /** The list of global constraints in the model */
    178    public List<GlobalConstraint<V, T>> globalConstraints() {
    179        return iGlobalConstraints;
    180    }
    181
    182    /** The number of global constraints in the model */
    183    public int countGlobalConstraints() {
    184        return iGlobalConstraints.size();
    185    }
    186
    187    /** Adds a global constraint to the model */
    188    @SuppressWarnings("unchecked")
    189    public void addGlobalConstraint(GlobalConstraint<V, T> constraint) {
    190        constraint.setModel(this);
    191        iGlobalConstraints.add(constraint);
    192        if (constraint instanceof InfoProvider<?>)
    193            iInfoProviders.add((InfoProvider<V>) constraint);
    194        for (ModelListener<V, T> listener : iModelListeners)
    195            listener.constraintAdded(constraint);
    196    }
    197
    198    /** Removes a global constraint from the model */
    199    public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) {
    200        constraint.setModel(null);
    201        iGlobalConstraints.remove(constraint);
    202        if (constraint instanceof InfoProvider<?>)
    203            iInfoProviders.remove(constraint);
    204        for (ModelListener<V, T> listener : iModelListeners)
    205            listener.constraintRemoved(constraint);
    206    }
    207
    208    /** The list of unassigned variables in the model */
    209    public Collection<V> unassignedVariables() {
    210        if (iUnassignedVariables != null)
    211            return iUnassignedVariables;
    212        Collection<V> un = new ArrayList<V>(iVariables.size());
    213        for (V variable : iVariables) {
    214            if (variable.getAssignment() == null)
    215                un.add(variable);
    216        }
    217        return un;
    218    }
    219
    220    /** Number of unassigned variables */
    221    public int nrUnassignedVariables() {
    222        if (iUnassignedVariables != null)
    223            return iUnassignedVariables.size();
    224        return iVariables.size() - iNrAssignedVariables;
    225    }
    226
    227    /** The list of assigned variables in the model */
    228    public Collection<V> assignedVariables() {
    229        if (iAssignedVariables != null)
    230            return iAssignedVariables;
    231        Collection<V> as = new ArrayList<V>(iVariables.size());
    232        for (V variable : iVariables) {
    233            if (variable.getAssignment() != null)
    234                as.add(variable);
    235        }
    236        return as;
    237    }
    238
    239    /** Number of assigned variables */
    240    public int nrAssignedVariables() {
    241        if (iAssignedVariables != null)
    242            return iAssignedVariables.size();
    243        return iNrAssignedVariables;
    244    }
    245
    246    /**
    247     * The list of perturbation variables in the model, i.e., the variables
    248     * which has an initial value but which are not assigned with this value.
    249     */
    250    public Collection<V> perturbVariables() {
    251        if (iPerturbVariables == null)
    252            iPerturbVariables = perturbVariables(variablesWithInitialValue());
    253        return iPerturbVariables;
    254    }
    255
    256    /**
    257     * The list of perturbation variables in the model, i.e., the variables
    258     * which has an initial value but which are not assigned with this value.
    259     * Only variables from the given set are considered.
    260     */
    261    public List<V> perturbVariables(Collection<V> variables) {
    262        List<V> perturbances = new ArrayList<V>();
    263        for (V variable : variables) {
    264            if (variable.getInitialAssignment() == null)
    265                continue;
    266            if (variable.getAssignment() != null) {
    267                if (!variable.getInitialAssignment().equals(variable.getAssignment()))
    268                    perturbances.add(variable);
    269            } else {
    270                boolean hasPerturbance = false;
    271                for (Constraint<V, T> constraint : variable.hardConstraints()) {
    272                    if (constraint.inConflict(variable.getInitialAssignment())) {
    273                        hasPerturbance = true;
    274                        break;
    275                    }
    276                }
    277                if (!hasPerturbance)
    278                    for (GlobalConstraint<V, T> constraint : globalConstraints()) {
    279                        if (constraint.inConflict(variable.getInitialAssignment())) {
    280                            hasPerturbance = true;
    281                            break;
    282                        }
    283                    }
    284                if (hasPerturbance)
    285                    perturbances.add(variable);
    286            }
    287        }
    288        return perturbances;
    289    }
    290
    291    /**
    292     * Returns the set of conflicting variables with this value, if it is
    293     * assigned to its variable
    294     */
    295    public Set<T> conflictValues(T value) {
    296        Set<T> conflictValues = new HashSet<T>();
    297        for (Constraint<V, T> constraint : value.variable().hardConstraints())
    298            constraint.computeConflicts(value, conflictValues);
    299        for (GlobalConstraint<V, T> constraint : globalConstraints())
    300            constraint.computeConflicts(value, conflictValues);
    301        return conflictValues;
    302    }
    303
    304    /** Return true if the given value is in conflict with a hard constraint */
    305    public boolean inConflict(T value) {
    306        for (Constraint<V, T> constraint : value.variable().hardConstraints())
    307            if (constraint.inConflict(value))
    308                return true;
    309        for (GlobalConstraint<V, T> constraint : globalConstraints())
    310            if (constraint.inConflict(value))
    311                return true;
    312        return false;
    313    }
    314
    315    /** The list of variables without initial value */
    316    public Collection<V> variablesWithInitialValue() {
    317        if (iVariablesWithInitialValueCache != null)
    318            return iVariablesWithInitialValueCache;
    319        iVariablesWithInitialValueCache = new ArrayList<V>();
    320        for (V variable : iVariables) {
    321            if (variable.getInitialAssignment() != null)
    322                iVariablesWithInitialValueCache.add(variable);
    323        }
    324        return iVariablesWithInitialValueCache;
    325    }
    326
    327    /** Invalidates cache containing all variables that possess an initial value */
    328    protected void invalidateVariablesWithInitialValueCache() {
    329        iVariablesWithInitialValueCache = null;
    330    }
    331
    332    /** Called before a value is assigned to its variable */
    333    public void beforeAssigned(long iteration, T value) {
    334        for (ModelListener<V, T> listener : iModelListeners)
    335            listener.beforeAssigned(iteration, value);
    336    }
    337
    338    /** Called before a value is unassigned from its variable */
    339    public void beforeUnassigned(long iteration, T value) {
    340        for (ModelListener<V, T> listener : iModelListeners)
    341            listener.beforeUnassigned(iteration, value);
    342    }
    343
    344    /** Called after a value is assigned to its variable */
    345    public void afterAssigned(long iteration, T value) {
    346        if (iUnassignedVariables != null)
    347            iUnassignedVariables.remove(value.variable());
    348        if (iAssignedVariables != null)
    349            iAssignedVariables.add(value.variable());
    350        iNrAssignedVariables++;
    351        iPerturbVariables = null;
    352        for (ModelListener<V, T> listener : iModelListeners)
    353            listener.afterAssigned(iteration, value);
    354    }
    355
    356    /** Called after a value is unassigned from its variable */
    357    public void afterUnassigned(long iteration, T value) {
    358        if (iUnassignedVariables != null)
    359            iUnassignedVariables.add(value.variable());
    360        if (iAssignedVariables != null)
    361            iAssignedVariables.remove(value.variable());
    362        iNrAssignedVariables--;
    363        iPerturbVariables = null;
    364        for (ModelListener<V, T> listener : iModelListeners)
    365            listener.afterUnassigned(iteration, value);
    366    }
    367
    368    @Override
    369    public String toString() {
    370        return "Model{\n    variables=" + ToolBox.col2string(variables(), 2) + ",\n    constraints="
    371                + ToolBox.col2string(constraints(), 2) + ",\n    #unassigned=" + nrUnassignedVariables()
    372                + ",\n    unassigned=" + ToolBox.col2string(unassignedVariables(), 2) + ",\n    #perturbations="
    373                + perturbVariables().size() + "+" + (variables().size() - variablesWithInitialValue().size())
    374                + ",\n    perturbations=" + ToolBox.col2string(perturbVariables(), 2) + ",\n    info=" + getInfo()
    375                + "\n  }";
    376    }
    377
    378    protected String getPerc(double value, double min, double max) {
    379        if (max == min)
    380            return sPercentageFormat.format(100.0);
    381        return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min));
    382    }
    383
    384    protected String getPercRev(double value, double min, double max) {
    385        if (max == min)
    386            return sPercentageFormat.format(0.0);
    387        return sPercentageFormat.format(100.0 * (value - min) / (max - min));
    388    }
    389
    390    /**
    391     * Returns information about the current solution. Information from all
    392     * model listeners and constraints is also included.
    393     */
    394    public Map<String, String> getInfo() {
    395        HashMap<String, String> ret = new HashMap<String, String>();
    396        ret.put("Assigned variables", getPercRev(nrAssignedVariables(), 0, variables().size()) + "% ("
    397                + nrAssignedVariables() + "/" + variables().size() + ")");
    398        int nrVarsWithInitialValue = variablesWithInitialValue().size();
    399        if (nrVarsWithInitialValue > 0) {
    400            ret.put("Perturbation variables", getPercRev(perturbVariables().size(), 0, nrVarsWithInitialValue) + "% ("
    401                    + perturbVariables().size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")");
    402        }
    403        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue()));
    404        for (InfoProvider<V> provider : iInfoProviders)
    405            provider.getInfo(ret);
    406        return ret;
    407    }
    408
    409    /**
    410     * Extended information about current solution. Similar to
    411     * {@link Model#getInfo()}, but some more information (that is more
    412     * expensive to compute) might be added.
    413     */
    414    public Map<String, String> getExtendedInfo() {
    415        return getInfo();
    416    }
    417
    418    /**
    419     * Returns information about the current solution. Information from all
    420     * model listeners and constraints is also included. Only variables from the
    421     * given set are considered.
    422     */
    423    public Map<String, String> getInfo(Collection<V> variables) {
    424        Map<String, String> ret = new HashMap<String, String>();
    425        int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0;
    426        for (V variable : variables) {
    427            if (variable.getAssignment() != null)
    428                assigned++;
    429            if (variable.getInitialAssignment() != null) {
    430                nrVarsWithInitialValue++;
    431                if (variable.getAssignment() != null) {
    432                    if (!variable.getInitialAssignment().equals(variable.getAssignment()))
    433                        perturb++;
    434                } else {
    435                    boolean hasPerturbance = false;
    436                    for (Constraint<V, T> constraint : variable.hardConstraints()) {
    437                        if (constraint.inConflict(variable.getInitialAssignment())) {
    438                            hasPerturbance = true;
    439                            break;
    440                        }
    441                    }
    442                    if (!hasPerturbance)
    443                        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
    444                            if (constraint.inConflict(variable.getInitialAssignment())) {
    445                                hasPerturbance = true;
    446                                break;
    447                            }
    448                        }
    449                    if (hasPerturbance)
    450                        perturb++;
    451                }
    452            }
    453        }
    454        ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/"
    455                + variables.size() + ")");
    456        if (nrVarsWithInitialValue > 0) {
    457            ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + "
    458                    + (variables.size() - nrVarsWithInitialValue) + ")");
    459        }
    460        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(variables)));
    461        for (InfoProvider<V> provider : iInfoProviders)
    462            provider.getInfo(ret, variables);
    463        return ret;
    464    }
    465
    466    /**
    467     * Returns the number of unassigned variables in the best ever found
    468     * solution
    469     */
    470    public int getBestUnassignedVariables() {
    471        return iBestUnassignedVariables;
    472    }
    473
    474    /**
    475     * Returns the number of perturbation variables in the best ever found
    476     * solution
    477     */
    478    public int getBestPerturbations() {
    479        return iBestPerturbations;
    480    }
    481
    482    /** Save the current assignment as the best ever found assignment */
    483    public void saveBest() {
    484        iBestUnassignedVariables = nrUnassignedVariables();// unassignedVariables().size();
    485        iBestPerturbations = perturbVariables().size();
    486        for (V variable : iVariables) {
    487            variable.setBestAssignment(variable.getAssignment());
    488        }
    489        for (Criterion<V, T> criterion: getCriteria()) {
    490            criterion.bestSaved();
    491        }
    492    }
    493
    494    /** Clear the best ever found assignment */
    495    public void clearBest() {
    496        iBestUnassignedVariables = -1;
    497        iBestPerturbations = 0;
    498        for (V variable : iVariables) {
    499            variable.setBestAssignment(null);
    500        }
    501    }
    502
    503    /** Restore the best ever found assignment into the current assignment */
    504    @SuppressWarnings("unchecked")
    505    protected void restoreBest(Comparator<V> assignmentOrder) {
    506        TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder);
    507        for (V variable : iVariables) {
    508            if (variable.getAssignment() == null) {
    509                if (variable.getBestAssignment() != null)
    510                    sortedVariables.add(variable);
    511            } else if (!variable.getAssignment().equals(variable.getBestAssignment())) {
    512                variable.unassign(0);
    513                if (variable.getBestAssignment() != null)
    514                    sortedVariables.add(variable);
    515            }
    516        }
    517        Set<T> problems = new HashSet<T>();
    518        for (V variable : sortedVariables) {
    519            Set<T> confs = conflictValues(variable.getBestAssignment());
    520            if (!confs.isEmpty()) {
    521                sLogger.error("restore best problem: assignment " + variable.getName() + " = "
    522                        + variable.getBestAssignment().getName());
    523                for (Constraint<V, T> c : variable.hardConstraints()) {
    524                    Set<T> x = new HashSet<T>();
    525                    c.computeConflicts(variable.getBestAssignment(), x);
    526                    if (!x.isEmpty()) {
    527                        if (c instanceof WeakeningConstraint) {
    528                            ((WeakeningConstraint<V, T>)c).weaken(variable.getBestAssignment());
    529                            sLogger.info("  constraint " + c.getClass().getName() + " " + c.getName() + " had to be weakened");
    530                        } else {
    531                            sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName() + " causes the following conflicts " + x);
    532                        }
    533                    }
    534                }
    535                for (GlobalConstraint<V, T> c : globalConstraints()) {
    536                    Set<T> x = new HashSet<T>();
    537                    c.computeConflicts(variable.getBestAssignment(), x);
    538                    if (!x.isEmpty()) {
    539                        if (c instanceof WeakeningConstraint) {
    540                            ((WeakeningConstraint<V, T>)c).weaken(variable.getBestAssignment());
    541                            sLogger.info("  constraint " + c.getClass().getName() + " " + c.getName() + " had to be weakened");
    542                        } else {
    543                            sLogger.error("  global constraint " + c.getClass().getName() + " " + c.getName() + " causes the following conflicts " + x);
    544                        }
    545                    }
    546                }
    547                problems.add(variable.getBestAssignment());
    548            } else
    549                variable.assign(0, variable.getBestAssignment());
    550        }
    551        int attempt = 0, maxAttempts = 3 * problems.size();
    552        while (!problems.isEmpty() && attempt <= maxAttempts) {
    553            attempt++;
    554            T value = ToolBox.random(problems);
    555            problems.remove(value);
    556            V variable = value.variable();
    557            Set<T> confs = conflictValues(value);
    558            if (!confs.isEmpty()) {
    559                sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName()
    560                        + " = " + value.getName());
    561                for (Constraint<V, T> c : variable.hardConstraints()) {
    562                    Set<T> x = new HashSet<T>();
    563                    c.computeConflicts(value, x);
    564                    if (!x.isEmpty())
    565                        sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName()
    566                                + " causes the following conflicts " + x);
    567                }
    568                for (GlobalConstraint<V, T> c : globalConstraints()) {
    569                    Set<T> x = new HashSet<T>();
    570                    c.computeConflicts(value, x);
    571                    if (!x.isEmpty())
    572                        sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName()
    573                                + " causes the following conflicts " + x);
    574                }
    575                for (T conf : confs)
    576                    conf.variable().unassign(0);
    577                problems.addAll(confs);
    578            }
    579            variable.assign(0, value);
    580        }
    581        for (Criterion<V, T> criterion: getCriteria()) {
    582            criterion.bestRestored();
    583        }
    584    }
    585
    586    public void restoreBest() {
    587        restoreBest(new Comparator<V>() {
    588            @Override
    589            public int compare(V v1, V v2) {
    590                if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1;
    591                if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1;
    592                return v1.compareTo(v2);
    593            }
    594        });
    595    }
    596
    597    /** The list of unassigned variables in the best ever found solution */
    598    public Collection<V> bestUnassignedVariables() {
    599        if (iBestUnassignedVariables < 0)
    600            return unassignedVariables();
    601        Collection<V> ret = new ArrayList<V>(variables().size());
    602        for (V variable : variables()) {
    603            if (variable.getBestAssignment() == null)
    604                ret.add(variable);
    605        }
    606        return ret;
    607    }
    608
    609    /**
    610     * Value of the current solution. It is the sum of all assigned values,
    611     * i.e., {@link Value#toDouble()}.
    612     */
    613    public double getTotalValue() {
    614        double ret = 0.0;
    615        for (V v: assignedVariables())
    616            ret += v.getAssignment().toDouble();
    617        return ret;
    618    }
    619
    620    /**
    621     * Value of the current solution. It is the sum of all assigned values,
    622     * i.e., {@link Value#toDouble()}. Only variables from the given set are
    623     * considered.
    624     **/
    625    public double getTotalValue(Collection<V> variables) {
    626        double ret = 0.0;
    627        for (V v: variables)
    628            if (v.getAssignment() != null)
    629                ret += v.getAssignment().toDouble();
    630        return ret;
    631    }
    632
    633    /** Adds a model listener */
    634    @SuppressWarnings("unchecked")
    635    public void addModelListener(ModelListener<V, T> listener) {
    636        iModelListeners.add(listener);
    637        if (listener instanceof InfoProvider<?>)
    638            iInfoProviders.add((InfoProvider<V>) listener);
    639        for (Constraint<V, T> constraint : iConstraints)
    640            listener.constraintAdded(constraint);
    641        for (V variable : iVariables)
    642            listener.variableAdded(variable);
    643    }
    644
    645    /** Removes a model listener */
    646    public void removeModelListener(ModelListener<V, T> listener) {
    647        if (listener instanceof InfoProvider<?>)
    648            iInfoProviders.remove(listener);
    649        for (V variable : iVariables)
    650            listener.variableRemoved(variable);
    651        for (Constraint<V, T> constraint : iConstraints)
    652            listener.constraintRemoved(constraint);
    653        iModelListeners.remove(listener);
    654    }
    655
    656    /** Model initialization */
    657    public boolean init(Solver<V, T> solver) {
    658        for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) {
    659            if (!listener.init(solver))
    660                return false;
    661        }
    662        return true;
    663    }
    664
    665    /** The list of model listeners */
    666    public List<ModelListener<V, T>> getModelListeners() {
    667        return iModelListeners;
    668    }
    669
    670    /** The list of model listeners that are of the given class */
    671    public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) {
    672        for (ModelListener<V, T> listener : iModelListeners) {
    673            if (listener.getClass() == type)
    674                return listener;
    675        }
    676        return null;
    677    }
    678
    679    /**
    680     * The list of constraints which are in a conflict with the given value if
    681     * it is assigned to its variable. This means the constraints, which adds a
    682     * value into the set of conflicting values in
    683     * {@link Constraint#computeConflicts(Value, Set)}.
    684     */
    685    public Map<Constraint<V, T>, Set<T>> conflictConstraints(T value) {
    686        Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>();
    687        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
    688            Set<T> conflicts = new HashSet<T>();
    689            constraint.computeConflicts(value, conflicts);
    690            if (!conflicts.isEmpty()) {
    691                conflictConstraints.put(constraint, conflicts);
    692            }
    693        }
    694        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
    695            Set<T> conflicts = new HashSet<T>();
    696            constraint.computeConflicts(value, conflicts);
    697            if (!conflicts.isEmpty()) {
    698                conflictConstraints.put(constraint, conflicts);
    699            }
    700        }
    701        return conflictConstraints;
    702    }
    703
    704    /**
    705     * The list of hard constraints which contain at least one variable that is
    706     * not assigned.
    707     */
    708    public List<Constraint<V, T>> unassignedHardConstraints() {
    709        List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>();
    710        constraints: for (Constraint<V, T> constraint : constraints()) {
    711            if (!constraint.isHard())
    712                continue;
    713            for (V v : constraint.variables()) {
    714                if (v.getAssignment() == null) {
    715                    ret.add(constraint);
    716                    continue constraints;
    717                }
    718            }
    719        }
    720        if (!unassignedVariables().isEmpty())
    721            ret.addAll(globalConstraints());
    722        return ret;
    723    }
    724
    725    /** Registered info providers (see {@link InfoProvider}) */
    726    protected List<InfoProvider<V>> getInfoProviders() {
    727        return iInfoProviders;
    728    }
    729
    730    /** Register a new criterion */
    731    public void addCriterion(Criterion<V,T> criterion) {
    732        iCriteria.put(criterion.getClass().getName(), criterion);
    733        addModelListener(criterion);
    734    }
    735
    736    /** Unregister an existing criterion */
    737    public void removeCriterion(Criterion<V,T> criterion) {
    738        iCriteria.remove(criterion.getClass().getName());
    739        removeModelListener(criterion);
    740    }
    741
    742    /** Unregister an existing criterion */
    743    public void removeCriterion(Class<? extends Criterion<V, T>> criterion) {
    744        Criterion<V,T> c = iCriteria.remove(criterion.getName());
    745        if (c != null)
    746            removeModelListener(c);
    747    }
    748
    749    /** Return a registered criterion of the given type. */
    750    public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) {
    751        return iCriteria.get(criterion.getName());
    752    }
    753
    754    /** List all registered criteria */
    755    public Collection<Criterion<V, T>> getCriteria() {
    756        return iCriteria.values();
    757    }
    758
    759    /**
    760     * Weaken all weakening constraint so that the given value can be assigned without
    761     * them creating a conflict using {@link WeakeningConstraint#weaken(Value)}.
    762     * This method is handy for instance when an existing solution is being loaded
    763     * into the solver.
    764     */
    765    @SuppressWarnings("unchecked")
    766    public void weaken(T value) {
    767        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
    768            if (constraint instanceof WeakeningConstraint)
    769                ((WeakeningConstraint<V,T>)constraint).weaken(value);
    770        }
    771        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
    772            if (constraint instanceof WeakeningConstraint)
    773                ((WeakeningConstraint<V,T>)constraint).weaken(value);
    774        }
    775    }
    776}