001package org.cpsolver.ifs.model;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Collections;
006import java.util.Comparator;
007import java.util.HashSet;
008import java.util.HashMap;
009import java.util.List;
010import java.util.Locale;
011import java.util.Map;
012import java.util.Set;
013import java.util.TreeSet;
014import java.util.concurrent.locks.ReentrantReadWriteLock;
015
016import org.cpsolver.coursett.criteria.TimetablingCriterion;
017import org.cpsolver.ifs.assignment.Assignment;
018import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
019import org.cpsolver.ifs.assignment.EmptyAssignment;
020import org.cpsolver.ifs.assignment.context.AssignmentContext;
021import org.cpsolver.ifs.assignment.context.AssignmentContextReference;
022import org.cpsolver.ifs.assignment.context.HasAssignmentContext;
023import org.cpsolver.ifs.criteria.Criterion;
024import org.cpsolver.ifs.solver.Solver;
025import org.cpsolver.ifs.util.ToolBox;
026
027
028/**
029 * Generic model (definition of a problem). <br>
030 * <br>
031 * It consists of variables and constraints. It has also capability of
032 * memorizing the current and the best ever found assignment. <br>
033 * <br>
034 * Example usage:<br>
035 * <pre>
036 * <code>
037 * MyModel model = new MyModel();
038 * Variable a = new MyVariable("A");
039 * model.addVariable(a);
040 * Variable b = new MyVariable("B");
041 * model.addVariable(b);
042 * Variable c = new MyVariable("C");
043 * model.addVariable(c);
044 * Constraint constr = MyConstraint("all-different");
045 * model.addConstraint(constr);
046 * constr.addVariable(a);
047 * constr.addVariable(b);
048 * constr.addVariable(c);
049 * solver.setInitialSolution(model);
050 * </code>
051 * </pre>
052 * 
053 * @see Variable
054 * @see Constraint
055 * @see org.cpsolver.ifs.solution.Solution
056 * @see org.cpsolver.ifs.solver.Solver
057 * 
058 * @version IFS 1.3 (Iterative Forward Search)<br>
059 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
060 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
061 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
062 * <br>
063 *          This library is free software; you can redistribute it and/or modify
064 *          it under the terms of the GNU Lesser General Public License as
065 *          published by the Free Software Foundation; either version 3 of the
066 *          License, or (at your option) any later version. <br>
067 * <br>
068 *          This library is distributed in the hope that it will be useful, but
069 *          WITHOUT ANY WARRANTY; without even the implied warranty of
070 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
071 *          Lesser General Public License for more details. <br>
072 * <br>
073 *          You should have received a copy of the GNU Lesser General Public
074 *          License along with this library; if not see
075 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
076 * 
077 * @param <V> Variable 
078 * @param <T> Value
079 */
080public class Model<V extends Variable<V, T>, T extends Value<V, T>> {
081    private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Model.class);
082    protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",
083            new java.text.DecimalFormatSymbols(Locale.US));
084    protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
085            new java.text.DecimalFormatSymbols(Locale.US));
086    protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00",
087            new java.text.DecimalFormatSymbols(Locale.US));
088
089    private List<V> iVariables = new ArrayList<V>();
090    private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
091    private List<GlobalConstraint<V, T>> iGlobalConstraints = new ArrayList<GlobalConstraint<V, T>>();
092    private Collection<V> iVariablesWithInitialValueCache = null;
093    private final ReentrantReadWriteLock iVariablesWithInitialValueLock = new ReentrantReadWriteLock();
094
095    private List<ModelListener<V, T>> iModelListeners = new ArrayList<ModelListener<V, T>>();
096    private List<InfoProvider<V, T>> iInfoProviders = new ArrayList<InfoProvider<V, T>>();
097    private HashMap<String, Criterion<V, T>> iCriteria = new HashMap<String, Criterion<V,T>>();
098
099    private int iBestUnassignedVariables = -1;
100    private int iBestPerturbations = 0;
101    private double iBestValue = 0.0;
102    private int iNextReferenceId = 0;
103    private int iNextVariableIndex = 0;
104    @Deprecated
105    private Assignment<V, T> iAssignment = null;
106    private Assignment<V, T> iEmptyAssignment = null;
107    private Map<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>> iAssignmentContextReferences = new HashMap<Integer, AssignmentContextReference<V, T, ? extends AssignmentContext>>();
108    
109    /** Constructor */
110    public Model() {
111    }
112
113    /** The list of variables in the model 
114     * @return list of variables in the model
115     **/
116    public List<V> variables() {
117        return iVariables;
118    }
119
120    /** The number of variables in the model
121     * @return number of variables in the model
122     **/
123    public int countVariables() {
124        return iVariables.size();
125    }
126
127    /** Adds a variable to the model
128     * @param variable a variable
129     **/
130    @SuppressWarnings("unchecked")
131    public void addVariable(V variable) {
132        variable.setModel(this);
133        variable.setIndex(iNextVariableIndex++);
134        iVariables.add(variable);
135        if (variable instanceof InfoProvider<?, ?>)
136            iInfoProviders.add((InfoProvider<V, T>) variable);
137        for (ModelListener<V, T> listener : iModelListeners)
138            listener.variableAdded(variable);
139        invalidateVariablesWithInitialValueCache();
140    }
141
142    /** Removes a variable from the model
143     * @param variable a variable
144     **/
145    @SuppressWarnings("unchecked")
146    public void removeVariable(V variable) {
147        variable.setModel(null);
148        iVariables.remove(variable);
149        if (variable instanceof InfoProvider<?, ?>)
150            iInfoProviders.remove(variable);
151        for (ModelListener<V, T> listener : iModelListeners)
152            listener.variableRemoved(variable);
153        invalidateVariablesWithInitialValueCache();
154        if (variable instanceof HasAssignmentContext)
155            removeReference((HasAssignmentContext<V, T, ?>)variable);
156    }
157
158    /** The list of constraints in the model
159     * @return list of constraints in the model
160     **/
161    public List<Constraint<V, T>> constraints() {
162        return iConstraints;
163    }
164
165    /** The number of constraints in the model
166     * @return number of constraints in the model
167     **/
168    public int countConstraints() {
169        return iConstraints.size();
170    }
171
172    /** Adds a constraint to the model
173     * @param constraint a constraint 
174     **/
175    @SuppressWarnings("unchecked")
176    public void addConstraint(Constraint<V, T> constraint) {
177        constraint.setModel(this);
178        iConstraints.add(constraint);
179        if (constraint instanceof InfoProvider<?, ?>)
180            iInfoProviders.add((InfoProvider<V, T>) constraint);
181        for (ModelListener<V, T> listener : iModelListeners)
182            listener.constraintAdded(constraint);
183    }
184
185    /** Removes a constraint from the model
186     * @param constraint a constraint
187     **/
188    @SuppressWarnings("unchecked")
189    public void removeConstraint(Constraint<V, T> constraint) {
190        constraint.setModel(null);
191        iConstraints.remove(constraint);
192        if (constraint instanceof InfoProvider<?, ?>)
193            iInfoProviders.remove(constraint);
194        for (ModelListener<V, T> listener : iModelListeners)
195            listener.constraintRemoved(constraint);
196        if (constraint instanceof HasAssignmentContext)
197            removeReference((HasAssignmentContext<V, T, ?>)constraint);
198    }
199
200    /** The list of global constraints in the model
201     * @return  list of global constraints in the model
202     **/
203    public List<GlobalConstraint<V, T>> globalConstraints() {
204        return iGlobalConstraints;
205    }
206
207    /** The number of global constraints in the model
208     * @return number of global constraints in the model
209     **/
210    public int countGlobalConstraints() {
211        return iGlobalConstraints.size();
212    }
213
214    /** Adds a global constraint to the model
215     * @param constraint a global constraint
216     **/
217    @SuppressWarnings("unchecked")
218    public void addGlobalConstraint(GlobalConstraint<V, T> constraint) {
219        constraint.setModel(this);
220        iGlobalConstraints.add(constraint);
221        if (constraint instanceof InfoProvider<?, ?>)
222            iInfoProviders.add((InfoProvider<V, T>) constraint);
223        for (ModelListener<V, T> listener : iModelListeners)
224            listener.constraintAdded(constraint);
225    }
226
227    /** Removes a global constraint from the model
228     * @param constraint a global constraint 
229     **/
230    @SuppressWarnings("unchecked")
231    public void removeGlobalConstraint(GlobalConstraint<V, T> constraint) {
232        constraint.setModel(null);
233        iGlobalConstraints.remove(constraint);
234        if (constraint instanceof InfoProvider<?, ?>)
235            iInfoProviders.remove(constraint);
236        for (ModelListener<V, T> listener : iModelListeners)
237            listener.constraintRemoved(constraint);
238        if (constraint instanceof HasAssignmentContext)
239            removeReference((HasAssignmentContext<V, T, ?>)constraint);
240    }
241
242    /**
243     * The list of unassigned variables in the model.
244     * Use {@link Model#unassignedVariables(Assignment)} or {@link Assignment#unassignedVariables(Model)} instead.
245     * @return list of unassigned variables in the model
246     **/
247    @Deprecated
248    public Collection<V> unassignedVariables() {
249        return unassignedVariables(getDefaultAssignment());
250    }
251
252    /** The list of unassigned variables in the model
253     * @param assignment current assignment
254     * @return list of unassigned variables in the model
255     **/
256    public Collection<V> unassignedVariables(Assignment<V, T> assignment) {
257        return assignment.unassignedVariables(this);
258    }
259
260    /**
261     * Number of unassigned variables.
262     * Use {@link Model#nrUnassignedVariables(Assignment)} or {@link Assignment#nrUnassignedVariables(Model)} instead.
263     * @return number of unassigned variables in the model
264     **/
265    @Deprecated
266    public int nrUnassignedVariables() {
267        return nrUnassignedVariables(getDefaultAssignment());
268    }
269
270    /** Number of unassigned variables
271     * @param assignment current assignment
272     * @return number of unassigned variables in the model
273     **/
274    public int nrUnassignedVariables(Assignment<V, T> assignment) {
275        return assignment.nrUnassignedVariables(this);
276    }
277
278    /**
279     * The list of assigned variables in the model.
280     * Use {@link Model#assignedVariables(Assignment)} or {@link Assignment#assignedVariables()} instead.
281     * @return list of assigned variables in the model
282     **/
283    @Deprecated
284    public Collection<V> assignedVariables() {
285        return assignedVariables(getDefaultAssignment());
286    }
287    
288    /** The list of assigned variables in the model
289     * @param assignment current assignment
290     * @return list of assigned variables in the model
291     **/
292    public Collection<V> assignedVariables(Assignment<V, T> assignment) {
293        return assignment.assignedVariables();
294    }
295
296    /**
297     * Number of assigned variables.
298     * Use {@link Model#nrAssignedVariables(Assignment)} or {@link Assignment#nrAssignedVariables()} instead.
299     * @return number of assigned variables in the model
300     **/
301    @Deprecated
302    public int nrAssignedVariables() {
303        return nrAssignedVariables(getDefaultAssignment());
304    }
305    
306    /** Number of assigned variables
307     * @param assignment current assignment
308     * @return number of assigned variables in the model
309     **/
310    public int nrAssignedVariables(Assignment<V, T> assignment) {
311        return assignment.nrAssignedVariables();
312    }
313
314    /**
315     * The list of perturbation variables in the model, i.e., the variables
316     * which has an initial value but which are not assigned with this value.
317     * Use {@link Model#perturbVariables(Assignment)} instead.
318     * @return list of perturbation variables in the model
319     */
320    @Deprecated
321    public Collection<V> perturbVariables() {
322        return perturbVariables(getDefaultAssignment(), variablesWithInitialValue());
323    }
324    
325    /**
326     * The list of perturbation variables in the model, i.e., the variables
327     * which has an initial value but which are not assigned with this value.
328     * @param assignment current assignment
329     * @return list of perturbation variables in the model
330     */
331    public Collection<V> perturbVariables(Assignment<V, T> assignment) {
332        return perturbVariables(assignment, variablesWithInitialValue());
333    }
334    
335    /**
336     * The list of perturbation variables in the model, i.e., the variables
337     * which has an initial value but which are not assigned with this value.
338     * Only variables from the given set are considered.
339     * Use {@link Model#perturbVariables(Assignment, Collection)} instead.
340     * @param variables sub-problem
341     * @return list of perturbation variables in the sub-problem
342     */
343    @Deprecated
344    public List<V> perturbVariables(Collection<V> variables) {
345        return perturbVariables(getDefaultAssignment(), variables);
346    }
347
348    /**
349     * The list of perturbation variables in the model, i.e., the variables
350     * which has an initial value but which are not assigned with this value.
351     * Only variables from the given set are considered.
352     * @param assignment current assignment
353     * @param variables sub-problem
354     * @return list of perturbation variables in the sub-problem
355     */
356    public List<V> perturbVariables(Assignment<V, T> assignment, Collection<V> variables) {
357        List<V> perturbances = new ArrayList<V>();
358        for (V variable : variables) {
359            if (variable.getInitialAssignment() == null)
360                continue;
361            T value = assignment.getValue(variable);
362            if (value != null) {
363                if (!variable.getInitialAssignment().equals(value))
364                    perturbances.add(variable);
365            } else {
366                boolean hasPerturbance = false;
367                for (Constraint<V, T> constraint : variable.hardConstraints()) {
368                    if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
369                        hasPerturbance = true;
370                        break;
371                    }
372                }
373                if (!hasPerturbance)
374                    for (GlobalConstraint<V, T> constraint : globalConstraints()) {
375                        if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
376                            hasPerturbance = true;
377                            break;
378                        }
379                    }
380                if (hasPerturbance)
381                    perturbances.add(variable);
382            }
383        }
384        return perturbances;
385    }
386
387    /**
388     * Returns the set of conflicting variables with this value, if it is
389     * assigned to its variable
390     * Use {@link Model#conflictValues(Assignment, Value)} instead.
391     * @param value a value to be assigned
392     * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable
393     */
394    @Deprecated
395    public Set<T> conflictValues(T value) {
396        return conflictValues(getDefaultAssignment(), value);
397    }
398    
399    /**
400     * Returns the set of conflicting variables with this value, if it is
401     * assigned to its variable
402     * @param assignment current assignment
403     * @param value a value to be assigned
404     * @return a set of conflicting values, i.e., values that would have to be unassigned if the given value is assigned to its variable
405     */
406    public Set<T> conflictValues(Assignment<V, T> assignment, T value) {
407        Set<T> conflictValues = new HashSet<T>();
408        for (Constraint<V, T> constraint : value.variable().hardConstraints())
409            constraint.computeConflicts(assignment, value, conflictValues);
410        for (GlobalConstraint<V, T> constraint : globalConstraints())
411            constraint.computeConflicts(assignment, value, conflictValues);
412        return conflictValues;
413    }
414
415    /**
416     * Return true if the given value is in conflict with a hard constraint
417     * Use {@link Model#inConflict(Assignment, Value)} instead.
418     * @param value a value in question
419     * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable
420     **/
421    @Deprecated
422    public boolean inConflict(T value) {
423        return inConflict(getDefaultAssignment(), value);
424    }
425
426    /** Return true if the given value is in conflict with a hard constraint
427     * @param assignment current assignment
428     * @param value a value in question
429     * @return true if there is a conflict, i.e., there is at least one value that would have to be unassigned if the given value is assigned to its variable
430     **/
431    public boolean inConflict(Assignment<V, T> assignment, T value) {
432        for (Constraint<V, T> constraint : value.variable().hardConstraints())
433            if (constraint.inConflict(assignment, value))
434                return true;
435        for (GlobalConstraint<V, T> constraint : globalConstraints())
436            if (constraint.inConflict(assignment, value))
437                return true;
438        return false;
439    }
440
441    /** The list of variables with an initial value (i.e., variables with {@link Variable#getInitialAssignment()} not null)
442     * @return list of variables with an initial value 
443     **/
444    public Collection<V> variablesWithInitialValue() {
445        iVariablesWithInitialValueLock.readLock().lock();
446        try {
447            if (iVariablesWithInitialValueCache != null)
448                return iVariablesWithInitialValueCache;
449        } finally {
450            iVariablesWithInitialValueLock.readLock().unlock();
451        }
452        iVariablesWithInitialValueLock.writeLock().lock();
453        try {
454            if (iVariablesWithInitialValueCache != null)
455                return iVariablesWithInitialValueCache;
456            iVariablesWithInitialValueCache = new ArrayList<V>();
457            for (V variable : iVariables) {
458                if (variable.getInitialAssignment() != null)
459                    iVariablesWithInitialValueCache.add(variable);
460            }
461            return iVariablesWithInitialValueCache;
462        } finally {
463            iVariablesWithInitialValueLock.writeLock().unlock();
464        }
465    }
466
467    /** Invalidates cache containing all variables that possess an initial value */
468    protected void invalidateVariablesWithInitialValueCache() {
469        iVariablesWithInitialValueLock.writeLock().lock();
470        iVariablesWithInitialValueCache = null;
471        iVariablesWithInitialValueLock.writeLock().unlock();
472    }
473    
474    /** Called before a value is assigned to its variable
475     * @param iteration current iteration
476     * @param value a value to be assigned
477     **/
478    @Deprecated
479    public void beforeAssigned(long iteration, T value) {
480    }
481
482    /** Called before a value is assigned to its variable
483     * @param assignment current assignment
484     * @param iteration current iteration
485     * @param value a value to be assigned
486     **/
487    public void beforeAssigned(Assignment<V, T> assignment, long iteration, T value) {
488        beforeAssigned(iteration, value);
489        for (ModelListener<V, T> listener : iModelListeners)
490            listener.beforeAssigned(assignment, iteration, value);
491    }
492
493    /** Called before a value is unassigned from its variable 
494     * @param iteration current iteration
495     * @param value a value to be unassigned
496     **/
497    @Deprecated
498    public void beforeUnassigned(long iteration, T value) {
499    }
500
501    /** Called before a value is unassigned from its variable
502     * @param assignment current assignment
503     * @param iteration current iteration
504     * @param value a value to be unassigned
505     **/
506    public void beforeUnassigned(Assignment<V, T> assignment, long iteration, T value) {
507        beforeUnassigned(iteration, value);
508        for (ModelListener<V, T> listener : iModelListeners)
509            listener.beforeUnassigned(assignment, iteration, value);
510    }
511
512    /** Called after a value is assigned to its variable
513     * @param iteration current iteration
514     * @param value a value that was assigned
515     **/
516    @Deprecated
517    public void afterAssigned(long iteration, T value) {
518    }
519
520    /** Called after a value is assigned to its variable
521     * @param assignment current assignment
522     * @param iteration current iteration
523     * @param value a value that was assigned
524     **/
525    public void afterAssigned(Assignment<V, T> assignment,  long iteration, T value) {
526        afterAssigned(iteration, value);
527        for (ModelListener<V, T> listener : iModelListeners)
528            listener.afterAssigned(assignment, iteration, value);
529    }
530    
531    /** Called after a value is unassigned from its variable
532     * @param iteration current iteration
533     * @param value a value that was unassigned
534     **/
535    @Deprecated
536    public void afterUnassigned(long iteration, T value) {
537    }
538
539    /** Called after a value is unassigned from its variable
540     * @param assignment current assignment
541     * @param iteration current iteration
542     * @param value a value that was unassigned
543     **/
544    public void afterUnassigned(Assignment<V, T> assignment, long iteration, T value) {
545        afterUnassigned(iteration, value);
546        for (ModelListener<V, T> listener : iModelListeners)
547            listener.afterUnassigned(assignment, iteration, value);
548    }
549
550    @Override
551    public String toString() {
552        return "Model{\n    variables=" + ToolBox.col2string(variables(), 2) + ",\n    constraints=" + ToolBox.col2string(constraints(), 2) + ",\n  }";
553    }
554    
555    /**
556     * String representation -- returns a list of values of objective criteria
557     * @param assignment current assignment
558     * @return comma separated string of {@link TimetablingCriterion#toString(Assignment)}
559     */
560    public String toString(Assignment<V, T> assignment) {
561        List<Criterion<V, T>> criteria = new ArrayList<Criterion<V,T>>(getCriteria());
562        Collections.sort(criteria, new Comparator<Criterion<V, T>>() {
563            @Override
564            public int compare(Criterion<V, T> c1, Criterion<V, T> c2) {
565                int cmp = -Double.compare(c1.getWeight(), c2.getWeight());
566                if (cmp != 0) return cmp;
567                return c1.getName().compareTo(c2.getName());
568            }
569        });
570        String ret = "";
571        for (Criterion<V, T> criterion: criteria) {
572            String val = criterion.toString(assignment);
573            if (val != null && !val.isEmpty())
574                ret += ", " + val;
575        }
576        return (nrUnassignedVariables(assignment) == 0 ? "" : "V:" + nrAssignedVariables(assignment) + "/" + variables().size() + ", ") + "T:" + sDoubleFormat.format(getTotalValue(assignment)) + ret;
577    }
578
579    protected String getPerc(double value, double min, double max) {
580        if (max == min)
581            return sPercentageFormat.format(100.0);
582        return sPercentageFormat.format(100.0 - 100.0 * (value - min) / (max - min));
583    }
584
585    protected String getPercRev(double value, double min, double max) {
586        if (max == min)
587            return sPercentageFormat.format(0.0);
588        return sPercentageFormat.format(100.0 * (value - min) / (max - min));
589    }
590    
591    /**
592     * Returns information about the current solution. Information from all
593     * model listeners and constraints is also included.
594     * Use {@link Model#getInfo(Assignment)} instead.
595     * @return info table
596     */
597    @Deprecated
598    public Map<String, String> getInfo() {
599        return getInfo(getDefaultAssignment());
600    }
601
602    /**
603     * Returns information about the current solution. Information from all
604     * model listeners and constraints is also included.
605     * @param assignment current assignment
606     * @return info table
607     */
608    public Map<String, String> getInfo(Assignment<V, T> assignment) {
609        Map<String, String> ret = new HashMap<String, String>();
610        ret.put("Assigned variables", getPercRev(assignment.nrAssignedVariables(), 0, variables().size()) + "% (" + assignment.nrAssignedVariables() + "/" + variables().size() + ")");
611        int nrVarsWithInitialValue = variablesWithInitialValue().size();
612        if (nrVarsWithInitialValue > 0) {
613            Collection<V> pv = perturbVariables(assignment);
614            ret.put("Perturbation variables", getPercRev(pv.size(), 0, nrVarsWithInitialValue) + "% (" + pv.size() + " + " + (variables().size() - nrVarsWithInitialValue) + ")");
615        }
616        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment)));
617        for (InfoProvider<V, T> provider : iInfoProviders)
618            provider.getInfo(assignment, ret);
619        return ret;
620    }
621    
622    /**
623     * Extended information about current solution. Similar to
624     * {@link Model#getInfo(Assignment)}, but some more information (that is more
625     * expensive to compute) might be added.
626     * Use {@link Model#getExtendedInfo(Assignment)} instead.
627     * @return extended info table
628     */
629    @Deprecated
630    public Map<String, String> getExtendedInfo() {
631        return getExtendedInfo(getDefaultAssignment());
632    }
633
634    /**
635     * Extended information about current solution. Similar to
636     * {@link Model#getInfo(Assignment)}, but some more information (that is more
637     * expensive to compute) might be added.
638     * @param assignment current assignment
639     * @return extended info table
640     */
641    public Map<String, String> getExtendedInfo(Assignment<V, T> assignment) {
642        Map<String, String> ret = getInfo(assignment);
643        for (InfoProvider<V, T> provider : iInfoProviders)
644            if (provider instanceof ExtendedInfoProvider)
645                ((ExtendedInfoProvider<V, T>)provider).getExtendedInfo(assignment, ret);
646        return ret;
647    }
648    
649    /**
650     * Returns information about the current solution. Information from all
651     * model listeners and constraints is also included. Only variables from the
652     * given set are considered.
653     * Use {@link Model#getInfo(Assignment, Collection)} instead.
654     * @param variables sub-problem 
655     * @return info table
656     **/
657    @Deprecated
658    public Map<String, String> getInfo(Collection<V> variables) {
659        return getInfo(getDefaultAssignment(), variables);
660    }
661
662    /**
663     * Returns information about the current solution. Information from all
664     * model listeners and constraints is also included. Only variables from the
665     * given set are considered.
666     * @param assignment current assignment
667     * @param variables sub-problem 
668     * @return info table
669     */
670    public Map<String, String> getInfo(Assignment<V, T> assignment, Collection<V> variables) {
671        Map<String, String> ret = new HashMap<String, String>();
672        int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0;
673        for (V variable : variables) {
674            T value = assignment.getValue(variable);
675            if (value != null)
676                assigned++;
677            if (variable.getInitialAssignment() != null) {
678                nrVarsWithInitialValue++;
679                if (value != null) {
680                    if (!variable.getInitialAssignment().equals(value))
681                        perturb++;
682                } else {
683                    boolean hasPerturbance = false;
684                    for (Constraint<V, T> constraint : variable.hardConstraints()) {
685                        if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
686                            hasPerturbance = true;
687                            break;
688                        }
689                    }
690                    if (!hasPerturbance)
691                        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
692                            if (constraint.inConflict(assignment, variable.getInitialAssignment())) {
693                                hasPerturbance = true;
694                                break;
695                            }
696                        }
697                    if (hasPerturbance)
698                        perturb++;
699                }
700            }
701        }
702        ret.put("Assigned variables", getPercRev(assigned, 0, variables.size()) + "% (" + assigned + "/" + variables.size() + ")");
703        if (nrVarsWithInitialValue > 0) {
704            ret.put("Perturbation variables", getPercRev(perturb, 0, nrVarsWithInitialValue) + "% (" + perturb + " + " + (variables.size() - nrVarsWithInitialValue) + ")");
705        }
706        ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(assignment, variables)));
707        for (InfoProvider<V, T> provider : iInfoProviders)
708            provider.getInfo(assignment, ret, variables);
709        return ret;
710    }
711
712    /**
713     * Returns the number of unassigned variables in the best ever found
714     * solution
715     * @return number of unassigned variables in the best solution
716     */
717    public int getBestUnassignedVariables() {
718        return iBestUnassignedVariables;
719    }
720
721    /**
722     * Returns the number of perturbation variables in the best ever found
723     * solution
724     * @return number of perturbation variables in the best solution
725     */
726    public int getBestPerturbations() {
727        return iBestPerturbations;
728    }
729    
730    /**
731     * Total value of the best ever found solution -- sum of all assigned values
732     * (see {@link Value#toDouble(Assignment)}).
733     * @return value of the best solution
734     */
735    public double getBestValue() {
736        return iBestValue;
737    }
738
739    /** Set total value of the best ever found solution 
740     * @param bestValue value of the best solution
741     **/
742    public void setBestValue(double bestValue) {
743        iBestValue = bestValue;
744    }
745    
746    /**
747     * Save the current assignment as the best ever found assignment
748     * Use {@link Model#saveBest(Assignment)} instead.
749     **/
750    @Deprecated
751    public void saveBest() {
752        saveBest(getDefaultAssignment());
753    }
754
755    /** Save the current assignment as the best ever found assignment 
756     * @param assignment current assignment 
757     **/
758    public void saveBest(Assignment<V, T> assignment) {
759        iBestUnassignedVariables = iVariables.size() - assignment.nrAssignedVariables();
760        iBestPerturbations = perturbVariables(assignment).size();
761        iBestValue = getTotalValue(assignment);
762        for (V variable : iVariables) {
763            variable.setBestAssignment(assignment.getValue(variable), assignment.getIteration(variable));
764        }
765        for (Criterion<V, T> criterion: getCriteria()) {
766            criterion.bestSaved(assignment);
767        }
768    }
769
770    /** Clear the best ever found assignment */
771    public void clearBest() {
772        iBestUnassignedVariables = -1;
773        iBestPerturbations = 0;
774        iBestValue = 0;
775        for (V variable : iVariables) {
776            variable.setBestAssignment(null, 0);
777        }
778    }
779
780    /**
781     * Restore the best ever found assignment into the current assignment
782     * Use {@link Model#restoreBest(Assignment)} instead.
783     **/
784    @Deprecated
785    protected void restoreBest() {
786        restoreBest(getDefaultAssignment());
787    }
788
789    /** Restore the best ever found assignment into the current assignment
790     * @param assignment current assignment
791     * @param assignmentOrder assignment order of the variables 
792     **/
793    @SuppressWarnings("unchecked")
794    protected void restoreBest(Assignment<V, T> assignment, Comparator<V> assignmentOrder) {
795        TreeSet<V> sortedVariables = new TreeSet<V>(assignmentOrder);
796        for (V variable : iVariables) {
797            T value = assignment.getValue(variable);
798            if (value == null) {
799                if (variable.getBestAssignment() != null)
800                    sortedVariables.add(variable);
801            } else if (!value.equals(variable.getBestAssignment())) {
802                assignment.unassign(0, variable);
803                if (variable.getBestAssignment() != null)
804                    sortedVariables.add(variable);
805            }
806        }
807        Set<T> problems = new HashSet<T>();
808        for (V variable : sortedVariables) {
809            Set<T> confs = conflictValues(assignment, variable.getBestAssignment());
810            if (!confs.isEmpty()) {
811                sLogger.error("restore best problem: assignment " + variable.getName() + " = " + variable.getBestAssignment().getName());
812                boolean weakened = false;
813                for (Constraint<V, T> c : variable.hardConstraints()) {
814                    Set<T> x = new HashSet<T>();
815                    c.computeConflicts(assignment, variable.getBestAssignment(), x);
816                    if (!x.isEmpty()) {
817                        if (c instanceof WeakeningConstraint) {
818                            ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment());
819                            sLogger.info("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened");
820                            weakened = true;
821                        } else {
822                            sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
823                        }
824                    }
825                }
826                for (GlobalConstraint<V, T> c : globalConstraints()) {
827                    Set<T> x = new HashSet<T>();
828                    c.computeConflicts(assignment, variable.getBestAssignment(), x);
829                    if (!x.isEmpty()) {
830                        if (c instanceof WeakeningConstraint) {
831                            ((WeakeningConstraint<V, T>)c).weaken(assignment, variable.getBestAssignment());
832                            sLogger.info("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " had to be weakened");
833                            weakened = true;
834                        } else {
835                            sLogger.error("  global constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
836                        }
837                    }
838                }
839                if (weakened && conflictValues(assignment, variable.getBestAssignment()).isEmpty())
840                    assignment.assign(0, variable.getBestAssignment());
841                else
842                    problems.add(variable.getBestAssignment());
843            } else
844                assignment.assign(0, variable.getBestAssignment());
845        }
846        int attempt = 0, maxAttempts = 3 * problems.size();
847        while (!problems.isEmpty() && attempt <= maxAttempts) {
848            attempt++;
849            T value = ToolBox.random(problems);
850            problems.remove(value);
851            V variable = value.variable();
852            Set<T> confs = conflictValues(assignment, value);
853            if (!confs.isEmpty()) {
854                sLogger.error("restore best problem (again, att=" + attempt + "): assignment " + variable.getName() + " = " + value.getName());
855                for (Constraint<V, T> c : variable.hardConstraints()) {
856                    Set<T> x = new HashSet<T>();
857                    c.computeConflicts(assignment, value, x);
858                    if (!x.isEmpty())
859                        sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
860                }
861                for (GlobalConstraint<V, T> c : globalConstraints()) {
862                    Set<T> x = new HashSet<T>();
863                    c.computeConflicts(assignment, value, x);
864                    if (!x.isEmpty())
865                        sLogger.error("  constraint " + c.getClass().getSimpleName() + " " + c.getName() + " causes the following conflicts " + x);
866                }
867                for (T conf : confs)
868                    assignment.unassign(0, conf.variable());
869                problems.addAll(confs);
870            }
871            assignment.assign(0, value);
872        }
873        for (Criterion<V, T> criterion: getCriteria()) {
874            criterion.bestRestored(assignment);
875        }
876    }
877    
878    /** Restore the best ever found assignment into the current assignment
879     * @param assignment current assignment
880     **/
881    public void restoreBest(Assignment<V, T> assignment) {
882        restoreBest(assignment, new Comparator<V>() {
883            @Override
884            public int compare(V v1, V v2) {
885                if (v1.getBestAssignmentIteration() < v2.getBestAssignmentIteration()) return -1;
886                if (v1.getBestAssignmentIteration() > v2.getBestAssignmentIteration()) return 1;
887                return v1.compareTo(v2);
888            }
889        });
890    }
891    
892    /**
893     * The list of unassigned variables in the best ever found solution.
894     * Use {@link Model#bestUnassignedVariables(Assignment)} instead.
895     * @return variables list of unassigned variables in the best solution
896     **/
897    @Deprecated
898    public Collection<V> bestUnassignedVariables() {
899        return bestUnassignedVariables(getDefaultAssignment());
900    }
901    
902    /** The list of unassigned variables in the best ever found solution
903     * @param assignment current assignment
904     * @return variables list of unassigned variables in the best solution
905     **/
906    public Collection<V> bestUnassignedVariables(Assignment<V, T> assignment) {
907        Collection<V> ret = new ArrayList<V>(variables().size());
908        if (iBestUnassignedVariables < 0) {
909            for (V variable : variables()) {
910                if (assignment.getValue(variable) == null)
911                    ret.add(variable);
912            }
913        } else {
914            for (V variable : variables()) {
915                if (variable.getBestAssignment() == null)
916                    ret.add(variable);
917            }
918        }
919        return ret;
920    }
921
922    /**
923     * Value of the current solution. It is the sum of all assigned values,
924     * i.e., {@link Value#toDouble(Assignment)}.
925     * Use {@link Model#getTotalValue(Assignment)} instead.
926     * @return solution value
927     */
928    @Deprecated
929    public double getTotalValue() {
930        return getTotalValue(getDefaultAssignment());
931    }
932    
933    /**
934     * Value of the current solution. It is the sum of all assigned values,
935     * i.e., {@link Value#toDouble(Assignment)}.
936     * @param assignment current assignment
937     * @return solution value
938     */
939    public double getTotalValue(Assignment<V, T> assignment) {
940        double ret = 0.0;
941        for (T t: assignment.assignedValues())
942            ret += t.toDouble(assignment);
943        return ret;
944    }
945
946    /**
947     * Value of the current solution. It is the sum of all assigned values,
948     * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are
949     * considered.
950     * Use {@link Model#getTotalValue(Assignment, Collection)} instead.
951     * @param variables sub-problem
952     * @return solution value
953     **/
954    @Deprecated
955    public double getTotalValue(Collection<V> variables) {
956        return getTotalValue(getDefaultAssignment(), variables);
957    }
958    
959    /**
960     * Value of the current solution. It is the sum of all assigned values,
961     * i.e., {@link Value#toDouble(Assignment)}. Only variables from the given set are
962     * considered.
963     * @param assignment current assignment
964     * @param variables sub-problem
965     * @return solution value
966     **/
967    public double getTotalValue(Assignment<V, T> assignment, Collection<V> variables) {
968        double ret = 0.0;
969        for (V v: variables) {
970            T t = assignment.getValue(v);
971            if (t != null)
972                ret += t.toDouble(assignment);
973        }
974        return ret;
975    }
976
977    /** Adds a model listener 
978     * @param listener a model listener
979     **/
980    @SuppressWarnings("unchecked")
981    public void addModelListener(ModelListener<V, T> listener) {
982        iModelListeners.add(listener);
983        if (listener instanceof InfoProvider<?, ?>)
984            iInfoProviders.add((InfoProvider<V, T>) listener);
985        for (Constraint<V, T> constraint : iConstraints)
986            listener.constraintAdded(constraint);
987        for (V variable : iVariables)
988            listener.variableAdded(variable);
989    }
990
991    /** Removes a model listener
992     * @param listener a model listener
993     **/
994    public void removeModelListener(ModelListener<V, T> listener) {
995        if (listener instanceof InfoProvider<?, ?>)
996            iInfoProviders.remove(listener);
997        for (V variable : iVariables)
998            listener.variableRemoved(variable);
999        for (Constraint<V, T> constraint : iConstraints)
1000            listener.constraintRemoved(constraint);
1001        iModelListeners.remove(listener);
1002    }
1003
1004    /** Model initialization
1005     * @param solver current solver
1006     * @return true if successfully initialized 
1007     **/
1008    public boolean init(Solver<V, T> solver) {
1009        for (ModelListener<V, T> listener : new ArrayList<ModelListener<V, T>>(iModelListeners)) {
1010            if (!listener.init(solver))
1011                return false;
1012        }
1013        return true;
1014    }
1015
1016    /** The list of model listeners 
1017     * @return list of model listeners
1018     **/
1019    public List<ModelListener<V, T>> getModelListeners() {
1020        return iModelListeners;
1021    }
1022
1023    /** The list of model listeners that are of the given class
1024     * @param type model listener type
1025     * @return list of model listeners that are of the given class
1026     **/
1027    public ModelListener<V, T> modelListenerOfType(Class<ModelListener<V, T>> type) {
1028        for (ModelListener<V, T> listener : iModelListeners) {
1029            if (listener.getClass() == type)
1030                return listener;
1031        }
1032        return null;
1033    }
1034
1035    /**
1036     * The list of constraints which are in a conflict with the given value if
1037     * it is assigned to its variable. This means the constraints, which adds a
1038     * value into the set of conflicting values in
1039     * {@link Constraint#computeConflicts(Assignment, Value, Set)}.
1040     * @param assignment current assignment
1041     * @param value given value
1042     * @return hard constraints and their conflicts that are conflicting with the given value
1043     */
1044    public Map<Constraint<V, T>, Set<T>> conflictConstraints(Assignment<V, T> assignment, T value) {
1045        Map<Constraint<V, T>, Set<T>> conflictConstraints = new HashMap<Constraint<V, T>, Set<T>>();
1046        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
1047            Set<T> conflicts = new HashSet<T>();
1048            constraint.computeConflicts(assignment, value, conflicts);
1049            if (!conflicts.isEmpty()) {
1050                conflictConstraints.put(constraint, conflicts);
1051            }
1052        }
1053        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
1054            Set<T> conflicts = new HashSet<T>();
1055            constraint.computeConflicts(assignment, value, conflicts);
1056            if (!conflicts.isEmpty()) {
1057                conflictConstraints.put(constraint, conflicts);
1058            }
1059        }
1060        return conflictConstraints;
1061    }
1062
1063    /**
1064     * The list of hard constraints which contain at least one variable that is
1065     * not assigned.
1066     * @param assignment current assignment
1067     * @return list of hard constraints which contain at least one variable that is not assigned
1068     */
1069    public List<Constraint<V, T>> unassignedHardConstraints(Assignment<V, T> assignment) {
1070        List<Constraint<V, T>> ret = new ArrayList<Constraint<V, T>>();
1071        constraints: for (Constraint<V, T> constraint : constraints()) {
1072            if (!constraint.isHard())
1073                continue;
1074            for (V v : constraint.variables()) {
1075                if (assignment.getValue(v) == null) {
1076                    ret.add(constraint);
1077                    continue constraints;
1078                }
1079            }
1080        }
1081        if (iVariables.size() > assignment.nrAssignedVariables())
1082            ret.addAll(globalConstraints());
1083        return ret;
1084    }
1085
1086    /** Registered info providers (see {@link InfoProvider}) 
1087     * @return list of registered info providers
1088     **/
1089    protected List<InfoProvider<V, T>> getInfoProviders() {
1090        return iInfoProviders;
1091    }
1092    
1093    /** Register a new criterion 
1094     * @param criterion a criterion
1095     **/
1096    public void addCriterion(Criterion<V,T> criterion) {
1097        iCriteria.put(criterion.getClass().getName(), criterion);
1098        criterion.setModel(this);
1099        addModelListener(criterion);
1100    }
1101    
1102    /** Unregister an existing criterion
1103     * @param criterion a criterion
1104     **/
1105    public void removeCriterion(Criterion<V,T> criterion) {
1106        iCriteria.remove(criterion.getClass().getName());
1107        criterion.setModel(null);
1108        removeModelListener(criterion);
1109    }
1110    
1111    /** Unregister an existing criterion
1112     * @param criterion a criterion
1113     **/
1114    public void removeCriterion(Class<? extends Criterion<V, T>> criterion) {
1115        Criterion<V,T> c = iCriteria.remove(criterion.getName());
1116        if (c != null)
1117            removeModelListener(c);
1118    }
1119
1120    /** Return a registered criterion of the given type. 
1121     * @param criterion criterion type 
1122     * @return registered criterion of the given type
1123     **/
1124    public Criterion<V, T> getCriterion(Class<? extends Criterion<V, T>> criterion) {
1125        return iCriteria.get(criterion.getName());
1126    }
1127    
1128    /** List all registered criteria
1129     * @return list all registered criteria
1130     **/
1131    public Collection<Criterion<V, T>> getCriteria() {
1132        return iCriteria.values();
1133    }
1134    
1135    /**
1136     * Weaken all weakening constraint so that the given value can be assigned without
1137     * them creating a conflict using {@link WeakeningConstraint#weaken(Assignment, Value)}.
1138     * This method is handy for instance when an existing solution is being loaded
1139     * into the solver.
1140     * @param assignment current assignment
1141     * @param value given value
1142     */
1143    @SuppressWarnings("unchecked")
1144    public void weaken(Assignment<V, T> assignment, T value) {
1145        for (Constraint<V, T> constraint : value.variable().hardConstraints()) {
1146            if (constraint instanceof WeakeningConstraint)
1147                ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value);
1148        }
1149        for (GlobalConstraint<V, T> constraint : globalConstraints()) {
1150            if (constraint instanceof WeakeningConstraint)
1151                ((WeakeningConstraint<V,T>)constraint).weaken(assignment, value);
1152        }
1153    }
1154    
1155    /**
1156     * Create a reference to an assignment context for a class that is in a need of one. Through this
1157     * reference an assignment context (see {@link AssignmentContext}) can be accessed using
1158     * {@link Assignment#getAssignmentContext(AssignmentContextReference)}.
1159     * @param parent class needing an assignment context
1160     * @param <C> assignment context type
1161     * @return reference to an assignment context
1162     */
1163    public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> createReference(HasAssignmentContext<V, T, C> parent) {
1164        AssignmentContextReference<V, T, C> ref = new AssignmentContextReference<V, T, C>(parent, iNextReferenceId);
1165        iAssignmentContextReferences.put(iNextReferenceId, ref);
1166        iNextReferenceId++;
1167        return ref;
1168    }
1169    
1170    /**
1171     * Clear all assignment contexts for the given assignment
1172     * @param assignment given {@link Assignment}
1173     */
1174    public synchronized void clearAssignmentContexts(Assignment<V, T> assignment) {
1175        for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values())
1176            assignment.clearContext(ref);
1177    }
1178    
1179    /**
1180     * Remove a reference to an assignment context for the model
1181     * @param parent class with an assignment context
1182     * @param <C> assignment context type
1183     * @return reference to an assignment context that was removed from the model (if any)
1184     */
1185    @SuppressWarnings("unchecked")
1186    public synchronized <C extends AssignmentContext> AssignmentContextReference<V,T,C> removeReference(HasAssignmentContext<V, T, C> parent) {
1187        AssignmentContextReference<V,T,C> reference = parent.getAssignmentContextReference();
1188        if (reference != null)
1189            return (AssignmentContextReference<V,T,C>) iAssignmentContextReferences.remove(reference.getIndex());
1190        return null;
1191    }
1192    
1193    /**
1194     * Create all assignment contexts for the given assignment
1195     * @param assignment given {@link Assignment}
1196     * @param clear if true {@link Assignment#clearContext(AssignmentContextReference)} is called first
1197     */
1198    public synchronized void createAssignmentContexts(Assignment<V, T> assignment, boolean clear) {
1199        for (AssignmentContextReference<V,T,? extends AssignmentContext> ref: iAssignmentContextReferences.values()) {
1200            if (clear) assignment.clearContext(ref);
1201            assignment.getAssignmentContext(ref);
1202        }
1203    }
1204
1205    /**
1206     * Return default assignment that is using the old {@link Variable#getAssignment()} assignments.
1207     * @return as instance of {@link DefaultSingleAssignment}
1208     */
1209    @Deprecated
1210    public Assignment<V, T> getDefaultAssignment() {
1211        if (iAssignment == null)
1212            iAssignment = new DefaultSingleAssignment<V, T>();
1213        return iAssignment;
1214    }
1215    
1216    /**
1217     * Set default assignment 
1218     * @param assignment current assignment to become default
1219     */
1220    @Deprecated
1221    public void setDefaultAssignment(Assignment<V, T> assignment) {
1222        iAssignment = assignment;
1223    }
1224    
1225    /**
1226     * Returns an instance of an empty assignment (using {@link EmptyAssignment})
1227     * @return an empty assignment
1228     */
1229    public Assignment<V, T> getEmptyAssignment() {
1230        if (iEmptyAssignment == null)
1231            iEmptyAssignment = new EmptyAssignment<V, T>();
1232        return iEmptyAssignment;
1233    }
1234}