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