001package org.cpsolver.studentsct.online.selection;
002
003import java.util.ArrayList;
004import java.util.HashSet;
005import java.util.Hashtable;
006import java.util.List;
007import java.util.Set;
008
009import org.cpsolver.coursett.model.TimeLocation;
010import org.cpsolver.ifs.assignment.Assignment;
011import org.cpsolver.studentsct.extension.DistanceConflict;
012import org.cpsolver.studentsct.extension.StudentQuality;
013import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
014import org.cpsolver.studentsct.model.CourseRequest;
015import org.cpsolver.studentsct.model.Enrollment;
016import org.cpsolver.studentsct.model.FreeTimeRequest;
017import org.cpsolver.studentsct.model.Request;
018import org.cpsolver.studentsct.model.Section;
019import org.cpsolver.studentsct.model.Student;
020import org.cpsolver.studentsct.model.Subpart;
021import org.cpsolver.studentsct.model.Unavailability;
022import org.cpsolver.studentsct.online.OnlineSectioningModel;
023import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion;
024import org.cpsolver.studentsct.weights.StudentWeights;
025
026/**
027* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the
028* following criteria:
029* <ul>
030* <li>best priority & alternativity ignoring free time requests (a better solution has a higher priority course assigned or does not use alternative request if possible)
031* <li>avoid or minimize course time overlaps
032* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process)
033* <li>best priority & alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests)
034* <li>maximise selection (preferred sections)
035* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests)
036* <li>avoid or minimise distance conflicts
037* <li>avoid classes that have no time assignment (arranged hours)
038* <li>balance sections
039* <li>minimise class penalties (expressing how much a class is over-expected)
040* </ul>
041* 
042* @version StudentSct 1.3 (Student Sectioning)<br>
043*          Copyright (C) 2014 Tomáš Müller<br>
044*          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
045*          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
046* <br>
047*          This library is free software; you can redistribute it and/or modify
048*          it under the terms of the GNU Lesser General Public License as
049*          published by the Free Software Foundation; either version 3 of the
050*          License, or (at your option) any later version. <br>
051* <br>
052*          This library is distributed in the hope that it will be useful, but
053*          WITHOUT ANY WARRANTY; without even the implied warranty of
054*          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
055*          Lesser General Public License for more details. <br>
056* <br>
057*          You should have received a copy of the GNU Lesser General Public
058*          License along with this library; if not see <a
059*          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
060* 
061*/
062public class OnlineSectioningCriterion implements SelectionCriterion {
063    private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
064    private List<TimeToAvoid> iTimesToAvoid = null;
065    private OnlineSectioningModel iModel;
066    private Student iStudent;
067    protected double[] iQalityWeights;
068
069    /**
070     * Constructor
071     * @param student current student
072     * @param model online student sectioning model
073     * @param assignment current assignment
074     * @param preferredSections preferred sections
075     */
076    public OnlineSectioningCriterion(Student student, OnlineSectioningModel model,
077            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) {
078        iStudent = student;
079        iModel = model;
080        iPreferredSections = preferredSections;
081        if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) {
082            iTimesToAvoid = new ArrayList<TimeToAvoid>();
083            for (Request r : iStudent.getRequests()) {
084                if (r instanceof CourseRequest) {
085                    List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment);
086                    if (enrollments.size() <= 5) {
087                        int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size());
088                        for (Enrollment enrollment : enrollments)
089                            for (Section section : enrollment.getSections())
090                                if (section.getTime() != null)
091                                    iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority()));
092                    }
093                } else if (r instanceof FreeTimeRequest) {
094                    iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE));
095                }
096            }
097            for (Unavailability unavailability: iStudent.getUnavailabilities())
098                if (unavailability.getTime() != null)
099                    iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE));
100        }
101        iQalityWeights = new double[StudentQuality.Type.values().length];
102        for (StudentQuality.Type type: StudentQuality.Type.values()) {
103            iQalityWeights[type.ordinal()] = model.getProperties().getPropertyDouble(type.getWeightName(), type.getWeightDefault());
104        }
105    }
106
107    protected OnlineSectioningModel getModel() {
108        return iModel;
109    }
110
111    protected Student getStudent() {
112        return iStudent;
113    }
114
115    protected Set<Section> getPreferredSections(Request request) {
116        return iPreferredSections.get(request);
117    }
118
119    protected List<TimeToAvoid> getTimesToAvoid() {
120        return iTimesToAvoid;
121    }
122
123    /**
124     * Distance conflicts of idx-th assignment of the current schedule
125     */
126    public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) {
127        if (getModel().getDistanceConflict() == null || assignment[idx] == null)
128            return null;
129        Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]);
130        for (int x = 0; x < idx; x++)
131            if (assignment[x] != null)
132                dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx]));
133        return dist;
134    }
135
136    /**
137     * Time overlapping conflicts of idx-th assignment of the current schedule
138     */
139    public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) {
140        if (getModel().getTimeOverlaps() == null || assignment[idx] == null)
141            return null;
142        Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
143        for (int x = 0; x < idx; x++)
144            if (assignment[x] != null) {
145                overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx]));
146            } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
147                overlaps.addAll(getModel().getTimeOverlaps().conflicts(
148                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx]));
149        overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx]));
150        return overlaps;
151    }
152    
153    public Set<StudentQuality.Conflict> getStudentQualityConflicts(Enrollment[] assignment, int idx) {
154        if (getModel().getStudentQuality() == null || assignment[idx] == null)
155            return null;
156        Set<StudentQuality.Conflict> conflicts = new HashSet<StudentQuality.Conflict>();
157        for (StudentQuality.Type t: StudentQuality.Type.values()) {
158            for (int x = 0; x < idx; x++)
159                if (assignment[x] != null)
160                    conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[x], assignment[idx]));
161            conflicts.addAll(getModel().getStudentQuality().conflicts(t, assignment[idx]));
162        }
163        return conflicts;
164    }
165
166    /**
167     * Weight of an assignment. Unlike
168     * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this
169     * side of distance conflicts and time overlaps.
170     **/
171    @Deprecated
172    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
173            Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
174        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
175        if (distanceConflicts != null)
176            for (DistanceConflict.Conflict c : distanceConflicts) {
177                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
178                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
179                    weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c);
180            }
181        if (timeOverlappingConflicts != null)
182            for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) {
183                weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c);
184            }
185        return enrollment.getRequest().getWeight() * weight;
186    }
187    
188    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> conflicts) {
189        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
190        if (conflicts != null)
191            for (StudentQuality.Conflict c : conflicts) {
192                weight += getModel().getStudentWeights().getStudentQualityConflictWeight(assignment, enrollment, c);
193            }
194        return enrollment.getRequest().getWeight() * weight;
195    }
196
197    public Request getRequest(int index) {
198        return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index));
199    }
200
201    public boolean isFreeTime(int index) {
202        Request r = getRequest(index);
203        return r != null && r instanceof FreeTimeRequest;
204    }
205    
206    @Override
207    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
208        if (best == null)
209            return -1;
210
211        // 0. best priority & alternativity ignoring free time requests
212        boolean ft = false;
213        boolean res = false;
214        for (int idx = 0; idx < current.length; idx++) {
215            if (isFreeTime(idx)) {
216                ft = true;
217                continue;
218            }
219            Request request = getRequest(idx);
220            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
221            if (best[idx] != null && best[idx].getAssignments() != null) {
222                if (current[idx] == null || current[idx].getSections() == null)
223                    return 1; // higher priority request assigned
224                if (best[idx].getTruePriority() < current[idx].getTruePriority())
225                    return 1; // less alternative request assigned
226                if (best[idx].getTruePriority() > current[idx].getTruePriority())
227                    return -1; // less alternative request assigned
228            } else {
229                if (current[idx] != null && current[idx].getAssignments() != null)
230                    return -1; // higher priority request assigned
231            }
232        }
233        
234        // 0.1. allowed, but not available sections
235        int bestNotAvailable = 0, currentNotAvailable = 0;
236        for (int idx = 0; idx < current.length; idx++) {
237            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
238                for (Section section: best[idx].getSections()) {
239                    if (section.getLimit() == 0)
240                        bestNotAvailable ++;
241                }
242            }
243            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
244                for (Section section: current[idx].getSections()) {
245                    if (section.getLimit() == 0)
246                        currentNotAvailable ++;
247                }
248            }
249        }
250        if (bestNotAvailable > currentNotAvailable) return -1;
251        if (bestNotAvailable < currentNotAvailable) return 1;
252
253        // 0.5. avoid course time overlaps & unavailabilities
254        if (getModel().getStudentQuality() != null) {
255            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
256            for (int idx = 0; idx < current.length; idx++) {
257                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) {
258                    for (int x = 0; x < idx; x++) {
259                        if (best[x] != null && best[x].getAssignments() != null && best[x].getRequest() instanceof CourseRequest)
260                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
261                    }
262                }
263                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) {
264                    for (int x = 0; x < idx; x++) {
265                        if (current[x] != null && current[x].getAssignments() != null && current[x].getRequest() instanceof CourseRequest)
266                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
267                    }
268                }
269            }
270            for (int idx = 0; idx < current.length; idx++) {
271                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
272                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
273                }
274                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
275                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
276                }
277            }
278            if (currentTimeOverlaps < bestTimeOverlaps)
279                return -1;
280            if (bestTimeOverlaps < currentTimeOverlaps)
281                return 1;
282        } else if (getModel().getTimeOverlaps() != null) {
283            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
284            for (int idx = 0; idx < current.length; idx++) {
285                if (best[idx] != null && best[idx].getAssignments() != null
286                                && best[idx].getRequest() instanceof CourseRequest) {
287                    for (int x = 0; x < idx; x++) {
288                        if (best[x] != null && best[x].getAssignments() != null
289                                        && best[x].getRequest() instanceof CourseRequest)
290                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
291                    }
292                    for (int x = 0; x < idx; x++) {
293                        if (current[x] != null && current[x].getAssignments() != null
294                                        && current[x].getRequest() instanceof CourseRequest)
295                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
296                    }
297                }
298            }
299            for (int idx = 0; idx < current.length; idx++) {
300                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
301                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
302                }
303                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
304                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
305                }
306            }
307            if (currentTimeOverlaps < bestTimeOverlaps)
308                return -1;
309            if (bestTimeOverlaps < currentTimeOverlaps)
310                return 1;
311        }
312
313        // 1. minimize number of penalties
314        double bestPenalties = 0, currentPenalties = 0;
315        for (int idx = 0; idx < current.length; idx++) {
316            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
317                for (Section section : best[idx].getSections())
318                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
319                for (Section section : current[idx].getSections())
320                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
321            }
322        }
323        if (currentPenalties < bestPenalties)
324            return -1;
325        if (bestPenalties < currentPenalties)
326            return 1;
327
328        // 2. best priority & alternativity including free time requests
329        if (ft) {
330            for (int idx = 0; idx < current.length; idx++) {
331                if (best[idx] != null && best[idx].getAssignments() != null) {
332                    if (current[idx] == null || current[idx].getSections() == null)
333                        return 1; // higher priority request assigned
334                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
335                        return 1; // less alternative request assigned
336                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
337                        return -1; // less alternative request assigned
338                } else {
339                    if (current[idx] != null && current[idx].getAssignments() != null)
340                        return -1; // higher priority request assigned
341                }
342            }
343        }
344
345        // 3. maximize selection
346        int bestSelected = 0, currentSelected = 0;
347        for (int idx = 0; idx < current.length; idx++) {
348            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
349                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
350                if (preferred != null && !preferred.isEmpty()) {
351                    for (Section section : best[idx].getSections())
352                        if (preferred.contains(section))
353                            bestSelected++;
354                    for (Section section : current[idx].getSections())
355                        if (preferred.contains(section))
356                            currentSelected++;
357                }
358            }
359        }
360        if (currentSelected > bestSelected)
361            return -1;
362        if (bestSelected > currentSelected)
363            return 1;
364        
365        // 3.5 maximize preferences
366        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
367        double bestSelectedSections = 0, currentSelectedSections = 0;
368        for (int idx = 0; idx < current.length; idx++) {
369            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
370                bestSelectedSections += best[idx].percentSelectedSameSection();
371                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
372            }
373            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
374                currentSelectedSections += current[idx].percentSelectedSameSection();
375                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
376            }
377        }
378        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
379        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
380        
381        // 3.9 maximize selection with penalization for not followed reservations
382        if (res) {
383            for (int idx = 0; idx < current.length; idx++) {
384                if (best[idx] != null && best[idx].getAssignments() != null) {
385                    if (current[idx] == null || current[idx].getSections() == null)
386                        return 1; // higher priority request assigned
387                    if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
388                        return 1; // less alternative request assigned
389                    if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
390                        return -1; // less alternative request assigned
391                } else {
392                    if (current[idx] != null && current[idx].getAssignments() != null)
393                        return -1; // higher priority request assigned
394                }
395            }
396        }
397        
398        // 3.95 avoid past sections
399        int bestPast = 0, currentPast = 0;
400        for (int idx = 0; idx < current.length; idx++) {
401            if (best[idx] != null && best[idx].getAssignments() != null) {
402                for (Section section : best[idx].getSections()) {
403                    if (section.isPast())
404                        bestPast++;
405                }
406            }
407            if (current[idx] != null && current[idx].getAssignments() != null) {
408                for (Section section : current[idx].getSections()) {
409                    if (section.isPast())
410                        currentPast++;
411                }
412            }
413        }
414        if (currentPast < bestPast)
415            return -1;
416        if (bestPast < currentPast)
417            return 1;
418
419        // 4-5. student quality
420        if (getModel().getStudentQuality() != null) {
421            double bestQuality = 0, currentQuality = 0;
422            for (StudentQuality.Type type: StudentQuality.Type.values()) {
423                for (int idx = 0; idx < current.length; idx++) {
424                    if (best[idx] != null && best[idx].getAssignments() != null) {
425                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
426                        for (int x = 0; x < idx; x++) {
427                            if (best[x] != null && best[x].getAssignments() != null)
428                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
429                        }
430                    }
431                    if (current[idx] != null && current[idx].getAssignments() != null) {
432                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
433                        for (int x = 0; x < idx; x++) {
434                            if (current[x] != null && current[x].getAssignments() != null)
435                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
436                        }
437                    }
438                }
439            }
440            if (currentQuality < bestQuality)
441                return -1;
442            if (bestQuality < currentQuality)
443                return 1;
444        } else {
445            // 4. avoid time overlaps
446            if (getModel().getTimeOverlaps() != null) {
447                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
448                for (int idx = 0; idx < current.length; idx++) {
449                    if (best[idx] != null && best[idx].getAssignments() != null) {
450                        for (int x = 0; x < idx; x++) {
451                            if (best[x] != null && best[x].getAssignments() != null)
452                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
453                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
454                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]);
455                        }
456                        for (int x = 0; x < idx; x++) {
457                            if (current[x] != null && current[x].getAssignments() != null)
458                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
459                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
460                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]);
461                        }
462                    }
463                }
464                for (int idx = 0; idx < current.length; idx++) {
465                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
466                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
467                    }
468                    if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
469                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
470                    }
471                }
472                if (currentTimeOverlaps < bestTimeOverlaps)
473                    return -1;
474                if (bestTimeOverlaps < currentTimeOverlaps)
475                    return 1;
476            }
477
478            // 5. avoid distance conflicts
479            if (getModel().getDistanceConflict() != null) {
480                int bestDistanceConf = 0, currentDistanceConf = 0;
481                for (int idx = 0; idx < current.length; idx++) {
482                    if (best[idx] != null && best[idx].getAssignments() != null) {
483                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
484                        for (int x = 0; x < idx; x++) {
485                            if (best[x] != null && best[x].getAssignments() != null)
486                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
487                        }
488                    }
489                    if (current[idx] != null && current[idx].getAssignments() != null) {
490                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
491                        for (int x = 0; x < idx; x++) {
492                            if (current[x] != null && current[x].getAssignments() != null)
493                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
494                        }
495                    }
496                }
497                if (currentDistanceConf < bestDistanceConf)
498                    return -1;
499                if (bestDistanceConf < currentDistanceConf)
500                    return 1;
501            }
502        }
503
504        // 6. avoid no-time and online sections (no-time first, online second)
505        int bestNoTime = 0, currentNoTime = 0;
506        int bestOnline = 0, currentOnline = 0;
507        for (int idx = 0; idx < current.length; idx++) {
508            if (best[idx] != null && best[idx].getAssignments() != null) {
509                for (Section section : best[idx].getSections()) {
510                    if (!section.hasTime())
511                        bestNoTime++;
512                    if (section.isOnline())
513                        bestOnline++;
514                }
515                for (Section section : current[idx].getSections()) {
516                    if (!section.hasTime())
517                        currentNoTime++;
518                    if (section.isOnline())
519                        currentOnline++;
520                }
521            }
522        }
523        if (currentNoTime < bestNoTime)
524            return -1;
525        if (bestNoTime < currentNoTime)
526            return 1;
527        if (currentOnline < bestOnline)
528            return -1;
529        if (bestOnline < currentOnline)
530            return 1;
531
532        // 7. balance sections
533        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
534        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
535        for (int idx = 0; idx < current.length; idx++) {
536            if (best[idx] != null && best[idx].getAssignments() != null) {
537                for (Section section : best[idx].getSections()) {
538                    Subpart subpart = section.getSubpart();
539                    // skip unlimited and single section subparts
540                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
541                        continue;
542                    // average size
543                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
544                    // section is below average
545                    if (section.getLimit() < averageSize)
546                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
547                    bestAltSectionsWithLimit++;
548                }
549                for (Section section : current[idx].getSections()) {
550                    Subpart subpart = section.getSubpart();
551                    // skip unlimited and single section subparts
552                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
553                        continue;
554                    // average size
555                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
556                    // section is below average
557                    if (section.getLimit() < averageSize)
558                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
559                    currentAltSectionsWithLimit++;
560                }
561            }
562        }
563        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
564                : 0.0);
565        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
566                / currentAltSectionsWithLimit : 0.0);
567        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
568            return -1;
569        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
570            return 1;
571
572        // 8. average penalty sections
573        double bestPenalty = 0.0, currentPenalty = 0.0;
574        for (int idx = 0; idx < current.length; idx++) {
575            if (best[idx] != null && best[idx].getAssignments() != null) {
576                for (Section section : best[idx].getSections())
577                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
578                for (Section section : current[idx].getSections())
579                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
580            }
581        }
582        if (currentPenalty < bestPenalty)
583            return -1;
584        if (bestPenalty < currentPenalty)
585            return 1;
586
587        return 0;
588    }
589
590    @Override
591    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
592            Enrollment[] best) {
593        // 0. best priority & alternativity ignoring free time requests
594        int alt = 0;
595        boolean ft = false;
596        boolean res = false;
597        for (int idx = 0; idx < current.length; idx++) {
598            if (isFreeTime(idx)) {
599                ft = true;
600                continue;
601            }
602            Request request = getRequest(idx);
603            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
604            if (idx < maxIdx) {
605                if (best[idx] != null) {
606                    if (current[idx] == null)
607                        return false; // higher priority request assigned
608                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
609                        return false; // less alternative request assigned
610                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
611                        return true; // less alternative request assigned
612                    if (request.isAlternative())
613                        alt--;
614                } else {
615                    if (current[idx] != null)
616                        return true; // higher priority request assigned
617                    if (!request.isAlternative())
618                        alt++;
619                }
620            } else {
621                if (best[idx] != null) {
622                    if (best[idx].getTruePriority() > 0)
623                        return true; // alternativity can be improved
624                } else {
625                    if (!request.isAlternative() || alt > 0)
626                        return true; // priority can be improved
627                }
628            }
629        }
630        
631        // 0.1. allowed, but not available sections
632        int notAvailable = 0;
633        for (int idx = 0; idx < current.length; idx++) {
634            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
635                for (Section section: best[idx].getSections()) {
636                    if (section.getLimit() == 0)
637                        notAvailable ++;
638                }
639            }
640            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
641                for (Section section: current[idx].getSections()) {
642                    if (section.getLimit() == 0)
643                        notAvailable --;
644                }
645            }
646        }
647        if (notAvailable > 0) {
648            return true;
649        }
650
651        // 0.5. avoid course time overlaps & unavailability overlaps
652        if (getModel().getStudentQuality() != null) {
653            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
654            for (int idx = 0; idx < current.length; idx++) {
655                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
656                    for (int x = 0; x < idx; x++) {
657                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
658                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
659                    }
660                }
661                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
662                    for (int x = 0; x < idx; x++) {
663                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
664                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
665                    }
666                }
667            }
668            for (int idx = 0; idx < current.length; idx++) {
669                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
670                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
671                }
672                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
673                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
674                }
675            }
676            if (currentTimeOverlaps < bestTimeOverlaps)
677                return true;
678            if (bestTimeOverlaps < currentTimeOverlaps)
679                return false;
680        } else if (getModel().getTimeOverlaps() != null) {
681            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
682            for (int idx = 0; idx < current.length; idx++) {
683                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
684                    for (int x = 0; x < idx; x++) {
685                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
686                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
687                    }
688                }
689                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
690                    for (int x = 0; x < idx; x++) {
691                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
692                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
693                    }
694                }
695            }
696            for (int idx = 0; idx < current.length; idx++) {
697                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
698                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
699                }
700                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
701                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
702                }
703            }
704            if (currentTimeOverlaps < bestTimeOverlaps)
705                return true;
706            if (bestTimeOverlaps < currentTimeOverlaps)
707                return false;
708        }
709
710        // 1. maximize number of penalties
711        double bestPenalties = 0, currentPenalties = 0;
712        for (int idx = 0; idx < current.length; idx++) {
713            if (best[idx] != null) {
714                for (Section section : best[idx].getSections())
715                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
716            }
717            if (current[idx] != null && idx < maxIdx) {
718                for (Section section : current[idx].getSections())
719                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
720            }
721        }
722        if (currentPenalties < bestPenalties)
723            return true;
724        if (bestPenalties < currentPenalties)
725            return false;
726
727        // 2. best priority & alternativity including free times
728        if (ft) {
729            alt = 0;
730            for (int idx = 0; idx < current.length; idx++) {
731                Request request = getStudent().getRequests().get(idx);
732                if (idx < maxIdx) {
733                    if (best[idx] != null) {
734                        if (current[idx] == null)
735                            return false; // higher priority request assigned
736                        if (best[idx].getTruePriority() < current[idx].getTruePriority())
737                            return false; // less alternative request assigned
738                        if (best[idx].getTruePriority() > current[idx].getTruePriority())
739                            return true; // less alternative request assigned
740                        if (request.isAlternative())
741                            alt--;
742                    } else {
743                        if (current[idx] != null)
744                            return true; // higher priority request assigned
745                        if (request instanceof CourseRequest && !request.isAlternative())
746                            alt++;
747                    }
748                } else {
749                    if (best[idx] != null) {
750                        if (best[idx].getTruePriority() > 0)
751                            return true; // alternativity can be improved
752                    } else {
753                        if (!request.isAlternative() || alt > 0)
754                            return true; // priority can be improved
755                    }
756                }
757            }
758        }
759
760        // 3. maximize selection
761        int bestSelected = 0, currentSelected = 0;
762        for (int idx = 0; idx < current.length; idx++) {
763            if (best[idx] != null && best[idx].isCourseRequest()) {
764                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
765                if (preferred != null && !preferred.isEmpty()) {
766                    for (Section section : best[idx].getSections())
767                        if (preferred.contains(section)) {
768                            if (idx < maxIdx)
769                                bestSelected++;
770                        } else if (idx >= maxIdx)
771                            bestSelected--;
772                }
773            }
774            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
775                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
776                if (preferred != null && !preferred.isEmpty()) {
777                    for (Section section : current[idx].getSections())
778                        if (preferred.contains(section))
779                            currentSelected++;
780                }
781            }
782        }
783        if (currentSelected > bestSelected)
784            return true;
785        if (bestSelected > currentSelected)
786            return false;
787
788        // 3.5 maximize preferences
789        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
790        double bestSelectedSections = 0, currentSelectedSections = 0;
791        for (int idx = 0; idx < current.length; idx++) {
792            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
793                bestSelectedSections += best[idx].percentSelectedSameSection();
794                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
795                if (idx >= maxIdx) {
796                    bestSelectedSections -= 1.0;
797                    bestSelectedConfigs -= 1.0;
798                }
799            }
800            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
801                currentSelectedSections += current[idx].percentSelectedSameSection();
802                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
803            }
804        }
805        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
806        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
807        
808        // 3.9 maximize selection with penalization for not followed reservations
809        if (res) {
810            alt = 0;
811            for (int idx = 0; idx < current.length; idx++) {
812                Request request = getStudent().getRequests().get(idx);
813                if (idx < maxIdx) {
814                    if (best[idx] != null) {
815                        if (current[idx] == null)
816                            return false; // higher priority request assigned
817                        if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
818                            return false; // less alternative request assigned
819                        if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
820                            return true; // less alternative request assigned
821                        if (request.isAlternative())
822                            alt--;
823                    } else {
824                        if (current[idx] != null)
825                            return true; // higher priority request assigned
826                        if (request instanceof CourseRequest && !request.isAlternative())
827                            alt++;
828                    }
829                } else {
830                    if (best[idx] != null) {
831                        if (best[idx].getTruePriority() > 0)
832                            return true; // alternativity can be improved
833                    } else {
834                        if (!request.isAlternative() || alt > 0)
835                            return true; // priority can be improved
836                    }
837                }
838            }
839        }
840        
841        // 3.95 avoid past sections
842        int bestPast = 0, currentPast = 0;
843        for (int idx = 0; idx < current.length; idx++) {
844            if (best[idx] != null && best[idx].getAssignments() != null) {
845                for (Section section : best[idx].getSections()) {
846                    if (section.isPast())
847                        bestPast++;
848                }
849            }
850            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null) {
851                for (Section section : current[idx].getSections()) {
852                    if (section.isPast())
853                        currentPast++;
854                }
855            }
856        }
857        if (currentPast < bestPast)
858            return true;
859        if (bestPast < currentPast)
860            return false;
861        
862        // 4-5. student quality
863        if (getModel().getStudentQuality() != null) {
864            double bestQuality = 0, currentQuality = 0;
865            for (StudentQuality.Type type: StudentQuality.Type.values()) {
866                for (int idx = 0; idx < current.length; idx++) {
867                    if (best[idx] != null) {
868                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
869                        for (int x = 0; x < idx; x++) {
870                            if (best[x] != null)
871                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
872                        }
873                    }
874                    if (current[idx] != null && idx < maxIdx) {
875                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
876                        for (int x = 0; x < idx; x++) {
877                            if (current[x] != null)
878                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
879                        }
880                    }
881                }
882            }
883            if (currentQuality < bestQuality)
884                return true;
885            if (bestQuality < currentQuality)
886                return false;
887        } else {
888            // 4. avoid time overlaps
889            if (getModel().getTimeOverlaps() != null) {
890                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
891                for (int idx = 0; idx < current.length; idx++) {
892                    if (best[idx] != null) {
893                        for (int x = 0; x < idx; x++) {
894                            if (best[x] != null)
895                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
896                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
897                                bestTimeOverlaps += getModel().getTimeOverlaps()
898                                        .nrConflicts(
899                                                ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
900                                                best[idx]);
901                        }
902                    }
903                    if (current[idx] != null && idx < maxIdx) {
904                        for (int x = 0; x < idx; x++) {
905                            if (current[x] != null)
906                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
907                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
908                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
909                                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
910                                        current[idx]);
911                        }
912                    }
913                }
914                for (int idx = 0; idx < current.length; idx++) {
915                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
916                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
917                    }
918                    if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
919                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
920                    }
921                }
922                if (currentTimeOverlaps < bestTimeOverlaps)
923                    return true;
924                if (bestTimeOverlaps < currentTimeOverlaps)
925                    return false;
926            }
927
928            // 5. avoid distance conflicts
929            if (getModel().getDistanceConflict() != null) {
930                int bestDistanceConf = 0, currentDistanceConf = 0;
931                for (int idx = 0; idx < current.length; idx++) {
932                    if (best[idx] != null) {
933                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
934                        for (int x = 0; x < idx; x++) {
935                            if (best[x] != null)
936                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
937                        }
938                    }
939                    if (current[idx] != null && idx < maxIdx) {
940                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
941                        for (int x = 0; x < idx; x++) {
942                            if (current[x] != null)
943                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
944                                        current[idx]);
945                        }
946                    }
947                }
948                if (currentDistanceConf < bestDistanceConf)
949                    return true;
950                if (bestDistanceConf < currentDistanceConf)
951                    return false;
952            }
953        }
954
955        // 6. avoid no-time and online sections (no-time first, online second)
956        int bestNoTime = 0, currentNoTime = 0;
957        int bestOnline = 0, currentOnline = 0;
958        for (int idx = 0; idx < current.length; idx++) {
959            if (best[idx] != null) {
960                for (Section section : best[idx].getSections()) {
961                    if (!section.hasTime())
962                        bestNoTime++;
963                    if (section.isOnline())
964                        bestOnline++;
965                }
966            }
967            if (current[idx] != null && idx < maxIdx) {
968                for (Section section : current[idx].getSections()) {
969                    if (!section.hasTime())
970                        currentNoTime++;
971                    if (section.isOnline())
972                        currentOnline++;
973                }
974            }
975        }
976        if (currentNoTime < bestNoTime)
977            return true;
978        if (bestNoTime < currentNoTime)
979            return false;
980        if (currentOnline < bestOnline)
981            return true;
982        if (bestOnline < currentOnline)
983            return false;
984
985        // 7. balance sections
986        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
987        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
988        for (int idx = 0; idx < current.length; idx++) {
989            if (best[idx] != null) {
990                for (Section section : best[idx].getSections()) {
991                    Subpart subpart = section.getSubpart();
992                    // skip unlimited and single section subparts
993                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
994                        continue;
995                    // average size
996                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
997                    // section is below average
998                    if (section.getLimit() < averageSize)
999                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
1000                    bestAltSectionsWithLimit++;
1001                }
1002            }
1003            if (current[idx] != null && idx < maxIdx) {
1004                for (Section section : current[idx].getSections()) {
1005                    Subpart subpart = section.getSubpart();
1006                    // skip unlimited and single section subparts
1007                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1008                        continue;
1009                    // average size
1010                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1011                    // section is below average
1012                    if (section.getLimit() < averageSize)
1013                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
1014                    currentAltSectionsWithLimit++;
1015                }
1016            }
1017        }
1018        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
1019                : 0.0);
1020        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
1021                / currentAltSectionsWithLimit : 0.0);
1022        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
1023            return true;
1024        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
1025            return false;
1026
1027        // 8. average penalty sections
1028        double bestPenalty = 0.0, currentPenalty = 0.0;
1029        for (int idx = 0; idx < current.length; idx++) {
1030            if (best[idx] != null) {
1031                for (Section section : best[idx].getSections())
1032                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
1033                if (idx >= maxIdx && best[idx].isCourseRequest())
1034                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
1035            }
1036            if (current[idx] != null && idx < maxIdx) {
1037                for (Section section : current[idx].getSections())
1038                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
1039            }
1040        }
1041        if (currentPenalty < bestPenalty)
1042            return true;
1043        if (bestPenalty < currentPenalty)
1044            return false;
1045
1046        return true;
1047    }
1048
1049    @Override
1050    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
1051        if (enrollemnts == null)
1052            return 0.0;
1053        double value = 0.0;
1054        for (int idx = 0; idx < enrollemnts.length; idx++) {
1055            if (enrollemnts[idx] != null)
1056                if (getModel().getStudentQuality() != null) {
1057                    value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx));
1058                } else { 
1059                    value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx));
1060                }
1061        }
1062        return value;
1063    }
1064
1065    @Override
1066    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
1067        // 1. alternativity
1068        if (e1.getTruePriority() < e2.getTruePriority())
1069            return -1;
1070        if (e1.getTruePriority() > e2.getTruePriority())
1071            return 1;
1072        
1073        // 1.5 not available sections
1074        int na1 = 0, na2 = 0;
1075        for (Section section: e1.getSections())
1076            if (section.getLimit() == 0) na1++;
1077        for (Section section: e2.getSections())
1078            if (section.getLimit() == 0) na2++;
1079        if (na1 < na2) return -1;
1080        if (na1 > na2) return 1;
1081        
1082        // 2. maximize number of penalties
1083        double p1 = 0, p2 = 0;
1084        for (Section section : e1.getSections())
1085            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
1086        for (Section section : e2.getSections())
1087            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
1088        if (p1 < p2)
1089            return -1;
1090        if (p2 < p1)
1091            return 1;
1092
1093        // 3. maximize selection
1094        if (e1.isCourseRequest()) {
1095            Set<Section> preferred = getPreferredSections(e1.getRequest());
1096            if (preferred != null && !preferred.isEmpty()) {
1097                int s1 = 0, s2 = 0;
1098                for (Section section : e1.getSections())
1099                    if (preferred.contains(section))
1100                        s1++;
1101                for (Section section : e2.getSections())
1102                    if (preferred.contains(section))
1103                        s2++;
1104                if (s2 > s1)
1105                    return -1;
1106                if (s1 > s2)
1107                    return 1;
1108            }
1109        }
1110        
1111        // 3.5 maximize preferences
1112        if (e1.isCourseRequest()) {
1113            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
1114            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
1115            if (s1 > s2) return -1;
1116            if (s2 > s1) return 1;
1117        }
1118        
1119        // 3.9 maximize selection with penalization for not followed reservations
1120        if (e1.getAdjustedPriority() < e2.getAdjustedPriority())
1121            return -1;
1122        if (e1.getAdjustedPriority() > e2.getAdjustedPriority())
1123            return 1;
1124        
1125        // 3.95 avoid past sections
1126        int w1 = 0, w2 = 0;
1127        for (Section section : e1.getSections()) {
1128            if (section.isPast())
1129                w1++;
1130        }
1131        for (Section section : e2.getSections()) {
1132            if (section.isPast())
1133                w2++;
1134        }
1135        if (w1 < w2)
1136            return -1;
1137        if (w2 < w1)
1138            return 1;
1139
1140        // 4. avoid time overlaps
1141        if (getTimesToAvoid() == null) {
1142            if (getModel().getStudentQuality() != null) {
1143                int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1);
1144                int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2);
1145                if (o1 < o2)
1146                    return -1;
1147                if (o2 < o1)
1148                    return 1;
1149            } else if (getModel().getTimeOverlaps() != null) {
1150                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
1151                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
1152                if (o1 < o2)
1153                    return -1;
1154                if (o2 < o1)
1155                    return 1;
1156            }
1157        } else {
1158            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
1159                double o1 = 0.0, o2 = 0.0;
1160                for (Section s : e1.getSections()) {
1161                    if (s.getTime() != null)
1162                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1163                            if (avoid.priority() > e1.getRequest().getPriority())
1164                                o1 += avoid.overlap(s.getTime());
1165                        }
1166                }
1167                for (Section s : e2.getSections()) {
1168                    if (s.getTime() != null)
1169                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1170                            if (avoid.priority() > e2.getRequest().getPriority())
1171                                o2 += avoid.overlap(s.getTime());
1172                        }
1173                }
1174                if (o1 < o2)
1175                    return -1;
1176                if (o2 < o1)
1177                    return 1;
1178            }
1179        }
1180
1181        // 5. avoid distance conflicts
1182        if (getModel().getDistanceConflict() != null) {
1183            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
1184            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
1185            if (c1 < c2)
1186                return -1;
1187            if (c2 < c1)
1188                return 1;
1189        }
1190
1191        // 6. avoid no-time and online sections (no-time first, online second)
1192        int n1 = 0, n2 = 0;
1193        int o1 = 0, o2 = 0;
1194        for (Section section : e1.getSections()) {
1195            if (!section.hasTime())
1196                n1++;
1197            if (section.isOnline())
1198                o1++;
1199        }
1200        for (Section section : e2.getSections()) {
1201            if (!section.hasTime())
1202                n2++;
1203            if (section.isOnline())
1204                o2++;
1205        }
1206        if (n1 < n2)
1207            return -1;
1208        if (n2 < n1)
1209            return 1;
1210        if (o1 < o2)
1211            return -1;
1212        if (o2 < o1)
1213            return 1;
1214
1215        // 7. balance sections
1216        double u1 = 0.0, u2 = 0.0;
1217        int a1 = 0, a2 = 0;
1218        for (Section section : e1.getSections()) {
1219            Subpart subpart = section.getSubpart();
1220            // skip unlimited and single section subparts
1221            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1222                continue;
1223            // average size
1224            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1225            // section is below average
1226            if (section.getLimit() < averageSize)
1227                u1 += (averageSize - section.getLimit()) / averageSize;
1228            a1++;
1229        }
1230        for (Section section : e2.getSections()) {
1231            Subpart subpart = section.getSubpart();
1232            // skip unlimited and single section subparts
1233            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1234                continue;
1235            // average size
1236            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1237            // section is below average
1238            if (section.getLimit() < averageSize)
1239                u2 += (averageSize - section.getLimit()) / averageSize;
1240            a2++;
1241        }
1242        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
1243        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
1244        if (f1 < f2)
1245            return -1;
1246        if (f2 < f1)
1247            return 1;
1248
1249        // 8. average penalty sections
1250        double x1 = 0.0, x2 = 0.0;
1251        for (Section section : e1.getSections())
1252            x1 += section.getPenalty() / e1.getSections().size();
1253        for (Section section : e2.getSections())
1254            x2 += section.getPenalty() / e2.getSections().size();
1255        if (x1 < x2)
1256            return -1;
1257        if (x2 < x1)
1258            return 1;
1259
1260        return 0;
1261    }
1262
1263    /**
1264     * Time to be avoided.
1265     */
1266    public static class TimeToAvoid {
1267        private TimeLocation iTime;
1268        private double iPenalty;
1269        private int iPriority;
1270
1271        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
1272            iTime = time;
1273            iPenalty = penalty;
1274            iPriority = priority;
1275        }
1276
1277        public int priority() {
1278            return iPriority;
1279        }
1280
1281        public double overlap(TimeLocation time) {
1282            if (time.hasIntersection(iTime)) {
1283                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime))
1284                        / (iTime.getNrMeetings() * iTime.getLength());
1285            } else {
1286                return 0.0;
1287            }
1288        }
1289
1290        @Override
1291        public String toString() {
1292            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
1293        }
1294    }
1295}