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}