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