001    package net.sf.cpsolver.coursett.criteria;
002    
003    import java.util.Collection;
004    import java.util.HashSet;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.coursett.Constants;
008    import net.sf.cpsolver.coursett.constraint.RoomConstraint;
009    import net.sf.cpsolver.coursett.model.Lecture;
010    import net.sf.cpsolver.coursett.model.Placement;
011    import net.sf.cpsolver.coursett.model.RoomLocation;
012    import net.sf.cpsolver.coursett.model.TimeLocation;
013    import net.sf.cpsolver.coursett.model.TimetableModel;
014    import net.sf.cpsolver.ifs.util.DataProperties;
015    
016    /**
017     * Broken time patterns. This criterion counts cases when an unused space is in a room
018     * which follows one of the standard MWF or TTh pattern. E.g., there is a penalty of
019     * Monday is available during a time when Wednesday and/or Friday is occupied. The aim
020     * is to use this space if possible in order to leave the available space in a way that 
021     * can be used by MWF or TTh classes.
022     * <br>
023     * 
024     * @version CourseTT 1.2 (University Course Timetabling)<br>
025     *          Copyright (C) 2006 - 2011 Tomas Muller<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     */
043    public class BrokenTimePatterns extends TimetablingCriterion {
044        
045        public BrokenTimePatterns() {
046            iValueUpdateType = ValueUpdateType.NoUpdate;
047        }
048        
049        @Override
050        public double getWeightDefault(DataProperties config) {
051            return Constants.sPreferenceLevelDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1);
052        }
053        
054        @Override
055        public String getPlacementSelectionWeightName() {
056            return "Placement.UselessSlotsWeight";
057        }
058        
059        protected int penalty(Placement value) {
060            if (value.isMultiRoom()) {
061                int ret = 0;
062                for (RoomLocation r : value.getRoomLocations()) {
063                    if (r.getRoomConstraint() == null)
064                        continue;
065                    ret += penalty(r.getRoomConstraint(), value.getTimeLocation());
066                }
067                return ret;
068            } else {
069                return (value.getRoomLocation().getRoomConstraint() == null ? 0 : penalty(value.getRoomLocation().getRoomConstraint(), value.getTimeLocation()));
070            }
071        }
072        
073        protected int penalty(RoomConstraint rc) {
074            return countUselessSlotsBrokenTimePatterns(rc);
075        }
076        
077       protected int penalty(RoomConstraint rc, TimeLocation value) {
078            return countUselessSlotsBrokenTimePatterns(rc, value);
079        }
080    
081       @Override
082        public double getValue(Placement value, Set<Placement> conflicts) {
083            double ret = penalty(value);
084            if (conflicts != null)
085                for (Placement conflict: conflicts)
086                    ret -= penalty(conflict);
087            return ret;
088        }
089        
090        @Override
091        public double getValue(Collection<Lecture> variables) {
092            double ret = 0;
093            Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
094            for (Lecture lect: variables) {
095                if (lect.getAssignment() == null) continue;
096                if (lect.getAssignment().isMultiRoom()) {
097                    for (RoomLocation r : lect.getAssignment().getRoomLocations()) {
098                        if (r.getRoomConstraint() != null && constraints.add(r.getRoomConstraint()))
099                            ret += penalty(r.getRoomConstraint());
100                    }
101                } else if (lect.getAssignment().getRoomLocation().getRoomConstraint() != null && 
102                        constraints.add(lect.getAssignment().getRoomLocation().getRoomConstraint())) {
103                    ret += penalty(lect.getAssignment().getRoomLocation().getRoomConstraint());
104                }
105            }
106            return ret;
107        }
108        
109        @Override
110        protected double[] computeBounds() {
111            return new double[] {
112                    ((TimetableModel)getModel()).getRoomConstraints().size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
113                    0.0
114            };
115        }
116        
117        @Override
118        public double[] getBounds(Collection<Lecture> variables) {
119            Set<RoomConstraint> constraints = new HashSet<RoomConstraint>();
120            for (Lecture lect: variables) {
121                if (lect.getAssignment() == null) continue;
122                if (lect.getAssignment().isMultiRoom()) {
123                    for (RoomLocation r : lect.getAssignment().getRoomLocations()) {
124                        if (r.getRoomConstraint() != null)
125                            constraints.add(r.getRoomConstraint());
126                    }
127                } else if (lect.getAssignment().getRoomLocation().getRoomConstraint() != null) {
128                    constraints.add(lect.getAssignment().getRoomLocation().getRoomConstraint());
129                }
130            }
131            return new double[] {
132                    constraints.size() * Constants.SLOTS_PER_DAY_NO_EVENINGS * Constants.NR_DAYS_WEEK,
133                    0.0 };
134        }
135        
136        private static int sDaysMWF = Constants.DAY_CODES[0] + Constants.DAY_CODES[2] + Constants.DAY_CODES[4];
137        private static int sDaysTTh = Constants.DAY_CODES[1] + Constants.DAY_CODES[3];
138    
139        /** Number of broken time patterns for this room */
140        protected static int countUselessSlotsBrokenTimePatterns(RoomConstraint rc, TimeLocation time) {
141            int ret = 0;
142            int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY;
143            int days = time.getDayCode();
144            if ((days & sDaysMWF) != 0 && (days & sDaysMWF) != sDaysMWF) {
145                for (int s = slot; s < slot + time.getLength(); s++) {
146                    int nrEmpty = 0;
147                    if ((Constants.DAY_CODES[0] & days) == 0 && rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty())
148                        nrEmpty++;
149                    if ((Constants.DAY_CODES[2] & days) == 0 && rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
150                        nrEmpty++;
151                    if ((Constants.DAY_CODES[4] & days) == 0 && rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
152                        nrEmpty++;
153                    if (nrEmpty > 0)
154                        ret ++;
155                }
156            }
157            if ((days & sDaysTTh) != 0 && (days & sDaysTTh) != sDaysTTh) {
158                for (int s = slot; s < slot + time.getLength(); s++) {
159                    int nrEmpty = 0;
160                    if ((Constants.DAY_CODES[1] & days) == 0 && rc.getResource(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
161                        nrEmpty++;
162                    if ((Constants.DAY_CODES[3] & days) == 0 && rc.getResource(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
163                        nrEmpty++;
164                    if (nrEmpty > 0)
165                        ret ++;
166                }
167            }
168            return ret / 6;
169        }
170        
171        /** Number of useless slots for this room */
172        public static int countUselessSlotsBrokenTimePatterns(RoomConstraint rc) {
173            int ret = 0;
174            for (int d = 0; d < Constants.NR_DAYS; d++) {
175                for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) {
176                    int slot = d * Constants.SLOTS_PER_DAY + s;
177                    if (rc.getResource(slot).isEmpty()) {
178                        switch (d) {
179                            case 0:
180                                if (!rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty()
181                                        && !rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
182                                    ret++;
183                                break;
184                            case 1:
185                                if (!rc.getResource(3 * Constants.SLOTS_PER_DAY + s).isEmpty())
186                                    ret++;
187                                break;
188                            case 2:
189                                if (!rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty()
190                                        && !rc.getResource(4 * Constants.SLOTS_PER_DAY + s).isEmpty())
191                                    ret++;
192                                break;
193                            case 3:
194                                if (!rc.getResource(1 * Constants.SLOTS_PER_DAY + s).isEmpty())
195                                    ret++;
196                                break;
197                            case 4:
198                                if (!rc.getResource(0 * Constants.SLOTS_PER_DAY + s).isEmpty()
199                                        && !rc.getResource(2 * Constants.SLOTS_PER_DAY + s).isEmpty())
200                                    ret++;
201                                break;
202                        }
203                    }
204                }
205            }
206            return Math.round((1.0f / 6.0f) * ret);
207        }
208    }