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