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