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