001package org.cpsolver.ifs.model; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.List; 006import java.util.Map; 007 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.assignment.DefaultParallelAssignment; 010import org.cpsolver.ifs.assignment.DefaultSingleAssignment; 011import org.cpsolver.ifs.assignment.EmptyAssignment; 012import org.cpsolver.ifs.util.IdGenerator; 013 014 015/** 016 * Generic variable. <br> 017 * <br> 018 * Besides a domain of values, a variable also contains information about 019 * assigned value, the value assigned in the best ever found solution and also 020 * the initial value (minimal perturbations problem). It also knows what 021 * constraints are associated with this variable and has a unique id. 022 * 023 * @see Value 024 * @see Model 025 * @see org.cpsolver.ifs.solver.Solver 026 * 027 * @version IFS 1.3 (Iterative Forward Search)<br> 028 * Copyright (C) 2006 - 2014 Tomas Muller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 * 046 * @param <V> Variable 047 * @param <T> Value 048 */ 049public class Variable<V extends Variable<V, T>, T extends Value<V, T>> implements Comparable<V> { 050 private static IdGenerator iIdGenerator = new IdGenerator(); 051 052 protected long iId = -1; 053 private Model<V, T> iModel = null; 054 055 private T iInitialValue = null; // initial value 056 /** Assigned value */ 057 protected T iValue = null; // assigned value 058 private T[] iAssignedValues = null; // assigned values 059 private T iBestValue = null; // best value 060 private long iBestAssignmentIteration = 0; 061 private List<T> iValues = null; 062 063 private T iRecentlyRemovedValue = null; 064 private long iLastIteration = 0; 065 private Object iExtra = null; 066 067 private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>(); 068 private List<Constraint<V, T>> iHardConstraints = new ArrayList<Constraint<V, T>>(); 069 private List<Constraint<V, T>> iSoftConstraints = new ArrayList<Constraint<V, T>>(); 070 private List<VariableListener<T>> iVariableListeners = null; 071 072 private Map<V, List<Constraint<V, T>>> iConstraintVariables = null; 073 protected int iIndex = -1; 074 075 /** Constructor */ 076 public Variable() { 077 this(null); 078 } 079 080 /** 081 * Constructor 082 * 083 * @param initialValue 084 * initial value (minimal-perturbation problem) 085 */ 086 public Variable(T initialValue) { 087 iId = iIdGenerator.newId(); 088 setInitialAssignment(initialValue); 089 } 090 091 /** Model, the variable belong to 092 * @return problem model 093 **/ 094 public Model<V, T> getModel() { 095 return iModel; 096 } 097 098 /** Set the model to which the variable belongs to 099 * @param model problem model 100 **/ 101 public void setModel(Model<V, T> model) { 102 iModel = model; 103 } 104 105 /** Variable's domain, use {@link Variable#values(Assignment)} instead. 106 * @return all possible values of this variable 107 **/ 108 @Deprecated 109 public List<T> values() { 110 return values(new EmptyAssignment<V, T>()); 111 } 112 113 /** Variable's domain 114 * @param assignment current assignment (if the domain is dependent on the current assignment) 115 * @return all possible values of this variable 116 **/ 117 public List<T> values(Assignment<V, T> assignment) { 118 return iValues; 119 } 120 121 /** Sets the domain 122 * @param values variable's domain to cache 123 **/ 124 protected void setValues(List<T> values) { 125 iValues = values; 126 } 127 128 /** True, if the variable's domain is not empty 129 * @return true if there is at least one value in the domain 130 **/ 131 @Deprecated 132 public boolean hasValues() { 133 return !values().isEmpty(); 134 } 135 136 /** 137 * Returns current assignment. 138 * Use {@link Assignment#getValue(Variable)} or {@link Variable#getAssignment(Assignment)} instead. 139 * @return currently assigned value 140 **/ 141 @Deprecated 142 public T getAssignment() { 143 return iValue; 144 } 145 146 /** 147 * Returns true if the variable is assigned. 148 * Use {@link Variable#hasAssignment(Assignment)} instead. 149 * @return true if currently assigned 150 **/ 151 @Deprecated 152 public boolean hasAssignment() { 153 return iValue != null; 154 } 155 156 /** Returns current assignment 157 * @param assignment current assignment 158 * @return currently assigned value 159 **/ 160 @SuppressWarnings("unchecked") 161 public T getAssignment(Assignment<V, T> assignment) { 162 return assignment.getValue((V) this); 163 } 164 165 /** Returns true if the variable is assigned 166 * @param assignment current assignment 167 * @return true if currently assigned 168 **/ 169 public boolean hasAssignment(Assignment<V, T> assignment) { 170 return getAssignment(assignment) != null; 171 } 172 173 /** 174 * Sets current assignment. 175 * BEWARE: Do not use outside of {@link DefaultSingleAssignment}. 176 * @param value current assignment 177 **/ 178 @Deprecated 179 public void setAssignment(T value) { 180 iValue = value; 181 } 182 183 /** 184 * Returns current assignments. 185 * BEWARE: Do not use outside of {@link DefaultParallelAssignment}. 186 * @return currently assigned values 187 **/ 188 @Deprecated 189 public T[] getAssignments() { 190 return iAssignedValues; 191 } 192 193 /** 194 * Sets current assignments. 195 * BEWARE: Do not use outside of {@link DefaultParallelAssignment}. 196 * @param values currently assigned values 197 **/ 198 @Deprecated 199 public void setAssignments(T[] values) { 200 iAssignedValues = values; 201 } 202 203 /** Returns initial assignment 204 * @return initial assignment (for the minimal perturbation problem) 205 **/ 206 public T getInitialAssignment() { 207 return iInitialValue; 208 } 209 210 /** Sets initial assignment 211 * @param initialValue initial assignment 212 **/ 213 public void setInitialAssignment(T initialValue) { 214 iInitialValue = initialValue; 215 if (iInitialValue != null && iInitialValue.variable() == null) 216 iInitialValue.setVariable(this); 217 if (iModel != null) 218 iModel.invalidateVariablesWithInitialValueCache(); 219 } 220 221 /** Returns true if the variable has an initial assignment 222 * @return true if this variable has an initial assignment 223 **/ 224 public boolean hasInitialAssignment() { 225 return iInitialValue != null; 226 } 227 228 /** 229 * Assign value to this variable. If the variable has already assigned 230 * another value, it is unassigned first. Also, all conflicting values are 231 * unassigned before the given value is assigned to this variable. 232 * Use {@link Assignment#assign(long, Value)} instead. 233 * 234 * @param iteration 235 * current iteration 236 * @param value 237 * the value to be assigned 238 */ 239 @Deprecated 240 public void assign(int iteration, T value) { 241 if (iRecentlyRemovedValue != null && iRecentlyRemovedValue.equals(value)) { 242 iRecentlyRemovedValue = null; 243 return; 244 } 245 getModel().getDefaultAssignment().assign(iteration, value); 246 } 247 248 /** 249 * Unassign value from this variable. 250 * Use {@link Assignment#unassign(long, Variable)} instead. 251 * 252 * @param iteration 253 * current iteration 254 */ 255 @Deprecated 256 @SuppressWarnings("unchecked") 257 public void unassign(int iteration) { 258 getModel().getDefaultAssignment().unassign(iteration, (V) this); 259 } 260 261 262 /** 263 * Returns iteration of the last assignment. 264 * Use {@link Assignment#getIteration(Variable)} instead. 265 * @return iteration of the last assignment 266 **/ 267 @Deprecated 268 public long getLastIteration() { 269 return iLastIteration; 270 } 271 272 /** 273 * Sets iteration of the last assignment. 274 * BEWARE: Do not use outside of {@link DefaultSingleAssignment}. 275 * @param iteration current iteration 276 **/ 277 @Deprecated 278 public void setLastIteration(long iteration) { 279 iLastIteration = iteration; 280 } 281 282 /** 283 * A value was assigned to this variable 284 * @param assignment current assignment 285 * @param iteration current iteration 286 * @param value assigned value 287 */ 288 public void variableAssigned(Assignment<V, T> assignment, long iteration, T value) { 289 if (iVariableListeners != null) 290 for (VariableListener<T> listener : iVariableListeners) { 291 listener.variableAssigned(assignment, iteration, value); 292 } 293 } 294 295 /** 296 * A value was unassigned from this variable 297 * @param assignment current assignment 298 * @param iteration current iteration 299 * @param oldValue unassigned value 300 */ 301 public void variableUnassigned(Assignment<V, T> assignment, long iteration, T oldValue) { 302 if (iVariableListeners != null) 303 for (VariableListener<T> listener : iVariableListeners) 304 listener.variableUnassigned(assignment, iteration, oldValue); 305 } 306 307 /** 308 * Adds a constraint. Called automatically when the constraint is added to 309 * the model, i.e., {@link Model#addConstraint(Constraint)} is called. 310 * 311 * @param constraint 312 * added constraint 313 */ 314 public void addContstraint(Constraint<V, T> constraint) { 315 iConstraints.add(constraint); 316 if (constraint.isHard()) { 317 iHardConstraints.add(constraint); 318 iConstraintVariables = null; 319 } else 320 iSoftConstraints.add(constraint); 321 } 322 323 /** 324 * Removes a constraint. Called automatically when the constraint is removed 325 * from the model, i.e., {@link Model#removeConstraint(Constraint)} is 326 * called. 327 * 328 * @param constraint 329 * added constraint 330 */ 331 public void removeContstraint(Constraint<V, T> constraint) { 332 iConstraints.remove(constraint); 333 if (iHardConstraints.contains(constraint)) { 334 iHardConstraints.remove(constraint); 335 iConstraintVariables = null; 336 } else 337 iSoftConstraints.remove(constraint); 338 } 339 340 /** Return the list of constraints associated with this variable 341 * @return list of constraints associated with this variable 342 **/ 343 public List<Constraint<V, T>> constraints() { 344 return iConstraints; 345 } 346 347 /** Return the list of hard constraints associated with this variable 348 * @return list of hard constraints associated with this variable 349 **/ 350 public List<Constraint<V, T>> hardConstraints() { 351 return iHardConstraints; 352 } 353 354 /** Return the list of soft constraints associated with this variable 355 * @return list of soft (not hard) constraints associated with this variable 356 **/ 357 public List<Constraint<V, T>> softConstraints() { 358 return iSoftConstraints; 359 } 360 361 @Override 362 public String toString() { 363 return "Variable{name=" + getName() + ", initial=" + getInitialAssignment() + ", values=" + values(null).size() + ", constraints=" + iConstraints.size() + "}"; 364 } 365 366 /** Unique id 367 * @return variable id 368 **/ 369 public long getId() { 370 return iId; 371 } 372 373 @Override 374 public int hashCode() { 375 return (int) iId; 376 } 377 378 /** Variable's name -- for printing purposes 379 * @return variable name 380 **/ 381 public String getName() { 382 return String.valueOf(iId); 383 } 384 385 /** Variable's description -- for printing purposes 386 * @return variable description 387 **/ 388 public String getDescription() { 389 return null; 390 } 391 392 /** 393 * Sets variable's value of the best ever found solution. Called when 394 * {@link Model#saveBest(Assignment)} is called. 395 * @param value a value 396 * @param iteration value's assignment iteration 397 */ 398 public void setBestAssignment(T value, long iteration) { 399 iBestValue = value; 400 iBestAssignmentIteration = iteration; 401 } 402 403 /** Returns the value from the best ever found solution. 404 * @return best assignment 405 **/ 406 public T getBestAssignment() { 407 return iBestValue; 408 } 409 410 /** Returns the iteration when the best value was assigned 411 * @return iteration of the best assignment 412 **/ 413 public long getBestAssignmentIteration() { 414 return iBestAssignmentIteration; 415 } 416 417 @Override 418 public int compareTo(V variable) { 419 if (variable == null) 420 return -1; 421 int cmp = getName().compareTo(variable.getName()); 422 if (cmp != 0) 423 return cmp; 424 return Double.compare(getId(), variable.getId()); 425 } 426 427 @Override 428 public boolean equals(Object o) { 429 if (o == null || !(o instanceof Variable<?, ?>)) 430 return false; 431 return getId() == ((Variable<?, ?>) o).getId(); 432 } 433 434 /** Adds variable listener 435 * @param listener a variable listener 436 **/ 437 public void addVariableListener(VariableListener<T> listener) { 438 if (iVariableListeners == null) 439 iVariableListeners = new ArrayList<VariableListener<T>>(); 440 iVariableListeners.add(listener); 441 } 442 443 /** Removes variable listener 444 * @param listener a variable listener 445 **/ 446 public void removeVariableListener(VariableListener<T> listener) { 447 if (iVariableListeners != null) 448 iVariableListeners.remove(listener); 449 } 450 451 /** Return variable listeners 452 * @return list of variable listeners 453 **/ 454 public List<VariableListener<T>> getVariableListeners() { 455 return iVariableListeners; 456 } 457 458 /** 459 * Extra information to which can be used by an extension (see 460 * {@link org.cpsolver.ifs.extension.Extension}). 461 * @param object extra object 462 */ 463 public <X> void setExtra(X object) { 464 iExtra = object; 465 } 466 467 /** 468 * Extra information to which can be used by an extension (see 469 * {@link org.cpsolver.ifs.extension.Extension}). 470 * @return extra object 471 */ 472 @SuppressWarnings("unchecked") 473 public <X> X getExtra() { 474 try { 475 return (X) iExtra; 476 } catch (ClassCastException e) { 477 return null; 478 } 479 } 480 481 /** 482 * Permanently remove a value from variable's domain. 483 * The variable should not have this value assigned in any existing assignment. 484 * @param iteration current iteration 485 * @param value value to be removed from this variable's domain 486 **/ 487 @SuppressWarnings({ "deprecation", "unchecked" }) 488 public void removeValue(long iteration, T value) { 489 if (value.equals(getModel().getDefaultAssignment().getValue((V) this))) 490 getModel().getDefaultAssignment().unassign(iteration, (V) this); 491 if (iValues == null) 492 return; 493 iValues.remove(value); 494 if (iInitialValue != null && iInitialValue.equals(value)) { 495 iInitialValue = null; 496 if (iModel != null) 497 iModel.invalidateVariablesWithInitialValueCache(); 498 } 499 if (iVariableListeners != null) 500 for (VariableListener<T> listener : iVariableListeners) 501 listener.valueRemoved(iteration, value); 502 iRecentlyRemovedValue = value; 503 } 504 505 /** 506 * Returns a table of all variables linked with this variable by a 507 * constraint. 508 * 509 * @return table (variable, constraint) 510 */ 511 public Map<V, List<Constraint<V, T>>> constraintVariables() { 512 if (iConstraintVariables == null) { 513 iConstraintVariables = new HashMap<V, List<Constraint<V, T>>>(); 514 for (Constraint<V, T> constraint : constraints()) { 515 for (V variable : constraint.variables()) { 516 if (!variable.equals(this)) { 517 List<Constraint<V, T>> constraints = iConstraintVariables.get(variable); 518 if (constraints == null) { 519 constraints = new ArrayList<Constraint<V, T>>(); 520 iConstraintVariables.put(variable, constraints); 521 } 522 constraints.add(constraint); 523 } 524 } 525 } 526 } 527 return iConstraintVariables; 528 } 529 530 /** 531 * Permanently remove the initial value from the variable's domain -- for 532 * testing MPP 533 */ 534 public void removeInitialValue() { 535 if (iInitialValue == null) 536 return; 537 if (iValues == null) 538 return; 539 iValues.remove(iInitialValue); 540 if (iModel != null) 541 iModel.invalidateVariablesWithInitialValueCache(); 542 iInitialValue = null; 543 } 544 545 /** 546 * Unique index of a variable, only to be assigned by {@link Model#addVariable(Variable)}. 547 * @param index an index 548 */ 549 public void setIndex(int index) { iIndex = index; } 550 551 /** 552 * Unique index of a variable that was assigned by {@link Model#addVariable(Variable)}. 553 * @return -1 if not in a model 554 */ 555 public int getIndex() { return iIndex; } 556}