Source code

001package org.cpsolver.coursett.constraint;
002
003import java.util.ArrayList;
004import java.util.BitSet;
005import java.util.HashMap;
006import java.util.HashSet;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010import java.util.regex.Matcher;
011import java.util.regex.Pattern;
012
013import org.cpsolver.coursett.Constants;
014import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
015import org.cpsolver.coursett.model.Lecture;
016import org.cpsolver.coursett.model.Placement;
017import org.cpsolver.coursett.model.TimeLocation;
018import org.cpsolver.coursett.model.TimetableModel;
019import org.cpsolver.ifs.assignment.Assignment;
020import org.cpsolver.ifs.criteria.Criterion;
021import org.cpsolver.ifs.model.Model;
022import org.cpsolver.ifs.util.ToolBox;
023
024/**
025 * 
026 * The MaxHalfDays constraint limits the number of half-days of week during which the given set of classes are taught.<br>
027 * It has one parameter: a maximal number of week half-days during which the given set of classes can be placed.<br>
028 * A day is split by noon (which can be changed using General.HalfDaySlot parameter). A class starting before noon is considered
029 * a morning class (despite of its end), a class starting at noon or later is considered an afternoon class.<br>
030 * Reference _MaxHalfDays:4_ translates to a maximum number of 4 half-days a week<br>
031 * 
032 * @version CourseTT 1.3 (University Course Timetabling)<br>
033 *          Copyright (C) 2017 Tomáš Müller<br>
034 * <br>
035 *          This library is free software; you can redistribute it and/or modify
036 *          it under the terms of the GNU Lesser General Public License as
037 *          published by the Free Software Foundation; either version 3 of the
038 *          License, or (at your option) any later version. <br>
039 * <br>
040 *          This library is distributed in the hope that it will be useful, but
041 *          WITHOUT ANY WARRANTY; without even the implied warranty of
042 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
043 *          Lesser General Public License for more details. <br>
044 * <br>
045 *          You should have received a copy of the GNU Lesser General Public
046 *          License along with this library; if not see
047 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
048 */
049public class MaxHalfDaysFlexibleConstraint extends FlexibleConstraint {
050    private int iMaxHalfDays;
051    private int iNoonSlot = 144;
052    
053    public MaxHalfDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
054        super(id, owner, preference, reference);     
055
056        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HALF_DAYS.getPattern()).matcher(reference);
057        if (matcher.find()) {
058            iMaxHalfDays = Integer.parseInt(matcher.group(2));
059            iConstraintType = FlexibleConstraintType.MAX_HALF_DAYS;           
060        }   
061    }
062    
063    @Override
064    public void setModel(Model<Lecture, Placement> model) {
065        super.setModel(model);
066        iNoonSlot = ((TimetableModel)model).getProperties().getPropertyInt("General.HalfDaySlot", iNoonSlot);
067    }
068    
069    /**
070     * Returns number of half-days in a day
071     */
072    protected int getNrHalfDays() {
073        return 2;
074    }
075    
076    /**
077     * Returns index of the half day
078     * @param time given time
079     * @return 0 for morning, 1 for evening
080     */
081    protected int getHalfDay(TimeLocation time) {
082        return (time.getStartSlot() < iNoonSlot ? 0 : 1);
083    }
084    
085    @Override
086    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
087        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
088    }
089
090    @Override
091    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
092        if (!isHard()) return;
093        
094        MaxHalfDaysFlexibleConstraintContext context = (MaxHalfDaysFlexibleConstraintContext)getContext(assignment);
095        while (context.nrHalfDays(value, conflicts) > iMaxHalfDays) {
096            Set<Lecture> candidates = context.candidates(value, conflicts);
097            if (candidates == null) {
098                conflicts.add(value);
099                return;
100            }
101            for (Lecture candidate: candidates) {
102                Placement conflict = assignment.getValue(candidate);
103                if (conflict != null)
104                    conflicts.add(conflict);
105            }
106        }
107    }
108    
109    @Override
110    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
111        if (!isHard()) return false;
112        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrHalfDays(value, null) > iMaxHalfDays;
113    }
114    
115    @Override
116    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
117        return new MaxHalfDaysFlexibleConstraintContext(assignment);
118    }
119    
120    public class MaxHalfDaysFlexibleConstraintContext extends FlexibleConstraintContext {
121        private Map<BitSet, Set<Lecture>[]> iHalfWeekDayAssignments = null;
122        private Set<Lecture> iHalfDayAssignments[] = null;
123        
124        public MaxHalfDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
125            super();
126            for (BitSet week: getWeeks()) {
127                Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
128                for (Lecture variable: variables()) {
129                    Placement value = assignment.getValue(variable);
130                    if (value != null) {
131                        for (int i = 0; i < Constants.DAY_CODES.length; i++)
132                            if (hasDay(week, i, value))
133                                halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
134                    }
135                }
136            }
137            if (!isHard()) {
138                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
139                if (criterion != null) {
140                    double pref = nrViolations(null, null);
141                    if (pref == 0)
142                        iLastPreference = -Math.abs(iPreference);
143                    else 
144                        iLastPreference = Math.abs(iPreference) * pref;
145                    criterion.inc(assignment, iLastPreference);  
146                }
147            }
148        }
149
150        protected boolean hasDay(BitSet week, int dayOfWeek, Placement value) {
151            if (value == null || value.getTimeLocation() == null) return false;
152            if (isPreciseDateComputation())
153                return value.getTimeLocation().hasDate(dayOfWeek, week, getDayOfWeekOffset());
154            if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false;
155            return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
156        }
157        
158        @SuppressWarnings("unchecked")
159        protected Set<Lecture>[] getHalfDayAssignments(BitSet week) {
160            if (week == null) {
161                if (iHalfDayAssignments == null) {
162                    iHalfDayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS];
163                    for (int i = 0; i < iHalfDayAssignments.length; i++)
164                        iHalfDayAssignments[i] = new HashSet<Lecture>();
165                }
166                return iHalfDayAssignments;
167            } else {
168                if (iHalfWeekDayAssignments == null)
169                    iHalfWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>();
170                Set<Lecture>[] dayAssignments = iHalfWeekDayAssignments.get(week);
171                if (dayAssignments == null) {
172                    dayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS];
173                    for (int i = 0; i < dayAssignments.length; i++)
174                        dayAssignments[i] = new HashSet<Lecture>();
175                    iHalfWeekDayAssignments.put(week, dayAssignments);
176                }
177                return dayAssignments;
178            }
179        }
180
181        @Override
182        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
183            for (BitSet week: getWeeks()) {
184                Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
185                for (int i = 0; i < Constants.DAY_CODES.length; i++)
186                    if (hasDay(week, i, value))
187                        halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
188            }
189            updateCriterion(assignment);
190        }
191        
192        @Override
193        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
194            for (BitSet week: getWeeks()) {
195                Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
196                for (int i = 0; i < Constants.DAY_CODES.length; i++)
197                    if (hasDay(week, i, value))
198                        halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].remove(value.variable());
199            }
200            updateCriterion(assignment);
201        }
202        
203        public int nrHalfDays(BitSet week, Placement value, Set<Placement> conflicts) {
204            Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
205            int ret = 0;
206            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
207                for (int j = 0; j < getNrHalfDays(); j++) {
208                    int idx = i * getNrHalfDays() + j;
209                    int cnt = halfDayAssignments[idx].size();
210                    if (value != null) {
211                        if (hasDay(week, i, value) && j == getHalfDay(value.getTimeLocation())) cnt ++;
212                        if (halfDayAssignments[idx].contains(value.variable())) cnt --; 
213                    }
214                    if (conflicts != null) {
215                        for (Placement conflict: conflicts) {
216                            if (value != null && conflict.variable().equals(value.variable())) continue;
217                            if (halfDayAssignments[idx].contains(conflict.variable())) cnt --;
218                        }
219                    }
220                    if (cnt > 0) ret++;                    
221                }
222            }
223            return ret;
224        }
225        
226        public int nrHalfDays(Placement value, Set<Placement> conflicts) {
227            int ret = 0;
228            for (BitSet week: getWeeks()) {
229                int days = nrHalfDays(week, value, conflicts);
230                if (days > ret) ret = days;
231            }
232            return ret;
233        }
234        
235        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
236            for (BitSet week: getWeeks()) {
237                Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
238                int bestCnt = 0;
239                int nrHalfDays = 0;
240                List<Integer> bestHalfDays = new ArrayList<Integer>();
241                for (int i = 0; i < Constants.DAY_CODES.length; i++) {
242                    for (int j = 0; j < getNrHalfDays(); j++) {
243                        int idx = i * getNrHalfDays() + j;
244                        if (hasDay(week, i, value) && j == getHalfDay(value.getTimeLocation())) {
245                            nrHalfDays ++;
246                            continue;
247                        }
248                        int cnt = halfDayAssignments[idx].size();
249                        if (halfDayAssignments[idx].contains(value.variable())) cnt --;
250                        for (Placement conflict: conflicts) {
251                            if (conflict.variable().equals(value.variable())) continue;
252                            if (halfDayAssignments[idx].contains(conflict.variable())) cnt --;
253                        }
254                        if (cnt <= 0) continue;
255                        nrHalfDays ++;
256                        if (bestHalfDays.isEmpty() || bestCnt > cnt) {
257                            bestHalfDays.clear(); bestHalfDays.add(idx); bestCnt = cnt;
258                        } else if (bestCnt == cnt) {
259                            bestHalfDays.add(idx);
260                        }
261                    }
262                }
263                if (!bestHalfDays.isEmpty() && nrHalfDays > iMaxHalfDays) return halfDayAssignments[ToolBox.random(bestHalfDays)];
264            }
265            return null;
266        }
267        
268        public int nrViolations(BitSet week,HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
269            Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week);
270            int halfDays = 0;
271            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
272                for (int j = 0; j < getNrHalfDays(); j++) {
273                    int idx = i * getNrHalfDays() + j;
274                    int cnt = halfDayAssignments[idx].size();
275                    if (assignments != null) {
276                        for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
277                            Placement assignment = entry.getValue();
278                            if (assignment != null && hasDay(week, i, assignment) && j == getHalfDay(assignment.getTimeLocation())) cnt ++;
279                        }
280                    }
281                    if (conflicts != null)
282                        for (Placement conflict: conflicts) {
283                            if (assignments != null && assignments.containsKey(conflict.variable())) continue;
284                            if (halfDayAssignments[idx].contains(conflict.variable())) cnt --;
285                        }
286                    if (cnt > 0) halfDays ++;
287                }
288            }
289            return (halfDays <= iMaxHalfDays ? 0 : halfDays - iMaxHalfDays);
290        }
291        
292        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
293            int ret = 0; 
294            for (BitSet week: getWeeks()) {
295                ret += nrViolations(week, assignments, conflicts);
296            }
297            return ret;
298        }
299    }
300}