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