001package org.cpsolver.studentsct.extension;
002
003import java.util.ArrayList;
004import java.util.BitSet;
005import java.util.Collection;
006import java.util.HashMap;
007import java.util.HashSet;
008import java.util.Iterator;
009import java.util.List;
010import java.util.Map;
011import java.util.Set;
012import java.util.concurrent.locks.ReentrantReadWriteLock;
013import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
014import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
015
016import org.apache.logging.log4j.Logger;
017import org.cpsolver.coursett.Constants;
018import org.cpsolver.coursett.model.Placement;
019import org.cpsolver.coursett.model.RoomLocation;
020import org.cpsolver.coursett.model.TimeLocation;
021import org.cpsolver.ifs.assignment.Assignment;
022import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
023import org.cpsolver.ifs.assignment.context.CanInheritContext;
024import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
025import org.cpsolver.ifs.model.InfoProvider;
026import org.cpsolver.ifs.model.ModelListener;
027import org.cpsolver.ifs.solver.Solver;
028import org.cpsolver.ifs.util.DataProperties;
029import org.cpsolver.ifs.util.DistanceMetric;
030import org.cpsolver.studentsct.StudentSectioningModel;
031import org.cpsolver.studentsct.StudentSectioningModel.StudentSectioningModelContext;
032import org.cpsolver.studentsct.model.CourseRequest;
033import org.cpsolver.studentsct.model.Enrollment;
034import org.cpsolver.studentsct.model.FreeTimeRequest;
035import org.cpsolver.studentsct.model.Request;
036import org.cpsolver.studentsct.model.SctAssignment;
037import org.cpsolver.studentsct.model.Section;
038import org.cpsolver.studentsct.model.Student;
039import org.cpsolver.studentsct.model.Student.BackToBackPreference;
040import org.cpsolver.studentsct.model.Student.ModalityPreference;
041
042import org.cpsolver.studentsct.model.Unavailability;
043
044/**
045 * This extension computes student schedule quality using various matrices.
046 * It replaces {@link TimeOverlapsCounter} and {@link DistanceConflict} extensions.
047 * Besides of time and distance conflicts, it also counts cases when a student
048 * has a lunch break conflict, travel time during the day, it can prefer
049 * or discourage student class back-to-back and cases when a student has more than
050 * a given number of hours between the first and the last class on a day.
051 * See {@link StudentQuality.Type} for more details.
052 * 
053 * <br>
054 * <br>
055 * 
056 * @version StudentSct 1.3 (Student Sectioning)<br>
057 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
058 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
059 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
060 * <br>
061 *          This library is free software; you can redistribute it and/or modify
062 *          it under the terms of the GNU Lesser General Public License as
063 *          published by the Free Software Foundation; either version 3 of the
064 *          License, or (at your option) any later version. <br>
065 * <br>
066 *          This library is distributed in the hope that it will be useful, but
067 *          WITHOUT ANY WARRANTY; without even the implied warranty of
068 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
069 *          Lesser General Public License for more details. <br>
070 * <br>
071 *          You should have received a copy of the GNU Lesser General Public
072 *          License along with this library; if not see
073 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
074 */
075
076public class StudentQuality extends ExtensionWithContext<Request, Enrollment, StudentQuality.StudentQualityContext> implements ModelListener<Request, Enrollment>, CanInheritContext<Request, Enrollment, StudentQuality.StudentQualityContext>, InfoProvider<Request, Enrollment> {
077    private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(StudentQuality.class);
078    private Context iContext;
079    
080    /**
081     * Constructor
082     * @param solver student scheduling solver
083     * @param properties solver configuration
084     */
085    public StudentQuality(Solver<Request, Enrollment> solver, DataProperties properties) {
086        super(solver, properties);
087        if (solver != null) {
088            StudentSectioningModel model = (StudentSectioningModel) solver.currentSolution().getModel(); 
089            iContext = new Context(model.getDistanceMetric(), properties);
090            model.setStudentQuality(this, false);
091        } else {
092            iContext = new Context(null, properties);
093        }
094    }
095    
096    /**
097     * Constructor
098     * @param metrics distance metric
099     * @param properties solver configuration
100     */
101    public StudentQuality(DistanceMetric metrics, DataProperties properties) {
102        super(null, properties);
103        iContext = new Context(metrics, properties);
104    }
105    
106    /**
107     * Current distance metric
108     * @return distance metric
109     */
110    public DistanceMetric getDistanceMetric() {
111        return iContext.getDistanceMetric();
112    }
113    
114    /**
115     * Is debugging enabled
116     * @return true when StudentQuality.Debug is true
117     */
118    public boolean isDebug() {
119        return iContext.isDebug();
120    }
121    
122    /**
123     * Student quality context
124     */
125    public Context getStudentQualityContext() {
126        return iContext;
127    }
128    
129    /**
130     * Weighting types 
131     */
132    public static enum WeightType {
133        /** Penalty is incurred on the request with higher priority */
134        HIGHER,
135        /** Penalty is incurred on the request with lower priority */
136        LOWER,
137        /** Penalty is incurred on both requests */
138        BOTH,
139        /** Penalty is incurred on the course request (for conflicts between course request and a free time) */
140        REQUEST,
141        ;
142    }
143    
144    /**
145     * Measured student qualities
146     *
147     */
148    public static enum Type {
149        /** 
150         * Time conflicts between two classes that is allowed. Time conflicts are penalized as shared time
151         * between two course requests proportional to the time of each, capped at one half of the time.
152         * This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5.
153         */
154        CourseTimeOverlap(WeightType.BOTH, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){
155            @Override
156            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
157                return r1 instanceof CourseRequest && r2 instanceof CourseRequest;
158            }
159
160            @Override
161            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
162                if (a1.getTime() == null || a2.getTime() == null) return false;
163                if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false;
164                return a1.getTime().hasIntersection(a2.getTime());
165            }
166
167            @Override
168            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
169                if (!inConflict(cx, a1, a2)) return 0;
170                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
171            }
172            
173            @Override
174            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
175                return new Nothing();
176            }
177
178            @Override
179            public double getWeight(Context cx, Conflict c, Enrollment e) {
180                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / e.getNrSlots(), cx.getTimeOverlapMaxLimit());
181            }
182        }),
183        /** 
184         * Time conflict between class and a free time request. Free time conflicts are penalized as the time
185         * of a course request overlapping with a free time proportional to the time of the request, capped at one half
186         * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5.
187         */
188        FreeTimeOverlap(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){
189            @Override
190            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
191                return false;
192            }
193
194            @Override
195            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
196                if (a1.getTime() == null || a2.getTime() == null) return false;
197                return a1.getTime().hasIntersection(a2.getTime());
198            }
199
200            @Override
201            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
202                if (!inConflict(cx, a1, a2)) return 0;
203                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
204            }
205            
206            @Override
207            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
208                return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing());
209            }
210            
211            @Override
212            public double getWeight(Context cx, Conflict c, Enrollment e) {
213                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit());
214            }
215        }),
216        /** 
217         * Student unavailability conflict. Time conflict between a class that the student is taking and a class that the student
218         * is teaching (if time conflicts are allowed). Unavailability conflicts are penalized as the time
219         * of a course request overlapping with an unavailability proportional to the time of the request, capped at one half
220         * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5.
221         */
222        Unavailability(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){
223            @Override
224            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
225                return false;
226            }
227
228            @Override
229            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
230                if (a1.getTime() == null || a2.getTime() == null) return false;
231                return a1.getTime().hasIntersection(a2.getTime());
232            }
233
234            @Override
235            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
236                if (!inConflict(cx, a1, a2)) return 0;
237                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
238            }
239
240            @Override
241            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
242                return (e.isCourseRequest() ? new Unavailabilities(e.getStudent()) : new Nothing());
243            }
244            
245            @Override
246            public double getWeight(Context cx, Conflict c, Enrollment e) {
247                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit());
248            }
249        }),
250        /**
251         * Distance conflict. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false,
252         * distance conflicts are only considered between back-to-back classes (break time of the first 
253         * class is shorter than the distance in minutes between the two classes). When 
254         * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the
255         * two classes is also considered.
256         * This criterion is weighted by StudentWeights.DistanceConflict, defaulting to 0.01.
257         */
258        Distance(WeightType.LOWER, "StudentWeights.DistanceConflict", 0.0100, new Quality(){
259            @Override
260            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
261                return r1 instanceof CourseRequest && r2 instanceof CourseRequest;
262            }
263
264            @Override
265            public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) {
266                Section s1 = (Section) sa1;
267                Section s2 = (Section) sa2;
268                if (s1.getPlacement() == null || s2.getPlacement() == null)
269                    return false;
270                TimeLocation t1 = s1.getTime();
271                TimeLocation t2 = s2.getTime();
272                if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
273                    return false;
274                int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
275                if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
276                    if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
277                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
278                        if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()))
279                            return true;
280                    } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
281                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
282                        if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()))
283                            return true;
284                    }
285                } else {
286                    if (a1 + t1.getNrSlotsPerMeeting() == a2) {
287                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
288                        if (dist > t1.getBreakTime())
289                            return true;
290                    } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
291                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
292                        if (dist > t2.getBreakTime())
293                            return true;
294                    }
295                }
296                return false;
297            }
298
299            @Override
300            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
301                return inConflict(cx, a1, a2) ? 1 : 0;
302            }
303
304            @Override
305            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
306                return new Nothing();
307            }
308            
309            @Override
310            public double getWeight(Context cx, Conflict c, Enrollment e) {
311                return c.getPenalty();
312            }
313        }),
314        /**
315         * Short distance conflict. Similar to distance conflicts but for students that require short
316         * distances. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false,
317         * distance conflicts are only considered between back-to-back classes (travel time between the
318         * two classes is more than zero minutes). When 
319         * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the
320         * two classes is also considered (break time is also ignored).
321         * This criterion is weighted by StudentWeights.ShortDistanceConflict, defaulting to 0.1.
322         */
323        ShortDistance(WeightType.LOWER, "StudentWeights.ShortDistanceConflict", 0.1000, new Quality(){
324            @Override
325            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
326                return student.isNeedShortDistances() && r1 instanceof CourseRequest && r2 instanceof CourseRequest;
327            }
328
329            @Override
330            public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) {
331                Section s1 = (Section) sa1;
332                Section s2 = (Section) sa2;
333                if (s1.getPlacement() == null || s2.getPlacement() == null)
334                    return false;
335                TimeLocation t1 = s1.getTime();
336                TimeLocation t2 = s2.getTime();
337                if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
338                    return false;
339                int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
340                if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
341                    if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
342                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
343                        if (dist > Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()))
344                            return true;
345                    } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
346                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
347                        if (dist > Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()))
348                            return true;
349                    }
350                } else {
351                    if (a1 + t1.getNrSlotsPerMeeting() == a2) {
352                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
353                        if (dist > 0) return true;
354                    } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
355                        int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
356                        if (dist > 0) return true;
357                    }
358                }
359                return false;
360            }
361
362            @Override
363            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
364                return inConflict(cx, a1, a2) ? 1 : 0;
365            }
366
367            @Override
368            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
369                return new Nothing();
370            }
371            
372            @Override
373            public double getWeight(Context cx, Conflict c, Enrollment e) {
374                return c.getPenalty();
375            }
376        }),
377        /**
378         * Naive, yet effective approach for modeling student lunch breaks. It creates a conflict whenever there are
379         * two classes (of a student) overlapping with the lunch time which are one after the other with a break in
380         * between smaller than the requested lunch break. Lunch time is defined by StudentLunch.StartSlot and
381         * StudentLunch.EndStart properties (default is 11:00 am - 1:30 pm), with lunch break of at least
382         * StudentLunch.Length slots (default is 30 minutes). Such a conflict is weighted
383         * by StudentWeights.LunchBreakFactor, which defaults to 0.005.
384         */
385        LunchBreak(WeightType.BOTH, "StudentWeights.LunchBreakFactor", 0.0050, new Quality() {
386            @Override
387            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
388                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy();
389            }
390
391            @Override
392            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
393                if (a1.getTime() == null || a2.getTime() == null) return false;
394                if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false;
395                if (a1.getTime().hasIntersection(a2.getTime())) return false;
396                TimeLocation t1 = a1.getTime(), t2 = a2.getTime();
397                if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
398                int s1 = t1.getStartSlot(), s2 = t2.getStartSlot();
399                int e1 = t1.getStartSlot() + t1.getNrSlotsPerMeeting(), e2 = t2.getStartSlot() + t2.getNrSlotsPerMeeting();
400                if (e1 + cx.getLunchLength() > s2 && e2 + cx.getLunchLength() > s1 && e1 > cx.getLunchStart() && cx.getLunchEnd() > s1 && e2 > cx.getLunchStart() && cx.getLunchEnd() > s2)
401                    return true;
402                return false;
403            }
404
405            @Override
406            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
407                if (!inConflict(cx, a1, a2)) return 0;
408                return a1.getTime().nrSharedDays(a2.getTime());
409            }
410            
411            @Override
412            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
413                return new Nothing();
414            }
415
416            @Override
417            public double getWeight(Context cx, Conflict c, Enrollment e) {
418                return c.getPenalty();
419            }
420        }),
421        /**
422         * Naive, yet effective approach for modeling travel times. A conflict with the penalty
423         * equal to the distance in minutes occurs when two classes are less than TravelTime.MaxTravelGap
424         * time slots a part (defaults 1 hour), or when they are less then twice as long apart 
425         * and the travel time is longer than the break time of the first class.
426         * Such a conflict is weighted by StudentWeights.TravelTimeFactor, which defaults to 0.001.
427         */
428        TravelTime(WeightType.BOTH, "StudentWeights.TravelTimeFactor", 0.0010, new Quality() {
429            @Override
430            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
431                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy();
432            }
433
434            @Override
435            public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) {
436                Section s1 = (Section) sa1;
437                Section s2 = (Section) sa2;
438                if (s1.getPlacement() == null || s2.getPlacement() == null)
439                    return false;
440                TimeLocation t1 = s1.getTime();
441                TimeLocation t2 = s2.getTime();
442                if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
443                    return false;
444                int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
445                if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
446                    int gap = a2 - (a1 + t1.getNrSlotsPerMeeting());
447                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
448                    return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime());
449                } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
450                    int gap = a1 - (a2 + t2.getNrSlotsPerMeeting());
451                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
452                    return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime());
453                }
454                return false;
455            }
456
457            @Override
458            public int penalty(Context cx, Student s, SctAssignment sa1, SctAssignment sa2) {
459                Section s1 = (Section) sa1;
460                Section s2 = (Section) sa2;
461                if (s1.getPlacement() == null || s2.getPlacement() == null) return 0;
462                TimeLocation t1 = s1.getTime();
463                TimeLocation t2 = s2.getTime();
464                if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0;
465                int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
466                if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
467                    int gap = a2 - (a1 + t1.getNrSlotsPerMeeting());
468                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
469                    if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime()))
470                        return dist;
471                } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
472                    int gap = a1 - (a2 + t2.getNrSlotsPerMeeting());
473                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
474                    if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime()))
475                        return dist;
476                }
477                return 0;
478            }
479            
480            @Override
481            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
482                return new Nothing();
483            }
484
485            @Override
486            public double getWeight(Context cx, Conflict c, Enrollment e) {
487                return c.getPenalty();
488            }
489        }),
490        /**
491         * A back-to-back conflict is there every time when a student has two classes that are
492         * back-to-back or less than StudentWeights.BackToBackDistance time slots apart (defaults to 30 minutes).
493         * Such a conflict is weighted by StudentWeights.BackToBackFactor, which
494         * defaults to -0.0001 (these conflicts are preferred by default, trying to avoid schedule gaps).
495         * NEW: Consider student's back-to-back preference. That is, students with no preference are ignored, and
496         * students that discourage back-to-backs have a negative weight on the conflict.
497         */
498        BackToBack(WeightType.BOTH, "StudentWeights.BackToBackFactor", -0.0001, new Quality() {
499            @Override
500            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
501                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && 
502                        (student.getBackToBackPreference() == BackToBackPreference.BTB_PREFERRED || student.getBackToBackPreference() == BackToBackPreference.BTB_DISCOURAGED);
503            }
504
505            @Override
506            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
507                TimeLocation t1 = a1.getTime();
508                TimeLocation t2 = a2.getTime();
509                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
510                if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) {
511                    int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting());
512                    return dist <= cx.getBackToBackDistance();
513                } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) {
514                    int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting());
515                    return dist <= cx.getBackToBackDistance();
516                }
517                return false;
518            }
519
520            @Override
521            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
522                if (!inConflict(cx, a1, a2)) return 0;
523                if (s.getBackToBackPreference() == BackToBackPreference.BTB_PREFERRED)
524                    return a1.getTime().nrSharedDays(a2.getTime());
525                else if (s.getBackToBackPreference() == BackToBackPreference.BTB_DISCOURAGED)
526                    return -a1.getTime().nrSharedDays(a2.getTime());
527                else
528                    return 0;
529            }
530            
531            @Override
532            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
533                return new Nothing();
534            }
535
536            @Override
537            public double getWeight(Context cx, Conflict c, Enrollment e) {
538                return c.getPenalty();
539            }
540        }),
541        /**
542         * A work-day conflict is there every time when a student has two classes that are too
543         * far apart. This means that the time between the start of the first class and the end
544         * of the last class is more than WorkDay.WorkDayLimit (defaults to 6 hours). A penalty
545         * of one is incurred for every hour started over this limit.
546         * Such a conflict is weighted by StudentWeights.WorkDayFactor, which defaults to 0.01.
547         */
548        WorkDay(WeightType.BOTH, "StudentWeights.WorkDayFactor", 0.0100, new Quality() {
549            @Override
550            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
551                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy();
552            }
553            
554            @Override
555            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
556                TimeLocation t1 = a1.getTime();
557                TimeLocation t2 = a2.getTime();
558                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
559                int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot());
560                return dist > cx.getWorkDayLimit();
561            }
562
563            @Override
564            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
565                TimeLocation t1 = a1.getTime();
566                TimeLocation t2 = a2.getTime();
567                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0;
568                int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot());
569                if (dist > cx.getWorkDayLimit())
570                    return a1.getTime().nrSharedDays(a2.getTime()) * (dist - cx.getWorkDayLimit());
571                else
572                    return 0;
573            }
574            
575            @Override
576            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
577                return new Nothing();
578            }
579
580            @Override
581            public double getWeight(Context cx, Conflict c, Enrollment e) {
582                return c.getPenalty() / 12.0;
583            }
584        }),
585        TooEarly(WeightType.REQUEST, "StudentWeights.TooEarlyFactor", 0.0500, new Quality(){
586            @Override
587            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
588                return false;
589            }
590
591            @Override
592            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
593                if (a1.getTime() == null || a2.getTime() == null) return false;
594                return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime());
595            }
596
597            @Override
598            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
599                if (!inConflict(cx, a1, a2)) return 0;
600                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
601            }
602            
603            @Override
604            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
605                return (e.isCourseRequest() && !e.getStudent().isDummy() ? new SingleTimeIterable(0, cx.getEarlySlot()) : new Nothing());
606            }
607            
608            @Override
609            public double getWeight(Context cx, Conflict c, Enrollment e) {
610                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit());
611            }
612        }),
613        TooLate(WeightType.REQUEST, "StudentWeights.TooLateFactor", 0.0250, new Quality(){
614            @Override
615            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
616                return false;
617            }
618
619            @Override
620            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
621                if (a1.getTime() == null || a2.getTime() == null) return false;
622                return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime());
623            }
624
625            @Override
626            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
627                if (!inConflict(cx, a1, a2)) return 0;
628                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
629            }
630            
631            @Override
632            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
633                return (e.isCourseRequest() && !e.getStudent().isDummy() ? new SingleTimeIterable(cx.getLateSlot(), 288) : new Nothing());
634            }
635            
636            @Override
637            public double getWeight(Context cx, Conflict c, Enrollment e) {
638                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit());
639            }
640        }),
641        /**
642         * There is a student modality preference conflict when a student that prefers online
643         * gets a non-online class ({@link Section#isOnline()} is false) or when a student that
644         * prefers non-online gets an online class (@{link Section#isOnline()} is true).
645         * Such a conflict is weighted by StudentWeights.ModalityFactor, which defaults to 0.05.
646         */
647        Modality(WeightType.REQUEST, "StudentWeights.ModalityFactor", 0.0500, new Quality(){
648            @Override
649            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
650                return false;
651            }
652
653            @Override
654            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
655                return a1.equals(a2);
656            }
657
658            @Override
659            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
660                return (inConflict(cx, a1, a2) ? 1 : 0);
661            }
662            
663            @Override
664            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
665                if (!e.isCourseRequest() || e.getStudent().isDummy()) return new Nothing();
666                if (e.getStudent().getModalityPreference() == ModalityPreference.ONLINE_PREFERRED)
667                    return new Online(e, false); // face-to-face sections are conflicting
668                else if (e.getStudent().getModalityPreference() == ModalityPreference.ONILNE_DISCOURAGED)
669                    return new Online(e, true); // online sections are conflicting
670                return new Nothing();
671            }
672            
673            @Override
674            public double getWeight(Context cx, Conflict c, Enrollment e) {
675                return ((double) c.getPenalty()) / ((double) e.getSections().size());
676            }
677        }),
678        /** 
679         * DRC: Time conflict between class and a free time request (for students with FT accommodation).
680         * Free time conflicts are penalized as the time of a course request overlapping with a free time
681         * proportional to the time of the request, capped at one half of the time.
682         * This criterion is weighted by Accommodations.FreeTimeOverlapFactor, defaulting to 0.5.
683         */
684        AccFreeTimeOverlap(WeightType.REQUEST, "Accommodations.FreeTimeOverlapFactor", 0.5000, new Quality(){
685            @Override
686            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
687                return false;
688            }
689
690            @Override
691            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
692                if (a1.getTime() == null || a2.getTime() == null) return false;
693                return a1.getTime().hasIntersection(a2.getTime());
694            }
695
696            @Override
697            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
698                if (!inConflict(cx, a1, a2)) return 0;
699                return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
700            }
701            
702            @Override
703            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
704                if (!e.getStudent().hasAccommodation(cx.getFreeTimeAccommodation())) return new Nothing();
705                return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing());
706            }
707            
708            @Override
709            public double getWeight(Context cx, Conflict c, Enrollment e) {
710                return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit());
711            }
712        }),
713        /**
714         * DRC: A back-to-back conflict (for students with BTB accommodation) is there every time when a student has two classes that are NOT
715         * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes).
716         * Such a conflict is weighted by Accommodations.BackToBackFactor, which defaults to 0.001
717         */
718        AccBackToBack(WeightType.BOTH, "Accommodations.BackToBackFactor", 0.001, new Quality() {
719            @Override
720            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
721                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBackToBackAccommodation());
722            }
723
724            @Override
725            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
726                TimeLocation t1 = a1.getTime();
727                TimeLocation t2 = a2.getTime();
728                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
729                if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) {
730                    int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting());
731                    return dist > cx.getBackToBackDistance();
732                } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) {
733                    int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting());
734                    return dist > cx.getBackToBackDistance();
735                }
736                return false;
737            }
738
739            @Override
740            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
741                if (!inConflict(cx, a1, a2)) return 0;
742                return a1.getTime().nrSharedDays(a2.getTime());
743            }
744            
745            @Override
746            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
747                return new Nothing();
748            }
749
750            @Override
751            public double getWeight(Context cx, Conflict c, Enrollment e) {
752                return c.getPenalty();
753            }
754        }),
755        /**
756         * DRC: A not back-to-back conflict (for students with BBC accommodation) is there every time when a student has two classes that are
757         * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes).
758         * Such a conflict is weighted by Accommodations.BreaksBetweenClassesFactor, which defaults to 0.001.
759         */
760        AccBreaksBetweenClasses(WeightType.BOTH, "Accommodations.BreaksBetweenClassesFactor", 0.001, new Quality() {
761            @Override
762            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
763                return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBreakBetweenClassesAccommodation());
764            }
765
766            @Override
767            public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) {
768                TimeLocation t1 = a1.getTime();
769                TimeLocation t2 = a2.getTime();
770                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
771                if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) {
772                    int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting());
773                    return dist <= cx.getBackToBackDistance();
774                } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) {
775                    int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting());
776                    return dist <= cx.getBackToBackDistance();
777                }
778                return false;
779            }
780
781            @Override
782            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
783                if (!inConflict(cx, a1, a2)) return 0;
784                return a1.getTime().nrSharedDays(a2.getTime());
785            }
786            
787            @Override
788            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
789                return new Nothing();
790            }
791
792            @Override
793            public double getWeight(Context cx, Conflict c, Enrollment e) {
794                return c.getPenalty();
795            }
796        }),
797        /** 
798         * Student unavailability distance conflict. Distance conflict between a class that the student is taking and a class that the student
799         * is teaching or attending in a different session.
800         * This criterion is weighted by StudentWeights.UnavailabilityDistanceConflict, defaulting to 0.1.
801         */
802        UnavailabilityDistance(WeightType.REQUEST, "StudentWeights.UnavailabilityDistanceConflict", 0.100, new Quality(){
803            @Override
804            public boolean isApplicable(Context cx, Student student, Request r1, Request r2) {
805                return false;
806            }
807            
808            @Override
809            public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) {
810                Section s1 = (Section) sa1;
811                Unavailability s2 = (Unavailability) sa2;
812                if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0)
813                    return false;
814                TimeLocation t1 = s1.getTime();
815                TimeLocation t2 = s2.getTime();
816                if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
817                    return false;
818                int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
819                if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
820                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2);
821                    if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()))
822                        return true;
823                } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
824                    int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2);
825                    if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()))
826                        return true;
827                }
828                return false;
829            }
830
831            @Override
832            public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) {
833                if (!inConflict(cx, a1, a2)) return 0;
834                return a1.getTime().nrSharedDays(a2.getTime());
835            }
836
837            @Override
838            public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) {
839                return (e.isCourseRequest() ? new Unavailabilities(e.getStudent()) : new Nothing());
840            }
841            
842            @Override
843            public double getWeight(Context cx, Conflict c, Enrollment e) {
844                return c.getPenalty();
845            }
846        }),
847        ;
848        
849        private WeightType iType;
850        private Quality iQuality;
851        private String iWeightName;
852        private double iWeightDefault;
853        Type(WeightType type, String weightName, double weightDefault, Quality quality) {
854            iQuality = quality;
855            iType = type;
856            iWeightName = weightName;
857            iWeightDefault = weightDefault;
858        }
859        
860        
861        public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { return iQuality.isApplicable(cx, student, r1, r2); }
862        public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { return iQuality.inConflict(cx, a1, a2); }
863        public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { return iQuality.penalty(cx, s, a1, a2); }
864        public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { return iQuality.other(cx, e); }
865        public double getWeight(Context cx, Conflict c, Enrollment e) { return iQuality.getWeight(cx, c, e); }
866        public String getName() { return name().replaceAll("(?<=[^A-Z0-9])([A-Z0-9])"," $1"); }
867        public String getAbbv() { return getName().replaceAll("[a-z ]",""); }
868        public WeightType getType() { return iType; }
869        public String getWeightName() { return iWeightName; }
870        public double getWeightDefault() { return iWeightDefault; }
871    }
872    
873    /**
874     * Schedule quality interface
875     */
876    public static interface Quality {
877        /**
878         * Check if the metric is applicable for the given student, between the given two requests
879         */
880        public boolean isApplicable(Context cx, Student student, Request r1, Request r2);
881        /**
882         * When applicable, is there a conflict between two sections
883         */
884        public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2);
885        /**
886         * When in conflict, what is the penalisation
887         */
888        public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2);
889        /**
890         * Enumerate other section assignments applicable for the given enrollment (e.g., student unavailabilities)
891         */
892        public Iterable<? extends SctAssignment> other(Context cx, Enrollment e);
893        /**
894         * Base weight of the given conflict and enrollment. Typically based on the {@link Conflict#getPenalty()}, but 
895         * change to be between 0.0 and 1.0. For example, for time conflicts, a percentage of share is used. 
896         */
897        public double getWeight(Context cx, Conflict c, Enrollment e);
898    }
899    
900    /**
901     * Penalisation of the given type between two enrollments of a student.
902     */
903    public int penalty(Type type, Enrollment e1, Enrollment e2) {
904        if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return 0;
905        int cnt = 0;
906        for (SctAssignment s1 : e1.getAssignments()) {
907            for (SctAssignment s2 : e2.getAssignments()) {
908                cnt += type.penalty(iContext, e1.getStudent(), s1, s2);
909            }
910        }
911        return cnt;
912    }
913    
914    /**
915     * Conflicss of the given type between two enrollments of a student.
916     */
917    public Set<Conflict> conflicts(Type type, Enrollment e1, Enrollment e2) {
918        Set<Conflict> ret = new HashSet<Conflict>();
919        if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return ret;
920        for (SctAssignment s1 : e1.getAssignments()) {
921            for (SctAssignment s2 : e2.getAssignments()) {
922                int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
923                if (penalty != 0)
924                    ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2));
925            }
926        }
927        return ret;
928    }
929    
930    /**
931     * Conflicts of any type between two enrollments of a student.
932     */
933    public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
934        Set<Conflict> ret = new HashSet<Conflict>();
935        for (Type type: iContext.getTypes()) {
936            if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) continue;
937            for (SctAssignment s1 : e1.getAssignments()) {
938                for (SctAssignment s2 : e2.getAssignments()) {
939                    int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
940                    if (penalty != 0)
941                        ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2));
942                }
943            }
944        }
945        return ret;
946    }
947    
948    /**
949     * Conflicts of the given type between classes of a single enrollment (or with free times, unavailabilities, etc.)
950     */
951    public Set<Conflict> conflicts(Type type, Enrollment e1) {
952        Set<Conflict> ret = new HashSet<Conflict>();
953        boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 
954        for (SctAssignment s1 : e1.getAssignments()) {
955            if (applicable) {
956                for (SctAssignment s2 : e1.getAssignments()) {
957                    if (s1.getId() < s2.getId()) {
958                        int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
959                        if (penalty != 0)
960                            ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2));
961                    }
962                }
963            }
964            for (SctAssignment s2: type.other(iContext, e1)) {
965                int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
966                if (penalty != 0)
967                    ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2));
968            }
969        }
970        return ret;
971    }
972    
973    /**
974     * Conflicts of any type between classes of a single enrollment (or with free times, unavailabilities, etc.)
975     */
976    public Set<Conflict> conflicts(Enrollment e1) {
977        Set<Conflict> ret = new HashSet<Conflict>();
978        for (Type type: iContext.getTypes()) {
979            boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 
980            for (SctAssignment s1 : e1.getAssignments()) {
981                if (applicable) {
982                    for (SctAssignment s2 : e1.getAssignments()) {
983                        if (s1.getId() < s2.getId()) {
984                            int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
985                            if (penalty != 0)
986                                ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2));
987                        }
988                    }
989                }
990                for (SctAssignment s2: type.other(iContext, e1)) {
991                    int penalty = type.penalty(iContext, e1.getStudent(), s1, s2);
992                    if (penalty != 0)
993                        ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2));
994                }
995            }            
996        }
997        return ret;
998    }
999    
1000    /**
1001     * Penalty of given type between classes of a single enrollment (or with free times, unavailabilities, etc.)
1002     */
1003    public int penalty(Type type, Enrollment e1) {
1004        int penalty = 0;
1005        boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest());
1006        for (SctAssignment s1 : e1.getAssignments()) {
1007            if (applicable) {
1008                for (SctAssignment s2 : e1.getAssignments()) {
1009                    if (s1.getId() < s2.getId()) {
1010                        penalty += type.penalty(iContext, e1.getStudent(), s1, s2);
1011                    }
1012                }
1013            }
1014            for (SctAssignment s2: type.other(iContext, e1)) {
1015                penalty += type.penalty(iContext, e1.getStudent(), s1, s2);
1016            }
1017        }
1018        return penalty;
1019    }
1020    
1021    /**
1022     * Check whether the given type is applicable for the student and the two requests.
1023     */
1024    public boolean isApplicable(Type type, Student student, Request r1, Request r2) {
1025        return type.isApplicable(iContext, student, r1, r2);
1026    }
1027  
1028    /**
1029     * Total penalisation of given type
1030     */
1031    public int getTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) {
1032        return getContext(assignment).getTotalPenalty(type);
1033    }
1034    
1035    /**
1036     * Total penalisation of given types
1037     */
1038    public int getTotalPenalty(Assignment<Request, Enrollment> assignment, Type... types) {
1039        int ret = 0;
1040        for (Type type: types)
1041            ret += getContext(assignment).getTotalPenalty(type);
1042        return ret;
1043    }
1044    
1045    /**
1046     * Re-check total penalization for the given assignment 
1047     */
1048    public void checkTotalPenalty(Assignment<Request, Enrollment> assignment) {
1049        for (Type type: iContext.getTypes())
1050            checkTotalPenalty(type, assignment);
1051    }
1052    
1053    /**
1054     * Re-check total penalization for the given assignment and conflict type 
1055     */
1056    public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) {
1057        getContext(assignment).checkTotalPenalty(type, assignment);
1058    }
1059
1060    /**
1061     * All conflicts of the given type for the given assignment 
1062     */
1063    public Set<Conflict> getAllConflicts(Type type, Assignment<Request, Enrollment> assignment) {
1064        return getContext(assignment).getAllConflicts(type);
1065    }
1066    
1067    /**
1068     * All conflicts of the any type for the enrollment (including conflicts with other enrollments of the student)
1069     */
1070    public Set<Conflict> allConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
1071        Set<Conflict> conflicts = new HashSet<Conflict>();
1072        for (Type t: iContext.getTypes()) {
1073            conflicts.addAll(conflicts(t, enrollment));
1074            for (Request request : enrollment.getStudent().getRequests()) {
1075                if (request.equals(enrollment.getRequest()) || assignment.getValue(request) == null) continue;
1076                conflicts.addAll(conflicts(t, enrollment, assignment.getValue(request)));
1077            }
1078        }
1079        return conflicts;
1080    }
1081    
1082    @Override
1083    public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1084        getContext(assignment).beforeAssigned(assignment, iteration, value);
1085    }
1086
1087    @Override
1088    public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1089        getContext(assignment).afterAssigned(assignment, iteration, value);
1090    }
1091
1092    @Override
1093    public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1094        getContext(assignment).afterUnassigned(assignment, iteration, value);
1095    }
1096    
1097    /** A representation of a time overlapping conflict */
1098    public class Conflict {
1099        private Type iType;
1100        private int iPenalty;
1101        private Student iStudent;
1102        private SctAssignment iA1, iA2;
1103        private Enrollment iE1, iE2;
1104        private int iHashCode;
1105
1106        /**
1107         * Constructor
1108         * 
1109         * @param student related student
1110         * @param type conflict type
1111         * @param penalty conflict penalization, e.g., the number of slots in common between the two conflicting sections
1112         * @param e1 first enrollment
1113         * @param a1 first conflicting section
1114         * @param e2 second enrollment
1115         * @param a2 second conflicting section
1116         */
1117        public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, Enrollment e2, SctAssignment a2) {
1118            iStudent = student;
1119            if (a1.compareById(a2) < 0 ) {
1120                iA1 = a1;
1121                iA2 = a2;
1122                iE1 = e1;
1123                iE2 = e2;
1124            } else {
1125                iA1 = a2;
1126                iA2 = a1;
1127                iE1 = e2;
1128                iE2 = e1;
1129            }
1130            iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode();
1131            iType = type;
1132            iPenalty = penalty;
1133        }
1134        
1135        public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, SctAssignment a2) {
1136            this(student, type, penalty, e1, a1, a2 instanceof FreeTimeRequest ? ((FreeTimeRequest)a2).createEnrollment() : a2 instanceof Unavailability ? ((Unavailability)a2).createEnrollment() : e1, a2);
1137            
1138        }
1139
1140        /** Related student
1141         * @return student
1142         **/
1143        public Student getStudent() {
1144            return iStudent;
1145        }
1146
1147        /** First section
1148         * @return first section
1149         **/
1150        public SctAssignment getS1() {
1151            return iA1;
1152        }
1153
1154        /** Second section
1155         * @return second section
1156         **/
1157        public SctAssignment getS2() {
1158            return iA2;
1159        }
1160
1161        /** First request
1162         * @return first request
1163         **/
1164        public Request getR1() {
1165            return iE1.getRequest();
1166        }
1167        
1168        /** First request weight
1169         * @return first request weight
1170         **/
1171        public double getR1Weight() {
1172            return (iE1.getRequest() == null ? 0.0 : iE1.getRequest().getWeight());
1173        }
1174        
1175        /** Second request weight
1176         * @return second request weight
1177         **/
1178        public double getR2Weight() {
1179            return (iE2.getRequest() == null ? 0.0 : iE2.getRequest().getWeight());
1180        }
1181        
1182        /** Second request
1183         * @return second request
1184         **/
1185        public Request getR2() {
1186            return iE2.getRequest();
1187        }
1188        
1189        /** First enrollment
1190         * @return first enrollment
1191         **/
1192        public Enrollment getE1() {
1193            return iE1;
1194        }
1195
1196        /** Second enrollment
1197         * @return second enrollment
1198         **/
1199        public Enrollment getE2() {
1200            return iE2;
1201        }
1202        
1203        @Override
1204        public int hashCode() {
1205            return iHashCode;
1206        }
1207
1208        /** Conflict penalty, e.g., the number of overlapping slots against the number of slots of the smallest section
1209         * @return conflict penalty 
1210         **/
1211        public int getPenalty() {
1212            return iPenalty;
1213        }
1214        
1215        /** Other enrollment of the conflict */
1216        public Enrollment getOther(Enrollment enrollment) {
1217            return (getE1().getRequest().equals(enrollment.getRequest()) ? getE2() : getE1());
1218        }
1219        
1220        /** Weight of the conflict on the given enrollment */
1221        public double getWeight(Enrollment e) {
1222            return iType.getWeight(iContext, this, e);
1223        }
1224        
1225        /** Weight of the conflict on both enrollment (sum) */
1226        public double getWeight() {
1227            return (iType.getWeight(iContext, this, iE1) + iType.getWeight(iContext, this, iE2)) / 2.0;
1228        }
1229        
1230        /** Conflict type
1231         * @return conflict type;
1232         */
1233        public Type getType() {
1234            return iType;
1235        }
1236
1237        @Override
1238        public boolean equals(Object o) {
1239            if (o == null || !(o instanceof Conflict)) return false;
1240            Conflict c = (Conflict) o;
1241            return getType() == c.getType() && getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
1242        }
1243
1244        @Override
1245        public String toString() {
1246            return getStudent() + ": (" + getType() + ", p:" + getPenalty() + ") " + getS1() + " -- " + getS2();
1247        }
1248    }
1249    
1250    /**
1251     * Context holding parameters and distance cache. See {@link Type} for the list of available parameters.
1252     */
1253    public static class Context {
1254        private List<Type> iTypes = null;
1255        private DistanceMetric iDistanceMetric = null;
1256        private boolean iDebug = false;
1257        protected double iTimeOverlapMaxLimit = 0.5000;
1258        private int iLunchStart, iLunchEnd, iLunchLength, iMaxTravelGap, iWorkDayLimit, iBackToBackDistance, iEarlySlot, iLateSlot, iAccBackToBackDistance;
1259        private String iFreeTimeAccommodation = "FT", iBackToBackAccommodation = "BTB", iBreakBetweenClassesAccommodation = "BBC";
1260        private ReentrantReadWriteLock iLock = new ReentrantReadWriteLock();
1261        
1262        public Context(DistanceMetric dm, DataProperties config) {
1263            iDistanceMetric = (dm == null ? new DistanceMetric(config) : dm);
1264            iDebug = config.getPropertyBoolean("StudentQuality.Debug", false);
1265            iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit);
1266            iLunchStart = config.getPropertyInt("StudentLunch.StartSlot", (11 * 60) / 5);
1267            iLunchEnd = config.getPropertyInt("StudentLunch.EndStart", (13 * 60) / 5);
1268            iLunchLength = config.getPropertyInt("StudentLunch.Length", 30 / 5);
1269            iMaxTravelGap = config.getPropertyInt("TravelTime.MaxTravelGap", 12);
1270            iWorkDayLimit = config.getPropertyInt("WorkDay.WorkDayLimit", 6 * 12);
1271            iBackToBackDistance = config.getPropertyInt("StudentWeights.BackToBackDistance", 6);
1272            iAccBackToBackDistance = config.getPropertyInt("Accommodations.BackToBackDistance", 6);
1273            iEarlySlot = config.getPropertyInt("WorkDay.EarlySlot", 102);
1274            iLateSlot = config.getPropertyInt("WorkDay.LateSlot", 210);
1275            iFreeTimeAccommodation = config.getProperty("Accommodations.FreeTimeReference", iFreeTimeAccommodation);
1276            iBackToBackAccommodation = config.getProperty("Accommodations.BackToBackReference", iBackToBackAccommodation);
1277            iBreakBetweenClassesAccommodation = config.getProperty("Accommodations.BreakBetweenClassesReference", iBreakBetweenClassesAccommodation);
1278            iTypes = new ArrayList<Type>();
1279            for (Type t: Type.values())
1280                if (config.getPropertyDouble(t.getWeightName(), t.getWeightDefault()) != 0.0)
1281                    iTypes.add(t);
1282        }
1283        
1284        public DistanceMetric getDistanceMetric() {
1285            return iDistanceMetric;
1286        }
1287        
1288        public boolean isDebug() { return iDebug; }
1289        
1290        public double getTimeOverlapMaxLimit() { return iTimeOverlapMaxLimit; }
1291        public int getLunchStart() { return iLunchStart; }
1292        public int getLunchEnd() { return iLunchEnd; }
1293        public int getLunchLength() { return iLunchLength; }
1294        public int getMaxTravelGap() { return iMaxTravelGap; }
1295        public int getWorkDayLimit() { return iWorkDayLimit; }
1296        public int getBackToBackDistance() { return iBackToBackDistance; }
1297        public int getAccBackToBackDistance() { return iAccBackToBackDistance; }
1298        public int getEarlySlot() { return iEarlySlot; }
1299        public int getLateSlot() { return iLateSlot; }
1300        public String getFreeTimeAccommodation() { return iFreeTimeAccommodation; }
1301        public String getBackToBackAccommodation() { return iBackToBackAccommodation; }
1302        public String getBreakBetweenClassesAccommodation() { return iBreakBetweenClassesAccommodation; }
1303        public List<Type> getTypes() { return iTypes; }
1304            
1305        private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>();
1306        protected Integer getDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2) {
1307            ReadLock lock = iLock.readLock();
1308            lock.lock();
1309            try {
1310                Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId());
1311                return other2distance == null ? null : other2distance.get(r2.getId());
1312            } finally {
1313                lock.unlock();
1314            }
1315        }
1316        
1317        protected void setDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2, Integer distance) {
1318            WriteLock lock = iLock.writeLock();
1319            lock.lock();
1320            try {
1321                Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId());
1322                if (other2distance == null) {
1323                    other2distance = new HashMap<Long, Integer>();
1324                    iDistanceCache.put(r1.getId(), other2distance);
1325                }
1326                other2distance.put(r2.getId(), distance);
1327            } finally {
1328                lock.unlock();
1329            }
1330        }
1331        
1332        protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) {
1333            if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1);
1334            if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar())
1335                return 0;
1336            if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null)
1337                return iDistanceMetric.getMaxTravelDistanceInMinutes();
1338            Integer distance = getDistanceInMinutesFromCache(r1, r2);
1339            if (distance == null) {
1340                distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY());
1341                setDistanceInMinutesFromCache(r1, r2, distance);
1342            }
1343            return distance;
1344        }
1345
1346        public int getDistanceInMinutes(Placement p1, Placement p2) {
1347            if (p1.isMultiRoom()) {
1348                if (p2.isMultiRoom()) {
1349                    int dist = 0;
1350                    for (RoomLocation r1 : p1.getRoomLocations()) {
1351                        for (RoomLocation r2 : p2.getRoomLocations()) {
1352                            dist = Math.max(dist, getDistanceInMinutes(r1, r2));
1353                        }
1354                    }
1355                    return dist;
1356                } else {
1357                    if (p2.getRoomLocation() == null)
1358                        return 0;
1359                    int dist = 0;
1360                    for (RoomLocation r1 : p1.getRoomLocations()) {
1361                        dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation()));
1362                    }
1363                    return dist;
1364                }
1365            } else if (p2.isMultiRoom()) {
1366                if (p1.getRoomLocation() == null)
1367                    return 0;
1368                int dist = 0;
1369                for (RoomLocation r2 : p2.getRoomLocations()) {
1370                    dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2));
1371                }
1372                return dist;
1373            } else {
1374                if (p1.getRoomLocation() == null || p2.getRoomLocation() == null)
1375                    return 0;
1376                return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation());
1377            }
1378        }
1379
1380        public int getDistanceInMinutes(Placement p1, Unavailability p2) {
1381            if (p1.isMultiRoom()) {
1382                int dist = 0;
1383                for (RoomLocation r1 : p1.getRoomLocations()) {
1384                    for (RoomLocation r2 : p2.getRooms()) {
1385                        dist = Math.max(dist, getDistanceInMinutes(r1, r2));
1386                    }
1387                }
1388                return dist;
1389            } else {
1390                if (p1.getRoomLocation() == null)
1391                    return 0;
1392                int dist = 0;
1393                for (RoomLocation r2 : p2.getRooms()) {
1394                    dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2));
1395                }
1396                return dist;
1397            }
1398        }      
1399    }
1400    
1401    /**
1402     * Assignment context
1403     */
1404    public class StudentQualityContext implements AssignmentConstraintContext<Request, Enrollment> {
1405        private int[] iTotalPenalty = null;
1406        private Set<Conflict>[] iAllConflicts = null;
1407        private Request iOldVariable = null;
1408        private Enrollment iUnassignedValue = null;
1409
1410        @SuppressWarnings("unchecked")
1411        public StudentQualityContext(Assignment<Request, Enrollment> assignment) {
1412            iTotalPenalty = new int[Type.values().length];
1413            for (Type t: iContext.getTypes())
1414                iTotalPenalty[t.ordinal()] = countTotalPenalty(t, assignment);
1415            if (iContext.isDebug()) {
1416                iAllConflicts = new Set[Type.values().length];
1417                for (Type t: iContext.getTypes())
1418                    iAllConflicts[t.ordinal()] = computeAllConflicts(t, assignment);
1419            }
1420            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
1421            for (Type t: iContext.getTypes())
1422                for (Conflict c: computeAllConflicts(t, assignment)) cx.add(assignment, c);
1423        }
1424        
1425        @SuppressWarnings("unchecked")
1426        public StudentQualityContext(StudentQualityContext parent) {
1427            iTotalPenalty = new int[Type.values().length];
1428            for (Type t: iContext.getTypes())
1429                iTotalPenalty[t.ordinal()] = parent.iTotalPenalty[t.ordinal()];
1430            if (iContext.isDebug()) {
1431                iAllConflicts = new Set[Type.values().length];
1432                for (Type t: iContext.getTypes())
1433                    iAllConflicts[t.ordinal()] = new HashSet<Conflict>(parent.iAllConflicts[t.ordinal()]);
1434            }
1435        }
1436
1437        @Override
1438        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment value) {
1439            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
1440            for (Type type: iContext.getTypes()) {
1441                iTotalPenalty[type.ordinal()] += allPenalty(type, assignment, value);
1442                for (Conflict c: allConflicts(type, assignment, value))
1443                    cx.add(assignment, c);
1444            }
1445            if (iContext.isDebug()) {
1446                sLog.debug("A:" + value.variable() + " := " + value);
1447                for (Type type: iContext.getTypes()) {
1448                    int inc = allPenalty(type, assignment, value);
1449                    if (inc != 0) {
1450                        sLog.debug("-- " + type + " +" + inc + " A: " + value.variable() + " := " + value);
1451                        for (Conflict c: allConflicts(type, assignment, value)) {
1452                            sLog.debug("  -- " + c);
1453                            iAllConflicts[type.ordinal()].add(c);
1454                            inc -= c.getPenalty();
1455                        }
1456                        if (inc != 0) {
1457                            sLog.error(type + ": Different penalty for the assigned value (difference: " + inc + ")!");
1458                        }
1459                    }
1460                }
1461            }
1462        }
1463
1464        /**
1465         * Called when a value is unassigned from a variable. Internal number of
1466         * time overlapping conflicts is updated, see
1467         * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}.
1468         */
1469        @Override
1470        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment value) {
1471            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
1472            for (Type type: iContext.getTypes()) {
1473                iTotalPenalty[type.ordinal()] -= allPenalty(type, assignment, value);
1474                for (Conflict c: allConflicts(type, assignment, value))
1475                    cx.remove(assignment, c);
1476            }
1477            if (iContext.isDebug()) {
1478                sLog.debug("U:" + value.variable() + " := " + value);
1479                for (Type type: iContext.getTypes()) {
1480                    int dec = allPenalty(type, assignment, value);
1481                    if (dec != 0) {
1482                        sLog.debug("--  " + type + " -" + dec + " U: " + value.variable() + " := " + value);
1483                        for (Conflict c: allConflicts(type, assignment, value)) {
1484                            sLog.debug("  -- " + c);
1485                            iAllConflicts[type.ordinal()].remove(c);
1486                            dec -= c.getPenalty();
1487                        }
1488                        if (dec != 0) {
1489                            sLog.error(type + ":Different penalty for the unassigned value (difference: " + dec + ")!");
1490                        }
1491                    }
1492                }
1493            }
1494        }
1495        
1496        /**
1497         * Called before a value is assigned to a variable.
1498         * @param assignment current assignment
1499         * @param iteration current iteration
1500         * @param value value to be assigned
1501         */
1502        public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1503            if (value != null) {
1504                Enrollment old = assignment.getValue(value.variable());
1505                if (old != null) {
1506                    iUnassignedValue = old;
1507                    unassigned(assignment, old);
1508                }
1509                iOldVariable = value.variable();
1510            }
1511        }
1512
1513        /**
1514         * Called after a value is assigned to a variable.
1515         * @param assignment current assignment
1516         * @param iteration current iteration
1517         * @param value value that was assigned
1518         */
1519        public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1520            iOldVariable = null;
1521            iUnassignedValue = null;
1522            if (value != null) {
1523                assigned(assignment, value);
1524            }
1525        }
1526
1527        /**
1528         * Called after a value is unassigned from a variable.
1529         * @param assignment current assignment
1530         * @param iteration current iteration
1531         * @param value value that was unassigned
1532         */
1533        public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
1534            if (value != null && !value.equals(iUnassignedValue)) {
1535                unassigned(assignment, value);
1536            }
1537        }
1538        
1539        public Set<Conflict> getAllConflicts(Type type) {
1540            return iAllConflicts[type.ordinal()];
1541        }
1542        
1543        public int getTotalPenalty(Type type) {
1544            return iTotalPenalty[type.ordinal()];
1545        }
1546        
1547        public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) {
1548            int total = countTotalPenalty(type, assignment);
1549            if (total != iTotalPenalty[type.ordinal()]) {
1550                sLog.error(type + " penalty does not match for (actual: " + total + ", count: " + iTotalPenalty[type.ordinal()] + ")!");
1551                iTotalPenalty[type.ordinal()] = total;
1552                if (iContext.isDebug()) {
1553                    Set<Conflict> conflicts = computeAllConflicts(type, assignment);
1554                    for (Conflict c: conflicts) {
1555                        if (!iAllConflicts[type.ordinal()].contains(c))
1556                            sLog.debug("  +add+ " + c);
1557                    }
1558                    for (Conflict c: iAllConflicts[type.ordinal()]) {
1559                        if (!conflicts.contains(c))
1560                            sLog.debug("  -rem- " + c);
1561                    }
1562                    for (Conflict c: conflicts) {
1563                        for (Conflict d: iAllConflicts[type.ordinal()]) {
1564                            if (c.equals(d) && c.getPenalty() != d.getPenalty()) {
1565                                sLog.debug("  -dif- " + c + " (other: " + d.getPenalty() + ")");
1566                            }
1567                        }
1568                    }                
1569                    iAllConflicts[type.ordinal()] = conflicts;
1570                }
1571            }
1572        }
1573        
1574        public int countTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) {
1575            int total = 0;
1576            for (Request r1 : getModel().variables()) {
1577                Enrollment e1 = assignment.getValue(r1);
1578                if (e1 == null || r1.equals(iOldVariable)) continue;
1579                for (Request r2 : r1.getStudent().getRequests()) {
1580                    Enrollment e2 = assignment.getValue(r2);
1581                    if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
1582                        if (type.isApplicable(iContext, r1.getStudent(), r1, r2))
1583                            total += penalty(type, e1, e2);
1584                    }
1585                }
1586                total += penalty(type, e1);
1587            }
1588            return total;
1589        }
1590
1591        public Set<Conflict> computeAllConflicts(Type type, Assignment<Request, Enrollment> assignment) {
1592            Set<Conflict> ret = new HashSet<Conflict>();
1593            for (Request r1 : getModel().variables()) {
1594                Enrollment e1 = assignment.getValue(r1);
1595                if (e1 == null || r1.equals(iOldVariable)) continue;
1596                for (Request r2 : r1.getStudent().getRequests()) {
1597                    Enrollment e2 = assignment.getValue(r2);
1598                    if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
1599                        if (type.isApplicable(iContext, r1.getStudent(), r1, r2))
1600                            ret.addAll(conflicts(type, e1, e2));
1601                    }                    
1602                }
1603                ret.addAll(conflicts(type, e1));
1604            }
1605            return ret;
1606        }
1607        
1608        public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Student student) {
1609            Set<Conflict> ret = new HashSet<Conflict>();
1610            for (Request r1 : student.getRequests()) {
1611                Enrollment e1 = assignment.getValue(r1);
1612                if (e1 == null) continue;
1613                for (Request r2 : student.getRequests()) {
1614                    Enrollment e2 = assignment.getValue(r2);
1615                    if (e2 != null && r1.getId() < r2.getId()) {
1616                        if (type.isApplicable(iContext, r1.getStudent(), r1, r2))
1617                            ret.addAll(conflicts(type, e1, e2));
1618                    }
1619                }
1620                ret.addAll(conflicts(type, e1));
1621            }
1622            return ret;
1623        }
1624
1625        public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
1626            Set<Conflict> ret = new HashSet<Conflict>();
1627            for (Request request : enrollment.getStudent().getRequests()) {
1628                if (request.equals(enrollment.getRequest())) continue;
1629                if (assignment.getValue(request) != null && !request.equals(iOldVariable)) {
1630                    ret.addAll(conflicts(type, enrollment, assignment.getValue(request)));
1631                }
1632            }
1633            ret.addAll(conflicts(type, enrollment));
1634            return ret;
1635        }
1636        
1637        public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Student student) {
1638            int penalty = 0;
1639            for (Request r1 : student.getRequests()) {
1640                Enrollment e1 = assignment.getValue(r1);
1641                if (e1 == null) continue;
1642                for (Request r2 : student.getRequests()) {
1643                    Enrollment e2 = assignment.getValue(r2);
1644                    if (e2 != null && r1.getId() < r2.getId()) {
1645                        if (type.isApplicable(iContext, r1.getStudent(), r1, r2))
1646                            penalty += penalty(type, e1, e2); 
1647                    }
1648                }
1649                penalty += penalty(type, e1);
1650            }
1651            return penalty;
1652        }
1653        
1654        public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
1655            int penalty = 0;
1656            for (Request request : enrollment.getStudent().getRequests()) {
1657                if (request.equals(enrollment.getRequest())) continue;
1658                if (assignment.getValue(request) != null && !request.equals(iOldVariable)) {
1659                    if (type.isApplicable(iContext, enrollment.getStudent(), enrollment.variable(), request))
1660                        penalty += penalty(type, enrollment, assignment.getValue(request));
1661                }
1662            }
1663            penalty += penalty(type, enrollment);
1664            return penalty;
1665        }
1666    }
1667
1668    @Override
1669    public StudentQualityContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
1670        return new StudentQualityContext(assignment);
1671    }
1672
1673    @Override
1674    public StudentQualityContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, StudentQualityContext parentContext) {
1675        return new StudentQualityContext(parentContext);
1676    }
1677    
1678    /** Empty iterator */
1679    public static class Nothing implements Iterable<SctAssignment> {
1680        @Override
1681        public Iterator<SctAssignment> iterator() {
1682            return new Iterator<SctAssignment>() {
1683                @Override
1684                public SctAssignment next() { return null; }
1685                @Override
1686                public boolean hasNext() { return false; }
1687                @Override
1688                public void remove() { throw new UnsupportedOperationException(); }
1689            };
1690        }
1691    }
1692    
1693    /** Unavailabilities of a student */
1694    public static class Unavailabilities implements Iterable<Unavailability> {
1695        private Student iStudent;
1696        public Unavailabilities(Student student) { iStudent = student; }
1697        @Override
1698        public Iterator<Unavailability> iterator() { return iStudent.getUnavailabilities().iterator(); }
1699    }
1700    
1701    private static class SingleTime implements SctAssignment {
1702        private TimeLocation iTime = null;
1703        
1704        public SingleTime(int start, int end) {
1705            iTime = new TimeLocation(0x7f, start, end-start, 0, 0.0, 0, null, null, new BitSet(), 0);
1706        }
1707
1708        @Override
1709        public TimeLocation getTime() { return iTime; }
1710        @Override
1711        public List<RoomLocation> getRooms() { return null; }
1712        @Override
1713        public int getNrRooms() { return 0; }
1714        @Override
1715        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {}
1716        @Override
1717        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {}
1718        @Override
1719        public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { return null; }
1720        @Override
1721        public boolean isAllowOverlap() { return false; }
1722        @Override
1723        public long getId() { return -1;}
1724        @Override
1725        public int compareById(SctAssignment a) { return 0; }
1726
1727        @Override
1728        public boolean isOverlapping(SctAssignment assignment) {
1729            return assignment.getTime() != null && getTime().shareDays(assignment.getTime()) && getTime().shareHours(assignment.getTime());
1730        }
1731
1732        @Override
1733        public boolean isOverlapping(Set<? extends SctAssignment> assignments) {
1734            for (SctAssignment assignment : assignments) {
1735                if (isOverlapping(assignment)) return true;
1736            }
1737            return false;
1738        }
1739    }
1740    
1741    /** Early/late time */
1742    public static class SingleTimeIterable implements Iterable<SingleTime> {
1743        private SingleTime iTime = null;
1744        public SingleTimeIterable(int start, int end) {
1745            if (start < end)
1746                iTime = new SingleTime(start, end);
1747            
1748        }
1749        @Override
1750        public Iterator<SingleTime> iterator() {
1751            return new Iterator<SingleTime>() {
1752                @Override
1753                public SingleTime next() {
1754                    SingleTime ret = iTime; iTime = null; return ret;
1755                }
1756                @Override
1757                public boolean hasNext() { return iTime != null; }
1758                @Override
1759                public void remove() { throw new UnsupportedOperationException(); }
1760            };
1761        }
1762    }
1763    
1764    /** Free times of a student */
1765    public static class FreeTimes implements Iterable<FreeTimeRequest> {
1766        private Student iStudent;
1767        public FreeTimes(Student student) {
1768            iStudent = student;
1769        }
1770        
1771        @Override
1772        public Iterator<FreeTimeRequest> iterator() {
1773            return new Iterator<FreeTimeRequest>() {
1774                Iterator<Request> i = iStudent.getRequests().iterator();
1775                FreeTimeRequest next = null;
1776                boolean hasNext = nextFreeTime();
1777                
1778                private boolean nextFreeTime() {
1779                    while (i.hasNext()) {
1780                        Request r = i.next();
1781                        if (r instanceof FreeTimeRequest) {
1782                            next = (FreeTimeRequest)r;
1783                            return true;
1784                        }
1785                    }
1786                    return false;
1787                }
1788                
1789                @Override
1790                public FreeTimeRequest next() {
1791                    try {
1792                        return next;
1793                    } finally {
1794                        hasNext = nextFreeTime();
1795                    }
1796                }
1797                @Override
1798                public boolean hasNext() { return hasNext; }
1799                @Override
1800                public void remove() { throw new UnsupportedOperationException(); }
1801            };
1802        }
1803    }
1804    
1805    /** Online (or not-online) classes of an enrollment */
1806    public static class Online implements Iterable<Section> {
1807        private Enrollment iEnrollment;
1808        private boolean iOnline;
1809        public Online(Enrollment enrollment, boolean online) {
1810            iEnrollment = enrollment;
1811            iOnline = online;
1812        }
1813        
1814        protected boolean skip(Section section) {
1815            return iOnline != section.isOnline();
1816        }
1817        
1818        @Override
1819        public Iterator<Section> iterator() {
1820            return new Iterator<Section>() {
1821                Iterator<Section> i = iEnrollment.getSections().iterator();
1822                Section next = null;
1823                boolean hasNext = nextSection();
1824                
1825                private boolean nextSection() {
1826                    while (i.hasNext()) {
1827                        Section r = i.next();
1828                        if (!skip(r)) {
1829                            next = r;
1830                            return true;
1831                        }
1832                    }
1833                    return false;
1834                }
1835                
1836                @Override
1837                public Section next() {
1838                    try {
1839                        return next;
1840                    } finally {
1841                        hasNext = nextSection();
1842                    }
1843                }
1844                @Override
1845                public boolean hasNext() { return hasNext; }
1846                @Override
1847                public void remove() { throw new UnsupportedOperationException(); }
1848            };
1849        }
1850    }
1851
1852    @Override
1853    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
1854        StudentQualityContext cx = getContext(assignment);
1855        if (iContext.isDebug())
1856            for (Type type: iContext.getTypes())
1857                info.put("[Schedule Quality] " + type.getName(), String.valueOf(cx.getTotalPenalty(type)));
1858    }
1859
1860    @Override
1861    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
1862    }
1863    
1864    public String toString(Assignment<Request, Enrollment> assignment) {
1865        String ret = "";
1866        StudentQualityContext cx = getContext(assignment);
1867        for (Type type: iContext.getTypes()) {
1868            int p = cx.getTotalPenalty(type);
1869            if (p != 0) {
1870                ret += (ret.isEmpty() ? "" : ", ") + type.getAbbv() + ": " + p;
1871            }
1872        }
1873        return ret;
1874    }
1875    
1876    public boolean hasDistanceConflict(Student student, Section s1, Section s2) {
1877        if (student.isNeedShortDistances())
1878            return Type.ShortDistance.inConflict(iContext, s1, s2);
1879        else
1880            return Type.Distance.inConflict(iContext, s1, s2);
1881    }
1882}