    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}