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