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.criteria.FlexibleConstraintCriterion;
014import org.cpsolver.coursett.model.Lecture;
015import org.cpsolver.coursett.model.Placement;
016import org.cpsolver.coursett.model.TimetableModel;
017import org.cpsolver.ifs.assignment.Assignment;
018import org.cpsolver.ifs.criteria.Criterion;
019import org.cpsolver.ifs.util.ToolBox;
020
021/**
022 * 
023 * The MaxWeeks constraint limits the number of weeks during which the given set of classes are taught.<br>
024 * It has two parameters: a maximal number of weeks during which the given set of classes can be placed
025 * and a day code indicating what days of week are considered.<br>
026 * Reference _MaxWeeks:3:6_ translates to a maximum number of 3 weeks, but only for classes that are placed on Fridays and Saturdays
027 * (64 for Monday, 32 for Tuesday, 16 for Wednesday, 8 for Thursday, 4 for Friday, 2 for Saturday, and 1 for Sunday).
028 * If the second parameter is zero, all days of week are considered.<br>
029 * 
030 * @version CourseTT 1.3 (University Course Timetabling)<br>
031 *          Copyright (C) 2013 - 2014 Tomáš Müller<br>
032 * <br>
033 *          This library is free software; you can redistribute it and/or modify
034 *          it under the terms of the GNU Lesser General Public License as
035 *          published by the Free Software Foundation; either version 3 of the
036 *          License, or (at your option) any later version. <br>
037 * <br>
038 *          This library is distributed in the hope that it will be useful, but
039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
041 *          Lesser General Public License for more details. <br>
042 * <br>
043 *          You should have received a copy of the GNU Lesser General Public
044 *          License along with this library; if not see
045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046 */
047public class MaxWeeksFlexibleConstraint extends FlexibleConstraint {
048    private int iMaxWeeks;
049    private int iDayCode;
050    
051    public MaxWeeksFlexibleConstraint(Long id, String owner, String preference, String reference) {
052        super(id, owner, preference, reference);     
053
054        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_WEEKS.getPattern()).matcher(reference);
055        if (matcher.find()) {
056            iMaxWeeks = Integer.parseInt(matcher.group(2));
057            iDayCode = Integer.parseInt(matcher.group(3));
058            iConstraintType = FlexibleConstraintType.MAX_WEEKS;           
059        }   
060    }
061    
062    public boolean isCorectDayOfWeek(Placement value) {
063        return value != null && value.getTimeLocation() != null && (iDayCode == 0 || (iDayCode & value.getTimeLocation().getDayCode()) != 0);
064    }
065
066    @Override
067    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
068        return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
069    }
070
071    @Override
072    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
073        if (!isHard() || !isCorectDayOfWeek(value)) return;
074        
075        MaxWeeksFlexibleConstraintContext context = (MaxWeeksFlexibleConstraintContext)getContext(assignment);
076        while (context.nrWeeks(value, conflicts) > iMaxWeeks) {
077            Set<Lecture> candidates = context.candidates(value, conflicts);
078            if (candidates == null) return;
079            for (Lecture candidate: candidates) {
080                Placement conflict = assignment.getValue(candidate);
081                if (conflict != null)
082                    conflicts.add(conflict);
083            }
084        }
085    }
086    
087    @Override
088    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
089        if (!isHard() || !isCorectDayOfWeek(value)) return false;
090        return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrWeeks(value, null) > iMaxWeeks;
091    }
092    
093    @Override
094    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
095        return new MaxWeeksFlexibleConstraintContext(assignment);
096    }
097
098    public class MaxWeeksFlexibleConstraintContext extends FlexibleConstraintContext {
099        private List<BitSet> iWeeks = null;
100        private Set<Lecture> iWeekAssignments[] = null;
101        
102        @SuppressWarnings("unchecked")
103        public MaxWeeksFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
104            super();
105            iWeeks = ((TimetableModel)getModel()).getWeeks();
106            iWeekAssignments = new Set[iWeeks.size()];
107            for (int i = 0; i < iWeekAssignments.length; i++)
108                iWeekAssignments[i] = new HashSet<Lecture>();
109            
110            for (Lecture variable: variables()) {
111                Placement value = assignment.getValue(variable);
112                if (value != null && isCorectDayOfWeek(value)) {
113                    for (int i = 0; i < iWeeks.size(); i++)
114                        if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
115                            iWeekAssignments[i].add(value.variable());
116                }
117            }
118            
119            if (!isHard()) {
120                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
121                if (criterion != null) {
122                    double pref = nrViolations(null, null);
123                    if (pref == 0)
124                        iLastPreference = -Math.abs(iPreference);
125                    else 
126                        iLastPreference = Math.abs(iPreference) * pref;
127                    criterion.inc(assignment, iLastPreference);  
128                }
129            }
130        }
131
132        @Override
133        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
134            if (isCorectDayOfWeek(value)) {
135                for (int i = 0; i < iWeeks.size(); i++)
136                    if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
137                        iWeekAssignments[i].add(value.variable());
138                updateCriterion(assignment);
139            }
140        }
141        
142        @Override
143        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
144            if (isCorectDayOfWeek(value)) {
145                for (int i = 0; i < iWeeks.size(); i++)
146                    if (value.getTimeLocation().shareWeeks(iWeeks.get(i)))
147                        iWeekAssignments[i].remove(value.variable());
148                updateCriterion(assignment);
149            }
150        }
151        
152        public int nrWeeks(Placement value, Set<Placement> conflicts) {
153            int ret = 0;
154            for (int i = 0; i < iWeeks.size(); i++) {
155                BitSet w = iWeeks.get(i);
156                int cnt = iWeekAssignments[i].size();
157                if (value != null) {
158                    if (value.getTimeLocation().shareWeeks(w)) cnt ++;
159                    if (iWeekAssignments[i].contains(value.variable())) cnt --; 
160                }
161                if (conflicts != null) {
162                    for (Placement conflict: conflicts) {
163                        if (value != null && conflict.variable().equals(value.variable())) continue;
164                        if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
165                    }
166                }
167                if (cnt > 0) ret++;
168            }
169            return ret;
170        }
171        
172        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
173            int bestCnt = 0;
174            List<Integer> bestWeeks = new ArrayList<Integer>();
175            for (int i = 0; i < iWeeks.size(); i++) {
176                BitSet w = iWeeks.get(i);
177                if (value.getTimeLocation().shareWeeks(w)) continue;
178                int cnt = iWeekAssignments[i].size();
179                if (iWeekAssignments[i].contains(value.variable())) cnt --;
180                for (Placement conflict: conflicts) {
181                    if (conflict.variable().equals(value.variable())) continue;
182                    if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
183                }
184                if (cnt <= 0) continue;
185                if (bestWeeks.isEmpty() || bestCnt > cnt) {
186                    bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt;
187                } else if (bestCnt == cnt) {
188                    bestWeeks.add(i);
189                }
190            }
191            return bestWeeks.isEmpty() ? null : iWeekAssignments[ToolBox.random(bestWeeks)];
192        }
193        
194        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
195            int weeks = 0;
196            for (int i = 0; i < iWeeks.size(); i++) {
197                BitSet w = iWeeks.get(i);
198                int cnt = iWeekAssignments[i].size();
199                if (assignments != null) {
200                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
201                        if (isCorectDayOfWeek(entry.getValue()) && entry.getValue().getTimeLocation().shareWeeks(w)) cnt ++;
202                        if (iWeekAssignments[i].contains(entry.getKey())) cnt --; 
203                    }
204                }
205                if (conflicts != null)
206                    for (Placement conflict: conflicts) {
207                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
208                        if (iWeekAssignments[i].contains(conflict.variable())) cnt --;
209                    }
210                if (cnt > 0) weeks ++;
211            }
212            return (weeks <= iMaxWeeks ? 0 : weeks - iMaxWeeks);
213        }
214    
215    }
216}