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.concurrent.ConcurrentHashMap;
010
011import org.cpsolver.coursett.model.Lecture;
012import org.cpsolver.coursett.model.Placement;
013import org.cpsolver.coursett.model.Student;
014import org.cpsolver.coursett.model.TimetableModel;
015import org.cpsolver.ifs.assignment.Assignment;
016import org.cpsolver.ifs.model.Constraint;
017import org.cpsolver.ifs.model.GlobalConstraint;
018import org.cpsolver.ifs.model.Model;
019import org.cpsolver.ifs.model.ModelListener;
020import org.cpsolver.ifs.solver.Solver;
021import org.cpsolver.ifs.util.DataProperties;
022import org.cpsolver.ifs.util.DistanceMetric;
023
024/**
025 * An experimental global constraint that does not allow any two classes that can be attended
026 * by the same student to have a conflict. The constraint checks any two classes of different
027 * offerings that share at least one student and that the student is allowed to take (not restricted
028 * by reservations). Class pairs included in the Ignore Student Conflicts constraints are ignored.
029 * Some classes may be excluded by using ExtendedStudentConflicts.IgnoreClasses parameter which may
030 * contain a regular expression matching class name(s).
031 * <br>
032 * Pairs of classes of the same offering are checked, too. In this case, the course structure must
033 * allow the two classes to be attended together (e.g., they are from the same configuration), and at
034 * least one student in the offering is allowed to take both classes. This feature can be disabled by
035 * setting ExtendedStudentConflicts.CheckSameCourse to false.
036 * <br>
037 * @version CourseTT 1.3 (University Course Timetabling)<br>
038 *          Copyright (C) 2013 - 2024 Tomáš Müller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 */
056public class ExtendedStudentConflicts extends GlobalConstraint<Lecture, Placement> implements ModelListener<Lecture, Placement>{
057    private String iIgnoreClasses = null;
058    private Map<Long, Map<Long, List<Student>>> iCommonStudents = null;
059    private Set<Long> iIgnoreClassIds = null;
060    private Map<Long, Map<Long, Boolean>> iClassCache = new ConcurrentHashMap<Long, Map<Long, Boolean>>();
061    private boolean iCheckSameCourse = true;
062    
063    @Override
064    public void setModel(Model<Lecture, Placement> model) {
065        super.setModel(model);
066        if (model != null && model instanceof TimetableModel) {
067            DataProperties config = ((TimetableModel)model).getProperties();
068            iIgnoreClasses = config.getProperty("ExtendedStudentConflicts.IgnoreClasses");
069            iCheckSameCourse = config.getPropertyBoolean("ExtendedStudentConflicts.CheckSameCourse", true);
070        }
071    }
072    
073    protected void clearCache() {
074        iClassCache.clear();
075        iCommonStudents = null;
076        iIgnoreClassIds = null;
077    }
078    
079    private DistanceMetric getDistanceMetric() {
080        return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
081    }
082    
083    protected List<Student> getCommonStudents(Long offeringId1, Long offeringId2) {
084        if (iCommonStudents == null) {
085            iCommonStudents = new ConcurrentHashMap<Long, Map<Long, List<Student>>>();
086            for (Lecture lecture: getModel().variables()) {
087                if (lecture.isCommitted() || lecture.getConfiguration() == null) continue;
088                Map<Long, List<Student>> commonStudents = iCommonStudents.get(lecture.getConfiguration().getOfferingId());
089                if (commonStudents != null) continue;
090                commonStudents = new ConcurrentHashMap<Long, List<Student>>();
091                iCommonStudents.put(lecture.getConfiguration().getOfferingId(), commonStudents);
092                for (Lecture other: getModel().variables()) {
093                    if (other.isCommitted() || other.getConfiguration() == null) continue;
094                    // if (other.getConfiguration().getOfferingId().equals(lecture.getConfiguration().getOfferingId())) continue;
095                    if (commonStudents.containsKey(other.getConfiguration().getOfferingId())) continue;
096                    List<Student> students = new ArrayList<Student>();
097                    for (Student student: ((TimetableModel)getModel()).getAllStudents()) {
098                        if (student.getOfferings().contains(lecture.getConfiguration().getOfferingId()) && student.getOfferings().contains(other.getConfiguration().getOfferingId()))
099                            students.add(student);
100                    }
101                    commonStudents.put(other.getConfiguration().getOfferingId(), students);
102                }
103            }
104        }
105        Map<Long, List<Student>> offeringIds = iCommonStudents.get(offeringId1);
106        return (offeringIds == null ? null :  offeringIds.get(offeringId2));
107    }
108    
109    protected boolean isIgnoreClass(Lecture lecture) {
110        if (iIgnoreClassIds == null) {
111            iIgnoreClassIds = new HashSet<Long>();
112            if (iIgnoreClasses != null && !iIgnoreClasses.isEmpty())
113                for (Lecture l: getModel().variables()) {
114                    if (l.getName().matches(iIgnoreClasses)) iIgnoreClassIds.add(l.getClassId());
115                }
116        }
117        return iIgnoreClassIds.contains(lecture.getClassId());
118        
119    }
120    
121    private Boolean getCachedPair(Lecture l1, Lecture l2) {
122        if (l1.getClassId() < l2.getClassId()) {
123            Map<Long, Boolean> cache = iClassCache.get(l1.getClassId());
124            return (cache == null ? null : cache.get(l2.getClassId()));
125        } else {
126            Map<Long, Boolean> cache = iClassCache.get(l2.getClassId());
127            return (cache == null ? null : cache.get(l1.getClassId()));
128        }
129    }
130    
131    private void setCachedPair(Lecture l1, Lecture l2, boolean value) {
132        if (l1.getClassId() < l2.getClassId()) {
133            Map<Long, Boolean> cache = iClassCache.get(l1.getClassId());
134            if (cache == null) {
135                cache = new ConcurrentHashMap<Long, Boolean>();
136                iClassCache.put(l1.getClassId(), cache);
137            }
138            cache.put(l2.getClassId(), value);
139        } else {
140            Map<Long, Boolean> cache = iClassCache.get(l2.getClassId());
141            if (cache == null) {
142                cache = new ConcurrentHashMap<Long, Boolean>();
143                iClassCache.put(l2.getClassId(), cache);
144            }
145            cache.put(l1.getClassId(), value);
146        }
147    }
148    
149    private boolean checkSameCourseCanTakeTogether(Lecture l1, Lecture l2) {
150        // check if the feature is disabled
151        if (!iCheckSameCourse) return false;
152        // same subpart -> cannot take together
153        if (l1.getSchedulingSubpartId().equals(l2.getSchedulingSubpartId())) return false;
154        // different config -> cannot take together
155        if (!l1.getConfiguration().equals(l2.getConfiguration())) return false;
156        // subpart id > class id (classes that are given by class l1 and its parents)
157        Map<Long, Long> mustTake = new HashMap<Long, Long>();
158        for (Lecture l = l1; l != null; l = l.getParent()) {
159            mustTake.put(l.getSchedulingSubpartId(), l.getClassId());
160        }
161        // also include top-level subparts of the same configuration that have only one class 
162        for (Map.Entry<Long, Set<Lecture>> e: l1.getConfiguration().getTopLectures().entrySet()) {
163            if (e.getValue().size() == 1) {
164                Lecture l = e.getValue().iterator().next();
165                mustTake.put(l.getSchedulingSubpartId(), l.getClassId());
166            }
167        }
168        // check l2 and its parents, if any of them does not follow mustTake -> cannot take together
169        for (Lecture l = l2; l != null; l = l.getParent()) {
170            Long id = mustTake.get(l.getSchedulingSubpartId());
171            if (id != null && !l.getClassId().equals(id)) return false;
172        }
173        // no issue found -> can take together
174        return true;
175    }
176    
177    protected boolean checkStudentForStudentConflicts(Lecture l1, Lecture l2) {
178        // are student conflicts between the two classes to be ignored ?
179        if (l1.isToIgnoreStudentConflictsWith(l2)) return false;
180        // check the cache
181        Boolean cache = getCachedPair(l1, l2);
182        if (cache != null) return cache.booleanValue();
183        // classes of the same offering that cannot be taken together
184        if (l1.getConfiguration().getOfferingId().equals(l2.getConfiguration().getOfferingId()) && !checkSameCourseCanTakeTogether(l1, l2)) {
185            setCachedPair(l1, l2, false);
186            return false;
187        }
188        // ignore matching class pairs
189        if (isIgnoreClass(l1) && isIgnoreClass(l2)) {
190            setCachedPair(l1, l2, false);
191            return false;
192        }
193        // check offerings
194        List<Student> commonStudents = getCommonStudents(l1.getConfiguration().getOfferingId(), l2.getConfiguration().getOfferingId());
195        // less then two students in common > do not check for conflicts
196        if (commonStudents == null || commonStudents.size() <= 1) {
197            setCachedPair(l1, l2, false);
198            return false;
199        }
200        // check if there is a student that can attend l1 and l2 together
201        for (Student student: commonStudents)
202            if (student.canEnroll(l1) && student.canEnroll(l2)) {
203                setCachedPair(l1, l2, true);
204                return true;
205            }
206        // no common students that can attend both classes
207        setCachedPair(l1, l2, false);
208        return false;
209    }
210    
211    @Override
212    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) {
213        Lecture lecture = placement.variable();
214        for (Lecture other: getModel().assignedVariables(assignment)) {
215            Placement otherPlacement = assignment.getValue(other);
216            if (checkStudentForStudentConflicts(lecture, other) && JenrlConstraint.isInConflict(placement, otherPlacement, getDistanceMetric(), 0))
217                conflicts.add(otherPlacement);
218        }
219    }
220    
221    @Override
222    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) {
223        Lecture lecture = placement.variable();
224        for (Lecture other: getModel().assignedVariables(assignment)) {
225            Placement otherPlacement = assignment.getValue(other);
226            if (checkStudentForStudentConflicts(lecture, other) && JenrlConstraint.isInConflict(placement, otherPlacement, getDistanceMetric(), 0))
227                return true;
228        }
229        return false;
230    }
231
232    @Override
233    public boolean isConsistent(Placement p1, Placement p2) {
234        return p1 != null && p2 != null &&
235                checkStudentForStudentConflicts(p1.variable(), p2.variable()) &&
236                JenrlConstraint.isInConflict(p1, p2, getDistanceMetric(), 0);
237    }
238    
239    @Override
240    public String getName() {
241        return "Extended Student Conflicts";
242    }
243    
244    @Override
245    public String toString() {
246        return "Extended Student Conflicts";
247    }
248
249    @Override
250    public void variableAdded(Lecture variable) {
251        clearCache();
252    }
253
254    @Override
255    public void variableRemoved(Lecture variable) {
256        clearCache();
257    }
258
259    @Override
260    public void constraintAdded(Constraint<Lecture, Placement> constraint) {}
261
262    @Override
263    public void constraintRemoved(Constraint<Lecture, Placement> constraint) {}
264
265    @Override
266    public void beforeAssigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {}
267
268    @Override
269    public void beforeUnassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {}
270
271    @Override
272    public void afterAssigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {}
273
274    @Override
275    public void afterUnassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement value) {}
276
277    @Override
278    public boolean init(Solver<Lecture, Placement> solver) {
279        clearCache();
280        return true;
281    }
282}