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