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