001    package net.sf.cpsolver.ifs.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashSet;
006    import java.util.List;
007    import java.util.Set;
008    
009    import 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 Tomas Muller<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    
103    public 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    }