    001package org.cpsolver.ifs.model;
    002
    003import java.lang.reflect.Array;
    004import java.util.ArrayList;
    005import java.util.HashMap;
    006import java.util.List;
    007import java.util.Map;
    008
    009import org.cpsolver.ifs.assignment.Assignment;
    010import org.cpsolver.ifs.assignment.DefaultParallelAssignment;
    011import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
    012import org.cpsolver.ifs.assignment.EmptyAssignment;
    013import org.cpsolver.ifs.assignment.context.CanHoldContext;
    014import org.cpsolver.ifs.util.IdGenerator;
    015
    016
    017/**
    018 * Generic variable. <br>
    019 * <br>
    020 * Besides a domain of values, a variable also contains information about
    021 * assigned value, the value assigned in the best ever found solution and also
    022 * the initial value (minimal perturbations problem). It also knows what
    023 * constraints are associated with this variable and has a unique id.
    024 *
    025 * @see Value
    026 * @see Model
    027 * @see org.cpsolver.ifs.solver.Solver
    028 *
    029 * @version IFS 1.3 (Iterative Forward Search)<br>
    030 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    031 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    032 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    033 * <br>
    034 *          This library is free software; you can redistribute it and/or modify
    035 *          it under the terms of the GNU Lesser General Public License as
    036 *          published by the Free Software Foundation; either version 3 of the
    037 *          License, or (at your option) any later version. <br>
    038 * <br>
    039 *          This library is distributed in the hope that it will be useful, but
    040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    042 *          Lesser General Public License for more details. <br>
    043 * <br>
    044 *          You should have received a copy of the GNU Lesser General Public
    045 *          License along with this library; if not see
    046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    047 *
    048 * @param <V> Variable
    049 * @param <T> Value
    050 */
    051public class Variable<V extends Variable<V, T>, T extends Value<V, T>> implements Comparable<V> {
    052    private static IdGenerator iIdGenerator = new IdGenerator();
    053
    054    protected long iId = -1;
    055    private Model<V, T> iModel = null;
    056
    057    private T iInitialValue = null; // initial value
    058    /** Assigned value */
    059    protected T iValue = null; // assigned value
    060    @SuppressWarnings("unchecked")
    061    private Value<V, T>[] iAssignedValues = (Value<V, T>[])Array.newInstance(Value.class, CanHoldContext.sMaxSize); // assigned values
    062    private T iBestValue = null; // best value
    063    private long iBestAssignmentIteration = 0;
    064    private List<T> iValues = null;
    065
    066    private T iRecentlyRemovedValue = null;
    067    private long iLastIteration = 0;
    068    private Object iExtra = null;
    069
    070    private List<Constraint<V, T>> iConstraints = new ArrayList<Constraint<V, T>>();
    071    private List<Constraint<V, T>> iHardConstraints = new ArrayList<Constraint<V, T>>();
    072    private List<Constraint<V, T>> iSoftConstraints = new ArrayList<Constraint<V, T>>();
    073    private List<VariableListener<T>> iVariableListeners = null;
    074
    075    private Map<V, List<Constraint<V, T>>> iConstraintVariables = null;
    076    protected int iIndex = -1;
    077
    078    /** Constructor */
    079    public Variable() {
    080        this(null);
    081    }
    082
    083    /**
    084     * Constructor
    085     *
    086     * @param initialValue
    087     *            initial value (minimal-perturbation problem)
    088     */
    089    public Variable(T initialValue) {
    090        iId = iIdGenerator.newId();
    091        setInitialAssignment(initialValue);
    092    }
    093
    094    /** Model, the variable belong to
    095     * @return problem model
    096     **/
    097    public Model<V, T> getModel() {
    098        return iModel;
    099    }
    100
    101    /** Set the model to which the variable belongs to
    102     * @param model problem model
    103     **/
    104    public void setModel(Model<V, T> model) {
    105        iModel = model;
    106    }
    107
    108    /** Variable's domain, use {@link Variable#values(Assignment)} instead.
    109     * @return all possible values of this variable
    110     **/
    111    @Deprecated
    112    public List<T> values() {
    113        return values(new EmptyAssignment<V, T>());
    114    }
    115
    116    /** Variable's domain
    117     * @param assignment current assignment (if the domain is dependent on the current assignment)
    118     * @return all possible values of this variable
    119     **/
    120    public List<T> values(Assignment<V, T> assignment) {
    121        return iValues;
    122    }
    123
    124    /** Sets the domain
    125     * @param values variable's domain to cache
    126     **/
    127    protected void setValues(List<T> values) {
    128        iValues = values;
    129    }
    130
    131    /** True, if the variable's domain is not empty
    132     * @return true if there is at least one value in the domain
    133     **/
    134    @Deprecated
    135    public boolean hasValues() {
    136        return !values().isEmpty();
    137    }
    138
    139    /**
    140     * Returns current assignment.
    141     * Use {@link Assignment#getValue(Variable)} or {@link Variable#getAssignment(Assignment)} instead.
    142     * @return currently assigned value
    143     **/
    144    @Deprecated
    145    public T getAssignment() {
    146        return iValue;
    147    }
    148
    149    /**
    150     * Returns true if the variable is assigned.
    151     * Use {@link Variable#hasAssignment(Assignment)} instead.
    152     * @return true if currently assigned
    153     **/
    154    @Deprecated
    155    public boolean hasAssignment() {
    156        return iValue != null;
    157    }
    158
    159    /** Returns current assignment
    160     * @param assignment current assignment
    161     * @return currently assigned value
    162     **/
    163    @SuppressWarnings("unchecked")
    164    public T getAssignment(Assignment<V, T> assignment) {
    165        return assignment.getValue((V) this);
    166    }
    167
    168    /** Returns true if the variable is assigned
    169     * @param assignment current assignment
    170     * @return true if currently assigned
    171     **/
    172    public boolean hasAssignment(Assignment<V, T> assignment) {
    173        return getAssignment(assignment) != null;
    174    }
    175
    176    /**
    177     * Sets current assignment.
    178     * BEWARE: Do not use outside of {@link DefaultSingleAssignment}.
    179     * @param value current assignment
    180     **/
    181    @Deprecated
    182    public void setAssignment(T value) {
    183        iValue = value;
    184    }
    185
    186    /**
    187     * Returns current assignments.
    188     * BEWARE: Do not use outside of {@link DefaultParallelAssignment}.
    189     * @return currently assigned values
    190     **/
    191    @Deprecated
    192    public Value<V, T>[] getAssignments() {
    193        return iAssignedValues;
    194    }
    195
    196    /** Returns initial assignment
    197     * @return initial assignment (for the minimal perturbation problem)
    198     **/
    199    public T getInitialAssignment() {
    200        return iInitialValue;
    201    }
    202
    203    /** Sets initial assignment
    204     * @param initialValue initial assignment
    205     **/
    206    public void setInitialAssignment(T initialValue) {
    207        iInitialValue = initialValue;
    208        if (iInitialValue != null && iInitialValue.variable() == null)
    209            iInitialValue.setVariable(this);
    210        if (iModel != null)
    211            iModel.invalidateVariablesWithInitialValueCache();
    212    }
    213
    214    /** Returns true if the variable has an initial assignment
    215     * @return true if this variable has an initial assignment
    216     **/
    217    public boolean hasInitialAssignment() {
    218        return iInitialValue != null;
    219    }
    220
    221    /**
    222     * Assign value to this variable. If the variable has already assigned
    223     * another value, it is unassigned first. Also, all conflicting values are
    224     * unassigned before the given value is assigned to this variable.
    225     * Use {@link Assignment#assign(long, Value)} instead.
    226     *
    227     * @param iteration
    228     *            current iteration
    229     * @param value
    230     *            the value to be assigned
    231     */
    232    @Deprecated
    233    public void assign(int iteration, T value) {
    234        if (iRecentlyRemovedValue != null && iRecentlyRemovedValue.equals(value)) {
    235            iRecentlyRemovedValue = null;
    236            return;
    237        }
    238        getModel().getDefaultAssignment().assign(iteration, value);
    239    }
    240
    241    /**
    242     * Unassign value from this variable.
    243     * Use {@link Assignment#unassign(long, Variable)} instead.
    244     *
    245     * @param iteration
    246     *            current iteration
    247     */
    248    @Deprecated
    249    @SuppressWarnings("unchecked")
    250    public void unassign(int iteration) {
    251        getModel().getDefaultAssignment().unassign(iteration, (V) this);
    252    }
    253
    254
    255    /**
    256     * Returns iteration of the last assignment.
    257     * Use {@link Assignment#getIteration(Variable)} instead.
    258     * @return iteration of the last assignment
    259     **/
    260    @Deprecated
    261    public long getLastIteration() {
    262        return iLastIteration;
    263    }
    264
    265    /**
    266     * Sets iteration of the last assignment.
    267     * BEWARE: Do not use outside of {@link DefaultSingleAssignment}.
    268     * @param iteration current iteration
    269     **/
    270    @Deprecated
    271    public void setLastIteration(long iteration) {
    272        iLastIteration = iteration;
    273    }
    274
    275    /**
    276     * A value was assigned to this variable
    277     * @param assignment current assignment
    278     * @param iteration current iteration
    279     * @param value assigned value
    280     */
    281    public void variableAssigned(Assignment<V, T> assignment, long iteration, T value) {
    282        if (iVariableListeners != null)
    283            for (VariableListener<T> listener : iVariableListeners) {
    284                listener.variableAssigned(assignment, iteration, value);
    285            }
    286    }
    287
    288    /**
    289     * A value was unassigned from this variable
    290     * @param assignment current assignment
    291     * @param iteration current iteration
    292     * @param oldValue unassigned value
    293     */
    294    public void variableUnassigned(Assignment<V, T> assignment, long iteration, T oldValue) {
    295        if (iVariableListeners != null)
    296            for (VariableListener<T> listener : iVariableListeners)
    297                listener.variableUnassigned(assignment, iteration, oldValue);
    298    }
    299
    300    /**
    301     * Adds a constraint. Called automatically when the constraint is added to
    302     * the model, i.e., {@link Model#addConstraint(Constraint)} is called.
    303     *
    304     * @param constraint
    305     *            added constraint
    306     */
    307    public void addContstraint(Constraint<V, T> constraint) {
    308        iConstraints.add(constraint);
    309        if (constraint.isHard()) {
    310            iHardConstraints.add(constraint);
    311            iConstraintVariables = null;
    312        } else
    313            iSoftConstraints.add(constraint);
    314    }
    315
    316    /**
    317     * Removes a constraint. Called automatically when the constraint is removed
    318     * from the model, i.e., {@link Model#removeConstraint(Constraint)} is
    319     * called.
    320     *
    321     * @param constraint
    322     *            added constraint
    323     */
    324    public void removeContstraint(Constraint<V, T> constraint) {
    325        iConstraints.remove(constraint);
    326        if (iHardConstraints.contains(constraint)) {
    327            iHardConstraints.remove(constraint);
    328            iConstraintVariables = null;
    329        } else
    330            iSoftConstraints.remove(constraint);
    331    }
    332
    333    /** Return the list of constraints associated with this variable
    334     * @return list of constraints associated with this variable
    335     **/
    336    public List<Constraint<V, T>> constraints() {
    337        return iConstraints;
    338    }
    339
    340    /** Return the list of hard constraints associated with this variable
    341     * @return list of hard constraints associated with this variable
    342     **/
    343    public List<Constraint<V, T>> hardConstraints() {
    344        return iHardConstraints;
    345    }
    346
    347    /** Return the list of soft constraints associated with this variable
    348     * @return list of soft (not hard) constraints associated with this variable
    349     **/
    350    public List<Constraint<V, T>> softConstraints() {
    351        return iSoftConstraints;
    352    }
    353
    354    @Override
    355    public String toString() {
    356        return getName();
    357    }
    358
    359    /** Unique id
    360     * @return variable id
    361     **/
    362    public long getId() {
    363        return iId;
    364    }
    365
    366    @Override
    367    public int hashCode() {
    368        return (int) iId;
    369    }
    370
    371    /** Variable's name -- for printing purposes
    372     * @return variable name
    373     **/
    374    public String getName() {
    375        return String.valueOf(iId);
    376    }
    377
    378    /** Variable's description -- for printing purposes
    379     * @return variable description
    380     **/
    381    public String getDescription() {
    382        return null;
    383    }
    384
    385    /**
    386     * Sets variable's value of the best ever found solution. Called when
    387     * {@link Model#saveBest(Assignment)} is called.
    388     * @param value a value
    389     * @param iteration value's assignment iteration
    390     */
    391    public void setBestAssignment(T value, long iteration) {
    392        iBestValue = value;
    393        iBestAssignmentIteration = iteration;
    394    }
    395
    396    /** Returns the value from the best ever found solution.
    397     * @return best assignment
    398     **/
    399    public T getBestAssignment() {
    400        return iBestValue;
    401    }
    402
    403    /** Returns the iteration when the best value was assigned
    404     * @return iteration of the best assignment
    405     **/
    406    public long getBestAssignmentIteration() {
    407        return iBestAssignmentIteration;
    408    }
    409
    410    @Override
    411    public int compareTo(V variable) {
    412        if (variable == null)
    413            return -1;
    414        int cmp = getName().compareTo(variable.getName());
    415        if (cmp != 0)
    416            return cmp;
    417        return Double.compare(getId(), variable.getId());
    418    }
    419
    420    @Override
    421    public boolean equals(Object o) {
    422        if (o == null || !(o instanceof Variable<?, ?>))
    423            return false;
    424        return getId() == ((Variable<?, ?>) o).getId();
    425    }
    426
    427    /** Adds variable listener
    428     * @param listener a variable listener
    429     **/
    430    public void addVariableListener(VariableListener<T> listener) {
    431        if (iVariableListeners == null)
    432            iVariableListeners = new ArrayList<VariableListener<T>>();
    433        iVariableListeners.add(listener);
    434    }
    435
    436    /** Removes variable listener
    437     * @param listener a variable listener
    438     **/
    439    public void removeVariableListener(VariableListener<T> listener) {
    440        if (iVariableListeners != null)
    441            iVariableListeners.remove(listener);
    442    }
    443
    444    /** Return variable listeners
    445     * @return list of variable listeners
    446     **/
    447    public List<VariableListener<T>> getVariableListeners() {
    448        return iVariableListeners;
    449    }
    450
    451    /**
    452     * Extra information to which can be used by an extension (see
    453     * {@link org.cpsolver.ifs.extension.Extension}).
    454     * @param object extra object
    455     */
    456    public <X> void setExtra(X object) {
    457        iExtra = object;
    458    }
    459
    460    /**
    461     * Extra information to which can be used by an extension (see
    462     * {@link org.cpsolver.ifs.extension.Extension}).
    463     * @return extra object
    464     */
    465    @SuppressWarnings("unchecked")
    466    public <X> X getExtra() {
    467        try {
    468            return (X) iExtra;
    469        } catch (ClassCastException e) {
    470            return null;
    471        }
    472    }
    473
    474    /**
    475     * Permanently remove a value from variable's domain.
    476     * The variable should not have this value assigned in any existing assignment.
    477     * @param iteration current iteration
    478     * @param value value to be removed from this variable's domain
    479     **/
    480    @SuppressWarnings({ "deprecation", "unchecked" })
    481    public void removeValue(long iteration, T value) {
    482        if (value.equals(getModel().getDefaultAssignment().getValue((V) this)))
    483                getModel().getDefaultAssignment().unassign(iteration, (V) this);
    484        if (iValues == null)
    485            return;
    486        iValues.remove(value);
    487        if (iInitialValue != null && iInitialValue.equals(value)) {
    488            iInitialValue = null;
    489            if (iModel != null)
    490                iModel.invalidateVariablesWithInitialValueCache();
    491        }
    492        if (iVariableListeners != null)
    493            for (VariableListener<T> listener : iVariableListeners)
    494                listener.valueRemoved(iteration, value);
    495        iRecentlyRemovedValue = value;
    496    }
    497
    498    /**
    499     * Returns a table of all variables linked with this variable by a
    500     * constraint.
    501     *
    502     * @return table (variable, constraint)
    503     */
    504    public Map<V, List<Constraint<V, T>>> constraintVariables() {
    505        if (iConstraintVariables == null) {
    506            iConstraintVariables = new HashMap<V, List<Constraint<V, T>>>();
    507            for (Constraint<V, T> constraint : constraints()) {
    508                for (V variable : constraint.variables()) {
    509                    if (!variable.equals(this)) {
    510                        List<Constraint<V, T>> constraints = iConstraintVariables.get(variable);
    511                        if (constraints == null) {
    512                            constraints = new ArrayList<Constraint<V, T>>();
    513                            iConstraintVariables.put(variable, constraints);
    514                        }
    515                        constraints.add(constraint);
    516                    }
    517                }
    518            }
    519        }
    520        return iConstraintVariables;
    521    }
    522
    523    /**
    524     * Permanently remove the initial value from the variable's domain -- for
    525     * testing MPP
    526     */
    527    public void removeInitialValue() {
    528        if (iInitialValue == null)
    529            return;
    530        if (iValues == null)
    531            return;
    532        iValues.remove(iInitialValue);
    533        if (iModel != null)
    534            iModel.invalidateVariablesWithInitialValueCache();
    535        iInitialValue = null;
    536    }
    537
    538    /**
    539     * Unique index of a variable, only to be assigned by {@link Model#addVariable(Variable)}.
    540     * @param index an index
    541     */
    542    public void setIndex(int index) { iIndex = index; }
    543
    544    /**
    545     * Unique index of a variable that was assigned by {@link Model#addVariable(Variable)}.
    546     * @return -1 if not in a model
    547     */
    548    public int getIndex() { return iIndex; }
    549}