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.coursett.model.TimeLocation;
017import org.cpsolver.coursett.model.TimetableModel;
018import org.cpsolver.ifs.assignment.Assignment;
019import org.cpsolver.ifs.criteria.Criterion;
020import org.cpsolver.ifs.model.Model;
021import org.cpsolver.ifs.util.ToolBox;
022
023/**
024 * 
025 * The MaxHalfDays constraint limits the number of half-days of week during which the given set of classes are taught.<br>
026 * It has one parameter: a maximal number of week half-days during which the given set of classes can be placed.<br>
027 * A day is split by noon (which can be changed using General.HalfDaySlot parameter). A class starting before noon is considered
028 * a morning class (despite of its end), a class starting at noon or later is considered an afternoon class.<br>
029 * Reference _MaxHalfDays:4_ translates to a maximum number of 4 half-days a week<br>
030 * 
031 * @version CourseTT 1.3 (University Course Timetabling)<br>
032 *          Copyright (C) 2017 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 MaxHalfDaysFlexibleConstraint extends FlexibleConstraint {
049    private int iMaxHalfDays;
050    private int iNoonSlot = 144;
051    
052    public MaxHalfDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
053        super(id, owner, preference, reference);     
054
055        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HALF_DAYS.getPattern()).matcher(reference);
056        if (matcher.find()) {
057            iMaxHalfDays = Integer.parseInt(matcher.group(2));
058            iConstraintType = FlexibleConstraintType.MAX_HALF_DAYS;           
059        }   
060    }
061    
062    @Override
063    public void setModel(Model<Lecture, Placement> model) {
064        super.setModel(model);
065        iNoonSlot = ((TimetableModel)model).getProperties().getPropertyInt("General.HalfDaySlot", iNoonSlot);
066    }
067    
068    /**
069     * Returns number of half-days in a day
070     */
071    protected int getNrHalfDays() {
072        return 2;
073    }
074    
075    /**
076     * Returns index of the half day
077     * @param time given time
078     * @return 0 for morning, 1 for evening
079     */
080    protected int getHalfDay(TimeLocation time) {
081        return (time.getStartSlot() < iNoonSlot ? 0 : 1);
082    }
083    
084    @Override
085    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
086        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
087    }
088
089    @Override
090    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
091        if (!isHard()) return;
092        
093        MaxHalfDaysFlexibleConstraintContext context = (MaxHalfDaysFlexibleConstraintContext)getContext(assignment);
094        while (context.nrHalfDays(value, conflicts) > iMaxHalfDays) {
095            Set<Lecture> candidates = context.candidates(value, conflicts);
096            if (candidates == null) return;
097            for (Lecture candidate: candidates) {
098                Placement conflict = assignment.getValue(candidate);
099                if (conflict != null)
100                    conflicts.add(conflict);
101            }
102        }
103    }
104    
105    @Override
106    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
107        if (!isHard()) return false;
108        return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrHalfDays(value, null) > iMaxHalfDays;
109    }
110    
111    @Override
112    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
113        return new MaxHalfDaysFlexibleConstraintContext(assignment);
114    }
115    
116    public class MaxHalfDaysFlexibleConstraintContext extends FlexibleConstraintContext {
117        private Set<Lecture> iHalfDayAssignments[] = null;
118        
119        @SuppressWarnings("unchecked")
120        public MaxHalfDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
121            super();
122            iHalfDayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS];
123            for (int i = 0; i < iHalfDayAssignments.length; i++)
124                iHalfDayAssignments[i] = new HashSet<Lecture>();
125            
126            for (Lecture variable: variables()) {
127                Placement value = assignment.getValue(variable);
128                if (value != null) {
129                    for (int i = 0; i < Constants.DAY_CODES.length; i++)
130                        if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
131                            iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
132                }
133            }
134            
135            if (!isHard()) {
136                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
137                if (criterion != null) {
138                    double pref = nrViolations(null, null);
139                    if (pref == 0)
140                        iLastPreference = -Math.abs(iPreference);
141                    else 
142                        iLastPreference = Math.abs(iPreference) * pref;
143                    criterion.inc(assignment, iLastPreference);  
144                }
145            }
146        }
147
148        @Override
149        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
150            for (int i = 0; i < Constants.DAY_CODES.length; i++)
151                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
152                    iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable());
153            updateCriterion(assignment);
154        }
155        
156        @Override
157        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
158            for (int i = 0; i < Constants.DAY_CODES.length; i++)
159                if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0)
160                    iHalfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].remove(value.variable());
161            updateCriterion(assignment);
162        }
163        
164        public int nrHalfDays(Placement value, Set<Placement> conflicts) {
165            int ret = 0;
166            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
167                for (int j = 0; j < getNrHalfDays(); j++) {
168                    int idx = i * getNrHalfDays() + j;
169                    int cnt = iHalfDayAssignments[idx].size();
170                    if (value != null) {
171                        if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(value.getTimeLocation())) cnt ++;
172                        if (iHalfDayAssignments[idx].contains(value.variable())) cnt --; 
173                    }
174                    if (conflicts != null) {
175                        for (Placement conflict: conflicts) {
176                            if (value != null && conflict.variable().equals(value.variable())) continue;
177                            if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
178                        }
179                    }
180                    if (cnt > 0) ret++;                    
181                }
182            }
183            return ret;
184        }
185        
186        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
187            int bestCnt = 0;
188            List<Integer> bestHalfDays = new ArrayList<Integer>();
189            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
190                for (int j = 0; j < getNrHalfDays(); j++) {
191                    int idx = i * getNrHalfDays() + j;
192                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(value.getTimeLocation())) continue;
193                    int cnt = iHalfDayAssignments[idx].size();
194                    if (iHalfDayAssignments[idx].contains(value.variable())) cnt --;
195                    for (Placement conflict: conflicts) {
196                        if (conflict.variable().equals(value.variable())) continue;
197                        if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
198                    }
199                    if (cnt <= 0) continue;
200                    if (bestHalfDays.isEmpty() || bestCnt > cnt) {
201                        bestHalfDays.clear(); bestHalfDays.add(idx); bestCnt = cnt;
202                    } else if (bestCnt == cnt) {
203                        bestHalfDays.add(idx);
204                    }
205                }
206            }
207            return bestHalfDays.isEmpty() ? null : iHalfDayAssignments[ToolBox.random(bestHalfDays)];
208        }
209        
210        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
211            int halfDays = 0;
212            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
213                for (int j = 0; j < getNrHalfDays(); j++) {
214                    int idx = i * getNrHalfDays() + j;
215                    int cnt = iHalfDayAssignments[idx].size();
216                    if (assignments != null) {
217                        for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
218                            Placement assignment = entry.getValue();
219                            if (assignment != null && (assignment.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0 && j == getHalfDay(assignment.getTimeLocation())) cnt ++;
220                        }
221                    }
222                    if (conflicts != null)
223                        for (Placement conflict: conflicts) {
224                            if (assignments != null && assignments.containsKey(conflict.variable())) continue;
225                            if (iHalfDayAssignments[idx].contains(conflict.variable())) cnt --;
226                        }
227                    if (cnt > 0) halfDays ++;
228                }
229            }
230            return (halfDays <= iMaxHalfDays ? 0 : halfDays - iMaxHalfDays);
231        }
232    
233    }
234}