001    package net.sf.cpsolver.ifs.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Comparator;
006    import java.util.HashSet;
007    import java.util.HashMap;
008    import java.util.List;
009    import java.util.Locale;
010    import java.util.Map;
011    import java.util.Set;
012    import java.util.TreeSet;
013    
014    import net.sf.cpsolver.ifs.criteria.Criterion;
015    import net.sf.cpsolver.ifs.solver.Solver;
016    import 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 Tomas Muller<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    
068    public 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        protected void restoreBest(Comparator<V> assignmentOrder) {
505            TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder);
506            for (V variable : iVariables) {
507                if (variable.getAssignment() == null) {
508                    if (variable.getBestAssignment() != null)
509                        sortedVariables.add(variable);
510                } else if (!variable.getAssignment().equals(variable.getBestAssignment())) {
511                    variable.unassign(0);
512                    if (variable.getBestAssignment() != null)
513                        sortedVariables.add(variable);
514                }
515            }
516            Set<T> problems = new HashSet<T>();
517            for (V variable : sortedVariables) {
518                Set<T> confs = conflictValues(variable.getBestAssignment());
519                if (!confs.isEmpty()) {
520                    sLogger.error("restore best problem: assignment " + variable.getName() + " = "
521                            + variable.getBestAssignment().getName());
522                    for (Constraint<V, T> c : variable.hardConstraints()) {
523                        Set<T> x = new HashSet<T>();
524                        c.computeConflicts(variable.getBestAssignment(), x);
525                        if (!x.isEmpty()) {
526                            sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName()
527                                    + " causes the following conflicts " + x);
528                        }
529                    }
530                    for (GlobalConstraint<V, T> c : globalConstraints()) {
531                        Set<T> x = new HashSet<T>();
532                        c.computeConflicts(variable.getBestAssignment(), x);
533                        if (!x.isEmpty()) {
534                            sLogger.error("  global constraint " + c.getClass().getName() + " " + c.getName()
535                                    + " causes the following conflicts " + x);
536                        }
537                    }
538                    problems.add(variable.getBestAssignment());
539                } else
540                    variable.assign(0, variable.getBestAssignment());
541            }
542            int attempt = 0, maxAttempts = 3 * problems.size();
543            while (!problems.isEmpty() && attempt <= maxAttempts) {
544                attempt++;
545                T value = ToolBox.random(problems);
546                problems.remove(value);
547                V variable = value.variable();
548                Set<T> confs = conflictValues(value);
549                if (!confs.isEmpty()) {
550                    sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName()
551                            + " = " + value.getName());
552                    for (Constraint<V, T> c : variable.hardConstraints()) {
553                        Set<T> x = new HashSet<T>();
554                        c.computeConflicts(value, x);
555                        if (!x.isEmpty())
556                            sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName()
557                                    + " causes the following conflicts " + x);
558                    }
559                    for (GlobalConstraint<V, T> c : globalConstraints()) {
560                        Set<T> x = new HashSet<T>();
561                        c.computeConflicts(value, x);
562                        if (!x.isEmpty())
563                            sLogger.error("  constraint " + c.getClass().getName() + " " + c.getName()
564                                    + " causes the following conflicts " + x);
565                    }
566                    for (T conf : confs)
567                        conf.variable().unassign(0);
568                    problems.addAll(confs);
569                }
570                variable.assign(0, value);
571            }
572            for (Criterion<V, T> criterion: getCriteria()) {
573                criterion.bestRestored();
574            }
575        }
576        
577        public void restoreBest() {
578            restoreBest(new Comparator<V>() {
579                @Override
580                public int compare(V v1, V v2) {
581                    if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1;
582                    if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1;
583                    return v1.compareTo(v2);
584                }
585            });
586        }
587    
588        /** The list of unassigned variables in the best ever found solution */
589        public Collection<V> bestUnassignedVariables() {
590            if (iBestUnassignedVariables < 0)
591                return unassignedVariables();
592            Collection<V> ret = new ArrayList<V>(variables().size());
593            for (V variable : variables()) {
594                if (variable.getBestAssignment() == null)
595                    ret.add(variable);
596            }
597            return ret;
598        }
599    
600        /**
601         * Value of the current solution. It is the sum of all assigned values,
602         * i.e., {@link Value#toDouble()}.
603         */
604        public double getTotalValue() {
605            double ret = 0.0;
606            for (V v: assignedVariables())
607                ret += v.getAssignment().toDouble();
608            return ret;
609        }
610    
611        /**
612         * Value of the current solution. It is the sum of all assigned values,
613         * i.e., {@link Value#toDouble()}. Only variables from the given set are
614         * considered.
615         **/
616        public double getTotalValue(Collection<V> variables) {
617            double ret = 0.0;
618            for (V v: variables)
619                if (v.getAssignment() != null)
620                    ret += v.getAssignment().toDouble();
621            return ret;
622        }
623    
624        /** Adds a model listener */
625        @SuppressWarnings("unchecked")
626        public void addModelListener(ModelListener<V, T> listener) {
627            iModelListeners.add(listener);
628            if (listener instanceof InfoProvider<?>)
629                iInfoProviders.add((InfoProvider<V>) listener);
630            for (Constraint<V, T> constraint : iConstraints)
631                listener.constraintAdded(constraint);
632            for (V variable : iVariables)
633                listener.variableAdded(variable);
634        }
635    
636        /** Removes a model listener */
637        public void removeModelListener(ModelListener<V, T> listener) {
638            if (listener instanceof InfoProvider<?>)
639                iInfoProviders.remove(listener);
640            for (V variable : iVariables)
641                listener.variableRemoved(variable);
642            for (Constraint<V, T> constraint : iConstraints)
643                listener.constraintRemoved(constraint);
644            iModelListeners.remove(listener);
645        }
646    
647        /** Model initialization */
648        public boolean init(Solver<V, T> solver) {
649            for (ModelListener<V, T> listener : iModelListeners) {
650                if (!listener.init(solver))
651                    return false;
652            }
653            return true;
654        }
655    
656        /** The list of model listeners */
657        public List<ModelListener<V, T>> getModelListeners() {
658            return iModelListeners;
659        }
660    
661        /** The list of model listeners that are of the given class */
662        public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) {
663            for (ModelListener<V, T> listener : iModelListeners) {
664                if (listener.getClass() == type)
665                    return listener;
666            }
667            return null;
668        }
669    
670        /**
671         * The list of constraints which are in a conflict with the given value if
672         * it is assigned to its variable. This means the constraints, which adds a
673         * value into the set of conflicting values in
674         * {@link Constraint#computeConflicts(Value, Set)}.
675         */
676        public Map<Constraint<V, T>, Set<T>> conflictConstraints(T value) {
677            Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>();
678            for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
679                Set<T> conflicts = new HashSet<T>();
680                constraint.computeConflicts(value, conflicts);
681                if (!conflicts.isEmpty()) {
682                    conflictConstraints.put(constraint, conflicts);
683                }
684            }
685            for (GlobalConstraint<V, T> constraint : globalConstraints()) {
686                Set<T> conflicts = new HashSet<T>();
687                constraint.computeConflicts(value, conflicts);
688                if (!conflicts.isEmpty()) {
689                    conflictConstraints.put(constraint, conflicts);
690                }
691            }
692            return conflictConstraints;
693        }
694    
695        /**
696         * The list of hard constraints which contain at least one variable that is
697         * not assigned.
698         */
699        public List<Constraint<V, T>> unassignedHardConstraints() {
700            List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>();
701            constraints: for (Constraint<V, T> constraint : constraints()) {
702                if (!constraint.isHard())
703                    continue;
704                for (V v : constraint.variables()) {
705                    if (v.getAssignment() == null) {
706                        ret.add(constraint);
707                        continue constraints;
708                    }
709                }
710            }
711            if (!unassignedVariables().isEmpty())
712                ret.addAll(globalConstraints());
713            return ret;
714        }
715    
716        /** Registered info providers (see {@link InfoProvider}) */
717        protected List<InfoProvider<V>> getInfoProviders() {
718            return iInfoProviders;
719        }
720        
721        /** Register a new criterion */
722        public void addCriterion(Criterion<V,T> criterion) {
723            iCriteria.put(criterion.getClass().getName(), criterion);
724            addModelListener(criterion);
725        }
726        
727        /** Unregister an existing criterion */
728        public void removeCriterion(Criterion<V,T> criterion) {
729            iCriteria.remove(criterion.getClass().getName());
730            removeModelListener(criterion);
731        }
732        
733        /** Unregister an existing criterion */
734        public void removeCriterion(Class<? extends Criterion<V, T>> criterion) {
735            Criterion<V,T> c = iCriteria.remove(criterion.getName());
736            if (c != null)
737                removeModelListener(c);
738        }
739    
740        /** Return a registered criterion of the given type. */
741        public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) {
742            return iCriteria.get(criterion.getName());
743        }
744        
745        /** List all registered criteria */
746        public Collection<Criterion<V, T>> getCriteria() {
747            return iCriteria.values();
748        }
749    }