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        @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    }