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}