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