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