001package org.cpsolver.exam.model;
002
003import java.util.Iterator;
004import java.util.Set;
005
006import org.cpsolver.exam.criteria.DistributionPenalty;
007import org.cpsolver.ifs.assignment.Assignment;
008import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
009import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
010
011
012/**
013 * Distribution binary constraint. <br>
014 * <br>
015 * The following binary distribution constraints are implemented
016 * <ul>
017 * <li>Same room
018 * <li>Different room
019 * <li>Same period
020 * <li>Different period
021 * <li>Precedence
022 * <li>Same day
023 * </ul>
024 * <br>
025 * <br>
026 * 
027 * @version ExamTT 1.3 (Examination Timetabling)<br>
028 *          Copyright (C) 2008 - 2014 Tomáš Müller<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    @Deprecated
048    public static int sDistSameRoom = DistributionType.SameRoom.ordinal() - 1;
049    private DistributionType iType = null;
050    private boolean iHard = true;
051    private int iWeight = 0;
052    
053    public static enum DistributionType {
054        /** Same room constraint type */
055        SameRoom("same-room", "EX_SAME_ROOM", false, new RoomCheck() {
056            @Override
057            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
058                return first.getRoomPlacements().containsAll(second.getRoomPlacements()) || second.getRoomPlacements().containsAll(first.getRoomPlacements());
059            }
060            @Override
061            public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) {
062                return first.getRoomPlacements().contains(second);
063            }}),
064        /** Different room constraint type */
065        DifferentRoom("different-room", "EX_SAME_ROOM", true, new RoomCheck() {
066            @Override
067            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
068                for (Iterator<ExamRoomPlacement> i = first.getRoomPlacements().iterator(); i.hasNext();)
069                    if (second.getRoomPlacements().contains(i.next()))
070                        return false;
071                return true;
072            }
073            @Override
074            public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) {
075                return !first.getRoomPlacements().contains(second);
076            }}),
077        /** Same period constraint type */
078        SamePeriod("same-period", "EX_SAME_PER", false, new PeriodCheck() {
079            @Override
080            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
081                return first.getPeriod().getIndex() == second.getPeriod().getIndex();
082            }
083            @Override
084            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
085                return first.getIndex() == second.getIndex();
086            }}),
087        /** Different period constraint type */
088        DifferentPeriod("different-period", "EX_SAME_PER", true, new PeriodCheck() {
089            @Override
090            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
091                return first.getPeriod().getIndex() != second.getPeriod().getIndex();
092            }
093            @Override
094            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
095                return first.getIndex() != second.getIndex();
096            }}),
097        /** Precedence constraint type */
098        Precedence("precedence", "EX_PRECEDENCE", false, new PeriodCheck() {
099            @Override
100            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
101                return first.getPeriod().getIndex() < second.getPeriod().getIndex();
102            }
103            @Override
104            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
105                return first.getIndex() < second.getIndex();
106            }}),
107        /** Precedence constraint type (reverse order) */
108        PrecedenceRev("precedence-rev", "EX_PRECEDENCE", true, new PeriodCheck() {
109            @Override
110            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
111                return first.getPeriod().getIndex() > second.getPeriod().getIndex();
112            }
113            @Override
114            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
115                return first.getIndex() > second.getIndex();
116            }}),
117        /** Same day constraint type */
118        SameDay("same-day", "EX_SAME_DAY", false, new PeriodCheck() {
119            @Override
120            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
121                return first.getPeriod().getDay() == second.getPeriod().getDay();
122            }
123            @Override
124            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
125                return first.getDay() == second.getDay();
126            }}),
127        /** Different day constraint type */
128        DifferentDay("different-day", "EX_SAME_DAY", true, new PeriodCheck() {
129            @Override
130            public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
131                return first.getPeriod().getDay() != second.getPeriod().getDay();
132            }
133            @Override
134            public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
135                return first.getDay() != second.getDay();
136            }}),
137        ;
138        private String iReference;
139        private String iUniTimeReference;
140        private boolean iUniTimeNegative;
141        private PairCheck iCheck;
142        private DistributionType(String reference, String utReference, boolean utNegative, PairCheck check) {
143            iReference = reference;
144            iUniTimeReference = utReference;
145            iUniTimeNegative = utNegative;
146            iCheck = check;
147        }
148        
149        public String getReference() { return iReference; }
150        public boolean isSatisfied(ExamPlacement first, ExamPlacement second) {
151            return iCheck.isSatisfied(first, second);
152        }
153        public boolean isRoomRelated() { return iCheck instanceof RoomCheck; }
154        public boolean isPeriodRelated() { return iCheck instanceof PeriodCheck; }
155        public boolean isSatisfied(ExamPeriod first, ExamPeriod second) {
156            if (iCheck instanceof PeriodCheck)
157                return ((PeriodCheck)iCheck).isSatisfied(first, second);
158            else
159                return true;
160        }
161        public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second) {
162            if (iCheck instanceof RoomCheck)
163                return ((RoomCheck)iCheck).isSatisfied(first, second);
164            else
165                return true;
166        }
167        public String getUniTimeReference() { return iUniTimeReference; }
168        public boolean isUniTimeNegative() { return iUniTimeNegative; }
169    }
170    
171    public static interface PairCheck {
172        public boolean isSatisfied(ExamPlacement first, ExamPlacement second);
173    }
174    
175    public static interface PeriodCheck extends PairCheck {
176        public boolean isSatisfied(ExamPeriod first, ExamPeriod second);
177    }
178    
179    public static interface RoomCheck extends PairCheck {
180        public boolean isSatisfied(ExamPlacement first, ExamRoomPlacement second);
181    }
182
183    /**
184     * Constructor
185     * 
186     * @param id
187     *            constraint unique id
188     * @param type
189     *            constraint type
190     * @param hard
191     *            true if the constraint is hard (cannot be violated)
192     * @param weight
193     *            if not hard, penalty for violation
194     */
195    public ExamDistributionConstraint(long id, DistributionType type, boolean hard, int weight) {
196        iId = id;
197        iType = type;
198        iHard = hard;
199        iWeight = weight;
200    }
201    
202    /**
203     * Constructor
204     * 
205     * @param id
206     *            constraint unique id
207     * @param type
208     *            constraint type
209     * @param hard
210     *            true if the constraint is hard (cannot be violated)
211     * @param weight
212     *            if not hard, penalty for violation
213     * @deprecated use {@link ExamDistributionConstraint#ExamDistributionConstraint(long, DistributionType, boolean, int)}
214     */
215    @Deprecated
216    public ExamDistributionConstraint(long id, int type, boolean hard, int weight) {
217        iId = id;
218        iType = DistributionType.values()[type];
219        iHard = hard;
220        iWeight = weight;
221    }
222
223    /**
224     * Constructor
225     * 
226     * @param id
227     *            constraint unique id
228     * @param type
229     *            constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE)
230     * @param pref
231     *            preference (R/P for required/prohibited, or -2, -1, 0, 1, 2
232     *            for preference (from preferred to discouraged))
233     */
234    public ExamDistributionConstraint(long id, String type, String pref) {
235        iId = id;
236        boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref);
237        for (DistributionType t: DistributionType.values()) {
238            if (t.getUniTimeReference().equals(type) && t.isUniTimeNegative() == neg) {
239                iType = t;
240                break;
241            }
242        }
243        if (iType == null)
244            throw new RuntimeException("Unkown type " + type);
245        if ("P".equals(pref) || "R".equals(pref))
246            iHard = true;
247        else {
248            iHard = false;
249            iWeight = Integer.parseInt(pref) * Integer.parseInt(pref);
250        }
251    }
252
253    /**
254     * Constructor
255     * 
256     * @param id
257     *            constraint unique id
258     * @param type
259     *            constraint type name
260     * @param hard true if the constraint is hard
261     * @param weight constraint penalty if violated (for soft constraint)
262     */
263    public ExamDistributionConstraint(long id, String type, boolean hard, int weight) {
264        iId = id;
265        for (DistributionType t: DistributionType.values()) {
266            if (t.getReference().equals(type)) {
267                iType = t; break;
268            }
269        }
270        if (iType == null)
271            throw new RuntimeException("Unknown type '" + type + "'.");
272        iHard = hard;
273        iWeight = weight;
274    }
275
276    /**
277     * True if hard (must be satisfied), false for soft (should be satisfied)
278     */
279    @Override
280    public boolean isHard() {
281        return iHard;
282    }
283
284    /**
285     * If not hard, penalty for violation
286     * @return constraint penalty if violated
287     */
288    public int getWeight() {
289        return iWeight;
290    }
291
292    /**
293     * Constraint type
294     * @return constraint type
295     */
296    public int getType() {
297        return iType.ordinal() - 1;
298    }
299    
300    public DistributionType getDistributionType() {
301        return iType;
302    }
303
304    /**
305     * Constraint type name
306     * @return constraint type name (one of {@link DistributionType#getReference()})
307     */
308    public String getTypeString() {
309        return iType.getReference();
310    }
311
312    /**
313     * String representation -- constraint type name (exam 1, exam 2)
314     */
315    @Override
316    public String toString() {
317        return getTypeString() + " (" + variables() + ")";
318    }
319
320    /**
321     * Compute conflicts -- there is a conflict if the other variable is
322     * assigned and
323     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
324     * false
325     */
326    @Override
327    public void computeConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPlacement givenPlacement, Set<ExamPlacement> conflicts) {
328        boolean before = true;
329        for (Exam exam : variables()) {
330            if (exam.equals(givenPlacement.variable())) {
331                before = false;
332                continue;
333            }
334            ExamPlacement placement = assignment.getValue(exam);
335            if (placement == null)
336                continue;
337            if (!iType.isSatisfied(before ? placement : givenPlacement, before ? givenPlacement : placement))
338                conflicts.add(placement);
339        }
340    }
341
342    /**
343     * Check for conflict -- there is a conflict if the other variable is
344     * assigned and
345     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
346     * false
347     */
348    @Override
349    public boolean inConflict(Assignment<Exam, ExamPlacement> assignment, ExamPlacement givenPlacement) {
350        boolean before = true;
351        for (Exam exam : variables()) {
352            if (exam.equals(givenPlacement.variable())) {
353                before = false;
354                continue;
355            }
356            ExamPlacement placement = assignment.getValue(exam);
357            if (placement == null)
358                continue;
359            if (!iType.isSatisfied(before ? placement : givenPlacement, before ? givenPlacement : placement))
360                return true;
361        }
362        return false;
363    }
364
365    /**
366     * Consistency check --
367     * {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is
368     * called
369     */
370    @Override
371    public boolean isConsistent(ExamPlacement first, ExamPlacement second) {
372        boolean before = (variables().indexOf(first.variable()) < variables().indexOf(second.variable()));
373        return iType.isSatisfied(before ? first : second, before ? second : first);
374    }
375
376    /**
377     * Check assignments of the given exams
378     * 
379     * @param first
380     *            assignment of the first exam
381     * @param second
382     *            assignment of the second exam
383     * @return true, if the constraint is satisfied
384     * @deprecated use {@link DistributionType#isSatisfied(ExamPlacement, ExamPlacement)}
385     */
386    @Deprecated
387    public boolean check(ExamPlacement first, ExamPlacement second) {
388        return iType.isSatisfied(first, second);
389    }
390
391    /**
392     * Compare with other constraint for equality
393     */
394    @Override
395    public boolean equals(Object o) {
396        if (o == null || !(o instanceof ExamDistributionConstraint))
397            return false;
398        ExamDistributionConstraint c = (ExamDistributionConstraint) o;
399        return getType() == c.getType() && getId() == c.getId();
400    }
401
402    /**
403     * Return true if this is hard constraint or this is a soft constraint
404     * without any violation
405     * @param assignment current assignment
406     * @return true if the constraint is satisfied
407     */
408    public boolean isSatisfied(Assignment<Exam, ExamPlacement> assignment) {
409        return isSatisfied(assignment, null);
410    }
411
412    /**
413     * Return true if this is hard constraint or this is a soft constraint
414     * without any violation
415     * 
416     * @param assignment current assignment
417     * @param p
418     *            exam assignment to be made
419     * @return true if the constraint is satisfied
420     */
421    public boolean isSatisfied(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p) {
422        return countViolations(assignment, p) == 0;
423    }
424    
425    /**
426     * Return number of violated pairs for a soft constraint and the given placement
427     * 
428     * @param assignment current assignment
429     * @param p
430     *            exam assignment to be made
431     * @return number of examination pairs violated
432     */
433    public int countViolations(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p) {
434        if (isHard()) return 0;
435        if (p == null) return countViolations(assignment);
436        if (countAssignedVariables(assignment) + (assignment.getValue(p.variable()) == null ? 1 : 0) < 2) return 0; // not enough variables
437        
438        int nrViolatedPairs = 0;
439        boolean before = true;
440        for (Exam other: variables()) {
441            if (other.equals(p.variable())) {
442                before = false;
443                continue;
444            }
445            ExamPlacement otherPlacement = assignment.getValue(other);
446            if (otherPlacement == null) continue;
447            if (before) {
448                if (!iType.isSatisfied(otherPlacement, p)) nrViolatedPairs ++;
449            } else {
450                if (!iType.isSatisfied(p, otherPlacement)) nrViolatedPairs ++;
451            }
452        }
453        return nrViolatedPairs;
454    }
455    
456    /**
457     * Return number of all violated pairs for a soft constraint
458     * 
459     * @param assignment current assignment
460     * @return number of examination pairs violated
461     */
462    public int countViolations(Assignment<Exam, ExamPlacement> assignment) {
463        if (isHard()) return 0;
464        int violations = 0;
465        for (int i = 0; i < variables().size() - 1; i++) {
466            ExamPlacement first = assignment.getValue(variables().get(i));
467            if (first == null) continue;
468            for (int j = i + 1; j < variables().size(); j++) {
469                ExamPlacement second = assignment.getValue(variables().get(j));
470                if (second == null) continue;
471                if (!iType.isSatisfied(first, second)) violations ++;
472            }
473        }
474        return violations;
475    }
476
477    /** True if the constraint is related to rooms 
478     * @return true if the constraint is related to room placement
479     **/
480    public boolean isRoomRelated() {
481        return iType.isRoomRelated();
482    }
483
484    /** True if the constraint is related to periods 
485     * @return true if the constraint is related to period placement
486     **/
487    public boolean isPeriodRelated() {
488        return iType.isPeriodRelated();
489    }
490    
491    @Override
492    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
493        return new Context(assignment);
494    }
495    
496    public class Context implements AssignmentConstraintContext<Exam, ExamPlacement> {
497        private int iViolations = 0;
498        
499        public Context(Assignment<Exam, ExamPlacement> assignment) {
500            updateCriterion(assignment);
501        }
502
503        @Override
504        public void assigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) {
505            updateCriterion(assignment);
506        }
507        
508        @Override
509        public void unassigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) {
510            updateCriterion(assignment);
511        }
512        
513        protected void updateCriterion(Assignment<Exam, ExamPlacement> assignment) {
514            if (!isHard()) {
515                ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(assignment, -iViolations * getWeight(), ExamDistributionConstraint.this);
516                iViolations = countViolations(assignment);
517                ((DistributionPenalty)getModel().getCriterion(DistributionPenalty.class)).inc(assignment, +iViolations * getWeight(), ExamDistributionConstraint.this);
518            }
519        }
520        
521        public int getViolations() { return iViolations; }
522    }
523}