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        for (int idx = 0; idx < current.length; idx++) {
214            if (isFreeTime(idx)) {
215                ft = true;
216                continue;
217            }
218            if (best[idx] != null && best[idx].getAssignments() != null) {
219                if (current[idx] == null || current[idx].getSections() == null)
220                    return 1; // higher priority request assigned
221                if (best[idx].getTruePriority() < current[idx].getTruePriority())
222                    return 1; // less alternative request assigned
223                if (best[idx].getTruePriority() > current[idx].getTruePriority())
224                    return -1; // less alternative request assigned
225            } else {
226                if (current[idx] != null && current[idx].getAssignments() != null)
227                    return -1; // higher priority request assigned
228            }
229        }
230        
231        // 0.1. allowed, but not available sections
232        int bestNotAvailable = 0, currentNotAvailable = 0;
233        for (int idx = 0; idx < current.length; idx++) {
234            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
235                for (Section section: best[idx].getSections()) {
236                    if (section.getLimit() == 0)
237                        bestNotAvailable ++;
238                }
239            }
240            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
241                for (Section section: current[idx].getSections()) {
242                    if (section.getLimit() == 0)
243                        currentNotAvailable ++;
244                }
245            }
246        }
247        if (bestNotAvailable > currentNotAvailable) return -1;
248        if (bestNotAvailable < currentNotAvailable) return 1;
249
250        // 0.5. avoid course time overlaps & unavailabilities
251        if (getModel().getStudentQuality() != null) {
252            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
253            for (int idx = 0; idx < current.length; idx++) {
254                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest) {
255                    for (int x = 0; x < idx; x++) {
256                        if (best[x] != null && best[x].getAssignments() != null && best[x].getRequest() instanceof CourseRequest)
257                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
258                    }
259                }
260                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest) {
261                    for (int x = 0; x < idx; x++) {
262                        if (current[x] != null && current[x].getAssignments() != null && current[x].getRequest() instanceof CourseRequest)
263                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
264                    }
265                }
266            }
267            for (int idx = 0; idx < current.length; idx++) {
268                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
269                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
270                }
271                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
272                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
273                }
274            }
275            if (currentTimeOverlaps < bestTimeOverlaps)
276                return -1;
277            if (bestTimeOverlaps < currentTimeOverlaps)
278                return 1;
279        } else if (getModel().getTimeOverlaps() != null) {
280            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
281            for (int idx = 0; idx < current.length; idx++) {
282                if (best[idx] != null && best[idx].getAssignments() != null
283                                && best[idx].getRequest() instanceof CourseRequest) {
284                    for (int x = 0; x < idx; x++) {
285                        if (best[x] != null && best[x].getAssignments() != null
286                                        && best[x].getRequest() instanceof CourseRequest)
287                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
288                    }
289                    for (int x = 0; x < idx; x++) {
290                        if (current[x] != null && current[x].getAssignments() != null
291                                        && current[x].getRequest() instanceof CourseRequest)
292                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
293                    }
294                }
295            }
296            for (int idx = 0; idx < current.length; idx++) {
297                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
298                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
299                }
300                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
301                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
302                }
303            }
304            if (currentTimeOverlaps < bestTimeOverlaps)
305                return -1;
306            if (bestTimeOverlaps < currentTimeOverlaps)
307                return 1;
308        }
309
310        // 1. minimize number of penalties
311        double bestPenalties = 0, currentPenalties = 0;
312        for (int idx = 0; idx < current.length; idx++) {
313            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
314                for (Section section : best[idx].getSections())
315                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
316                for (Section section : current[idx].getSections())
317                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
318            }
319        }
320        if (currentPenalties < bestPenalties)
321            return -1;
322        if (bestPenalties < currentPenalties)
323            return 1;
324
325        // 2. best priority & alternativity including free time requests
326        if (ft) {
327            for (int idx = 0; idx < current.length; idx++) {
328                if (best[idx] != null && best[idx].getAssignments() != null) {
329                    if (current[idx] == null || current[idx].getSections() == null)
330                        return 1; // higher priority request assigned
331                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
332                        return 1; // less alternative request assigned
333                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
334                        return -1; // less alternative request assigned
335                } else {
336                    if (current[idx] != null && current[idx].getAssignments() != null)
337                        return -1; // higher priority request assigned
338                }
339            }
340        }
341
342        // 3. maximize selection
343        int bestSelected = 0, currentSelected = 0;
344        for (int idx = 0; idx < current.length; idx++) {
345            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
346                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
347                if (preferred != null && !preferred.isEmpty()) {
348                    for (Section section : best[idx].getSections())
349                        if (preferred.contains(section))
350                            bestSelected++;
351                    for (Section section : current[idx].getSections())
352                        if (preferred.contains(section))
353                            currentSelected++;
354                }
355            }
356        }
357        if (currentSelected > bestSelected)
358            return -1;
359        if (bestSelected > currentSelected)
360            return 1;
361        
362        // 3.5 maximize preferences
363        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
364        double bestSelectedSections = 0, currentSelectedSections = 0;
365        for (int idx = 0; idx < current.length; idx++) {
366            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
367                bestSelectedSections += best[idx].percentSelectedSameSection();
368                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
369            }
370            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
371                currentSelectedSections += current[idx].percentSelectedSameSection();
372                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
373            }
374        }
375        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
376        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
377
378        // 4-5. student quality
379        if (getModel().getStudentQuality() != null) {
380            double bestQuality = 0, currentQuality = 0;
381            for (StudentQuality.Type type: StudentQuality.Type.values()) {
382                for (int idx = 0; idx < current.length; idx++) {
383                    if (best[idx] != null && best[idx].getAssignments() != null) {
384                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
385                        for (int x = 0; x < idx; x++) {
386                            if (best[x] != null && best[x].getAssignments() != null)
387                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
388                        }
389                    }
390                    if (current[idx] != null && current[idx].getAssignments() != null) {
391                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
392                        for (int x = 0; x < idx; x++) {
393                            if (current[x] != null && current[x].getAssignments() != null)
394                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
395                        }
396                    }
397                }
398            }
399            if (currentQuality < bestQuality)
400                return -1;
401            if (bestQuality < currentQuality)
402                return 1;
403        } else {
404            // 4. avoid time overlaps
405            if (getModel().getTimeOverlaps() != null) {
406                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
407                for (int idx = 0; idx < current.length; idx++) {
408                    if (best[idx] != null && best[idx].getAssignments() != null) {
409                        for (int x = 0; x < idx; x++) {
410                            if (best[x] != null && best[x].getAssignments() != null)
411                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
412                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
413                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), best[idx]);
414                        }
415                        for (int x = 0; x < idx; x++) {
416                            if (current[x] != null && current[x].getAssignments() != null)
417                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
418                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
419                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), current[idx]);
420                        }
421                    }
422                }
423                for (int idx = 0; idx < current.length; idx++) {
424                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
425                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
426                    }
427                    if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
428                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
429                    }
430                }
431                if (currentTimeOverlaps < bestTimeOverlaps)
432                    return -1;
433                if (bestTimeOverlaps < currentTimeOverlaps)
434                    return 1;
435            }
436
437            // 5. avoid distance conflicts
438            if (getModel().getDistanceConflict() != null) {
439                int bestDistanceConf = 0, currentDistanceConf = 0;
440                for (int idx = 0; idx < current.length; idx++) {
441                    if (best[idx] != null && best[idx].getAssignments() != null) {
442                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
443                        for (int x = 0; x < idx; x++) {
444                            if (best[x] != null && best[x].getAssignments() != null)
445                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
446                        }
447                    }
448                    if (current[idx] != null && current[idx].getAssignments() != null) {
449                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
450                        for (int x = 0; x < idx; x++) {
451                            if (current[x] != null && current[x].getAssignments() != null)
452                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x], current[idx]);
453                        }
454                    }
455                }
456                if (currentDistanceConf < bestDistanceConf)
457                    return -1;
458                if (bestDistanceConf < currentDistanceConf)
459                    return 1;
460            }
461        }
462
463        // 6. avoid no-time sections
464        int bestNoTime = 0, currentNoTime = 0;
465        for (int idx = 0; idx < current.length; idx++) {
466            if (best[idx] != null && best[idx].getAssignments() != null) {
467                for (Section section : best[idx].getSections())
468                    if (section.getTime() == null)
469                        bestNoTime++;
470                for (Section section : current[idx].getSections())
471                    if (section.getTime() == null)
472                        currentNoTime++;
473            }
474        }
475        if (currentNoTime < bestNoTime)
476            return -1;
477        if (bestNoTime < currentNoTime)
478            return 1;
479
480        // 7. balance sections
481        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
482        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
483        for (int idx = 0; idx < current.length; idx++) {
484            if (best[idx] != null && best[idx].getAssignments() != null) {
485                for (Section section : best[idx].getSections()) {
486                    Subpart subpart = section.getSubpart();
487                    // skip unlimited and single section subparts
488                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
489                        continue;
490                    // average size
491                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
492                    // section is below average
493                    if (section.getLimit() < averageSize)
494                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
495                    bestAltSectionsWithLimit++;
496                }
497                for (Section section : current[idx].getSections()) {
498                    Subpart subpart = section.getSubpart();
499                    // skip unlimited and single section subparts
500                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
501                        continue;
502                    // average size
503                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
504                    // section is below average
505                    if (section.getLimit() < averageSize)
506                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
507                    currentAltSectionsWithLimit++;
508                }
509            }
510        }
511        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
512                : 0.0);
513        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
514                / currentAltSectionsWithLimit : 0.0);
515        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
516            return -1;
517        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
518            return 1;
519
520        // 8. average penalty sections
521        double bestPenalty = 0.0, currentPenalty = 0.0;
522        for (int idx = 0; idx < current.length; idx++) {
523            if (best[idx] != null && best[idx].getAssignments() != null) {
524                for (Section section : best[idx].getSections())
525                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
526                for (Section section : current[idx].getSections())
527                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
528            }
529        }
530        if (currentPenalty < bestPenalty)
531            return -1;
532        if (bestPenalty < currentPenalty)
533            return 1;
534
535        return 0;
536    }
537
538    @Override
539    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
540            Enrollment[] best) {
541        // 0. best priority & alternativity ignoring free time requests
542        int alt = 0;
543        boolean ft = false;
544        for (int idx = 0; idx < current.length; idx++) {
545            if (isFreeTime(idx)) {
546                ft = true;
547                continue;
548            }
549            Request request = getRequest(idx);
550            if (idx < maxIdx) {
551                if (best[idx] != null) {
552                    if (current[idx] == null)
553                        return false; // higher priority request assigned
554                    if (best[idx].getTruePriority() < current[idx].getTruePriority())
555                        return false; // less alternative request assigned
556                    if (best[idx].getTruePriority() > current[idx].getTruePriority())
557                        return true; // less alternative request assigned
558                    if (request.isAlternative())
559                        alt--;
560                } else {
561                    if (current[idx] != null)
562                        return true; // higher priority request assigned
563                    if (!request.isAlternative())
564                        alt++;
565                }
566            } else {
567                if (best[idx] != null) {
568                    if (best[idx].getPriority() > 0)
569                        return true; // alternativity can be improved
570                } else {
571                    if (!request.isAlternative() || alt > 0)
572                        return true; // priority can be improved
573                }
574            }
575        }
576        
577        // 0.1. allowed, but not available sections
578        int notAvailable = 0;
579        for (int idx = 0; idx < current.length; idx++) {
580            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
581                for (Section section: best[idx].getSections()) {
582                    if (section.getLimit() == 0)
583                        notAvailable ++;
584                }
585            }
586            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
587                for (Section section: current[idx].getSections()) {
588                    if (section.getLimit() == 0)
589                        notAvailable --;
590                }
591            }
592        }
593        if (notAvailable > 0) {
594            return true;
595        }
596
597        // 0.5. avoid course time overlaps & unavailability overlaps
598        if (getModel().getStudentQuality() != null) {
599            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
600            for (int idx = 0; idx < current.length; idx++) {
601                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
602                    for (int x = 0; x < idx; x++) {
603                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
604                            bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, best[x], best[idx]);
605                    }
606                }
607                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
608                    for (int x = 0; x < idx; x++) {
609                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
610                            currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.CourseTimeOverlap, current[x], current[idx]);
611                    }
612                }
613            }
614            for (int idx = 0; idx < current.length; idx++) {
615                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
616                    bestTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, best[idx]);
617                }
618                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
619                    currentTimeOverlaps += getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, current[idx]);
620                }
621            }
622            if (currentTimeOverlaps < bestTimeOverlaps)
623                return true;
624            if (bestTimeOverlaps < currentTimeOverlaps)
625                return false;
626        } else if (getModel().getTimeOverlaps() != null) {
627            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
628            for (int idx = 0; idx < current.length; idx++) {
629                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
630                    for (int x = 0; x < idx; x++) {
631                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
632                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
633                    }
634                }
635                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
636                    for (int x = 0; x < idx; x++) {
637                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
638                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
639                    }
640                }
641            }
642            for (int idx = 0; idx < current.length; idx++) {
643                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
644                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
645                }
646                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
647                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
648                }
649            }
650            if (currentTimeOverlaps < bestTimeOverlaps)
651                return true;
652            if (bestTimeOverlaps < currentTimeOverlaps)
653                return false;
654        }
655
656        // 1. maximize number of penalties
657        double bestPenalties = 0, currentPenalties = 0;
658        for (int idx = 0; idx < current.length; idx++) {
659            if (best[idx] != null) {
660                for (Section section : best[idx].getSections())
661                    bestPenalties += getModel().getOverExpected(assignment, best, idx, section, best[idx].getRequest());
662            }
663            if (current[idx] != null && idx < maxIdx) {
664                for (Section section : current[idx].getSections())
665                    currentPenalties += getModel().getOverExpected(assignment, current, idx, section, current[idx].getRequest());
666            }
667        }
668        if (currentPenalties < bestPenalties)
669            return true;
670        if (bestPenalties < currentPenalties)
671            return false;
672
673        // 2. best priority & alternativity including free times
674        if (ft) {
675            alt = 0;
676            for (int idx = 0; idx < current.length; idx++) {
677                Request request = getStudent().getRequests().get(idx);
678                if (idx < maxIdx) {
679                    if (best[idx] != null) {
680                        if (current[idx] == null)
681                            return false; // higher priority request assigned
682                        if (best[idx].getTruePriority() < current[idx].getTruePriority())
683                            return false; // less alternative request assigned
684                        if (best[idx].getTruePriority() > current[idx].getTruePriority())
685                            return true; // less alternative request assigned
686                        if (request.isAlternative())
687                            alt--;
688                    } else {
689                        if (current[idx] != null)
690                            return true; // higher priority request assigned
691                        if (request instanceof CourseRequest && !request.isAlternative())
692                            alt++;
693                    }
694                } else {
695                    if (best[idx] != null) {
696                        if (best[idx].getPriority() > 0)
697                            return true; // alternativity can be improved
698                    } else {
699                        if (!request.isAlternative() || alt > 0)
700                            return true; // priority can be improved
701                    }
702                }
703            }
704        }
705
706        // 3. maximize selection
707        int bestSelected = 0, currentSelected = 0;
708        for (int idx = 0; idx < current.length; idx++) {
709            if (best[idx] != null && best[idx].isCourseRequest()) {
710                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
711                if (preferred != null && !preferred.isEmpty()) {
712                    for (Section section : best[idx].getSections())
713                        if (preferred.contains(section)) {
714                            if (idx < maxIdx)
715                                bestSelected++;
716                        } else if (idx >= maxIdx)
717                            bestSelected--;
718                }
719            }
720            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
721                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
722                if (preferred != null && !preferred.isEmpty()) {
723                    for (Section section : current[idx].getSections())
724                        if (preferred.contains(section))
725                            currentSelected++;
726                }
727            }
728        }
729        if (currentSelected > bestSelected)
730            return true;
731        if (bestSelected > currentSelected)
732            return false;
733
734        // 3.5 maximize preferences
735        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
736        double bestSelectedSections = 0, currentSelectedSections = 0;
737        for (int idx = 0; idx < current.length; idx++) {
738            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
739                bestSelectedSections += best[idx].percentSelectedSameSection();
740                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
741                if (idx >= maxIdx) {
742                    bestSelectedSections -= 1.0;
743                    bestSelectedConfigs -= 1.0;
744                }
745            }
746            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
747                currentSelectedSections += current[idx].percentSelectedSameSection();
748                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
749            }
750        }
751        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
752        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
753        
754        // 4-5. student quality
755        if (getModel().getStudentQuality() != null) {
756            double bestQuality = 0, currentQuality = 0;
757            for (StudentQuality.Type type: StudentQuality.Type.values()) {
758                for (int idx = 0; idx < current.length; idx++) {
759                    if (best[idx] != null) {
760                        bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[idx]);
761                        for (int x = 0; x < idx; x++) {
762                            if (best[x] != null)
763                                bestQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, best[x], best[idx]);
764                        }
765                    }
766                    if (current[idx] != null && idx < maxIdx) {
767                        currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[idx]);
768                        for (int x = 0; x < idx; x++) {
769                            if (current[x] != null)
770                                currentQuality += iQalityWeights[type.ordinal()] * getModel().getStudentQuality().penalty(type, current[x], current[idx]);
771                        }
772                    }
773                }
774            }
775            if (currentQuality < bestQuality)
776                return true;
777            if (bestQuality < currentQuality)
778                return false;
779        } else {
780            // 4. avoid time overlaps
781            if (getModel().getTimeOverlaps() != null) {
782                int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
783                for (int idx = 0; idx < current.length; idx++) {
784                    if (best[idx] != null) {
785                        for (int x = 0; x < idx; x++) {
786                            if (best[x] != null)
787                                bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
788                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
789                                bestTimeOverlaps += getModel().getTimeOverlaps()
790                                        .nrConflicts(
791                                                ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
792                                                best[idx]);
793                        }
794                    }
795                    if (current[idx] != null && idx < maxIdx) {
796                        for (int x = 0; x < idx; x++) {
797                            if (current[x] != null)
798                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
799                            else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
800                                currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
801                                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
802                                        current[idx]);
803                        }
804                    }
805                }
806                for (int idx = 0; idx < current.length; idx++) {
807                    if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
808                        bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
809                    }
810                    if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
811                        currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
812                    }
813                }
814                if (currentTimeOverlaps < bestTimeOverlaps)
815                    return true;
816                if (bestTimeOverlaps < currentTimeOverlaps)
817                    return false;
818            }
819
820            // 5. avoid distance conflicts
821            if (getModel().getDistanceConflict() != null) {
822                int bestDistanceConf = 0, currentDistanceConf = 0;
823                for (int idx = 0; idx < current.length; idx++) {
824                    if (best[idx] != null) {
825                        bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[idx]);
826                        for (int x = 0; x < idx; x++) {
827                            if (best[x] != null)
828                                bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
829                        }
830                    }
831                    if (current[idx] != null && idx < maxIdx) {
832                        currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[idx]);
833                        for (int x = 0; x < idx; x++) {
834                            if (current[x] != null)
835                                currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
836                                        current[idx]);
837                        }
838                    }
839                }
840                if (currentDistanceConf < bestDistanceConf)
841                    return true;
842                if (bestDistanceConf < currentDistanceConf)
843                    return false;
844            }
845        }
846
847        // 6. avoid no-time sections
848        int bestNoTime = 0, currentNoTime = 0;
849        for (int idx = 0; idx < current.length; idx++) {
850            if (best[idx] != null) {
851                for (Section section : best[idx].getSections())
852                    if (section.getTime() == null)
853                        bestNoTime++;
854            }
855            if (current[idx] != null && idx < maxIdx) {
856                for (Section section : current[idx].getSections())
857                    if (section.getTime() == null)
858                        currentNoTime++;
859            }
860        }
861        if (currentNoTime < bestNoTime)
862            return true;
863        if (bestNoTime < currentNoTime)
864            return false;
865
866        // 7. balance sections
867        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
868        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
869        for (int idx = 0; idx < current.length; idx++) {
870            if (best[idx] != null) {
871                for (Section section : best[idx].getSections()) {
872                    Subpart subpart = section.getSubpart();
873                    // skip unlimited and single section subparts
874                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
875                        continue;
876                    // average size
877                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
878                    // section is below average
879                    if (section.getLimit() < averageSize)
880                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
881                    bestAltSectionsWithLimit++;
882                }
883            }
884            if (current[idx] != null && idx < maxIdx) {
885                for (Section section : current[idx].getSections()) {
886                    Subpart subpart = section.getSubpart();
887                    // skip unlimited and single section subparts
888                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
889                        continue;
890                    // average size
891                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
892                    // section is below average
893                    if (section.getLimit() < averageSize)
894                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
895                    currentAltSectionsWithLimit++;
896                }
897            }
898        }
899        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
900                : 0.0);
901        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
902                / currentAltSectionsWithLimit : 0.0);
903        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
904            return true;
905        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
906            return false;
907
908        // 8. average penalty sections
909        double bestPenalty = 0.0, currentPenalty = 0.0;
910        for (int idx = 0; idx < current.length; idx++) {
911            if (best[idx] != null) {
912                for (Section section : best[idx].getSections())
913                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
914                if (idx >= maxIdx && best[idx].isCourseRequest())
915                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
916            }
917            if (current[idx] != null && idx < maxIdx) {
918                for (Section section : current[idx].getSections())
919                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
920            }
921        }
922        if (currentPenalty < bestPenalty)
923            return true;
924        if (bestPenalty < currentPenalty)
925            return false;
926
927        return true;
928    }
929
930    @Override
931    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
932        if (enrollemnts == null)
933            return 0.0;
934        double value = 0.0;
935        for (int idx = 0; idx < enrollemnts.length; idx++) {
936            if (enrollemnts[idx] != null)
937                if (getModel().getStudentQuality() != null) {
938                    value += getWeight(assignment, enrollemnts[idx], getStudentQualityConflicts(enrollemnts, idx));
939                } else { 
940                    value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx), getTimeOverlappingConflicts(enrollemnts, idx));
941                }
942        }
943        return value;
944    }
945
946    @Override
947    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
948        // 1. alternativity
949        if (e1.getPriority() < e2.getPriority())
950            return -1;
951        if (e1.getPriority() > e2.getPriority())
952            return 1;
953        
954        // 1.5 not available sections
955        int na1 = 0, na2 = 0;
956        for (Section section: e1.getSections())
957            if (section.getLimit() == 0) na1++;
958        for (Section section: e2.getSections())
959            if (section.getLimit() == 0) na2++;
960        if (na1 < na2) return -1;
961        if (na1 > na2) return 1;
962        
963        // 2. maximize number of penalties
964        double p1 = 0, p2 = 0;
965        for (Section section : e1.getSections())
966            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
967        for (Section section : e2.getSections())
968            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
969        if (p1 < p2)
970            return -1;
971        if (p2 < p1)
972            return 1;
973
974        // 3. maximize selection
975        if (e1.isCourseRequest()) {
976            Set<Section> preferred = getPreferredSections(e1.getRequest());
977            if (preferred != null && !preferred.isEmpty()) {
978                int s1 = 0, s2 = 0;
979                for (Section section : e1.getSections())
980                    if (preferred.contains(section))
981                        s1++;
982                for (Section section : e2.getSections())
983                    if (preferred.contains(section))
984                        s2++;
985                if (s2 > s1)
986                    return -1;
987                if (s1 > s2)
988                    return 1;
989            }
990        }
991        
992        // 3.5 maximize preferences
993        if (e1.isCourseRequest()) {
994            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
995            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
996            if (s1 > s2) return -1;
997            if (s2 > s1) return 1;
998        }
999
1000        // 4. avoid time overlaps
1001        if (getTimesToAvoid() == null) {
1002            if (getModel().getStudentQuality() != null) {
1003                int o1 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e1) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e1);
1004                int o2 = getModel().getStudentQuality().penalty(StudentQuality.Type.FreeTimeOverlap, e2) + getModel().getStudentQuality().penalty(StudentQuality.Type.Unavailability, e2);
1005                if (o1 < o2)
1006                    return -1;
1007                if (o2 < o1)
1008                    return 1;
1009            } else if (getModel().getTimeOverlaps() != null) {
1010                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
1011                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
1012                if (o1 < o2)
1013                    return -1;
1014                if (o2 < o1)
1015                    return 1;
1016            }
1017        } else {
1018            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
1019                double o1 = 0.0, o2 = 0.0;
1020                for (Section s : e1.getSections()) {
1021                    if (s.getTime() != null)
1022                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1023                            if (avoid.priority() > e1.getRequest().getPriority())
1024                                o1 += avoid.overlap(s.getTime());
1025                        }
1026                }
1027                for (Section s : e2.getSections()) {
1028                    if (s.getTime() != null)
1029                        for (TimeToAvoid avoid : getTimesToAvoid()) {
1030                            if (avoid.priority() > e2.getRequest().getPriority())
1031                                o2 += avoid.overlap(s.getTime());
1032                        }
1033                }
1034                if (o1 < o2)
1035                    return -1;
1036                if (o2 < o1)
1037                    return 1;
1038            }
1039        }
1040
1041        // 5. avoid distance conflicts
1042        if (getModel().getDistanceConflict() != null) {
1043            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
1044            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
1045            if (c1 < c2)
1046                return -1;
1047            if (c2 < c1)
1048                return 1;
1049        }
1050
1051        // 6. avoid no-time sections
1052        int n1 = 0, n2 = 0;
1053        for (Section section : e1.getSections())
1054            if (section.getTime() == null)
1055                n1++;
1056        for (Section section : e2.getSections())
1057            if (section.getTime() == null)
1058                n2++;
1059        if (n1 < n2)
1060            return -1;
1061        if (n2 < n1)
1062            return 1;
1063
1064        // 7. balance sections
1065        double u1 = 0.0, u2 = 0.0;
1066        int a1 = 0, a2 = 0;
1067        for (Section section : e1.getSections()) {
1068            Subpart subpart = section.getSubpart();
1069            // skip unlimited and single section subparts
1070            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1071                continue;
1072            // average size
1073            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1074            // section is below average
1075            if (section.getLimit() < averageSize)
1076                u1 += (averageSize - section.getLimit()) / averageSize;
1077            a1++;
1078        }
1079        for (Section section : e2.getSections()) {
1080            Subpart subpart = section.getSubpart();
1081            // skip unlimited and single section subparts
1082            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
1083                continue;
1084            // average size
1085            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
1086            // section is below average
1087            if (section.getLimit() < averageSize)
1088                u2 += (averageSize - section.getLimit()) / averageSize;
1089            a2++;
1090        }
1091        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
1092        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
1093        if (f1 < f2)
1094            return -1;
1095        if (f2 < f1)
1096            return 1;
1097
1098        // 8. average penalty sections
1099        double x1 = 0.0, x2 = 0.0;
1100        for (Section section : e1.getSections())
1101            x1 += section.getPenalty() / e1.getSections().size();
1102        for (Section section : e2.getSections())
1103            x2 += section.getPenalty() / e2.getSections().size();
1104        if (x1 < x2)
1105            return -1;
1106        if (x2 < x1)
1107            return 1;
1108
1109        return 0;
1110    }
1111
1112    /**
1113     * Time to be avoided.
1114     */
1115    protected static class TimeToAvoid {
1116        private TimeLocation iTime;
1117        private double iPenalty;
1118        private int iPriority;
1119
1120        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
1121            iTime = time;
1122            iPenalty = penalty;
1123            iPriority = priority;
1124        }
1125
1126        public int priority() {
1127            return iPriority;
1128        }
1129
1130        public double overlap(TimeLocation time) {
1131            if (time.hasIntersection(iTime)) {
1132                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime))
1133                        / (iTime.getNrMeetings() * iTime.getLength());
1134            } else {
1135                return 0.0;
1136            }
1137        }
1138
1139        @Override
1140        public String toString() {
1141            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
1142        }
1143    }
1144}