001 package net.sf.cpsolver.ifs.model;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.solver.*;
006 import net.sf.cpsolver.ifs.util.*;
007
008 /**
009 * Generic model (definition of a problem).
010 * <br><br>
011 * It consists of variables and constraints. It has also capability of memorizing the current
012 * and the best ever found assignment.
013 * <br><br>
014 * Example usage:<br><ul><code>
015 * MyModel model = new MyModel();<br>
016 * Variable a = new MyVariable("A");<br>
017 * model.addVariable(a);<br>
018 * Variable b = new MyVariable("B");<br>
019 * model.addVariable(b);<br>
020 * Variable c = new MyVariable("C");<br>
021 * model.addVariable(c);<br>
022 * Constraint constr = MyConstraint("all-different");<br>
023 * model.addConstraint(constr);<br>
024 * constr.addVariable(a);<br>
025 * constr.addVariable(b);<br>
026 * constr.addVariable(c);<br>
027 * solver.setInitialSolution(model);
028 * </code></ul>
029 *
030 * @see Variable
031 * @see Constraint
032 * @see net.sf.cpsolver.ifs.solution.Solution
033 * @see net.sf.cpsolver.ifs.solver.Solver
034 *
035 * @version
036 * IFS 1.1 (Iterative Forward Search)<br>
037 * Copyright (C) 2006 Tomáš Müller<br>
038 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
039 * Lazenska 391, 76314 Zlin, Czech Republic<br>
040 * <br>
041 * This library is free software; you can redistribute it and/or
042 * modify it under the terms of the GNU Lesser General Public
043 * License as published by the Free Software Foundation; either
044 * version 2.1 of the License, or (at your option) any later version.
045 * <br><br>
046 * This library is distributed in the hope that it will be useful,
047 * but WITHOUT ANY WARRANTY; without even the implied warranty of
048 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
049 * Lesser General Public License for more details.
050 * <br><br>
051 * You should have received a copy of the GNU Lesser General Public
052 * License along with this library; if not, write to the Free Software
053 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
054 */
055
056 public class Model {
057 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(Model.class);
058 protected static java.text.DecimalFormat sTimeFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
059 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
060 protected static java.text.DecimalFormat sPercentageFormat = new java.text.DecimalFormat("0.00",new java.text.DecimalFormatSymbols(Locale.US));
061
062 private Vector iVariables = new FastVector();
063 private Vector iConstraints = new FastVector();
064 private Vector iGlobalConstraints = new FastVector();
065 protected EnumerableCollection iUnassignedVariables = new FastVector();
066 protected EnumerableCollection iAssignedVariables = new FastVector();
067 private Vector iInfoProviders = new FastVector();
068 private Vector iVariablesWithInitialValueCache = null;
069
070 protected EnumerableCollection iPerturbVariables = null;
071
072 private int iBestUnassignedVariables = -1;
073 private int iBestPerturbations = 0;
074 private int iNrAssignedVariables = 0;
075
076 /** Constructor */
077 public Model() {
078 }
079
080 /** The list of variables in the model */
081 public Vector variables() { return iVariables; }
082 /** The number of variables in the model */
083 public int countVariables() { return iVariables.size(); }
084 /** Adds a variable to the model */
085 public void addVariable(Variable variable) {
086 variable.setModel(this);
087 iVariables.addElement(variable);
088 if (variable instanceof InfoProvider)
089 iInfoProviders.addElement(variable);
090 if (variable.getAssignment()==null) {
091 if (iUnassignedVariables!=null) iUnassignedVariables.addElement(variable);
092 } else {
093 if (iAssignedVariables!=null) iAssignedVariables.addElement(variable);
094 iNrAssignedVariables++;
095 }
096 if (variable.getAssignment()!=null) variable.assign(0L,variable.getAssignment());
097 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
098 ((ModelListener)e.nextElement()).variableAdded(variable);
099 invalidateVariablesWithInitialValueCache();
100 }
101 /** Removes a variable from the model */
102 public void removeVariable(Variable variable) {
103 variable.setModel(null);
104 iVariables.removeElement(variable);
105 if (variable instanceof InfoProvider)
106 iInfoProviders.removeElement(variable);
107 if (iUnassignedVariables!=null && iUnassignedVariables.contains(variable)) iUnassignedVariables.removeElement(variable);
108 if (iAssignedVariables!=null && iAssignedVariables.contains(variable)) iAssignedVariables.removeElement(variable);
109 if (variable.getAssignment()!=null) iNrAssignedVariables--;
110 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
111 ((ModelListener)e.nextElement()).variableRemoved(variable);
112 invalidateVariablesWithInitialValueCache();
113 }
114
115 /** The list of constraints in the model */
116 public Vector constraints() { return iConstraints; }
117 /** The number of constraints in the model */
118 public int countConstraints() { return iConstraints.size(); }
119 /** Adds a constraint to the model */
120 public void addConstraint(Constraint constraint) {
121 constraint.setModel(this);
122 iConstraints.addElement(constraint);
123 if (constraint instanceof InfoProvider)
124 iInfoProviders.addElement(constraint);
125 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
126 ((ModelListener)e.nextElement()).constraintAdded(constraint);
127 }
128 /** Removes a constraint from the model */
129 public void removeConstraint(Constraint constraint) {
130 constraint.setModel(null);
131 iConstraints.removeElement(constraint);
132 if (constraint instanceof InfoProvider)
133 iInfoProviders.removeElement(constraint);
134 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
135 ((ModelListener)e.nextElement()).constraintRemoved(constraint);
136 }
137
138 /** The list of global constraints in the model */
139 public Vector globalConstraints() { return iGlobalConstraints; }
140 /** The number of global constraints in the model */
141 public int countGlobalConstraints() { return iGlobalConstraints.size(); }
142 /** Adds a global constraint to the model */
143 public void addGlobalConstraint(GlobalConstraint constraint) {
144 constraint.setModel(this);
145 iGlobalConstraints.addElement(constraint);
146 if (constraint instanceof InfoProvider)
147 iInfoProviders.addElement(constraint);
148 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
149 ((ModelListener)e.nextElement()).constraintAdded(constraint);
150 }
151 /** Removes a global constraint from the model */
152 public void removeGlobalConstraint(GlobalConstraint constraint) {
153 constraint.setModel(null);
154 iGlobalConstraints.removeElement(constraint);
155 if (constraint instanceof InfoProvider)
156 iInfoProviders.removeElement(constraint);
157 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
158 ((ModelListener)e.nextElement()).constraintRemoved(constraint);
159 }
160
161 /** The list of unassigned variables in the model */
162 public EnumerableCollection unassignedVariables() {
163 if (iUnassignedVariables!=null) return iUnassignedVariables;
164 FastVector un = new FastVector(iVariables.size());
165 for (Enumeration e=iVariables.elements();e.hasMoreElements();) {
166 Variable variable = (Variable)e.nextElement();
167 if (variable.getAssignment()==null) un.add(variable);
168 }
169 return un;
170 }
171
172 /** Number of unassigned variables */
173 public int nrUnassignedVariables() {
174 if (iUnassignedVariables!=null) return iUnassignedVariables.size();
175 return iVariables.size() - iNrAssignedVariables;
176 }
177
178 /** The list of assigned variables in the model */
179 public EnumerableCollection assignedVariables() {
180 if (iAssignedVariables!=null) return iAssignedVariables;
181 FastVector as = new FastVector(iVariables.size());
182 for (Enumeration e=iVariables.elements();e.hasMoreElements();) {
183 Variable variable = (Variable)e.nextElement();
184 if (variable.getAssignment()!=null) as.add(variable);
185 }
186 return as;
187 }
188
189 /** Number of assigned variables */
190 public int nrAssignedVariables() {
191 if (iAssignedVariables!=null) return iAssignedVariables.size();
192 return iNrAssignedVariables;
193 }
194
195 /** The list of perturbation variables in the model, i.e., the variables which has an initial value but which are not
196 * assigned with this value.
197 */
198 public EnumerableCollection perturbVariables() {
199 if (iPerturbVariables!=null) return iPerturbVariables;
200 EnumerableCollection perturbances = new FastVector();
201 for (Enumeration e=variablesWithInitialValue().elements();e.hasMoreElements();) {
202 Variable variable = (Variable)e.nextElement();
203 if (variable.getAssignment()!=null) {
204 if (!variable.getInitialAssignment().equals(variable.getAssignment())) perturbances.addElement(variable);
205 } else {
206 boolean hasPerturbance = false;
207 for (Enumeration x=variable.hardConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
208 Constraint constraint = (Constraint)x.nextElement();
209 if (constraint.inConflict(variable.getInitialAssignment()))
210 hasPerturbance=true;
211 }
212 for (Enumeration x=globalConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
213 GlobalConstraint constraint = (GlobalConstraint)x.nextElement();
214 if (constraint.inConflict(variable.getInitialAssignment()))
215 hasPerturbance=true;
216 }
217 if (hasPerturbance) perturbances.addElement(variable);
218 }
219 }
220 iPerturbVariables = perturbances;
221 return perturbances;
222 }
223
224 /** The list of perturbation variables in the model, i.e., the variables which has an initial value but which are not
225 * assigned with this value. Only variables from the given set are considered.
226 */
227 public EnumerableCollection perturbVariables(Vector variables) {
228 EnumerableCollection perturbances = new FastVector();
229 for (Enumeration e=variables.elements();e.hasMoreElements();) {
230 Variable variable = (Variable)e.nextElement();
231 if (variable.getInitialAssignment()==null) continue;
232 if (variable.getAssignment()!=null) {
233 if (!variable.getInitialAssignment().equals(variable.getAssignment())) perturbances.addElement(variable);
234 } else {
235 boolean hasPerturbance = false;
236 for (Enumeration x=variable.hardConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
237 Constraint constraint = (Constraint)x.nextElement();
238 if (constraint.inConflict(variable.getInitialAssignment()))
239 hasPerturbance=true;
240 }
241 for (Enumeration x=globalConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
242 GlobalConstraint constraint = (GlobalConstraint)x.nextElement();
243 if (constraint.inConflict(variable.getInitialAssignment()))
244 hasPerturbance=true;
245 }
246 if (hasPerturbance) perturbances.addElement(variable);
247 }
248 }
249 return perturbances;
250 }
251
252
253 /** Returns the set of confliction variables with this value, if it is assigned to its variable */
254 public Set conflictValues(Value value) {
255 HashSet conflictValues = new HashSet();
256 for (Enumeration c=value.variable().hardConstraints().elements(); c.hasMoreElements();)
257 ((Constraint)c.nextElement()).computeConflicts(value, conflictValues);
258 for (Enumeration c=globalConstraints().elements(); c.hasMoreElements();)
259 ((GlobalConstraint)c.nextElement()).computeConflicts(value, conflictValues);
260 return conflictValues;
261 }
262
263 /** Return true if the given value is in conflict with a hard constraint */
264 public boolean inConflict(Value value) {
265 for (Enumeration c=value.variable().hardConstraints().elements(); c.hasMoreElements();)
266 if (((Constraint)c.nextElement()).inConflict(value)) return true;
267 for (Enumeration c=globalConstraints().elements(); c.hasMoreElements();)
268 if (((GlobalConstraint)c.nextElement()).inConflict(value)) return true;
269 return false;
270 }
271
272 /** The list of variales without initial value */
273 public Vector variablesWithInitialValue() {
274 if (iVariablesWithInitialValueCache!=null)
275 return iVariablesWithInitialValueCache;
276 iVariablesWithInitialValueCache = new FastVector();
277 for (Enumeration e=variables().elements();e.hasMoreElements();) {
278 Variable variable = (Variable)e.nextElement();
279 if (variable.getInitialAssignment()!=null) iVariablesWithInitialValueCache.addElement(variable);
280 }
281 return iVariablesWithInitialValueCache;
282 }
283
284 /** Invalidates cache containing all variables that possess an initial value */
285 protected void invalidateVariablesWithInitialValueCache() {
286 iVariablesWithInitialValueCache = null;
287 }
288
289 /** Called before a value is assigned to its variable */
290 public void beforeAssigned(long iteration, Value value) {
291 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
292 ((ModelListener)e.nextElement()).beforeAssigned(iteration, value);
293 }
294
295 /** Called before a value is unassigned from its variable */
296 public void beforeUnassigned(long iteration, Value value) {
297 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
298 ((ModelListener)e.nextElement()).beforeUnassigned(iteration, value);
299 }
300
301 /** Called after a value is assigned to its variable */
302 public void afterAssigned(long iteration, Value value) {
303 if (iUnassignedVariables!=null) iUnassignedVariables.removeElement(value.variable());
304 if (iAssignedVariables!=null) iAssignedVariables.addElement(value.variable());
305 iNrAssignedVariables++;
306 iPerturbVariables = null;
307 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
308 ((ModelListener)e.nextElement()).afterAssigned(iteration, value);
309 }
310
311 /** Called after a value is unassigned from its variable */
312 public void afterUnassigned(long iteration, Value value) {
313 if (iUnassignedVariables!=null) iUnassignedVariables.addElement(value.variable());
314 if (iAssignedVariables!=null) iAssignedVariables.removeElement(value.variable());
315 iNrAssignedVariables--;
316 iPerturbVariables = null;
317 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();)
318 ((ModelListener)e.nextElement()).afterUnassigned(iteration, value);
319 }
320
321 public String toString() {
322 Collections.sort(variables(), new Comparator() {
323 public int compare(Object o1, Object o2) {
324 Variable v1 = (Variable)o1;
325 Variable v2 = (Variable)o2;
326 return (v1.getName()!=null?v1.getName().compareTo(v2.getName()):(int)(v1.getId()-v2.getId()));
327 }
328 });
329 return "Model{\n variables="+ToolBox.col2string(variables(),2)+
330 ",\n constraints="+ToolBox.col2string(constraints(),2)+
331 ",\n #unassigned="+nrUnassignedVariables()+
332 ",\n unassigned="+ToolBox.col2string(unassignedVariables(),2)+
333 ",\n #perturbations="+perturbVariables().size()+"+"+(variables().size()-variablesWithInitialValue().size())+
334 ",\n perturbations="+ToolBox.col2string(perturbVariables(),2)+
335 ",\n info="+getInfo()+
336 "\n }";
337 }
338
339 protected String getPerc(double value, double min, double max) {
340 if (max==min) return sPercentageFormat.format(100.0);
341 return sPercentageFormat.format(100.0 - 100.0*(value-min)/(max-min));
342 }
343
344 protected String getPercRev(double value, double min, double max) {
345 if (max==min) return sPercentageFormat.format(0.0);
346 return sPercentageFormat.format(100.0*(value-min)/(max-min));
347 }
348
349
350 /** Returns information about the current solution. Information from all model listeners and constraints is also included.
351 */
352 public java.util.Hashtable getInfo() {
353 java.util.Hashtable ret = new java.util.Hashtable();
354 ret.put("Assigned variables", getPercRev(nrAssignedVariables(),0,variables().size())+"% ("+nrAssignedVariables()+"/"+variables().size()+")");
355 int nrVarsWithInitialValue = variablesWithInitialValue().size();
356 if (nrVarsWithInitialValue>0) {
357 ret.put("Perturbation variables", getPercRev(perturbVariables().size(),0,nrVarsWithInitialValue)+"% ("+perturbVariables().size()+" + "+(variables().size()-nrVarsWithInitialValue)+")");
358 }
359 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue()));
360 for (Enumeration e=iInfoProviders.elements();e.hasMoreElements();)
361 ((InfoProvider)e.nextElement()).getInfo(ret);
362 return ret;
363 }
364
365 /**
366 * Extended information about current solution.
367 * Similar to {@link Model#getInfo()}, but some more information (that is more expensive to compute) might be added.
368 */
369 public java.util.Hashtable getExtendedInfo() {
370 return getInfo();
371 }
372
373 /** Returns information about the current solution. Information from all model listeners and constraints is also included.
374 * Only variables from the given set are considered.
375 */
376 public java.util.Hashtable getInfo(Vector variables) {
377 java.util.Hashtable ret = new java.util.Hashtable();
378 int assigned = 0, perturb = 0, nrVarsWithInitialValue = 0;
379 for (Enumeration e=variables.elements();e.hasMoreElements();) {
380 Variable variable = (Variable)e.nextElement();
381 if (variable.getAssignment()!=null) assigned++;
382 if (variable.getInitialAssignment()!=null) {
383 nrVarsWithInitialValue++;
384 if (variable.getAssignment()!=null) {
385 if (!variable.getInitialAssignment().equals(variable.getAssignment())) perturb++;
386 } else {
387 boolean hasPerturbance = false;
388 for (Enumeration x=variable.hardConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
389 Constraint constraint = (Constraint)x.nextElement();
390 if (constraint.inConflict(variable.getInitialAssignment()))
391 hasPerturbance=true;
392 }
393 for (Enumeration x=globalConstraints().elements();!hasPerturbance && x.hasMoreElements();) {
394 GlobalConstraint constraint = (GlobalConstraint)x.nextElement();
395 if (constraint.inConflict(variable.getInitialAssignment()))
396 hasPerturbance=true;
397 }
398 if (hasPerturbance) perturb++;
399 }
400 }
401 }
402 ret.put("Assigned variables", getPercRev(assigned,0,variables.size())+"% ("+assigned+"/"+variables.size()+")");
403 if (nrVarsWithInitialValue>0) {
404 ret.put("Perturbation variables", getPercRev(perturb,0,nrVarsWithInitialValue)+"% ("+perturb+" + "+(variables.size()-nrVarsWithInitialValue)+")");
405 }
406 ret.put("Overall solution value", sDoubleFormat.format(getTotalValue(variables)));
407 for (Enumeration e=iInfoProviders.elements();e.hasMoreElements();)
408 ((InfoProvider)e.nextElement()).getInfo(ret, variables);
409 return ret;
410 }
411
412 /** Returns the number of unassigned variables in the best ever found solution */
413 public int getBestUnassignedVariables() { return iBestUnassignedVariables; }
414 /** Returns the number of perturbation variables in the best ever found solution */
415 public int getBestPerturbations() { return iBestPerturbations; }
416 /** Save the current assignment as the best ever found assignment */
417 public void saveBest() {
418 iBestUnassignedVariables = nrUnassignedVariables();//unassignedVariables().size();
419 iBestPerturbations = perturbVariables().size();
420 for (Enumeration e=variables().elements();e.hasMoreElements();) {
421 Variable variable = (Variable)e.nextElement();
422 variable.setBestAssignment(variable.getAssignment());
423 }
424 }
425 /** Clear the best ever found assignment */
426 public void clearBest() {
427 iBestUnassignedVariables = -1;
428 iBestPerturbations = 0;
429 for (Enumeration e=variables().elements();e.hasMoreElements();) {
430 Variable variable = (Variable)e.nextElement();
431 variable.setBestAssignment(null);
432 }
433 }
434 /** Restore the best ever found assignment into the current assignment*/
435 public void restoreBest() {
436 for (Enumeration e=variables().elements();e.hasMoreElements();) {
437 Variable variable = (Variable)e.nextElement();
438 if (variable.getAssignment()!=null && !variable.getAssignment().equals(variable.getBestAssignment()))
439 variable.unassign(0);
440 }
441 HashSet problems = new HashSet();
442 for (Enumeration e=ToolBox.sortEnumeration(variables().elements(), new BestAssignmentComparator());e.hasMoreElements();) {
443 Variable variable = (Variable)e.nextElement();
444 if (variable.getBestAssignment()!=null && variable.getAssignment()==null) {
445 Set confs = conflictValues(variable.getBestAssignment());
446 if (!confs.isEmpty()) {
447 sLogger.error("restore best problem: assignment "+variable.getName()+" = "+variable.getBestAssignment().getName());
448 for (Enumeration en=variable.hardConstraints().elements();en.hasMoreElements();) {
449 Constraint c=(Constraint)en.nextElement();
450 Set x = new HashSet();
451 c.computeConflicts(variable.getBestAssignment(),x);
452 if (!x.isEmpty()) {
453 sLogger.error(" constraint "+c.getClass().getName()+" "+c.getName()+" causes the following conflicts "+x);
454 }
455 }
456 for (Enumeration en=globalConstraints().elements();en.hasMoreElements();) {
457 GlobalConstraint c=(GlobalConstraint)en.nextElement();
458 Set x = new HashSet();
459 c.computeConflicts(variable.getBestAssignment(),x);
460 if (!x.isEmpty()) {
461 sLogger.error(" global constraint "+c.getClass().getName()+" "+c.getName()+" causes the following conflicts "+x);
462 }
463 }
464 problems.add(variable.getBestAssignment());
465 } else variable.assign(0,variable.getBestAssignment());
466 }
467 }
468 int attempt = 0;
469 while (!problems.isEmpty() && attempt<=100) {
470 attempt++;
471 Value value = (Value)ToolBox.random(problems); problems.remove(value);
472 Variable variable = value.variable();
473 Set confs = conflictValues(value);
474 if (!confs.isEmpty()) {
475 sLogger.error("restore best problem (again, att="+attempt+"): assignment "+variable.getName()+" = "+value.getName());
476 for (Enumeration en=variable.hardConstraints().elements();en.hasMoreElements();) {
477 Constraint c=(Constraint)en.nextElement();
478 Set x = new HashSet();
479 c.computeConflicts(value,x);
480 if (!x.isEmpty()) sLogger.error(" constraint "+c.getClass().getName()+" "+c.getName()+" causes the following conflicts "+x);
481 }
482 for (Enumeration en=globalConstraints().elements();en.hasMoreElements();) {
483 GlobalConstraint c=(GlobalConstraint)en.nextElement();
484 Set x = new HashSet();
485 c.computeConflicts(value,x);
486 if (!x.isEmpty()) sLogger.error(" constraint "+c.getClass().getName()+" "+c.getName()+" causes the following conflicts "+x);
487 }
488 for (Iterator i=confs.iterator();i.hasNext();)
489 ((Value)i.next()).variable().unassign(0);
490 problems.addAll(confs);
491 }
492 variable.assign(0,value);
493 }
494 }
495
496 /** The list of unassigned variables in the best ever found solution*/
497 public EnumerableCollection bestUnassignedVariables() {
498 if (iBestUnassignedVariables<0) return unassignedVariables();
499 EnumerableCollection ret = new FastVector(variables().size());
500 for (Enumeration e=variables().elements();e.hasMoreElements();) {
501 Variable variable = (Variable)e.nextElement();
502 if (variable.getBestAssignment()==null) ret.addElement(variable);
503 }
504 return ret;
505 }
506
507 /** Value of the current solution. It is the sum of all assigned values, i.e., {@link Value#toDouble()}.*/
508 public double getTotalValue() {
509 double valCurrent = 0;
510 for (Enumeration e=assignedVariables().elements();e.hasMoreElements();)
511 valCurrent += ((Variable)e.nextElement()).getAssignment().toDouble();
512 return valCurrent;
513 }
514
515 /** Value of the current solution. It is the sum of all assigned values, i.e., {@link Value#toDouble()}.
516 * Only variables from the given set are considered.
517 **/
518 public double getTotalValue(Vector variables) {
519 double valCurrent = 0;
520 for (Enumeration e=variables.elements();e.hasMoreElements();) {
521 Variable variable = (Variable)e.nextElement();
522 if (variable.getAssignment()!=null)
523 valCurrent += variable.getAssignment().toDouble();
524 }
525 return valCurrent;
526 }
527
528 private Vector iModelListeners = new FastVector();
529 /** Adds a model listener */
530 public void addModelListener(ModelListener listener) {
531 iModelListeners.addElement(listener);
532 if (listener instanceof InfoProvider)
533 iInfoProviders.addElement(listener);
534 for (Enumeration e=iConstraints.elements();e.hasMoreElements();)
535 listener.constraintAdded((Constraint)e.nextElement());
536 for (Enumeration e=iVariables.elements();e.hasMoreElements();)
537 listener.variableAdded((Variable)e.nextElement());
538 }
539 /** Removes a model listener */
540 public void removeModelListener(ModelListener listener) {
541 if (listener instanceof InfoProvider)
542 iInfoProviders.removeElement(listener);
543 for (Enumeration e=iVariables.elements();e.hasMoreElements();)
544 listener.variableRemoved((Variable)e.nextElement());
545 for (Enumeration e=iConstraints.elements();e.hasMoreElements();)
546 listener.constraintRemoved((Constraint)e.nextElement());
547 iModelListeners.removeElement(listener);
548 }
549
550 /** Model initialization */
551 public boolean init(Solver solver) {
552 boolean ok = true;
553 for (Enumeration e=iModelListeners.elements();ok && e.hasMoreElements();)
554 ok = ((ModelListener)e.nextElement()).init(solver);
555 return ok;
556 }
557 /** The list of model listeners */
558 public Vector getModelListeners() { return iModelListeners; }
559 /** The list of model listeners that are of the given class*/
560 public ModelListener modelListenerOfType(Class type) {
561 for (Enumeration e=iModelListeners.elements();e.hasMoreElements();) {
562 ModelListener listener = (ModelListener)e.nextElement();
563 if (listener.getClass() == type) return listener;
564 }
565 return null;
566 }
567 /** The list of constraints which are in a conflict with the given value if it is assigned to its variable.
568 * This means the constraints, which adds a value into the set of conflicting values in {@link Constraint#computeConflicts(Value, Set)}.
569 */
570 public Hashtable conflictConstraints(Value value) {
571 Hashtable conflictConstraints = new Hashtable();
572 for (Enumeration c=value.variable().hardConstraints().elements(); c.hasMoreElements();) {
573 Constraint constraint = (Constraint)c.nextElement();
574 HashSet conflicts = new HashSet();
575 constraint.computeConflicts(value, conflicts);
576 if (conflicts!=null && !conflicts.isEmpty()) {
577 conflictConstraints.put(constraint,conflicts);
578 }
579 }
580 for (Enumeration c=globalConstraints().elements(); c.hasMoreElements();) {
581 GlobalConstraint constraint = (GlobalConstraint)c.nextElement();
582 HashSet conflicts = new HashSet();
583 constraint.computeConflicts(value, conflicts);
584 if (conflicts!=null && !conflicts.isEmpty()) {
585 conflictConstraints.put(constraint,conflicts);
586 }
587 }
588 return conflictConstraints;
589 }
590 /** The list of hard constraints which contain at least one variable that is not assigned. */
591 public Vector unassignedHardConstraints() {
592 Vector ret = new FastVector();
593 for (Enumeration c=constraints().elements();c.hasMoreElements();) {
594 Constraint constraint = (Constraint)c.nextElement();
595 if (!constraint.isHard()) continue;
596 boolean assigned = true;
597 for (Enumeration v=constraint.variables().elements();assigned && v.hasMoreElements();)
598 if (((Variable)v.nextElement()).getAssignment()==null) assigned=false;
599 if (!assigned)
600 ret.addElement(constraint);
601 }
602 if (!unassignedVariables().isEmpty())
603 ret.addAll(globalConstraints());
604 return ret;
605 }
606
607 private class BestAssignmentComparator implements Comparator {
608 public int compare(Object o1, Object o2) {
609 Variable v1=(Variable)o1;
610 Variable v2=(Variable)o2;
611 return (int)(v1.getBestAssignmentIteration()-v2.getBestAssignmentIteration());
612 }
613 }
614
615 /** Registered info providers (see {@link InfoProvider}) */
616 protected Vector getInfoProviders() { return iInfoProviders; }
617 }