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