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