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