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