001 package net.sf.cpsolver.ifs.model;
002
003 import java.util.ArrayList;
004 import java.util.HashMap;
005 import java.util.List;
006 import java.util.Map;
007
008 import net.sf.cpsolver.ifs.util.IdGenerator;
009
010 /**
011 * Generic variable. <br>
012 * <br>
013 * Besides a domain of values, a variable also contains information about
014 * assigned value, the value assigned in the best ever found solution and also
015 * the initial value (minimal perturbations problem). It also knows what
016 * constraints are associated with this variable and has a unique id.
017 *
018 * @see Value
019 * @see Model
020 * @see net.sf.cpsolver.ifs.solver.Solver
021 *
022 * @version IFS 1.2 (Iterative Forward Search)<br>
023 * Copyright (C) 2006 - 2010 Tomas Muller<br>
024 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
025 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
026 * <br>
027 * This library is free software; you can redistribute it and/or modify
028 * it under the terms of the GNU Lesser General Public License as
029 * published by the Free Software Foundation; either version 3 of the
030 * License, or (at your option) any later version. <br>
031 * <br>
032 * This library is distributed in the hope that it will be useful, but
033 * WITHOUT ANY WARRANTY; without even the implied warranty of
034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
035 * Lesser General Public License for more details. <br>
036 * <br>
037 * You should have received a copy of the GNU Lesser General Public
038 * License along with this library; if not see
039 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
040 */
041 public class Variable<V extends Variable<V, T>, T extends Value<V, T>> implements Comparable<V> {
042 private static IdGenerator iIdGenerator = new IdGenerator();
043
044 protected long iId = -1;
045 private Model<V, T> iModel = null;
046
047 private T iInitialValue = null; // initial value
048 /** Assigned value */
049 protected T iValue = null; // assigned value
050 private T iBestValue = null; // best value
051 private long iBestAssignmentIteration = 0;
052 private List<T> iValues = null;
053
054 private T iRecentlyRemovedValue = null;
055
056 private long iAssignmentCounter = 0;
057 private long iLastAssignmentIteration = -1;
058 private long iLastUnassignmentIteration = -1;
059 private Object iExtra = null;
060
061 private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
062 private List<Constraint<V, T>> iHardConstraints = new ArrayList<Constraint<V, T>>();
063 private List<Constraint<V, T>> iSoftConstraints = new ArrayList<Constraint<V, T>>();
064 private List<VariableListener<T>> iVariableListeners = null;
065
066 private Map<V, List<Constraint<V, T>>> iConstraintVariables = null;
067
068 /** Constructor */
069 public Variable() {
070 this(null);
071 }
072
073 /**
074 * Constructor
075 *
076 * @param initialValue
077 * initial value (minimal-perturbation problem)
078 */
079 public Variable(T initialValue) {
080 iId = iIdGenerator.newId();
081 setInitialAssignment(initialValue);
082 }
083
084 /** Model, the variable belong to */
085 public Model<V, T> getModel() {
086 return iModel;
087 }
088
089 /** Set the model to which the variable belongs to */
090 public void setModel(Model<V, T> model) {
091 iModel = model;
092 }
093
094 /** Domain */
095 public List<T> values() {
096 return iValues;
097 }
098
099 /** Sets the domain */
100 protected void setValues(List<T> values) {
101 iValues = values;
102 }
103
104 /** True, if the variable's domain is not empty */
105 public boolean hasValues() {
106 return !values().isEmpty();
107 }
108
109 /** Returns current assignment */
110 public T getAssignment() {
111 return iValue;
112 }
113
114 /** Returns true if the variable is assigned */
115 public boolean hasAssignment() {
116 return iValue != null;
117 }
118
119 /** Returns initial assignment */
120 public T getInitialAssignment() {
121 return iInitialValue;
122 }
123
124 /** Sets initial assignment */
125 public void setInitialAssignment(T initialValue) {
126 iInitialValue = initialValue;
127 if (iInitialValue != null && iInitialValue.variable() == null)
128 iInitialValue.setVariable(this);
129 if (iModel != null)
130 iModel.invalidateVariablesWithInitialValueCache();
131 }
132
133 /** Returns true if the variable has an initial assignment */
134 public boolean hasInitialAssignment() {
135 return iInitialValue != null;
136 }
137
138 /**
139 * Assign value to this variable. If the variable has already assigned
140 * another value, it is unassigned first. Also, all conflicting values are
141 * unassigned before the given value is assigned to this variable.
142 *
143 * @param iteration
144 * current iteration
145 * @param value
146 * the value to be assigned
147 */
148 public void assign(long iteration, T value) {
149 if (getModel() != null)
150 getModel().beforeAssigned(iteration, value);
151 iLastAssignmentIteration = iteration;
152 if (iValue != null)
153 unassign(iteration);
154 if (iRecentlyRemovedValue != null && iRecentlyRemovedValue.equals(value)) {
155 iRecentlyRemovedValue = null;
156 return;
157 }
158 if (value == null)
159 return;
160 iValue = value;
161 for (Constraint<?, T> constraint : iConstraints) {
162 constraint.assigned(iteration, value);
163 }
164 if (getModel() != null)
165 for (GlobalConstraint<?, T> constraint : getModel().globalConstraints()) {
166 constraint.assigned(iteration, value);
167 }
168 iAssignmentCounter++;
169 value.assigned(iteration);
170 if (iVariableListeners != null)
171 for (VariableListener<T> listener : iVariableListeners) {
172 listener.variableAssigned(iteration, value);
173 }
174 if (getModel() != null)
175 getModel().afterAssigned(iteration, value);
176 }
177
178 /**
179 * Unassign value from this variable.
180 *
181 * @param iteration
182 * current iteration
183 */
184 public void unassign(long iteration) {
185 if (iValue == null)
186 return;
187 if (getModel() != null)
188 getModel().beforeUnassigned(iteration, iValue);
189 iLastUnassignmentIteration = iteration;
190 T oldValue = iValue;
191 iValue = null;
192 for (Constraint<?, T> constraint : iConstraints) {
193 constraint.unassigned(iteration, oldValue);
194 }
195 if (getModel() != null)
196 for (GlobalConstraint<?, T> constraint : getModel().globalConstraints()) {
197 constraint.unassigned(iteration, oldValue);
198 }
199 oldValue.unassigned(iteration);
200 if (iVariableListeners != null)
201 for (VariableListener<T> listener : iVariableListeners)
202 listener.variableUnassigned(iteration, oldValue);
203 if (getModel() != null)
204 getModel().afterUnassigned(iteration, oldValue);
205 }
206
207 /** Return how many times was this variable assigned in the past. */
208 public long countAssignments() {
209 return iAssignmentCounter;
210 }
211
212 /**
213 * Adds a constraint. Called automatically when the constraint is added to
214 * the model, i.e., {@link Model#addConstraint(Constraint)} is called.
215 *
216 * @param constraint
217 * added constraint
218 */
219 public void addContstraint(Constraint<V, T> constraint) {
220 iConstraints.add(constraint);
221 if (constraint.isHard()) {
222 iHardConstraints.add(constraint);
223 iConstraintVariables = null;
224 } else
225 iSoftConstraints.add(constraint);
226 }
227
228 /**
229 * Removes a constraint. Called automatically when the constraint is removed
230 * from the model, i.e., {@link Model#removeConstraint(Constraint)} is
231 * called.
232 *
233 * @param constraint
234 * added constraint
235 */
236 public void removeContstraint(Constraint<V, T> constraint) {
237 iConstraints.remove(constraint);
238 if (iHardConstraints.contains(constraint)) {
239 iHardConstraints.remove(constraint);
240 iConstraintVariables = null;
241 } else
242 iSoftConstraints.remove(constraint);
243 }
244
245 /** Return the list of constraints associated with this variable */
246 public List<Constraint<V, T>> constraints() {
247 return iConstraints;
248 }
249
250 /** Return the list of hard constraints associated with this variable */
251 public List<Constraint<V, T>> hardConstraints() {
252 return iHardConstraints;
253 }
254
255 /** Return the list of soft constraints associated with this variable */
256 public List<Constraint<V, T>> softConstraints() {
257 return iSoftConstraints;
258 }
259
260 @Override
261 public String toString() {
262 return "Variable{name=" + getName() + ", initial=" + getInitialAssignment() + ", current=" + getAssignment()
263 + ", values=" + values().size() + ", constraints=" + iConstraints.size() + "}";
264 }
265
266 /** Unique id */
267 public long getId() {
268 return iId;
269 }
270
271 @Override
272 public int hashCode() {
273 return (int) iId;
274 }
275
276 /** Variable's name -- for printing purposes */
277 public String getName() {
278 return String.valueOf(iId);
279 }
280
281 /** Variable's description -- for printing purposes */
282 public String getDescription() {
283 return null;
284 }
285
286 /**
287 * Sets variable's value of the best ever found solution. Called when
288 * {@link Model#saveBest()} is called.
289 */
290 public void setBestAssignment(T value) {
291 iBestValue = value;
292 iBestAssignmentIteration = (value == null ? 0l : value.lastAssignmentIteration());
293 }
294
295 /** Returns the value from the best ever found soultion. */
296 public T getBestAssignment() {
297 return iBestValue;
298 }
299
300 /** Returns the iteration when the best value was assigned */
301 public long getBestAssignmentIteration() {
302 return iBestAssignmentIteration;
303 }
304
305 /**
306 * Returns the iteration when the variable was assigned for the last time
307 * (-1 if never)
308 */
309 public long lastAssignmentIteration() {
310 return iLastAssignmentIteration;
311 }
312
313 /**
314 * Returns the iteration when the variable was unassigned for the last time
315 * (-1 if never)
316 */
317 public long lastUnassignmentIteration() {
318 return iLastUnassignmentIteration;
319 }
320
321 @Override
322 public int compareTo(V variable) {
323 if (variable == null)
324 return -1;
325 int cmp = getName().compareTo(variable.getName());
326 if (cmp != 0)
327 return cmp;
328 return Double.compare(getId(), variable.getId());
329 }
330
331 @Override
332 public boolean equals(Object o) {
333 if (o == null || !(o instanceof Variable<?, ?>))
334 return false;
335 return getId() == ((Variable<?, ?>) o).getId();
336 }
337
338 /** Adds variable listener */
339 public void addVariableListener(VariableListener<T> listener) {
340 if (iVariableListeners == null)
341 iVariableListeners = new ArrayList<VariableListener<T>>();
342 iVariableListeners.add(listener);
343 }
344
345 /** Removes variable listener */
346 public void removeVariableListener(VariableListener<T> listener) {
347 if (iVariableListeners != null)
348 iVariableListeners.remove(listener);
349 }
350
351 /** Return variable listeners */
352 public List<VariableListener<T>> getVariableListeners() {
353 return iVariableListeners;
354 }
355
356 /**
357 * Extra information to which can be used by an extension (see
358 * {@link net.sf.cpsolver.ifs.extension.Extension}).
359 */
360 public void setExtra(Object object) {
361 iExtra = object;
362 }
363
364 /**
365 * Extra information to which can be used by an extension (see
366 * {@link net.sf.cpsolver.ifs.extension.Extension}).
367 */
368 public Object getExtra() {
369 return iExtra;
370 }
371
372 /** Permanently remove a value from variables domain. */
373 public void removeValue(long iteration, T value) {
374 if (iValue != null && iValue.equals(value))
375 unassign(iteration);
376 if (iValues == null)
377 return;
378 iValues.remove(value);
379 if (iInitialValue != null && iInitialValue.equals(value)) {
380 iInitialValue = null;
381 if (iModel != null)
382 iModel.invalidateVariablesWithInitialValueCache();
383 }
384 if (iVariableListeners != null)
385 for (VariableListener<T> listener : iVariableListeners)
386 listener.valueRemoved(iteration, value);
387 iRecentlyRemovedValue = value;
388 }
389
390 /**
391 * Returns a table of all variables linked with this variable by a
392 * constraint.
393 *
394 * @return table (variable, constraint)
395 */
396 public Map<V, List<Constraint<V, T>>> constraintVariables() {
397 if (iConstraintVariables == null) {
398 iConstraintVariables = new HashMap<V, List<Constraint<V, T>>>();
399 for (Constraint<V, T> constraint : constraints()) {
400 for (V variable : constraint.variables()) {
401 if (!variable.equals(this)) {
402 List<Constraint<V, T>> constraints = iConstraintVariables.get(variable);
403 if (constraints == null) {
404 constraints = new ArrayList<Constraint<V, T>>();
405 iConstraintVariables.put(variable, constraints);
406 }
407 constraints.add(constraint);
408 }
409 }
410 }
411 }
412 return iConstraintVariables;
413 }
414
415 /**
416 * Permanently remove the initial value from the variable's domain -- for
417 * testing MPP
418 */
419 public void removeInitialValue() {
420 if (iInitialValue == null)
421 return;
422 if (iValues == null)
423 return;
424 if (getAssignment() != null && getAssignment().equals(iInitialValue))
425 unassign(0);
426 iValues.remove(iInitialValue);
427 if (iModel != null)
428 iModel.invalidateVariablesWithInitialValueCache();
429 iInitialValue = null;
430 }
431 }