    001package org.cpsolver.coursett.criteria;
    002
    003import java.util.Collection;
    004import java.util.HashSet;
    005import java.util.List;
    006import java.util.Set;
    007
    008import org.cpsolver.coursett.Constants;
    009import org.cpsolver.coursett.constraint.RoomConstraint;
    010import org.cpsolver.coursett.constraint.RoomConstraint.RoomConstraintContext;
    011import org.cpsolver.coursett.model.Lecture;
    012import org.cpsolver.coursett.model.Placement;
    013import org.cpsolver.coursett.model.RoomLocation;
    014import org.cpsolver.coursett.model.TimeLocation;
    015import org.cpsolver.coursett.model.TimetableModel;
    016import org.cpsolver.ifs.assignment.Assignment;
    017import org.cpsolver.ifs.util.DataProperties;
    018
    019
    020/**
    021 * Broken time patterns. This criterion counts cases when an unused space is in a room
    022 * which follows one of the standard MWF or TTh pattern. E.g., there is a penalty of
    023 * Monday is available during a time when Wednesday and/or Friday is occupied. The aim
    024 * is to use this space if possible in order to leave the available space in a way that
    025 * can be used by MWF or TTh classes.
    026 * <br>
    027 *
    028 * @author  Tomáš Müller
    029 * @version CourseTT 1.3 (University Course Timetabling)<br>
    030 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    031 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    032 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    033 * <br>
    034 *          This library is free software; you can redistribute it and/or modify
    035 *          it under the terms of the GNU Lesser General Public License as
    036 *          published by the Free Software Foundation; either version 3 of the
    037 *          License, or (at your option) any later version. <br>
    038 * <br>
    039 *          This library is distributed in the hope that it will be useful, but
    040 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    041 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    042 *          Lesser General Public License for more details. <br>
    043 * <br>
    044 *          You should have received a copy of the GNU Lesser General Public
    045 *          License along with this library; if not see
    046 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    047 */
    048public class BrokenTimePatterns extends TimetablingCriterion {
    049    private int iFirstDaySlot, iLastDaySlot, iFirstWorkDay, iLastWorkDay;
    050
    051    public BrokenTimePatterns() {
    052        setValueUpdateType(ValueUpdateType.NoUpdate);
    053    }
    054
    055    @Override
    056    public void configure(DataProperties properties) {
    057        super.configure(properties);
    058        iFirstDaySlot = properties.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST);
    059        iLastDaySlot = properties.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST);
    060        iFirstWorkDay = properties.getPropertyInt("General.FirstWorkDay", 0);
    061        iLastWorkDay = properties.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1);
    062        if (iLastWorkDay < iFirstWorkDay) iLastWorkDay += 7;
    063    }
    064
    065    @Override
    066    public double getWeightDefault(DataProperties config) {
    067        return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1);
    068    }
    069
    070    @Override
    071    public String getPlacementSelectionWeightName() {
    072        return "Placement.UselessSlotsWeight";
    073    }
    074
    075    protected double penalty(Assignment<Lecture, Placement> assignment, Placement value) {
    076        if (value.isMultiRoom()) {
    077            int ret = 0;
    078            for (RoomLocation r : value.getRoomLocations()) {
    079                if (r.getRoomConstraint() == null)
    080                    continue;
    081                ret += penalty(r.getRoomConstraint().getContext(assignment), value);
    082            }
    083            return ret;
    084        } else {
    085            return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint().getContext(assignment), value));
    086        }
    087    }
    088
    089    protected double penalty(RoomConstraintContext rc) {
    090        return countUselessSlotsBrokenTimePatterns(rc) / 6.0;
    091    }
    092
    093    protected double penalty(RoomConstraintContext rc, Placement value) {
    094        return countUselessSlotsBrokenTimePatterns(rc, value) / 6.0;
    095    }
    096
    097   @Override
    098    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    099        double ret = penalty(assignment, value);
    100        if (conflicts != null)
    101            for (Placement conflict: conflicts)
    102                ret -= penalty(assignment, conflict);
    103        return ret;
    104    }
    105
    106    @Override
    107    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    108        double ret = 0;
    109        Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
    110        for (Lecture lect: variables) {
    111            Placement placement = assignment.getValue(lect);
    112            if (placement == null) continue;
    113            if (placement.isMultiRoom()) {
    114                for (RoomLocation r : placement.getRoomLocations()) {
    115                    if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint()))
    116                        ret += penalty(r.getRoomConstraint().getContext(assignment));
    117                }
    118            } else if (placement.getRoomLocation().getRoomConstraint() != null &&
    119                    constraints.add(placement.getRoomLocation().getRoomConstraint())) {
    120                ret += penalty(placement.getRoomLocation().getRoomConstraint().getContext(assignment));
    121            }
    122        }
    123        return ret;
    124    }
    125
    126    @Override
    127    protected double[] computeBounds(Assignment<Lecture, Placement> assignment) {
    128        return new double[] {
    129                ((TimetableModel)getModel()).getRoomConstraints().size() * (iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1),
    130                0.0 };
    131    }
    132
    133    @Override
    134    public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    135        Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
    136        for (Lecture lect: variables) {
    137            Placement placement = assignment.getValue(lect);
    138            if (placement == null) continue;
    139            if (placement.isMultiRoom()) {
    140                for (RoomLocation r : placement.getRoomLocations()) {
    141                    if (r.getRoomConstraint() != null)
    142                        constraints.add(r.getRoomConstraint());
    143                }
    144            } else if (placement.getRoomLocation().getRoomConstraint() != null) {
    145                constraints.add(placement.getRoomLocation().getRoomConstraint());
    146            }
    147        }
    148        return new double[] {
    149                constraints.size() * (iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1),
    150                0.0 };
    151    }
    152
    153    private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4];
    154    private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3];
    155
    156    private static boolean isEmpty(RoomConstraintContext rc, int s, int d, Placement placement) {
    157        List<Placement> assigned = rc.getPlacements(d * Constants.SLOTS_PER_DAY + s);
    158        return assigned.isEmpty() || (placement != null && assigned.size() == 1 && assigned.get(0).variable().equals(placement.variable()));
    159    }
    160
    161    /** Number of broken time patterns for this room
    162     * @param rc room constraint
    163     * @param placement placement that is being considered
    164     * @return number of broken time patterns caused by the given placement
    165     **/
    166    protected static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc, Placement placement) {
    167        int ret = 0;
    168        TimeLocation time = placement.getTimeLocation();
    169        int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY;
    170        int days = time.getDayCode();
    171        if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) {
    172            for (int s = slot; s < slot + time.getLength(); s++) {
    173                int d = (days & sDaysMWF);
    174                if (d == Constants.DAY_CODES[0] && isEmpty(rc, s, 0, placement)) {
    175                    if (isEmpty(rc, s, 2, placement) != isEmpty(rc, s, 4, placement)) ret ++;
    176                    if (!isEmpty(rc, s, 2, placement) && !isEmpty(rc, s, 4, placement)) ret --;
    177                } else if (d == Constants.DAY_CODES[2] && isEmpty(rc, s, 2, placement)) {
    178                    if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 4, placement)) ret ++;
    179                    if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 4, placement)) ret --;
    180                } else if (d == Constants.DAY_CODES[4] && isEmpty(rc, s, 4, placement)) {
    181                    if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 2, placement)) ret ++;
    182                    if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 2, placement)) ret --;
    183                } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[2]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 2, placement)) {
    184                    if (isEmpty(rc, s, 4, placement)) ret ++;
    185                } else if (d == (Constants.DAY_CODES[2] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 2, placement) && isEmpty(rc, s, 4, placement)) {
    186                    if (isEmpty(rc, s, 0, placement)) ret ++;
    187                } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 4, placement)) {
    188                    if (isEmpty(rc, s, 2, placement)) ret ++;
    189                }
    190            }
    191        }
    192        if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) {
    193            for (int s = slot; s < slot + time.getLength(); s++) {
    194                if (isEmpty(rc, s, 1, placement) && isEmpty(rc, s, 3, placement)) ret ++;
    195                int d = (days & sDaysTTh);
    196                if (d == Constants.DAY_CODES[1] && isEmpty(rc, s, 1, placement) && !isEmpty(rc, s, 3, placement)) ret --;
    197                if (d == Constants.DAY_CODES[3] && isEmpty(rc, s, 3, placement) && !isEmpty(rc, s, 1, placement)) ret --;
    198            }
    199        }
    200        return ret;
    201    }
    202
    203    /** Number of useless slots for this room
    204     * @param rc room constraint
    205     * @return current penalty for the given room
    206     **/
    207    public static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc) {
    208        int ret = 0;
    209        for (int d = 0; d < Constants.NR_DAYS; d++) {
    210            for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) {
    211                int slot = d * Constants.SLOTS_PER_DAY + s;
    212                if (rc.getPlacements(slot).isEmpty()) {
    213                    switch (d) {
    214                        case 0:
    215                            if (!rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
    216                                ret++;
    217                            break;
    218                        case 1:
    219                            if (!rc.getPlacements(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
    220                                ret++;
    221                            break;
    222                        case 2:
    223                            if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
    224                                ret++;
    225                            break;
    226                        case 3:
    227                            if (!rc.getPlacements(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
    228                                ret++;
    229                            break;
    230                        case 4:
    231                            if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
    232                                ret++;
    233                            break;
    234                    }
    235                }
    236            }
    237        }
    238        return ret;
    239    }
    240}