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