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