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