001package org.cpsolver.studentsct.constraint;
002
003import java.util.Set;
004
005import org.cpsolver.coursett.Constants;
006import org.cpsolver.coursett.model.TimeLocation;
007import org.cpsolver.ifs.assignment.Assignment;
008import org.cpsolver.ifs.model.GlobalConstraint;
009import org.cpsolver.studentsct.StudentSectioningModel;
010import org.cpsolver.studentsct.extension.StudentQuality;
011import org.cpsolver.studentsct.model.Config;
012import org.cpsolver.studentsct.model.Enrollment;
013import org.cpsolver.studentsct.model.Request;
014import org.cpsolver.studentsct.model.SctAssignment;
015import org.cpsolver.studentsct.model.Section;
016import org.cpsolver.studentsct.model.Student;
017import org.cpsolver.studentsct.model.Unavailability;
018
019/**
020 * Hard distance conflicts constraint. This global constraint checks for distance conflicts
021 * that should not be allowed. These are distance conflicts where the distance betweem the
022 * two sections is longer than HardDistanceConflict.DistanceHardLimitInMinutes minutes (defaults to 60)
023 * and the distance to travel between the two sections is longer than
024 * HardDistanceConflict.AllowedDistanceInMinutes minutes (defaults to 30).
025 * The constraint checks both pairs of sections that the student is to be enrolled in 
026 * and distance conflicts with unavailabilities.
027 * 
028 * @author  Tomáš Müller
029 * @version StudentSct 1.3 (Student Sectioning)<br>
030 *          Copyright (C) 2007 - 2015 Tomáš Müller<br>
031 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
032 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><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 HardDistanceConflicts extends GlobalConstraint<Request, Enrollment> {
049    /**
050     * A given enrollment is conflicting, if there is a section that
051     * is disabled and there is not a matching reservation that would allow for that.
052     * 
053     * @param enrollment {@link Enrollment} that is being considered
054     * @param conflicts all computed conflicting requests are added into this set
055     */
056    @Override
057    public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) {
058        if (enrollment.variable().getModel() == null || !(enrollment.variable().getModel() instanceof StudentSectioningModel)) return;
059        StudentSectioningModel model = (StudentSectioningModel)enrollment.variable().getModel();
060        StudentQuality studentQuality = model.getStudentQuality();
061        if (studentQuality == null) return;
062        StudentQuality.Context cx = studentQuality.getStudentQualityContext();
063        
064        // enrollment's student
065        Student student = enrollment.getStudent();
066        // no unavailabilities > no distance conflicts
067        if (student.getUnavailabilities().isEmpty()) return;
068        
069        // enrollment's config
070        Config config = enrollment.getConfig();
071
072        // exclude free time requests
073        if (config == null) return;
074        
075        // check for an unavailability distance conflict
076        if (cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) {
077            for (Section s1: enrollment.getSections()) {
078                // no time or no room > no conflict
079                if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
080                for (Unavailability s2: student.getUnavailabilities()) {
081                    // no time or no room > no conflict
082                    if (s2.getTime() == null || s2.getNrRooms() == 0) continue;
083                    TimeLocation t1 = s1.getTime();
084                    TimeLocation t2 = s2.getTime();
085                    // no shared day > no conflict
086                    if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
087                    int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
088                    if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
089                        int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
090                        if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes()
091                                && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) {
092                            conflicts.add(enrollment);
093                            return;
094                        }
095                    } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
096                        int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
097                        if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes()
098                                && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes()) {
099                            conflicts.add(enrollment);
100                            return;
101                        }
102                    }
103                }
104            }
105        }
106        
107        // check for distance conflicts within the enrollment
108        if (cx.getDistanceMetric().isHardDistanceConflictsEnabled()) {
109            for (Section s1: enrollment.getSections()) {
110                // no time or no room > no conflict
111                if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
112                for (Section s2: enrollment.getSections()) {
113                    if (s1.getId() < s2.getId()) {
114                        // no time or no room > no conflict
115                        if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
116                        TimeLocation t1 = s1.getTime();
117                        TimeLocation t2 = s2.getTime();
118                        // no shared day > no conflict
119                        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
120                        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
121                        if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
122                            if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
123                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
124                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
125                                        && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
126                                    conflicts.add(enrollment);
127                                    return;
128                                }
129                            } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
130                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
131                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
132                                        && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
133                                    conflicts.add(enrollment);
134                                    return;
135                                }
136                            }
137                        } else {
138                            if (a1 + t1.getNrSlotsPerMeeting() == a2) {
139                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
140                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
141                                        && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
142                                    conflicts.add(enrollment);
143                                    return;
144                                }
145                            } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
146                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
147                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
148                                        && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
149                                    conflicts.add(enrollment);
150                                    return;
151                                }
152                            }
153                        }
154                    }
155                }
156            }
157            
158            // check conflicts with other enrollments of the student
159            other: for (Request other: student.getRequests()) {
160                if (other.equals(enrollment.variable())) continue;
161                Enrollment e2 = other.getAssignment(assignment);
162                if (e2 == null || conflicts.contains(e2)) continue;
163                for (Section s1: enrollment.getSections()) {
164                    // no time or no room > no conflict
165                    if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
166                    for (Section s2: e2.getSections()) {
167                        // no time or no room > no conflict
168                        if (!s2.hasTime() || s2.getNrRooms() == 0) continue;
169                        TimeLocation t1 = s1.getTime();
170                        TimeLocation t2 = s2.getTime();
171                        // no shared day > no conflict
172                        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
173                        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
174                        if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
175                            if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
176                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
177                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
178                                        && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
179                                    conflicts.add(e2);
180                                    continue other;
181                                }
182                            } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
183                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
184                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
185                                        && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
186                                    conflicts.add(e2);
187                                    continue other;
188                                }
189                            }
190                        } else {
191                            if (a1 + t1.getNrSlotsPerMeeting() == a2) {
192                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
193                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
194                                        && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
195                                    conflicts.add(e2);
196                                    continue other;
197                                }
198                            } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
199                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
200                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
201                                        && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes()) {
202                                    conflicts.add(e2);
203                                    continue other;
204                                }
205                            }
206                        }
207                    }
208                }
209            }
210        }
211    }
212    
213    /**
214     * A given enrollment is conflicting, if there is a section that
215     * is disabled and there is not a matching reservation that would allow for that.
216     * 
217     * @param enrollment {@link Enrollment} that is being considered
218     * @return true, if the enrollment does not follow a reservation that must be used 
219     */
220    @Override
221    public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
222        if (enrollment.variable().getModel() == null || !(enrollment.variable().getModel() instanceof StudentSectioningModel)) return false;
223        StudentSectioningModel model = (StudentSectioningModel)enrollment.variable().getModel();
224        StudentQuality studentQuality = model.getStudentQuality();
225        if (studentQuality == null) return false;
226        StudentQuality.Context cx = studentQuality.getStudentQualityContext();
227        
228        // enrollment's student
229        Student student = enrollment.getStudent();
230        // no unavailabilities > no distance conflicts
231        if (student.getUnavailabilities().isEmpty()) return false;
232        
233        // enrollment's config
234        Config config = enrollment.getConfig();
235
236        // exclude free time requests
237        if (config == null) return false;
238        
239        // check for an unavailability distance conflict
240        if (cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) {
241            for (Section s1: enrollment.getSections()) {
242                // no time or no room > no conflict
243                if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
244                for (Unavailability s2: student.getUnavailabilities()) {
245                    // no time or no room > no conflict
246                    if (s2.getTime() == null || s2.getNrRooms() == 0) continue;
247                    TimeLocation t1 = s1.getTime();
248                    TimeLocation t2 = s2.getTime();
249                    // no shared day > no conflict
250                    if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
251                    int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
252                    if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
253                        int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
254                        if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes()
255                                && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes())
256                            return true;
257                    } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
258                        int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
259                        if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes()
260                                && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes())
261                            return true;
262                    }
263                }
264            }
265        }
266        
267        // check for distance conflicts within the enrollment
268        if (cx.getDistanceMetric().isHardDistanceConflictsEnabled()) {
269            for (Section s1: enrollment.getSections()) {
270                // no time or no room > no conflict
271                if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
272                for (Section s2: enrollment.getSections()) {
273                    if (s1.getId() < s2.getId()) {
274                        // no time or no room > no conflict
275                        if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
276                        TimeLocation t1 = s1.getTime();
277                        TimeLocation t2 = s2.getTime();
278                        // no shared day > no conflict
279                        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
280                        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
281                        if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
282                            if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
283                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
284                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() 
285                                       && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
286                                    return true;
287                            } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
288                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
289                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
290                                        && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
291                                    return true;
292                            }
293                        } else {
294                            if (a1 + t1.getNrSlotsPerMeeting() == a2) {
295                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
296                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
297                                        && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes())
298                                    return true;
299                            } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
300                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
301                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes()
302                                        && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes())
303                                    return true;
304                            }
305                        }
306                    }
307                }
308            }
309            
310            // check conflicts with other enrollments of the student
311            for (Request other: student.getRequests()) {
312                if (other.equals(enrollment.variable())) continue;
313                Enrollment e2 = other.getAssignment(assignment);
314                if (e2 == null) continue;
315                for (Section s1: enrollment.getSections()) {
316                    // no time or no room > no conflict
317                    if (!s1.hasTime() || s1.getNrRooms() == 0) continue;
318                    for (Section s2: e2.getSections()) {
319                        // no time or no room > no conflict
320                        if (!s2.hasTime() || s2.getNrRooms() == 0) continue;
321                        TimeLocation t1 = s1.getTime();
322                        TimeLocation t2 = s2.getTime();
323                        // no shared day > no conflict
324                        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) continue;
325                        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
326                        if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
327                            if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
328                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
329                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
330                                    return true;
331                            } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
332                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
333                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
334                                    return true;
335                            }
336                        } else {
337                            if (a1 + t1.getNrSlotsPerMeeting() == a2) {
338                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
339                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t1.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes())
340                                    return true;
341                            } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
342                                int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
343                                if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() && dist > t2.getBreakTime() + cx.getDistanceMetric().getAllowedDistanceInMinutes())
344                                    return true;
345                            }
346                        }
347                        
348                    }
349                    
350                }
351            }
352        }
353        
354        return false;
355    }
356    
357    public static boolean inConflict(StudentQuality sq, Section s1, Unavailability s2) {
358        if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0) return false;
359        if (sq == null) return false;
360        StudentQuality.Context cx = sq.getStudentQualityContext();
361        if (!cx.getUnavailabilityDistanceMetric().isHardDistanceConflictsEnabled()) return false;
362        TimeLocation t1 = s1.getTime();
363        TimeLocation t2 = s2.getTime();
364        if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
365            return false;
366        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
367        if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
368            int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
369            if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() &&
370                    dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes())
371                return true;
372        } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
373            int dist = cx.getUnavailabilityDistanceInMinutes(s1.getPlacement(), s2);
374            if (dist >= cx.getUnavailabilityDistanceMetric().getDistanceHardLimitInMinutes() &&
375                    dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getUnavailabilityDistanceMetric().getAllowedDistanceInMinutes())
376                return true;
377        }
378        return false;
379    }
380    
381    public static boolean inConflict(StudentQuality sq, Section s1, Section s2) {
382        if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0) return false;
383        if (sq == null) return false;
384        StudentQuality.Context cx = sq.getStudentQualityContext();
385        if (!cx.getDistanceMetric().isHardDistanceConflictsEnabled()) return false;
386        TimeLocation t1 = s1.getTime();
387        TimeLocation t2 = s2.getTime();
388        if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
389            return false;
390        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
391        if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
392            int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
393            if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() &&
394                    dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
395                return true;
396        } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
397            int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
398            if (dist >= cx.getDistanceMetric().getDistanceHardLimitInMinutes() &&
399                    dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()) + cx.getDistanceMetric().getAllowedDistanceInMinutes())
400                return true;
401        }
402        return false;
403    }
404    
405    public static boolean inConflict(StudentQuality sq, SctAssignment s1, Enrollment e) {
406        if (sq == null) return false;
407        if (!sq.getStudentQualityContext().getDistanceMetric().isHardDistanceConflictsEnabled()) return false;
408        if (s1 instanceof Section)
409            for (SctAssignment s2: e.getAssignments())
410                if (s2 instanceof Section && inConflict(sq, (Section)s1, (Section)s2)) return true;
411        return false;
412    }
413
414    @Override
415    public String toString() {
416        return "DistanceConflict";
417    }
418}