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