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 Tomas Muller<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        // 4-5. student quality
399        if (getModel().getStudentQuality() != null) {
400            double bestQuality = 0, currentQuality = 0;
401            for (StudentQuality.Type type: StudentQuality.Type.values()) {
402                for (int idx = 0; idx < current.length; idx++) {
403                    if (best[idx] != null && best[idx].getAssignments() != null) {
404                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
405                        for (int x = 0; x < idx; x++) {
406                            if (best[x] != null && best[x].getAssignments() != null)
407                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
408                        }
409                    }
410                    if (current[idx] != null && current[idx].getAssignments() != null) {
411                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
412                        for (int x = 0; x < idx; x++) {
413                            if (current[x] != null && current[x].getAssignments() != null)
414                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
415                        }
416                    }
417                }
418            }
419            if (currentQuality < bestQuality)
420                return -1;
421            if (bestQuality < currentQuality)
422                return 1;
423        } else {
424            // 4. avoid time overlaps
425            if (getModel().getTimeOverlaps() != null) {
426                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
427                for (int idx = 0; idx < current.length; idx++) {
428                    if (best[idx] != null && best[idx].getAssignments() != null) {
429                        for (int x = 0; x < idx; x++) {
430                            if (best[x] != null && best[x].getAssignments() != null)
431                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
432                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
433                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]);
434                        }
435                        for (int x = 0; x < idx; x++) {
436                            if (current[x] != null && current[x].getAssignments() != null)
437                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
438                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
439                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]);
440                        }
441                    }
442                }
443                for (int idx = 0; idx < current.length; idx++) {
444                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
445                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
446                    }
447                    if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
448                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
449                    }
450                }
451                if (currentTimeOverlaps < bestTimeOverlaps)
452                    return -1;
453                if (bestTimeOverlaps < currentTimeOverlaps)
454                    return 1;
455            }
456
457            // 5. avoid distance conflicts
458            if (getModel().getDistanceConflict() != null) {
459                int bestDistanceConf = 0, currentDistanceConf = 0;
460                for (int idx = 0; idx < current.length; idx++) {
461                    if (best[idx] != null && best[idx].getAssignments() != null) {
462                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
463                        for (int x = 0; x < idx; x++) {
464                            if (best[x] != null && best[x].getAssignments() != null)
465                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
466                        }
467                    }
468                    if (current[idx] != null && current[idx].getAssignments() != null) {
469                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
470                        for (int x = 0; x < idx; x++) {
471                            if (current[x] != null && current[x].getAssignments() != null)
472                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
473                        }
474                    }
475                }
476                if (currentDistanceConf < bestDistanceConf)
477                    return -1;
478                if (bestDistanceConf < currentDistanceConf)
479                    return 1;
480            }
481        }
482
483        // 6. avoid no-time and online sections (no-time first, online second)
484        int bestNoTime = 0, currentNoTime = 0;
485        int bestOnline = 0, currentOnline = 0;
486        for (int idx = 0; idx < current.length; idx++) {
487            if (best[idx] != null && best[idx].getAssignments() != null) {
488                for (Section section : best[idx].getSections()) {
489                    if (section.getTime() == null)
490                        bestNoTime++;
491                    if (section.isOnline())
492                        bestOnline++;
493                }
494                for (Section section : current[idx].getSections()) {
495                    if (section.getTime() == null)
496                        currentNoTime++;
497                    if (section.isOnline())
498                        currentOnline++;
499                }
500            }
501        }
502        if (currentNoTime < bestNoTime)
503            return -1;
504        if (bestNoTime < currentNoTime)
505            return 1;
506        if (currentOnline < bestOnline)
507            return -1;
508        if (bestOnline < currentOnline)
509            return 1;
510
511        // 7. balance sections
512        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
513        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
514        for (int idx = 0; idx < current.length; idx++) {
515            if (best[idx] != null && best[idx].getAssignments() != null) {
516                for (Section section : best[idx].getSections()) {
517                    Subpart subpart = section.getSubpart();
518                    // skip unlimited and single section subparts
519                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
520                        continue;
521                    // average size
522                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
523                    // section is below average
524                    if (section.getLimit() < averageSize)
525                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
526                    bestAltSectionsWithLimit++;
527                }
528                for (Section section : current[idx].getSections()) {
529                    Subpart subpart = section.getSubpart();
530                    // skip unlimited and single section subparts
531                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
532                        continue;
533                    // average size
534                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
535                    // section is below average
536                    if (section.getLimit() < averageSize)
537                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
538                    currentAltSectionsWithLimit++;
539                }
540            }
541        }
542        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
543                : 0.0);
544        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
545                / currentAltSectionsWithLimit : 0.0);
546        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
547            return -1;
548        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
549            return 1;
550
551        // 8. average penalty sections
552        double bestPenalty = 0.0, currentPenalty = 0.0;
553        for (int idx = 0; idx < current.length; idx++) {
554            if (best[idx] != null && best[idx].getAssignments() != null) {
555                for (Section section : best[idx].getSections())
556                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
557                for (Section section : current[idx].getSections())
558                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
559            }
560        }
561        if (currentPenalty < bestPenalty)
562            return -1;
563        if (bestPenalty < currentPenalty)
564            return 1;
565
566        return 0;
567    }
568
569    @Override
570    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
571            Enrollment[] best) {
572        // 0. best priority & alternativity ignoring free time requests
573        int alt = 0;
574        boolean ft = false;
575        boolean res = false;
576        for (int idx = 0; idx < current.length; idx++) {
577            if (isFreeTime(idx)) {
578                ft = true;
579                continue;
580            }
581            Request request = getRequest(idx);
582            if (request instanceof CourseRequest && ((CourseRequest)request).hasReservations()) res = true;
583            if (idx < maxIdx) {
584                if (best[idx] != null) {
585                    if (current[idx] == null)
586                        return false; // higher priority request assigned
587                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
588                        return false; // less alternative request assigned
589                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
590                        return true; // less alternative request assigned
591                    if (request.isAlternative())
592                        alt--;
593                } else {
594                    if (current[idx] != null)
595                        return true; // higher priority request assigned
596                    if (!request.isAlternative())
597                        alt++;
598                }
599            } else {
600                if (best[idx] != null) {
601                    if (best[idx].getTruePriority() > 0)
602                        return true; // alternativity can be improved
603                } else {
604                    if (!request.isAlternative() || alt > 0)
605                        return true; // priority can be improved
606                }
607            }
608        }
609        
610        // 0.1. allowed, but not available sections
611        int notAvailable = 0;
612        for (int idx = 0; idx < current.length; idx++) {
613            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
614                for (Section section: best[idx].getSections()) {
615                    if (section.getLimit() == 0)
616                        notAvailable ++;
617                }
618            }
619            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
620                for (Section section: current[idx].getSections()) {
621                    if (section.getLimit() == 0)
622                        notAvailable --;
623                }
624            }
625        }
626        if (notAvailable > 0) {
627            return true;
628        }
629
630        // 0.5. avoid course time overlaps & unavailability overlaps
631        if (getModel().getStudentQuality() != null) {
632            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
633            for (int idx = 0; idx < current.length; idx++) {
634                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
635                    for (int x = 0; x < idx; x++) {
636                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
637                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
638                    }
639                }
640                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
641                    for (int x = 0; x < idx; x++) {
642                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
643                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
644                    }
645                }
646            }
647            for (int idx = 0; idx < current.length; idx++) {
648                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
649                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
650                }
651                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
652                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
653                }
654            }
655            if (currentTimeOverlaps < bestTimeOverlaps)
656                return true;
657            if (bestTimeOverlaps < currentTimeOverlaps)
658                return false;
659        } else if (getModel().getTimeOverlaps() != null) {
660            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
661            for (int idx = 0; idx < current.length; idx++) {
662                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
663                    for (int x = 0; x < idx; x++) {
664                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
665                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
666                    }
667                }
668                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
669                    for (int x = 0; x < idx; x++) {
670                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
671                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
672                    }
673                }
674            }
675            for (int idx = 0; idx < current.length; idx++) {
676                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
677                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
678                }
679                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
680                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
681                }
682            }
683            if (currentTimeOverlaps < bestTimeOverlaps)
684                return true;
685            if (bestTimeOverlaps < currentTimeOverlaps)
686                return false;
687        }
688
689        // 1. maximize number of penalties
690        double bestPenalties = 0, currentPenalties = 0;
691        for (int idx = 0; idx < current.length; idx++) {
692            if (best[idx] != null) {
693                for (Section section : best[idx].getSections())
694                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
695            }
696            if (current[idx] != null && idx < maxIdx) {
697                for (Section section : current[idx].getSections())
698                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
699            }
700        }
701        if (currentPenalties < bestPenalties)
702            return true;
703        if (bestPenalties < currentPenalties)
704            return false;
705
706        // 2. best priority & alternativity including free times
707        if (ft) {
708            alt = 0;
709            for (int idx = 0; idx < current.length; idx++) {
710                Request request = getStudent().getRequests().get(idx);
711                if (idx < maxIdx) {
712                    if (best[idx] != null) {
713                        if (current[idx] == null)
714                            return false; // higher priority request assigned
715                        if (best[idx].getTruePriority() < current[idx].getTruePriority())
716                            return false; // less alternative request assigned
717                        if (best[idx].getTruePriority() > current[idx].getTruePriority())
718                            return true; // less alternative request assigned
719                        if (request.isAlternative())
720                            alt--;
721                    } else {
722                        if (current[idx] != null)
723                            return true; // higher priority request assigned
724                        if (request instanceof CourseRequest && !request.isAlternative())
725                            alt++;
726                    }
727                } else {
728                    if (best[idx] != null) {
729                        if (best[idx].getTruePriority() > 0)
730                            return true; // alternativity can be improved
731                    } else {
732                        if (!request.isAlternative() || alt > 0)
733                            return true; // priority can be improved
734                    }
735                }
736            }
737        }
738
739        // 3. maximize selection
740        int bestSelected = 0, currentSelected = 0;
741        for (int idx = 0; idx < current.length; idx++) {
742            if (best[idx] != null && best[idx].isCourseRequest()) {
743                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
744                if (preferred != null && !preferred.isEmpty()) {
745                    for (Section section : best[idx].getSections())
746                        if (preferred.contains(section)) {
747                            if (idx < maxIdx)
748                                bestSelected++;
749                        } else if (idx >= maxIdx)
750                            bestSelected--;
751                }
752            }
753            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
754                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
755                if (preferred != null && !preferred.isEmpty()) {
756                    for (Section section : current[idx].getSections())
757                        if (preferred.contains(section))
758                            currentSelected++;
759                }
760            }
761        }
762        if (currentSelected > bestSelected)
763            return true;
764        if (bestSelected > currentSelected)
765            return false;
766
767        // 3.5 maximize preferences
768        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
769        double bestSelectedSections = 0, currentSelectedSections = 0;
770        for (int idx = 0; idx < current.length; idx++) {
771            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
772                bestSelectedSections += best[idx].percentSelectedSameSection();
773                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
774                if (idx >= maxIdx) {
775                    bestSelectedSections -= 1.0;
776                    bestSelectedConfigs -= 1.0;
777                }
778            }
779            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
780                currentSelectedSections += current[idx].percentSelectedSameSection();
781                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
782            }
783        }
784        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
785        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
786        
787        // 3.9 maximize selection with penalization for not followed reservations
788        if (res) {
789            alt = 0;
790            for (int idx = 0; idx < current.length; idx++) {
791                Request request = getStudent().getRequests().get(idx);
792                if (idx < maxIdx) {
793                    if (best[idx] != null) {
794                        if (current[idx] == null)
795                            return false; // higher priority request assigned
796                        if (best[idx].getAdjustedPriority() < current[idx].getAdjustedPriority())
797                            return false; // less alternative request assigned
798                        if (best[idx].getAdjustedPriority() > current[idx].getAdjustedPriority())
799                            return true; // less alternative request assigned
800                        if (request.isAlternative())
801                            alt--;
802                    } else {
803                        if (current[idx] != null)
804                            return true; // higher priority request assigned
805                        if (request instanceof CourseRequest && !request.isAlternative())
806                            alt++;
807                    }
808                } else {
809                    if (best[idx] != null) {
810                        if (best[idx].getTruePriority() > 0)
811                            return true; // alternativity can be improved
812                    } else {
813                        if (!request.isAlternative() || alt > 0)
814                            return true; // priority can be improved
815                    }
816                }
817            }
818        }
819        
820        // 4-5. student quality
821        if (getModel().getStudentQuality() != null) {
822            double bestQuality = 0, currentQuality = 0;
823            for (StudentQuality.Type type: StudentQuality.Type.values()) {
824                for (int idx = 0; idx < current.length; idx++) {
825                    if (best[idx] != null) {
826                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
827                        for (int x = 0; x < idx; x++) {
828                            if (best[x] != null)
829                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
830                        }
831                    }
832                    if (current[idx] != null && idx < maxIdx) {
833                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
834                        for (int x = 0; x < idx; x++) {
835                            if (current[x] != null)
836                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
837                        }
838                    }
839                }
840            }
841            if (currentQuality < bestQuality)
842                return true;
843            if (bestQuality < currentQuality)
844                return false;
845        } else {
846            // 4. avoid time overlaps
847            if (getModel().getTimeOverlaps() != null) {
848                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
849                for (int idx = 0; idx < current.length; idx++) {
850                    if (best[idx] != null) {
851                        for (int x = 0; x < idx; x++) {
852                            if (best[x] != null)
853                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
854                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
855                                bestTimeOverlaps += getModel().getTimeOverlaps()
856                                        .nrConflicts(
857                                                ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
858                                                best[idx]);
859                        }
860                    }
861                    if (current[idx] != null && idx < maxIdx) {
862                        for (int x = 0; x < idx; x++) {
863                            if (current[x] != null)
864                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
865                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
866                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
867                                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
868                                        current[idx]);
869                        }
870                    }
871                }
872                for (int idx = 0; idx < current.length; idx++) {
873                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
874                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
875                    }
876                    if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
877                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
878                    }
879                }
880                if (currentTimeOverlaps < bestTimeOverlaps)
881                    return true;
882                if (bestTimeOverlaps < currentTimeOverlaps)
883                    return false;
884            }
885
886            // 5. avoid distance conflicts
887            if (getModel().getDistanceConflict() != null) {
888                int bestDistanceConf = 0, currentDistanceConf = 0;
889                for (int idx = 0; idx < current.length; idx++) {
890                    if (best[idx] != null) {
891                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
892                        for (int x = 0; x < idx; x++) {
893                            if (best[x] != null)
894                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
895                        }
896                    }
897                    if (current[idx] != null && idx < maxIdx) {
898                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
899                        for (int x = 0; x < idx; x++) {
900                            if (current[x] != null)
901                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
902                                        current[idx]);
903                        }
904                    }
905                }
906                if (currentDistanceConf < bestDistanceConf)
907                    return true;
908                if (bestDistanceConf < currentDistanceConf)
909                    return false;
910            }
911        }
912
913        // 6. avoid no-time and online sections (no-time first, online second)
914        int bestNoTime = 0, currentNoTime = 0;
915        int bestOnline = 0, currentOnline = 0;
916        for (int idx = 0; idx < current.length; idx++) {
917            if (best[idx] != null) {
918                for (Section section : best[idx].getSections()) {
919                    if (section.getTime() == null)
920                        bestNoTime++;
921                    if (section.isOnline())
922                        bestOnline++;
923                }
924            }
925            if (current[idx] != null && idx < maxIdx) {
926                for (Section section : current[idx].getSections()) {
927                    if (section.getTime() == null)
928                        currentNoTime++;
929                    if (section.isOnline())
930                        currentOnline++;
931                }
932            }
933        }
934        if (currentNoTime < bestNoTime)
935            return true;
936        if (bestNoTime < currentNoTime)
937            return false;
938        if (currentOnline < bestOnline)
939            return true;
940        if (bestOnline < currentOnline)
941            return false;
942
943        // 7. balance sections
944        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
945        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
946        for (int idx = 0; idx < current.length; idx++) {
947            if (best[idx] != null) {
948                for (Section section : best[idx].getSections()) {
949                    Subpart subpart = section.getSubpart();
950                    // skip unlimited and single section subparts
951                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
952                        continue;
953                    // average size
954                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
955                    // section is below average
956                    if (section.getLimit() < averageSize)
957                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
958                    bestAltSectionsWithLimit++;
959                }
960            }
961            if (current[idx] != null && idx < maxIdx) {
962                for (Section section : current[idx].getSections()) {
963                    Subpart subpart = section.getSubpart();
964                    // skip unlimited and single section subparts
965                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
966                        continue;
967                    // average size
968                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
969                    // section is below average
970                    if (section.getLimit() < averageSize)
971                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
972                    currentAltSectionsWithLimit++;
973                }
974            }
975        }
976        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
977                : 0.0);
978        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
979                / currentAltSectionsWithLimit : 0.0);
980        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
981            return true;
982        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
983            return false;
984
985        // 8. average penalty sections
986        double bestPenalty = 0.0, currentPenalty = 0.0;
987        for (int idx = 0; idx < current.length; idx++) {
988            if (best[idx] != null) {
989                for (Section section : best[idx].getSections())
990                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
991                if (idx >= maxIdx && best[idx].isCourseRequest())
992                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
993            }
994            if (current[idx] != null && idx < maxIdx) {
995                for (Section section : current[idx].getSections())
996                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
997            }
998        }
999        if (currentPenalty < bestPenalty)
1000            return true;
1001        if (bestPenalty < currentPenalty)
1002            return false;
1003
1004        return true;
1005    }
1006
1007    @Override
1008    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
1009        if (enrollemnts == null)
1010            return 0.0;
1011        double value = 0.0;
1012        for (int idx = 0; idx < enrollemnts.length; idx++) {
1013            if (enrollemnts[idx] != null)
1014                if (getModel().getStudentQuality() != null) {
1015                    value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx));
1016                } else { 
1017                    value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx));
1018                }
1019        }
1020        return value;
1021    }
1022
1023    @Override
1024    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
1025        // 1. alternativity
1026        if (e1.getTruePriority() < e2.getTruePriority())
1027            return -1;
1028        if (e1.getTruePriority() > e2.getTruePriority())
1029            return 1;
1030        
1031        // 1.5 not available sections
1032        int na1 = 0, na2 = 0;
1033        for (Section section: e1.getSections())
1034            if (section.getLimit() == 0) na1++;
1035        for (Section section: e2.getSections())
1036            if (section.getLimit() == 0) na2++;
1037        if (na1 < na2) return -1;
1038        if (na1 > na2) return 1;
1039        
1040        // 2. maximize number of penalties
1041        double p1 = 0, p2 = 0;
1042        for (Section section : e1.getSections())
1043            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
1044        for (Section section : e2.getSections())
1045            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
1046        if (p1 < p2)
1047            return -1;
1048        if (p2 < p1)
1049            return 1;
1050
1051        // 3. maximize selection
1052        if (e1.isCourseRequest()) {
1053            Set<Section> preferred = getPreferredSections(e1.getRequest());
1054            if (preferred != null && !preferred.isEmpty()) {
1055                int s1 = 0, s2 = 0;
1056                for (Section section : e1.getSections())
1057                    if (preferred.contains(section))
1058                        s1++;
1059                for (Section section : e2.getSections())
1060                    if (preferred.contains(section))
1061                        s2++;
1062                if (s2 > s1)
1063                    return -1;
1064                if (s1 > s2)
1065                    return 1;
1066            }
1067        }
1068        
1069        // 3.5 maximize preferences
1070        if (e1.isCourseRequest()) {
1071            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
1072            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
1073            if (s1 > s2) return -1;
1074            if (s2 > s1) return 1;
1075        }
1076        
1077        // 3.9 maximize selection with penalization for not followed reservations
1078        if (e1.getAdjustedPriority() < e2.getAdjustedPriority())
1079            return -1;
1080        if (e1.getAdjustedPriority() > e2.getAdjustedPriority())
1081            return 1;
1082
1083        // 4. avoid time overlaps
1084        if (getTimesToAvoid() == null) {
1085            if (getModel().getStudentQuality() != null) {
1086                int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1);
1087                int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2);
1088                if (o1 < o2)
1089                    return -1;
1090                if (o2 < o1)
1091                    return 1;
1092            } else if (getModel().getTimeOverlaps() != null) {
1093                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
1094                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
1095                if (o1 < o2)
1096                    return -1;
1097                if (o2 < o1)
1098                    return 1;
1099            }
1100        } else {
1101            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
1102                double o1 = 0.0, o2 = 0.0;
1103                for (Section s : e1.getSections()) {
1104                    if (s.getTime() != null)
1105                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1106                            if (avoid.priority() > e1.getRequest().getPriority())
1107                                o1 += avoid.overlap(s.getTime());
1108                        }
1109                }
1110                for (Section s : e2.getSections()) {
1111                    if (s.getTime() != null)
1112                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1113                            if (avoid.priority() > e2.getRequest().getPriority())
1114                                o2 += avoid.overlap(s.getTime());
1115                        }
1116                }
1117                if (o1 < o2)
1118                    return -1;
1119                if (o2 < o1)
1120                    return 1;
1121            }
1122        }
1123
1124        // 5. avoid distance conflicts
1125        if (getModel().getDistanceConflict() != null) {
1126            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
1127            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
1128            if (c1 < c2)
1129                return -1;
1130            if (c2 < c1)
1131                return 1;
1132        }
1133
1134        // 6. avoid no-time and online sections (no-time first, online second)
1135        int n1 = 0, n2 = 0;
1136        int o1 = 0, o2 = 0;
1137        for (Section section : e1.getSections()) {
1138            if (section.getTime() == null)
1139                n1++;
1140            if (section.isOnline())
1141                o1++;
1142        }
1143        for (Section section : e2.getSections()) {
1144            if (section.getTime() == null)
1145                n2++;
1146            if (section.isOnline())
1147                o2++;
1148        }
1149        if (n1 < n2)
1150            return -1;
1151        if (n2 < n1)
1152            return 1;
1153        if (o1 < o2)
1154            return -1;
1155        if (o2 < o1)
1156            return 1;
1157
1158        // 7. balance sections
1159        double u1 = 0.0, u2 = 0.0;
1160        int a1 = 0, a2 = 0;
1161        for (Section section : e1.getSections()) {
1162            Subpart subpart = section.getSubpart();
1163            // skip unlimited and single section subparts
1164            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1165                continue;
1166            // average size
1167            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1168            // section is below average
1169            if (section.getLimit() < averageSize)
1170                u1 += (averageSize - section.getLimit()) / averageSize;
1171            a1++;
1172        }
1173        for (Section section : e2.getSections()) {
1174            Subpart subpart = section.getSubpart();
1175            // skip unlimited and single section subparts
1176            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1177                continue;
1178            // average size
1179            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1180            // section is below average
1181            if (section.getLimit() < averageSize)
1182                u2 += (averageSize - section.getLimit()) / averageSize;
1183            a2++;
1184        }
1185        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
1186        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
1187        if (f1 < f2)
1188            return -1;
1189        if (f2 < f1)
1190            return 1;
1191
1192        // 8. average penalty sections
1193        double x1 = 0.0, x2 = 0.0;
1194        for (Section section : e1.getSections())
1195            x1 += section.getPenalty() / e1.getSections().size();
1196        for (Section section : e2.getSections())
1197            x2 += section.getPenalty() / e2.getSections().size();
1198        if (x1 < x2)
1199            return -1;
1200        if (x2 < x1)
1201            return 1;
1202
1203        return 0;
1204    }
1205
1206    /**
1207     * Time to be avoided.
1208     */
1209    public static class TimeToAvoid {
1210        private TimeLocation iTime;
1211        private double iPenalty;
1212        private int iPriority;
1213
1214        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
1215            iTime = time;
1216            iPenalty = penalty;
1217            iPriority = priority;
1218        }
1219
1220        public int priority() {
1221            return iPriority;
1222        }
1223
1224        public double overlap(TimeLocation time) {
1225            if (time.hasIntersection(iTime)) {
1226                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedHours(iTime))
1227                        / (iTime.getNrMeetings() * iTime.getLength());
1228            } else {
1229                return 0.0;
1230            }
1231        }
1232
1233        @Override
1234        public String toString() {
1235            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
1236        }
1237    }
1238}