    001package net.sf.cpsolver.ifs.model;
    002
    003import java.util.ArrayList;
    004import java.util.HashMap;
    005import java.util.List;
    006import java.util.Map;
    007
    008import 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 Tomáš Müller<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 */
    041public 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}