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.ifs.assignment.Assignment;
018import org.cpsolver.ifs.criteria.Criterion;
019import org.cpsolver.ifs.util.ToolBox;
020
021/**
022 * 
023 * The MaxDays constraint limits the number of days of week during which the given set of classes are taught.<br>
024 * It has one parameter: a maximal number of week days during which the given set of classes can be placed.<br>
025 * Reference _MaxDays:2_ translates to a maximum number of 2 days a week<br>
026 * 
027 * @version CourseTT 1.3 (University Course Timetabling)<br>
028 *          Copyright (C) 2015 Tomáš Müller<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 MaxDaysFlexibleConstraint extends FlexibleConstraint {
045    private int iMaxDays;
046    
047    public MaxDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
048        super(id, owner, preference, reference);     
049
050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_DAYS.getPattern()).matcher(reference);
051        if (matcher.find()) {
052            iMaxDays = Integer.parseInt(matcher.group(2));
053            iConstraintType = FlexibleConstraintType.MAX_DAYS;           
054        }   
055    }
056    
057    @Override
058    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
059        return ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
060    }
061
062    @Override
063    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
064        if (!isHard()) return;
065        
066        MaxDaysFlexibleConstraintContext context = (MaxDaysFlexibleConstraintContext)getContext(assignment);
067        while (context.nrDays(value, conflicts) > iMaxDays) {
068            Set<Lecture> candidates = context.candidates(value, conflicts);
069            if (candidates == null) {
070                conflicts.add(value);
071                return;
072            }
073            for (Lecture candidate: candidates) {
074                Placement conflict = assignment.getValue(candidate);
075                if (conflict != null)
076                    conflicts.add(conflict);
077            }
078        }
079    }
080    
081    @Override
082    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
083        if (!isHard()) return false;
084        return ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays;
085    }
086    
087    @Override
088    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
089        return new MaxDaysFlexibleConstraintContext(assignment);
090    }
091    
092    public class MaxDaysFlexibleConstraintContext extends FlexibleConstraintContext {
093        private Map<BitSet, Set<Lecture>[]> iWeekDayAssignments = null;
094        private Set<Lecture> iDayAssignments[] = null;
095        
096        public MaxDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
097            super();
098            for (BitSet week: getWeeks()) {
099                Set<Lecture>[] dayAssignments = getDayAssignments(week);            
100                for (Lecture variable: variables()) {
101                    Placement value = assignment.getValue(variable);
102                    if (value != null) {
103                        for (int i = 0; i < dayAssignments.length; i++)
104                            if (hasDay(week, i, value))
105                                dayAssignments[i].add(value.variable());
106                    }
107                }
108            }
109            
110            if (!isHard()) {
111                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
112                if (criterion != null) {
113                    double pref = nrViolations(null, null);
114                    if (pref == 0)
115                        iLastPreference = -Math.abs(iPreference);
116                    else 
117                        iLastPreference = Math.abs(iPreference) * pref;
118                    criterion.inc(assignment, iLastPreference);  
119                }
120            }
121        }
122        
123        protected boolean hasDay(BitSet week, int dayOfWeek, Placement value) {
124            if (value == null || value.getTimeLocation() == null) return false;
125            if (isPreciseDateComputation())
126                return value.getTimeLocation().hasDate(dayOfWeek, week, getDayOfWeekOffset());
127            if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false;
128            return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
129        }
130        
131        @SuppressWarnings("unchecked")
132        protected Set<Lecture>[] getDayAssignments(BitSet week) {
133            if (week == null) {
134                if (iDayAssignments == null) {
135                    iDayAssignments = new Set[Constants.NR_DAYS];
136                    for (int i = 0; i < iDayAssignments.length; i++)
137                        iDayAssignments[i] = new HashSet<Lecture>();
138                }
139                return iDayAssignments;
140            } else {
141                if (iWeekDayAssignments == null)
142                    iWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>();
143                Set<Lecture>[] dayAssignments = iWeekDayAssignments.get(week);
144                if (dayAssignments == null) {
145                    dayAssignments = new Set[Constants.NR_DAYS];
146                    for (int i = 0; i < dayAssignments.length; i++)
147                        dayAssignments[i] = new HashSet<Lecture>();
148                    iWeekDayAssignments.put(week, dayAssignments);
149                }
150                return dayAssignments;
151            }
152        }
153
154        @Override
155        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
156            for (BitSet week: getWeeks()) {
157                Set<Lecture>[] dayAssignments = getDayAssignments(week);
158                for (int i = 0; i < dayAssignments.length; i++)
159                    if (hasDay(week, i, value))
160                        dayAssignments[i].add(value.variable());
161            }
162            updateCriterion(assignment);
163        }
164        
165        @Override
166        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
167            for (BitSet week: getWeeks()) {
168                Set<Lecture>[] dayAssignments = getDayAssignments(week);
169                for (int i = 0; i < dayAssignments.length; i++)
170                    if (hasDay(week, i, value))
171                        dayAssignments[i].remove(value.variable());
172            }
173            updateCriterion(assignment);
174        }
175        
176        public int nrDays(BitSet week, Placement value, Set<Placement> conflicts) {
177            Set<Lecture>[] dayAssignments = getDayAssignments(week);
178            int ret = 0;
179            for (int i = 0; i < dayAssignments.length; i++) {
180                int cnt = dayAssignments[i].size();
181                if (value != null) {
182                    if (hasDay(week, i, value)) cnt ++;
183                    if (dayAssignments[i].contains(value.variable())) cnt --; 
184                }
185                if (conflicts != null) {
186                    for (Placement conflict: conflicts) {
187                        if (value != null && conflict.variable().equals(value.variable())) continue;
188                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
189                    }
190                }
191                if (cnt > 0) ret++;
192            }
193            return ret;
194        }
195        
196        public int nrDays(Placement value, Set<Placement> conflicts) {
197            int ret = 0; 
198            for (BitSet week: getWeeks()) {
199                int days = nrDays(week, value, conflicts);
200                if (days > ret) ret = days;
201            }
202            return ret;
203        }
204        
205        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
206            for (BitSet week: getWeeks()) {
207                Set<Lecture>[] dayAssignments = getDayAssignments(week);
208                int bestCnt = 0;
209                int nrDays = 0;
210                List<Integer> bestWeeks = new ArrayList<Integer>();
211                for (int i = 0; i < dayAssignments.length; i++) {
212                    if (hasDay(week, i, value)) {
213                        nrDays++;
214                        continue;
215                    }
216                    int cnt = dayAssignments[i].size();
217                    if (dayAssignments[i].contains(value.variable())) cnt --;
218                    for (Placement conflict: conflicts) {
219                        if (conflict.variable().equals(value.variable())) continue;
220                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
221                    }
222                    if (cnt <= 0) continue;
223                    nrDays ++;
224                    if (bestWeeks.isEmpty() || bestCnt > cnt) {
225                        bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt;
226                    } else if (bestCnt == cnt) {
227                        bestWeeks.add(i);
228                    }
229                }
230                if (!bestWeeks.isEmpty() && nrDays > iMaxDays) return dayAssignments[ToolBox.random(bestWeeks)];
231            }
232            return null;
233        }
234        
235        public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
236            Set<Lecture>[] dayAssignments = getDayAssignments(week);
237            int days = 0;
238            for (int i = 0; i < dayAssignments.length; i++) {
239                int cnt = dayAssignments[i].size();
240                if (assignments != null) {
241                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
242                        Placement assignment = entry.getValue();
243                        if (assignment != null && hasDay(week, i, assignment)) cnt ++;
244                    }
245                }
246                if (conflicts != null)
247                    for (Placement conflict: conflicts) {
248                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
249                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
250                    }
251                if (cnt > 0) days ++;
252            }
253            return (days <= iMaxDays ? 0 : days - iMaxDays);
254        }
255        
256        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
257            int ret = 0; 
258            for (BitSet week: getWeeks()) {
259                ret += nrViolations(week, assignments, conflicts);
260            }
261            return ret;
262        }
263    }
264}