    001package net.sf.cpsolver.ifs.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.List;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.ifs.util.IdGenerator;
    010
    011/**
    012 * Generic constraint. <br>
    013 * <br>
    014 * Like in other traditional Constraint Logic Programming (CLP) frameworks, the
    015 * input problem consists of variables, values and constraints. Each constraint
    016 * is defined over a subset of the problem variables and it prohibits some
    017 * combinations of values which these variables can simultaneously take. In
    018 * usual CSP problems, all constraints are binary (or the problem is transformed
    019 * into an equivalent problem with only binary constrains before the search is
    020 * started) since most of the consistency and filtering techniques are designed
    021 * only for binary constraints. In such a case, the procedure computing
    022 * conflicting variables is rather simple and it returns an unambiguous set of
    023 * variables. It enumerates all the constraints which contain the selected
    024 * variable and which are not consistent with the selected value. It returns all
    025 * the variables of such constraints, different from the selected variable. <br>
    026 * <br>
    027 * On the other hand, most of real problems have plenty of multi-variable
    028 * constraints, like, for instance, resource constraint in timetabling. Such
    029 * resource constraint enforces the rule that none of the variables which are
    030 * using the given resource can be overlapping in time (if the resource has
    031 * capacity one) or that the amount of the resource used at a time does not
    032 * exceed its capacity. It is not very useful to replace such resource
    033 * constraint by a set of binary constraints (e.g., prohibiting two overlapping
    034 * placements in time of two particular events using the same resource), since
    035 * this approach usually ends up with thousands of constraints. Also, there is
    036 * usually a much more effective consistency and/or filtering technique working
    037 * with the original constraint (for instance, "cumulative" constraint is
    038 * usually used for modelling resource constraints in CLP). <br>
    039 * <br>
    040 * Using multi-variable constraints, the set of conflicting variables returned
    041 * by the procedure computing conflicting variables can differ according to its
    042 * implementation. For instance, we can have a constraint A+B=C where A and C is
    043 * already assigned to A=3 and C=5. Then if the assignment B=3 is selected,
    044 * either A or B or both A and B can be unassigned to make the problem {A=3,
    045 * B=3, C=5} consistent with the constraint A+B=C. Intuitively, there should be
    046 * minimal number of variables unassigned in each iteration step (we are trying
    047 * to increase the number of the assigned variables during the search). Also,
    048 * for many constraints, it is possible to find inconsistencies even when not
    049 * all variables of the constraint are yet assigned. For instance, if there are
    050 * two lectures using the same room at the same time, we know that one of them
    051 * needs to be unassigned even when there are unassigned lectures which will
    052 * also need to be placed in that room. <br>
    053 * <br>
    054 * In the current implementation, each hard constraint needs to implement the
    055 * procedure {@link Constraint#computeConflicts(Value, Set)} which returns all
    056 * the already assigned values that are incompatible we the selected assignment
    057 * (value which is to be assigned to its variable). This procedure is called for
    058 * all constraints which contain the selected variable in an ordered manner.
    059 * Furthermore, this order can be changed during the search. Moreover, the
    060 * computed set of conflicting variables is passed to this
    061 * {@link Constraint#computeConflicts(Value, Set)} procedure as a parameter, so
    062 * the constraint can "see" what variables are already selected for unassignment
    063 * by previously processed constraints. This way, we are not computing the very
    064 * minimal set of conflicting variables, however, we allow for computing this
    065 * set in an efficient way. It can be also tuned for a particular problem by
    066 * changing the order of constraints. <br>
    067 * <br>
    068 * Also note that each constraint can keep its notion about the assigned
    069 * variables. For instance, the resource constraint of a particular room can
    070 * memorize a look-up table stating what lecture is assigned in what time
    071 * slot(s), so for the computation of the conflicting lectures it only looks
    072 * through the appropriate fields of this table. The implementation is based on
    073 * {@link Constraint#assigned(long,Value)} and
    074 * {@link Constraint#unassigned(long,Value)} methods that are responsible to
    075 * keeping the problem consistent with the constraint. Also note that this
    076 * default consistency technique is defined on a problem level and it can be
    077 * changed by a more dedicated one, implemented for a particular problem.
    078 *
    079 * @see Variable
    080 * @see Model
    081 * @see net.sf.cpsolver.ifs.solver.Solver
    082 *
    083 * @version IFS 1.2 (Iterative Forward Search)<br>
    084 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    085 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    086 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    087 * <br>
    088 *          This library is free software; you can redistribute it and/or modify
    089 *          it under the terms of the GNU Lesser General Public License as
    090 *          published by the Free Software Foundation; either version 3 of the
    091 *          License, or (at your option) any later version. <br>
    092 * <br>
    093 *          This library is distributed in the hope that it will be useful, but
    094 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    095 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    096 *          Lesser General Public License for more details. <br>
    097 * <br>
    098 *          You should have received a copy of the GNU Lesser General Public
    099 *          License along with this library; if not see
    100 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    101 */
    102
    103public abstract class Constraint<V extends Variable<V, T>, T extends Value<V, T>> implements
    104        Comparable<Constraint<V, T>> {
    105    private static IdGenerator iIdGenerator = new IdGenerator();
    106
    107    protected long iId = -1;
    108
    109    private List<V> iVariables = new ArrayList<V>();
    110    protected Collection<V> iAssignedVariables = new HashSet<V>();
    111    private Model<V, T> iModel = null;
    112    protected List<ConstraintListener<T>> iConstraintListeners = null;
    113
    114    /** Constructor */
    115    public Constraint() {
    116        iId = iIdGenerator.newId();
    117    }
    118
    119    /** The model which the constraint belongs to */
    120    public Model<V, T> getModel() {
    121        return iModel;
    122    }
    123
    124    /** Sets the model which the constraint belongs to */
    125    public void setModel(Model<V, T> model) {
    126        iModel = model;
    127    }
    128
    129    /** The list of variables of this constraint */
    130    public List<V> variables() {
    131        return iVariables;
    132    }
    133
    134    /** The list of variables of this constraint that are assigned */
    135    public Collection<V> assignedVariables() {
    136        return iAssignedVariables;
    137    }
    138
    139    /** The number of variables of this constraint */
    140    public int countVariables() {
    141        return variables().size();
    142    }
    143
    144    /** The number of variables of this constraint that are assigned */
    145    public int countAssignedVariables() {
    146        return assignedVariables().size();
    147    }
    148
    149    /** Add a variable to this constraint */
    150    public void addVariable(V variable) {
    151        iVariables.add(variable);
    152        variable.addContstraint(this);
    153        if (variable.getAssignment() != null) {
    154            assigned(0, variable.getAssignment());
    155            if (iAssignedVariables != null)
    156                iAssignedVariables.add(variable);
    157        }
    158    }
    159
    160    /** Remove a variable from this constraint */
    161    public void removeVariable(V variable) {
    162        if (variable.getAssignment() != null) {
    163            unassigned(0, variable.getAssignment());
    164        }
    165        variable.removeContstraint(this);
    166        iVariables.remove(variable);
    167        if (iAssignedVariables != null && iAssignedVariables.contains(variable))
    168            iAssignedVariables.remove(variable);
    169    }
    170
    171    /**
    172     * The only method which has to be implemented by any constraint. It returns
    173     * the values which needs to be unassigned in order to make this constraint
    174     * consistent with the given value if it is assigned to its variable. The
    175     * computed list of conflicting values is added to the given set of
    176     * conflicts.
    177     *
    178     * @param value
    179     *            value to be assigned to its varaible
    180     * @param conflicts
    181     *            resultant set of conflicting values
    182     */
    183    public abstract void computeConflicts(T value, Set<T> conflicts);
    184
    185    /**
    186     * Returns true if the given assignments are consistent respecting this
    187     * constraint. This method is used by MAC (see
    188     * {@link net.sf.cpsolver.ifs.extension.MacPropagation}).
    189     */
    190    public boolean isConsistent(T value1, T value2) {
    191        return true;
    192    }
    193
    194    /**
    195     * Returns true if the given assignment is inconsistent with the existing
    196     * assignments respecting this constraint. This method is used by MAC (see
    197     * {@link net.sf.cpsolver.ifs.extension.MacPropagation}).
    198     */
    199    public boolean inConflict(T value) {
    200        Set<T> conflicts = new HashSet<T>();
    201        computeConflicts(value, conflicts);
    202        return !conflicts.isEmpty();
    203    }
    204
    205    /**
    206     * Given value is to be assigned to its varable. In this method, the
    207     * constraint should unassigns all varaibles which are in conflict with the
    208     * given assignment because of this constraint.
    209     */
    210    public void assigned(long iteration, T value) {
    211        Set<T> conf = null;
    212        if (isHard()) {
    213            conf = new HashSet<T>();
    214            computeConflicts(value, conf);
    215        }
    216        if (iConstraintListeners != null)
    217            for (ConstraintListener<T> listener : iConstraintListeners)
    218                listener.constraintBeforeAssigned(iteration, this, value, conf);
    219        if (conf != null) {
    220            for (T conflictValue : conf) {
    221                if (!conflictValue.equals(value))
    222                    conflictValue.variable().unassign(iteration);
    223            }
    224        }
    225        if (iAssignedVariables != null)
    226            iAssignedVariables.add(value.variable());
    227        if (iConstraintListeners != null)
    228            for (ConstraintListener<T> listener : iConstraintListeners)
    229                listener.constraintAfterAssigned(iteration, this, value, conf);
    230    }
    231
    232    /**
    233     * Given value is unassigned from its variable.
    234     */
    235    public void unassigned(long iteration, T value) {
    236        if (iAssignedVariables != null)
    237            iAssignedVariables.remove(value.variable());
    238    }
    239
    240    /** Adds a constraint listener */
    241    public void addConstraintListener(ConstraintListener<T> listener) {
    242        if (iConstraintListeners == null)
    243            iConstraintListeners = new ArrayList<ConstraintListener<T>>();
    244        iConstraintListeners.add(listener);
    245    }
    246
    247    /** Removes a constraint listener */
    248    public void removeConstraintListener(ConstraintListener<T> listener) {
    249        if (iConstraintListeners != null)
    250            iConstraintListeners.remove(listener);
    251    }
    252
    253    /** Returns the list of registered constraint listeners */
    254    public List<ConstraintListener<T>> constraintListeners() {
    255        return iConstraintListeners;
    256    }
    257
    258    /** Unique id */
    259    public long getId() {
    260        return iId;
    261    }
    262
    263    /** Constraint's name -- for printing purposes */
    264    public String getName() {
    265        return String.valueOf(iId);
    266    }
    267
    268    /** Constraint's description -- for printing purposes */
    269    public String getDescription() {
    270        return null;
    271    }
    272
    273    @Override
    274    public int hashCode() {
    275        return (int) iId;
    276    }
    277
    278    /**
    279     * Returns true if the constraint is hard. Only hard constraints are allowed
    280     * to unassign a variable when there is a conflict with a value that is
    281     * being assigned
    282     */
    283    public boolean isHard() {
    284        return true;
    285    }
    286
    287    /**
    288     * Compare two constraints for equality ({@link Constraint#getId()} is used)
    289     */
    290    @Override
    291    public boolean equals(Object o) {
    292        if (o == null || !(o instanceof Constraint<?, ?>))
    293            return false;
    294        return getId() == ((Constraint<?, ?>) o).getId();
    295    }
    296
    297    @Override
    298    public int compareTo(Constraint<V, T> c) {
    299        return Double.compare(getId(), c.getId());
    300    }
    301}