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    }