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 * @version CourseTT 1.3 (University Course Timetabling)<br>
029 *          Copyright (C) 2006 - 2014 Tomas Muller<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 BrokenTimePatterns extends TimetablingCriterion {
048    
049    public BrokenTimePatterns() {
050        setValueUpdateType(ValueUpdateType.NoUpdate);
051    }
052    
053    @Override
054    public double getWeightDefault(DataProperties config) {
055        return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1);
056    }
057    
058    @Override
059    public String getPlacementSelectionWeightName() {
060        return "Placement.UselessSlotsWeight";
061    }
062    
063    protected double penalty(Assignment<Lecture, Placement> assignment, Placement value) {
064        if (value.isMultiRoom()) {
065            int ret = 0;
066            for (RoomLocation r : value.getRoomLocations()) {
067                if (r.getRoomConstraint() == null)
068                    continue;
069                ret += penalty(r.getRoomConstraint().getContext(assignment), value);
070            }
071            return ret;
072        } else {
073            return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint().getContext(assignment), value));
074        }
075    }
076    
077    protected double penalty(RoomConstraintContext rc) {
078        return countUselessSlotsBrokenTimePatterns(rc) / 6.0;
079    }
080    
081    protected double penalty(RoomConstraintContext rc, Placement value) {
082        return countUselessSlotsBrokenTimePatterns(rc, value) / 6.0;
083    }
084
085   @Override
086    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
087        double ret = penalty(assignment, value);
088        if (conflicts != null)
089            for (Placement conflict: conflicts)
090                ret -= penalty(assignment, conflict);
091        return ret;
092    }
093    
094    @Override
095    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
096        double ret = 0;
097        Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
098        for (Lecture lect: variables) {
099            Placement placement = assignment.getValue(lect);
100            if (placement == null) continue;
101            if (placement.isMultiRoom()) {
102                for (RoomLocation r : placement.getRoomLocations()) {
103                    if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint()))
104                        ret += penalty(r.getRoomConstraint().getContext(assignment));
105                }
106            } else if (placement.getRoomLocation().getRoomConstraint() != null && 
107                    constraints.add(placement.getRoomLocation().getRoomConstraint())) {
108                ret += penalty(placement.getRoomLocation().getRoomConstraint().getContext(assignment));
109            }
110        }
111        return ret;
112    }
113    
114    @Override
115    protected double[] computeBounds(Assignment<Lecture, Placement> assignment) {
116        return new double[] {
117                ((TimetableModel)getModel()).getRoomConstraints().size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
118                0.0
119        };
120    }
121    
122    @Override
123    public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
124        Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
125        for (Lecture lect: variables) {
126            Placement placement = assignment.getValue(lect);
127            if (placement == null) continue;
128            if (placement.isMultiRoom()) {
129                for (RoomLocation r : placement.getRoomLocations()) {
130                    if (r.getRoomConstraint() != null)
131                        constraints.add(r.getRoomConstraint());
132                }
133            } else if (placement.getRoomLocation().getRoomConstraint() != null) {
134                constraints.add(placement.getRoomLocation().getRoomConstraint());
135            }
136        }
137        return new double[] {
138                constraints.size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
139                0.0 };
140    }
141    
142    private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4];
143    private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3];
144    
145    private static boolean isEmpty(RoomConstraintContext rc, int s, int d, Placement placement) {
146        List<Placement> assigned = rc.getPlacements(d * Constants.SLOTS_PER_DAY + s);
147        return assigned.isEmpty() || (placement != null && assigned.size() == 1 && assigned.get(0).variable().equals(placement.variable()));
148    }
149
150    /** Number of broken time patterns for this room 
151     * @param rc room constraint
152     * @param placement placement that is being considered
153     * @return number of broken time patterns caused by the given placement
154     **/
155    protected static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc, Placement placement) {
156        int ret = 0;
157        TimeLocation time = placement.getTimeLocation();
158        int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY;
159        int days = time.getDayCode();
160        if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) {
161            for (int s = slot; s < slot + time.getLength(); s++) {
162                int d = (days & sDaysMWF);
163                if (d == Constants.DAY_CODES[0] && isEmpty(rc, s, 0, placement)) {
164                    if (isEmpty(rc, s, 2, placement) != isEmpty(rc, s, 4, placement)) ret ++;
165                    if (!isEmpty(rc, s, 2, placement) && !isEmpty(rc, s, 4, placement)) ret --;
166                } else if (d == Constants.DAY_CODES[2] && isEmpty(rc, s, 2, placement)) {
167                    if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 4, placement)) ret ++;
168                    if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 4, placement)) ret --;
169                } else if (d == Constants.DAY_CODES[4] && isEmpty(rc, s, 4, placement)) {
170                    if (isEmpty(rc, s, 0, placement) != isEmpty(rc, s, 2, placement)) ret ++;
171                    if (!isEmpty(rc, s, 0, placement) && !isEmpty(rc, s, 2, placement)) ret --;
172                } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[2]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 2, placement)) {
173                    if (isEmpty(rc, s, 4, placement)) ret ++;
174                } else if (d == (Constants.DAY_CODES[2] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 2, placement) && isEmpty(rc, s, 4, placement)) {
175                    if (isEmpty(rc, s, 0, placement)) ret ++;
176                } else if (d == (Constants.DAY_CODES[0] | Constants.DAY_CODES[4]) && isEmpty(rc, s, 0, placement) && isEmpty(rc, s, 4, placement)) {
177                    if (isEmpty(rc, s, 2, placement)) ret ++;
178                }
179            }
180        }
181        if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) {
182            for (int s = slot; s < slot + time.getLength(); s++) {
183                if (isEmpty(rc, s, 1, placement) && isEmpty(rc, s, 3, placement)) ret ++;
184                int d = (days & sDaysTTh);
185                if (d == Constants.DAY_CODES[1] && isEmpty(rc, s, 1, placement) && !isEmpty(rc, s, 3, placement)) ret --;
186                if (d == Constants.DAY_CODES[3] && isEmpty(rc, s, 3, placement) && !isEmpty(rc, s, 1, placement)) ret --;
187            }
188        }
189        return ret;
190    }
191    
192    /** Number of useless slots for this room 
193     * @param rc room constraint
194     * @return current penalty for the given room
195     **/
196    public static int countUselessSlotsBrokenTimePatterns(RoomConstraintContext rc) {
197        int ret = 0;
198        for (int d = 0; d < Constants.NR_DAYS; d++) {
199            for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) {
200                int slot = d * Constants.SLOTS_PER_DAY + s;
201                if (rc.getPlacements(slot).isEmpty()) {
202                    switch (d) {
203                        case 0:
204                            if (!rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
205                                ret++;
206                            break;
207                        case 1:
208                            if (!rc.getPlacements(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
209                                ret++;
210                            break;
211                        case 2:
212                            if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
213                                ret++;
214                            break;
215                        case 3:
216                            if (!rc.getPlacements(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
217                                ret++;
218                            break;
219                        case 4:
220                            if (!rc.getPlacements(0 * Constants.SLOTS_PER_DAY + s).isEmpty() && !rc.getPlacements(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
221                                ret++;
222                            break;
223                    }
224                }
225            }
226        }
227        return ret;
228    }
229}