001 package net.sf.cpsolver.ifs.model;
002
003 import java.util.*;
004
005 import net.sf.cpsolver.ifs.util.*;
006
007 /**
008 * Generic variable.
009 * <br><br>
010 * Besides a domain of values, a variable also contains information about assigned value,
011 * the value assigned in the best ever found solution and also the initial value (minimal
012 * perturbations problem). It also knows what constraints are associated with this variable and
013 * has a unique id.
014 *
015 * @see Value
016 * @see Model
017 * @see net.sf.cpsolver.ifs.solver.Solver
018 *
019 * @version
020 * IFS 1.1 (Iterative Forward Search)<br>
021 * Copyright (C) 2006 Tomáš Müller<br>
022 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
023 * Lazenska 391, 76314 Zlin, Czech Republic<br>
024 * <br>
025 * This library is free software; you can redistribute it and/or
026 * modify it under the terms of the GNU Lesser General Public
027 * License as published by the Free Software Foundation; either
028 * version 2.1 of the License, or (at your option) any later version.
029 * <br><br>
030 * This library is distributed in the hope that it will be useful,
031 * but WITHOUT ANY WARRANTY; without even the implied warranty of
032 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
033 * Lesser General Public License for more details.
034 * <br><br>
035 * You should have received a copy of the GNU Lesser General Public
036 * License along with this library; if not, write to the Free Software
037 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
038 */
039 public class Variable implements Comparable {
040 private static IdGenerator iIdGenerator = new IdGenerator();
041
042 protected long iId = -1;
043 private Model iModel = null;
044
045 private Value iInitialValue = null; // initial value
046 /** Assigned value */
047 protected Value iValue = null; // assigned value
048 private Value iBestValue = null; // best value
049 private long iBestAssignmentIteration = 0;
050 private Vector iValues = null;
051
052 private Value iRecentlyRemovedValue = null;
053
054 private long iAssignmentCounter = 0;
055 private long iLastAssignmentIteration = -1;
056 private long iLastUnassignmentIteration = -1;
057 private Object iExtra = null;
058
059 private Vector iConstraints = new FastVector();
060 private Vector iHardConstraints = new FastVector();
061 private Vector iSoftConstraints = new FastVector();
062 private Vector iVariableListeners = null;
063
064 private Hashtable iConstraintVariables = null;
065
066 /** Constructor */
067 public Variable() {
068 this(null);
069 }
070
071 /** Constructor
072 * @param initialValue initial value (minimal-perturbation problem)
073 */
074 public Variable(Value initialValue) {
075 iId = iIdGenerator.newId();
076 setInitialAssignment(initialValue);
077 }
078
079 /** Model, the variable belong to */
080 public Model getModel() { return iModel; }
081 /** Set the model to which the variable belongs to */
082 public void setModel(Model model) { iModel = model; }
083
084 /** Domain */
085 public Vector values() {
086 return iValues;
087 }
088 /** Sets the domain */
089 protected void setValues(Vector values) {
090 iValues = values;
091 }
092 /** True, if the variable's domain is not empty */
093 public boolean hasValues() {
094 return !values().isEmpty();
095 }
096
097 /** Returns current assignment */
098 public Value getAssignment() { return iValue; }
099 /** Returns true if the variable is assigned */
100 public boolean hasAssignment() { return iValue!=null; }
101 /** Returns initial assignment */
102 public Value getInitialAssignment() { return iInitialValue; }
103 /** Sets initial assignment */
104 public void setInitialAssignment(Value initialValue) {
105 iInitialValue = initialValue;
106 if (iInitialValue!=null && iInitialValue.variable()==null) iInitialValue.setVariable(this);
107 if (iModel!=null)
108 iModel.invalidateVariablesWithInitialValueCache();
109 }
110 /** Returns true if the variable has an initial assignment */
111 public boolean hasInitialAssignment() { return iInitialValue!=null; }
112
113 /** Assign value to this variable. If the variable has already assigned another value, it is
114 * unassigned first. Also, all conflicting values are unassigned before the given value is assigned
115 * to this variable.
116 * @param iteration current iteration
117 * @param value the value to be assigned
118 */
119 public void assign(long iteration, Value value) {
120 if (getModel()!=null)
121 getModel().beforeAssigned(iteration,value);
122 iLastAssignmentIteration = iteration;
123 if (iValue!=null) unassign(iteration);
124 if (iRecentlyRemovedValue!=null && iRecentlyRemovedValue.equals(value)) {
125 iRecentlyRemovedValue = null;
126 return;
127 }
128 if (value==null) return;
129 iValue = value;
130 for (Enumeration e=iConstraints.elements(); e.hasMoreElements();) {
131 Constraint constraint = (Constraint)e.nextElement();
132 constraint.assigned(iteration, value);
133 }
134 if (getModel()!=null)
135 for (Enumeration e=getModel().globalConstraints().elements(); e.hasMoreElements();) {
136 Constraint constraint = (Constraint)e.nextElement();
137 constraint.assigned(iteration, value);
138 }
139 iAssignmentCounter++;
140 value.assigned(iteration);
141 if (iVariableListeners!=null)
142 for (Enumeration e=iVariableListeners.elements(); e.hasMoreElements();)
143 ((VariableListener)e.nextElement()).variableAssigned(iteration, value);
144 if (getModel()!=null)
145 getModel().afterAssigned(iteration,value);
146 }
147
148 /** Unassign value from this variable.
149 * @param iteration current iteration
150 */
151 public void unassign(long iteration) {
152 if (iValue==null) return;
153 if (getModel()!=null)
154 getModel().beforeUnassigned(iteration,iValue);
155 iLastUnassignmentIteration = iteration;
156 Value oldValue = iValue;
157 iValue = null;
158 for (Enumeration e=iConstraints.elements(); e.hasMoreElements();) {
159 Constraint constraint = (Constraint)e.nextElement();
160 constraint.unassigned(iteration, oldValue);
161 }
162 if (getModel()!=null)
163 for (Enumeration e=getModel().globalConstraints().elements(); e.hasMoreElements();) {
164 Constraint constraint = (Constraint)e.nextElement();
165 constraint.unassigned(iteration, oldValue);
166 }
167 oldValue.unassigned(iteration);
168 if (iVariableListeners!=null)
169 for (Enumeration e=iVariableListeners.elements(); e.hasMoreElements();)
170 ((VariableListener)e.nextElement()).variableUnassigned(iteration, oldValue);
171 if (getModel()!=null)
172 getModel().afterUnassigned(iteration,oldValue);
173 }
174 /** Return how many times was this variable assigned in the past. */
175 public long countAssignments() { return iAssignmentCounter; }
176
177 /** Adds a constraint. Called automatically when the constraint is added to the model, i.e.,
178 * {@link Model#addConstraint(Constraint)} is called.
179 * @param constraint added constraint
180 */
181 public void addContstraint(Constraint constraint) {
182 iConstraints.addElement(constraint);
183 if (constraint.isHard()) {
184 iHardConstraints.addElement(constraint);
185 iConstraintVariables = null;
186 } else iSoftConstraints.addElement(constraint);
187 }
188
189 /** Removes a constraint. Called automatically when the constraint is removed from the model, i.e.,
190 * {@link Model#removeConstraint(Constraint)} is called.
191 * @param constraint added constraint
192 */
193 public void removeContstraint(Constraint constraint) {
194 iConstraints.removeElement(constraint);
195 if (iHardConstraints.contains(constraint)) {
196 iHardConstraints.removeElement(constraint);
197 iConstraintVariables = null;
198 } else iSoftConstraints.removeElement(constraint);
199 }
200
201 /** Return the list of constraints associated with this variable */
202 public Vector constraints() { return iConstraints; }
203 /** Return the list of hard constraints associated with this variable */
204 public Vector hardConstraints() { return iHardConstraints; }
205 /** Return the list of soft constraints associated with this variable */
206 public Vector softConstraints() { return iSoftConstraints; }
207
208 public String toString() {
209 return "Variable{name="+getName()+", initial="+getInitialAssignment()+", current="+getAssignment()+", values="+values().size()+", constraints="+iConstraints.size()+"}";
210 }
211
212 /** Unique id */
213 public long getId() { return iId;}
214
215 public int hashCode() { return (int)iId; }
216 /** Variable's name -- for printing purposes */
217 public String getName() { return String.valueOf(iId); }
218 /** Variable's description -- for printing purposes */
219 public String getDescription() { return null; }
220
221 /** Sets variable's value of the best ever found solution. Called when {@link Model#saveBest()} is called. */
222 public void setBestAssignment(Value value) { iBestValue = value; iBestAssignmentIteration = (value==null?0l:value.lastAssignmentIteration()); }
223 /** Returns the value from the best ever found soultion. */
224 public Value getBestAssignment() { return iBestValue; }
225 /** Returns the iteration when the best value was assigned */
226 public long getBestAssignmentIteration() { return iBestAssignmentIteration; }
227
228 /** Returns the iteration when the variable was assigned for the last time (-1 if never) */
229 public long lastAssignmentIteration() { return iLastAssignmentIteration; }
230 /** Returns the iteration when the variable was unassigned for the last time (-1 if never) */
231 public long lastUnassignmentIteration() { return iLastUnassignmentIteration; }
232
233 public int compareTo(Object o) {
234 if (o==null || !(o instanceof Variable)) return -1;
235 Variable v = (Variable)o;
236 return getName().compareTo(v.getName());
237 }
238
239 public boolean equals(Object o) {
240 try {
241 if (o==null) return false;
242 Variable v = (Variable)o;
243 return getId()==v.getId();
244 } catch (Exception e) {
245 return false;
246 }
247 }
248
249 /** Adds variable listener */
250 public void addVariableListener(VariableListener listener) {
251 if (iVariableListeners==null) iVariableListeners=new FastVector();
252 iVariableListeners.addElement(listener);
253 }
254 /** Removes variable listener */
255 public void removeVariableListener(VariableListener listener) {
256 if (iVariableListeners==null) iVariableListeners=new FastVector();
257 iVariableListeners.removeElement(listener);
258 }
259 /** Return variable listeners */
260 public Vector getVariableListeners() { return iVariableListeners; }
261
262 /** Extra information to which can be used by an extension (see {@link net.sf.cpsolver.ifs.extension.Extension}). */
263 public void setExtra(Object object) { iExtra = object; }
264 /** Extra information to which can be used by an extension (see {@link net.sf.cpsolver.ifs.extension.Extension}). */
265 public Object getExtra() { return iExtra; }
266
267 /** Permanently remove a value from variables domain. */
268 public void removeValue(long iteration, Value value) {
269 if (iValue!=null && iValue.equals(value)) unassign(iteration);
270 if (iValues==null) return;
271 iValues.remove(value);
272 if (iInitialValue!=null && iInitialValue.equals(value)) {
273 iInitialValue=null;
274 if (iModel!=null) iModel.invalidateVariablesWithInitialValueCache();
275 }
276 if (iVariableListeners!=null)
277 for (Enumeration e=iVariableListeners.elements(); e.hasMoreElements();)
278 ((VariableListener)e.nextElement()).valueRemoved(iteration, value);
279 iRecentlyRemovedValue = value;
280 }
281
282 /** Returns a table of all variables linked with this variable by a constraint.
283 * @return table (variable, constraint)
284 */
285 public Hashtable constraintVariables() {
286 if (iConstraintVariables == null) {
287 iConstraintVariables = new Hashtable();
288 for (Enumeration e1=constraints().elements();e1.hasMoreElements();) {
289 Constraint constraint = (Constraint)e1.nextElement();
290 for (Enumeration e2=constraint.variables().elements();e2.hasMoreElements();) {
291 Variable variable = (Variable)e2.nextElement();
292 if (!variable.equals(this)) {
293 Vector constraints = (Vector)iConstraintVariables.get(variable);
294 if (constraints==null) {
295 constraints = new FastVector(1,10);
296 iConstraintVariables.put(variable, constraints);
297 }
298 constraints.add(constraint);
299 }
300 }
301 }
302 }
303 return iConstraintVariables;
304 }
305
306 /** Permanently remove the initial value from the variable's domain -- for testing MPP */
307 public void removeInitialValue() {
308 if (iInitialValue==null) return;
309 if (iValues==null) return;
310 if (getAssignment()!=null && getAssignment().equals(iInitialValue)) unassign(0);
311 iValues.remove(iInitialValue);
312 if (iModel!=null)
313 iModel.invalidateVariablesWithInitialValueCache();
314 iInitialValue=null;
315 }
316 }