001    package net.sf.cpsolver.exam.model;
002    
003    import java.util.HashSet;
004    import java.util.Iterator;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.exam.criteria.DistributionPenalty;
008    import net.sf.cpsolver.ifs.model.Constraint;
009    
010    /**
011     * Distribution binary constraint. <br>
012     * <br>
013     * The following binary distribution constraints are implemented
014     * <ul>
015     * <li>Same room
016     * <li>Different room
017     * <li>Same period
018     * <li>Different period
019     * <li>Precedence
020     * </ul>
021     * <br>
022     * <br>
023     * 
024     * @version ExamTT 1.2 (Examination Timetabling)<br>
025     *          Copyright (C) 2008 - 2010 Tomas Muller<br>
026     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028     * <br>
029     *          This library is free software; you can redistribute it and/or modify
030     *          it under the terms of the GNU Lesser General Public License as
031     *          published by the Free Software Foundation; either version 3 of the
032     *          License, or (at your option) any later version. <br>
033     * <br>
034     *          This library is distributed in the hope that it will be useful, but
035     *          WITHOUT ANY WARRANTY; without even the implied warranty of
036     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037     *          Lesser General Public License for more details. <br>
038     * <br>
039     *          You should have received a copy of the GNU Lesser General Public
040     *          License along with this library; if not see
041     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042     */
043    public class ExamDistributionConstraint extends Constraint<Exam, ExamPlacement> {
044        /** Same room constraint type */
045        public static final int sDistSameRoom = 0;
046        /** Different room constraint type */
047        public static final int sDistDifferentRoom = 1;
048        /** Same period constraint type */
049        public static final int sDistSamePeriod = 2;
050        /** Different period constraint type */
051        public static final int sDistDifferentPeriod = 3;
052        /** Precedence constraint type */
053        public static final int sDistPrecedence = 4;
054        /** Precedence constraint type (reverse order) */
055        public static final int sDistPrecedenceRev = 5;
056        /** Distribution type name */
057        public static final String[] sDistType = new String[] { "same-room", "different-room", "same-period",
058                "different-period", "precedence", "precedence-rev" };
059    
060        private int iType = -1;
061        private boolean iHard = true;
062        private int iWeight = 0;
063    
064        /**
065         * Constructor
066         * 
067         * @param id
068         *            constraint unique id
069         * @param type
070         *            constraint type
071         * @param hard
072         *            true if the constraint is hard (cannot be violated)
073         * @param weight
074         *            if not hard, penalty for violation
075         */
076        public ExamDistributionConstraint(long id, int type, boolean hard, int weight) {
077            iId = id;
078            iType = type;
079            iHard = hard;
080            iWeight = weight;
081        }
082    
083        /**
084         * Constructor
085         * 
086         * @param id
087         *            constraint unique id
088         * @param type
089         *            constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE)
090         * @param pref
091         *            preference (R/P for required/prohibited, or -2, -1, 0, 1, 2
092         *            for preference (from preferred to discouraged))
093         */
094        public ExamDistributionConstraint(long id, String type, String pref) {
095            iId = id;
096            boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref);
097            if ("EX_SAME_PER".equals(type)) {
098                iType = (neg ? sDistDifferentPeriod : sDistSamePeriod);
099            } else if ("EX_SAME_ROOM".equals(type)) {
100                iType = (neg ? sDistDifferentRoom : sDistSameRoom);
101            } else if ("EX_PRECEDENCE".equals(type)) {
102                iType = (neg ? sDistPrecedenceRev : sDistPrecedence);
103            } else
104                throw new RuntimeException("Unkown type " + type);
105            if ("P".equals(pref) || "R".equals(pref))
106                iHard = true;
107            else {
108                iHard = false;
109                iWeight = Integer.parseInt(pref) * Integer.parseInt(pref);
110            }
111        }
112    
113        /**
114         * Constructor
115         * 
116         * @param id
117         *            constraint unique id
118         * @param type
119         *            constraint type name
120         */
121        public ExamDistributionConstraint(long id, String type, boolean hard, int weight) {
122            iId = id;
123            for (int i = 0; i < sDistType.length; i++)
124                if (sDistType[i].equals(type))
125                    iType = i;
126            if (iType < 0)
127                throw new RuntimeException("Unknown type '" + type + "'.");
128            iHard = hard;
129            iWeight = weight;
130        }
131    
132        /**
133         * True if hard (must be satisfied), false for soft (should be satisfied)
134         */
135        @Override
136        public boolean isHard() {
137            return iHard;
138        }
139    
140        /**
141         * If not hard, penalty for violation
142         */
143        public int getWeight() {
144            return iWeight;
145        }
146    
147        /**
148         * Constraint type
149         */
150        public int getType() {
151            return iType;
152        }
153    
154        /**
155         * Constraint type name
156         */
157        public String getTypeString() {
158            return sDistType[iType];
159        }
160    
161        /**
162         * String representation -- constraint type name (exam 1, exam 2)
163         */
164        @Override
165        public String toString() {
166            return getTypeString() + " (" + variables() + ")";
167        }
168    
169        /**
170         * Compute conflicts -- there is a conflict if the other variable is
171         * assigned and
172         * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
173         * false
174         */
175        @Override
176        public void computeConflicts(ExamPlacement givenPlacement, Set<ExamPlacement> conflicts) {
177            boolean before = true;
178            for (Exam exam : variables()) {
179                if (exam.equals(givenPlacement.variable())) {
180                    before = false;
181                    continue;
182                }
183                ExamPlacement placement = exam.getAssignment();
184                if (placement == null)
185                    continue;
186                if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
187                    conflicts.add(placement);
188            }
189        }
190    
191        /**
192         * Check for conflict -- there is a conflict if the other variable is
193         * assigned and
194         * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
195         * false
196         */
197        @Override
198        public boolean inConflict(ExamPlacement givenPlacement) {
199            boolean before = true;
200            for (Exam exam : variables()) {
201                if (exam.equals(givenPlacement.variable())) {
202                    before = false;
203                    continue;
204                }
205                ExamPlacement placement = exam.getAssignment();
206                if (placement == null)
207                    continue;
208                if (!check(before ? placement : givenPlacement, before ? givenPlacement : placement))
209                    return true;
210            }
211            return false;
212        }
213    
214        /**
215         * Consistency check --
216         * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
217         * called
218         */
219        @Override
220        public boolean isConsistent(ExamPlacement first, ExamPlacement second) {
221            boolean before = (variables().indexOf(first.variable()) < variables().indexOf(second.variable()));
222            return check(before ? first : second, before ? second : first);
223        }
224    
225        /**
226         * Check assignments of the given exams
227         * 
228         * @param first
229         *            assignment of the first exam
230         * @param second
231         *            assignment of the second exam
232         * @return true, if the constraint is satisfied
233         */
234        public boolean check(ExamPlacement first, ExamPlacement second) {
235            switch (getType()) {
236                case sDistPrecedence:
237                    return first.getPeriod().getIndex() < second.getPeriod().getIndex();
238                case sDistPrecedenceRev:
239                    return first.getPeriod().getIndex() > second.getPeriod().getIndex();
240                case sDistSamePeriod:
241                    return first.getPeriod().getIndex() == second.getPeriod().getIndex();
242                case sDistDifferentPeriod:
243                    return first.getPeriod().getIndex() != second.getPeriod().getIndex();
244                case sDistSameRoom:
245                    return first.getRoomPlacements().containsAll(second.getRoomPlacements())
246                            || second.getRoomPlacements().containsAll(first.getRoomPlacements());
247                case sDistDifferentRoom:
248                    for (Iterator<ExamRoomPlacement> i = first.getRoomPlacements().iterator(); i.hasNext();)
249                        if (second.getRoomPlacements().contains(i.next()))
250                            return false;
251                    return true;
252                default:
253                    return false;
254            }
255        }
256    
257        /**
258         * Compare with other constraint for equality
259         */
260        @Override
261        public boolean equals(Object o) {
262            if (o == null || !(o instanceof ExamDistributionConstraint))
263                return false;
264            ExamDistributionConstraint c = (ExamDistributionConstraint) o;
265            return getType() == c.getType() && getId() == c.getId();
266        }
267    
268        /**
269         * Return true if this is hard constraint or this is a soft constraint
270         * without any violation
271         */
272        public boolean isSatisfied() {
273            return isSatisfied(null);
274        }
275    
276        /**
277         * Return true if this is hard constraint or this is a soft constraint
278         * without any violation
279         * 
280         * @param p
281         *            exam assignment to be made
282         */
283        public boolean isSatisfied(ExamPlacement p) {
284            if (isHard())
285                return true;
286            switch (getType()) {
287                case sDistPrecedence:
288                    ExamPeriod last = null;
289                    for (Exam exam : variables()) {
290                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
291                        if (placement == null)
292                            continue;
293                        if (last == null || last.getIndex() < placement.getPeriod().getIndex())
294                            last = placement.getPeriod();
295                        else
296                            return false;
297                    }
298                    return true;
299                case sDistPrecedenceRev:
300                    last = null;
301                    for (Exam exam : variables()) {
302                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
303                        if (placement == null)
304                            continue;
305                        if (last == null || last.getIndex() > placement.getPeriod().getIndex())
306                            last = placement.getPeriod();
307                        else
308                            return false;
309                    }
310                    return true;
311                case sDistSamePeriod:
312                    ExamPeriod period = null;
313                    for (Exam exam : variables()) {
314                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
315                        if (placement == null)
316                            continue;
317                        if (period == null)
318                            period = placement.getPeriod();
319                        else if (period.getIndex() != placement.getPeriod().getIndex())
320                            return false;
321                    }
322                    return true;
323                case sDistDifferentPeriod:
324                    HashSet<ExamPeriod> periods = new HashSet<ExamPeriod>();
325                    for (Exam exam : variables()) {
326                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
327                        if (placement == null)
328                            continue;
329                        if (!periods.add(placement.getPeriod()))
330                            return false;
331                    }
332                    return true;
333                case sDistSameRoom:
334                    Set<ExamRoomPlacement> rooms = null;
335                    for (Exam exam : variables()) {
336                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
337                        if (placement == null)
338                            continue;
339                        if (rooms == null)
340                            rooms = placement.getRoomPlacements();
341                        else if (!rooms.containsAll(placement.getRoomPlacements())
342                                || !placement.getRoomPlacements().containsAll(rooms))
343                            return false;
344                    }
345                    return true;
346                case sDistDifferentRoom:
347                    HashSet<ExamRoomPlacement> allRooms = new HashSet<ExamRoomPlacement>();
348                    for (Exam exam : variables()) {
349                        ExamPlacement placement = (p != null && exam.equals(p.variable()) ? p : exam.getAssignment());
350                        if (placement == null)
351                            continue;
352                        for (ExamRoomPlacement room : placement.getRoomPlacements()) {
353                            if (!allRooms.add(room))
354                                return false;
355                        }
356                    }
357                    return true;
358                default:
359                    return false;
360            }
361        }
362    
363        boolean iIsSatisfied = true;
364    
365        @Override
366        public void assigned(long iteration, ExamPlacement value) {
367            super.assigned(iteration, value);
368            if (!isHard() && iIsSatisfied != isSatisfied()) {
369                iIsSatisfied = !iIsSatisfied;
370                ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
371            }
372        }
373    
374        @Override
375        public void unassigned(long iteration, ExamPlacement value) {
376            super.unassigned(iteration, value);
377            if (!isHard() && iIsSatisfied != isSatisfied()) {
378                iIsSatisfied = !iIsSatisfied;
379                ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(iIsSatisfied ? -getWeight() : getWeight());
380            }
381        }
382    
383        /** True if the constraint is related to rooms */
384        public boolean isRoomRelated() {
385            return iType == sDistSameRoom || iType == sDistDifferentRoom;
386        }
387    
388        /** True if the constraint is related to periods */
389        public boolean isPeriodRelated() {
390            return !isRoomRelated();
391        }
392    }