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