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.TimeOverlapsCounter;
013import org.cpsolver.studentsct.model.CourseRequest;
014import org.cpsolver.studentsct.model.Enrollment;
015import org.cpsolver.studentsct.model.FreeTimeRequest;
016import org.cpsolver.studentsct.model.Request;
017import org.cpsolver.studentsct.model.Section;
018import org.cpsolver.studentsct.model.Student;
019import org.cpsolver.studentsct.model.Subpart;
020import org.cpsolver.studentsct.model.Unavailability;
021import org.cpsolver.studentsct.online.OnlineSectioningModel;
022import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionCriterion;
023import org.cpsolver.studentsct.weights.StudentWeights;
024
025/**
026* Multi-criteria selection criterion. This provides a lexicographical order of solutions using the
027* following criteria:
028* <ul>
029* <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)
030* <li>avoid or minimize course time overlaps
031* <li>minimise use of over-expected classes (this prevents students of getting into classes that we know will be needed later in the process)
032* <li>best priority & alternativity including free time requests (this is to prevent students of gaming the system by adding free time requests)
033* <li>maximise selection (preferred sections)
034* <li>avoid or minimise time overlaps (for classes that are allowed to overlap and for free time requests)
035* <li>avoid or minimise distance conflicts
036* <li>avoid classes that have no time assignment (arranged hours)
037* <li>balance sections
038* <li>minimise class penalties (expressing how much a class is over-expected)
039* </ul>
040* 
041* @version StudentSct 1.3 (Student Sectioning)<br>
042*          Copyright (C) 2014 Tomas Muller<br>
043*          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
044*          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
045* <br>
046*          This library is free software; you can redistribute it and/or modify
047*          it under the terms of the GNU Lesser General Public License as
048*          published by the Free Software Foundation; either version 3 of the
049*          License, or (at your option) any later version. <br>
050* <br>
051*          This library is distributed in the hope that it will be useful, but
052*          WITHOUT ANY WARRANTY; without even the implied warranty of
053*          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
054*          Lesser General Public License for more details. <br>
055* <br>
056*          You should have received a copy of the GNU Lesser General Public
057*          License along with this library; if not see <a
058*          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
059* 
060*/
061public class OnlineSectioningCriterion implements SelectionCriterion {
062    private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
063    private List<TimeToAvoid> iTimesToAvoid = null;
064    private OnlineSectioningModel iModel;
065    private Student iStudent;
066
067    /**
068     * Constructor
069     * @param student current student
070     * @param model online student sectioning model
071     * @param assignment current assignment
072     * @param preferredSections preferred sections
073     */
074    public OnlineSectioningCriterion(Student student, OnlineSectioningModel model,
075            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> preferredSections) {
076        iStudent = student;
077        iModel = model;
078        iPreferredSections = preferredSections;
079        if (model.getProperties().getPropertyBoolean("OnlineStudentSectioning.TimesToAvoidHeuristics", true)) {
080            iTimesToAvoid = new ArrayList<TimeToAvoid>();
081            for (Request r : iStudent.getRequests()) {
082                if (r instanceof CourseRequest) {
083                    List<Enrollment> enrollments = ((CourseRequest) r).getAvaiableEnrollmentsSkipSameTime(assignment);
084                    if (enrollments.size() <= 5) {
085                        int penalty = (7 - enrollments.size()) * (r.isAlternative() ? 1 : 7 - enrollments.size());
086                        for (Enrollment enrollment : enrollments)
087                            for (Section section : enrollment.getSections())
088                                if (section.getTime() != null)
089                                    iTimesToAvoid.add(new TimeToAvoid(section.getTime(), penalty, r.getPriority()));
090                    }
091                } else if (r instanceof FreeTimeRequest) {
092                    iTimesToAvoid.add(new TimeToAvoid(((FreeTimeRequest) r).getTime(), 1, Integer.MAX_VALUE));
093                }
094            }
095            for (Unavailability unavailability: iStudent.getUnavailabilities())
096                if (unavailability.getTime() != null)
097                    iTimesToAvoid.add(new TimeToAvoid(unavailability.getTime(), 1, Integer.MAX_VALUE));
098        }
099    }
100
101    protected OnlineSectioningModel getModel() {
102        return iModel;
103    }
104
105    protected Student getStudent() {
106        return iStudent;
107    }
108
109    protected Set<Section> getPreferredSections(Request request) {
110        return iPreferredSections.get(request);
111    }
112
113    protected List<TimeToAvoid> getTimesToAvoid() {
114        return iTimesToAvoid;
115    }
116
117    /**
118     * Distance conflicts of idx-th assignment of the current schedule
119     */
120    public Set<DistanceConflict.Conflict> getDistanceConflicts(Enrollment[] assignment, int idx) {
121        if (getModel().getDistanceConflict() == null || assignment[idx] == null)
122            return null;
123        Set<DistanceConflict.Conflict> dist = getModel().getDistanceConflict().conflicts(assignment[idx]);
124        for (int x = 0; x < idx; x++)
125            if (assignment[x] != null)
126                dist.addAll(getModel().getDistanceConflict().conflicts(assignment[x], assignment[idx]));
127        return dist;
128    }
129
130    /**
131     * Time overlapping conflicts of idx-th assignment of the current schedule
132     */
133    public Set<TimeOverlapsCounter.Conflict> getTimeOverlappingConflicts(Enrollment[] assignment, int idx) {
134        if (getModel().getTimeOverlaps() == null || assignment[idx] == null)
135            return null;
136        Set<TimeOverlapsCounter.Conflict> overlaps = new HashSet<TimeOverlapsCounter.Conflict>();
137        for (int x = 0; x < idx; x++)
138            if (assignment[x] != null) {
139                overlaps.addAll(getModel().getTimeOverlaps().conflicts(assignment[x], assignment[idx]));
140            } else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
141                overlaps.addAll(getModel().getTimeOverlaps().conflicts(
142                        ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(), assignment[idx]));
143        overlaps.addAll(getModel().getTimeOverlaps().notAvailableTimeConflicts(assignment[idx]));
144        return overlaps;
145    }
146
147    /**
148     * Weight of an assignment. Unlike
149     * {@link StudentWeights#getWeight(Assignment, Enrollment, Set, Set)}, only count this
150     * side of distance conflicts and time overlaps.
151     **/
152    protected double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment,
153            Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
154        double weight = -getModel().getStudentWeights().getWeight(assignment, enrollment);
155        if (distanceConflicts != null)
156            for (DistanceConflict.Conflict c : distanceConflicts) {
157                Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
158                if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
159                    weight += getModel().getStudentWeights().getDistanceConflictWeight(assignment, c);
160            }
161        if (timeOverlappingConflicts != null)
162            for (TimeOverlapsCounter.Conflict c : timeOverlappingConflicts) {
163                weight += getModel().getStudentWeights().getTimeOverlapConflictWeight(assignment, enrollment, c);
164            }
165        return enrollment.getRequest().getWeight() * weight;
166    }
167
168    public Request getRequest(int index) {
169        return (index < 0 || index >= getStudent().getRequests().size() ? null : getStudent().getRequests().get(index));
170    }
171
172    public boolean isFreeTime(int index) {
173        Request r = getRequest(index);
174        return r != null && r instanceof FreeTimeRequest;
175    }
176    
177    @Override
178    public int compare(Assignment<Request, Enrollment> assignment, Enrollment[] current, Enrollment[] best) {
179        if (best == null)
180            return -1;
181
182        // 0. best priority & alternativity ignoring free time requests
183        boolean ft = false;
184        for (int idx = 0; idx < current.length; idx++) {
185            if (isFreeTime(idx)) {
186                ft = true;
187                continue;
188            }
189            if (best[idx] != null && best[idx].getAssignments() != null) {
190                if (current[idx] == null || current[idx].getSections() == null)
191                    return 1; // higher priority request assigned
192                if (best[idx].getPriority() < current[idx].getPriority())
193                    return 1; // less alternative request assigned
194            } else {
195                if (current[idx] != null && current[idx].getAssignments() != null)
196                    return -1; // higher priority request assigned
197            }
198        }
199        
200        // 0.1. allowed, but not available sections
201        int bestNotAvailable = 0, currentNotAvailable = 0;
202        for (int idx = 0; idx < current.length; idx++) {
203            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
204                for (Section section: best[idx].getSections()) {
205                    if (section.getLimit() == 0)
206                        bestNotAvailable ++;
207                }
208            }
209            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
210                for (Section section: current[idx].getSections()) {
211                    if (section.getLimit() == 0)
212                        currentNotAvailable ++;
213                }
214            }
215        }
216        if (bestNotAvailable > currentNotAvailable) return -1;
217        if (bestNotAvailable < currentNotAvailable) return 1;
218
219        // 0.5. avoid course time overlaps & unavailabilities
220        if (getModel().getTimeOverlaps() != null) {
221            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
222            for (int idx = 0; idx < current.length; idx++) {
223                if (best[idx] != null && best[idx].getAssignments() != null
224                                && best[idx].getRequest() instanceof CourseRequest) {
225                    for (int x = 0; x < idx; x++) {
226                        if (best[x] != null && best[x].getAssignments() != null
227                                        && best[x].getRequest() instanceof CourseRequest)
228                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
229                    }
230                    for (int x = 0; x < idx; x++) {
231                        if (current[x] != null && current[x].getAssignments() != null
232                                        && current[x].getRequest() instanceof CourseRequest)
233                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
234                    }
235                }
236            }
237            for (int idx = 0; idx < current.length; idx++) {
238                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
239                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
240                }
241                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
242                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
243                }
244            }
245            if (currentTimeOverlaps < bestTimeOverlaps)
246                return -1;
247            if (bestTimeOverlaps < currentTimeOverlaps)
248                return 1;
249        }
250
251        // 1. minimize number of penalties
252        double bestPenalties = 0, currentPenalties = 0;
253        for (int idx = 0; idx < current.length; idx++) {
254            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
255                for (Section section : best[idx].getSections())
256                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
257                for (Section section : current[idx].getSections())
258                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
259            }
260        }
261        if (currentPenalties < bestPenalties)
262            return -1;
263        if (bestPenalties < currentPenalties)
264            return 1;
265
266        // 2. best priority & alternativity including free time requests
267        if (ft) {
268            for (int idx = 0; idx < current.length; idx++) {
269                if (best[idx] != null && best[idx].getAssignments() != null) {
270                    if (current[idx] == null || current[idx].getSections() == null)
271                        return 1; // higher priority request assigned
272                    if (best[idx].getPriority() < current[idx].getPriority())
273                        return 1; // less alternative request assigned
274                } else {
275                    if (current[idx] != null && current[idx].getAssignments() != null)
276                        return -1; // higher priority request assigned
277                }
278            }
279        }
280
281        // 3. maximize selection
282        int bestSelected = 0, currentSelected = 0;
283        for (int idx = 0; idx < current.length; idx++) {
284            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
285                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
286                if (preferred != null && !preferred.isEmpty()) {
287                    for (Section section : best[idx].getSections())
288                        if (preferred.contains(section))
289                            bestSelected++;
290                    for (Section section : current[idx].getSections())
291                        if (preferred.contains(section))
292                            currentSelected++;
293                }
294            }
295        }
296        if (currentSelected > bestSelected)
297            return -1;
298        if (bestSelected > currentSelected)
299            return 1;
300        
301        // 3.5 maximize preferences
302        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
303        double bestSelectedSections = 0, currentSelectedSections = 0;
304        for (int idx = 0; idx < current.length; idx++) {
305            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
306                bestSelectedSections += best[idx].percentSelectedSameSection();
307                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
308            }
309            if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
310                currentSelectedSections += current[idx].percentSelectedSameSection();
311                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
312            }
313        }
314        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return -1;
315        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return 1;
316
317        // 4. avoid time overlaps
318        if (getModel().getTimeOverlaps() != null) {
319            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
320            for (int idx = 0; idx < current.length; idx++) {
321                if (best[idx] != null && best[idx].getAssignments() != null) {
322                    for (int x = 0; x < idx; x++) {
323                        if (best[x] != null && best[x].getAssignments() != null)
324                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
325                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
326                            bestTimeOverlaps += getModel().getTimeOverlaps()
327                                    .nrConflicts(
328                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
329                                            best[idx]);
330                    }
331                    for (int x = 0; x < idx; x++) {
332                        if (current[x] != null && current[x].getAssignments() != null)
333                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
334                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
335                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
336                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
337                                    current[idx]);
338                    }
339                }
340            }
341            for (int idx = 0; idx < current.length; idx++) {
342                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
343                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
344                }
345                if (current[idx] != null && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
346                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
347                }
348            }
349            if (currentTimeOverlaps < bestTimeOverlaps)
350                return -1;
351            if (bestTimeOverlaps < currentTimeOverlaps)
352                return 1;
353        }
354
355        // 5. avoid distance conflicts
356        if (getModel().getDistanceConflict() != null) {
357            int bestDistanceConf = 0, currentDistanceConf = 0;
358            for (int idx = 0; idx < current.length; idx++) {
359                if (best[idx] != null && best[idx].getAssignments() != null) {
360                    for (int x = 0; x < idx; x++) {
361                        if (best[x] != null && best[x].getAssignments() != null)
362                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
363                    }
364                    for (int x = 0; x < idx; x++) {
365                        if (current[x] != null && current[x].getAssignments() != null)
366                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
367                                    current[idx]);
368                    }
369                }
370            }
371            if (currentDistanceConf < bestDistanceConf)
372                return -1;
373            if (bestDistanceConf < currentDistanceConf)
374                return 1;
375        }
376
377        // 6. avoid no-time sections
378        int bestNoTime = 0, currentNoTime = 0;
379        for (int idx = 0; idx < current.length; idx++) {
380            if (best[idx] != null && best[idx].getAssignments() != null) {
381                for (Section section : best[idx].getSections())
382                    if (section.getTime() == null)
383                        bestNoTime++;
384                for (Section section : current[idx].getSections())
385                    if (section.getTime() == null)
386                        currentNoTime++;
387            }
388        }
389        if (currentNoTime < bestNoTime)
390            return -1;
391        if (bestNoTime < currentNoTime)
392            return 1;
393
394        // 7. balance sections
395        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
396        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
397        for (int idx = 0; idx < current.length; idx++) {
398            if (best[idx] != null && best[idx].getAssignments() != null) {
399                for (Section section : best[idx].getSections()) {
400                    Subpart subpart = section.getSubpart();
401                    // skip unlimited and single section subparts
402                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
403                        continue;
404                    // average size
405                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
406                    // section is below average
407                    if (section.getLimit() < averageSize)
408                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
409                    bestAltSectionsWithLimit++;
410                }
411                for (Section section : current[idx].getSections()) {
412                    Subpart subpart = section.getSubpart();
413                    // skip unlimited and single section subparts
414                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
415                        continue;
416                    // average size
417                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
418                    // section is below average
419                    if (section.getLimit() < averageSize)
420                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
421                    currentAltSectionsWithLimit++;
422                }
423            }
424        }
425        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
426                : 0.0);
427        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
428                / currentAltSectionsWithLimit : 0.0);
429        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
430            return -1;
431        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
432            return 1;
433
434        // 8. average penalty sections
435        double bestPenalty = 0.0, currentPenalty = 0.0;
436        for (int idx = 0; idx < current.length; idx++) {
437            if (best[idx] != null && best[idx].getAssignments() != null) {
438                for (Section section : best[idx].getSections())
439                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
440                for (Section section : current[idx].getSections())
441                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
442            }
443        }
444        if (currentPenalty < bestPenalty)
445            return -1;
446        if (bestPenalty < currentPenalty)
447            return 1;
448
449        return 0;
450    }
451
452    @Override
453    public boolean canImprove(Assignment<Request, Enrollment> assignment, int maxIdx, Enrollment[] current,
454            Enrollment[] best) {
455        // 0. best priority & alternativity ignoring free time requests
456        int alt = 0;
457        boolean ft = false;
458        for (int idx = 0; idx < current.length; idx++) {
459            if (isFreeTime(idx)) {
460                ft = true;
461                continue;
462            }
463            Request request = getRequest(idx);
464            if (idx < maxIdx) {
465                if (best[idx] != null) {
466                    if (current[idx] == null)
467                        return false; // higher priority request assigned
468                    if (best[idx].getPriority() < current[idx].getPriority())
469                        return false; // less alternative request assigned
470                    if (request.isAlternative())
471                        alt--;
472                } else {
473                    if (current[idx] != null)
474                        return true; // higher priority request assigned
475                    if (!request.isAlternative())
476                        alt++;
477                }
478            } else {
479                if (best[idx] != null) {
480                    if (best[idx].getPriority() > 0)
481                        return true; // alternativity can be improved
482                } else {
483                    if (!request.isAlternative() || alt > 0)
484                        return true; // priority can be improved
485                }
486            }
487        }
488        
489        // 0.1. allowed, but not available sections
490        int notAvailable = 0;
491        for (int idx = 0; idx < current.length; idx++) {
492            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].getRequest() instanceof CourseRequest && best[idx].getReservation() != null && best[idx].getReservation().canAssignOverLimit()) {
493                for (Section section: best[idx].getSections()) {
494                    if (section.getLimit() == 0)
495                        notAvailable ++;
496                }
497            }
498            if (idx < maxIdx && current[idx] != null && current[idx].getAssignments() != null && current[idx].getRequest() instanceof CourseRequest && current[idx].getReservation() != null && current[idx].getReservation().canAssignOverLimit()) {
499                for (Section section: current[idx].getSections()) {
500                    if (section.getLimit() == 0)
501                        notAvailable --;
502                }
503            }
504        }
505        if (notAvailable > 0) {
506            return true;
507        }
508
509        // 0.5. avoid course time overlaps & unavailability overlaps
510        if (getModel().getTimeOverlaps() != null) {
511            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
512            for (int idx = 0; idx < current.length; idx++) {
513                if (best[idx] != null && best[idx].getRequest() instanceof CourseRequest) {
514                    for (int x = 0; x < idx; x++) {
515                        if (best[x] != null && best[x].getRequest() instanceof CourseRequest)
516                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
517                    }
518                }
519                if (current[idx] != null && idx < maxIdx && current[idx].getRequest() instanceof CourseRequest) {
520                    for (int x = 0; x < idx; x++) {
521                        if (current[x] != null && current[x].getRequest() instanceof CourseRequest)
522                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
523                    }
524                }
525            }
526            for (int idx = 0; idx < current.length; idx++) {
527                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
528                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
529                }
530                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
531                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
532                }
533            }
534            if (currentTimeOverlaps < bestTimeOverlaps)
535                return true;
536            if (bestTimeOverlaps < currentTimeOverlaps)
537                return false;
538        }
539
540        // 1. maximize number of penalties
541        double bestPenalties = 0, currentPenalties = 0;
542        for (int idx = 0; idx < current.length; idx++) {
543            if (best[idx] != null) {
544                for (Section section : best[idx].getSections())
545                    bestPenalties += getModel().getOverExpected(assignment, section, best[idx].getRequest());
546            }
547            if (current[idx] != null && idx < maxIdx) {
548                for (Section section : current[idx].getSections())
549                    currentPenalties += getModel().getOverExpected(assignment, section, current[idx].getRequest());
550            }
551        }
552        if (currentPenalties < bestPenalties)
553            return true;
554        if (bestPenalties < currentPenalties)
555            return false;
556
557        // 2. best priority & alternativity including free times
558        if (ft) {
559            alt = 0;
560            for (int idx = 0; idx < current.length; idx++) {
561                Request request = getStudent().getRequests().get(idx);
562                if (idx < maxIdx) {
563                    if (best[idx] != null) {
564                        if (current[idx] == null)
565                            return false; // higher priority request assigned
566                        if (best[idx].getPriority() < current[idx].getPriority())
567                            return false; // less alternative request assigned
568                        if (request.isAlternative())
569                            alt--;
570                    } else {
571                        if (current[idx] != null)
572                            return true; // higher priority request assigned
573                        if (request instanceof CourseRequest && !request.isAlternative())
574                            alt++;
575                    }
576                } else {
577                    if (best[idx] != null) {
578                        if (best[idx].getPriority() > 0)
579                            return true; // alternativity can be improved
580                    } else {
581                        if (!request.isAlternative() || alt > 0)
582                            return true; // priority can be improved
583                    }
584                }
585            }
586        }
587
588        // 3. maximize selection
589        int bestSelected = 0, currentSelected = 0;
590        for (int idx = 0; idx < current.length; idx++) {
591            if (best[idx] != null && best[idx].isCourseRequest()) {
592                Set<Section> preferred = getPreferredSections(best[idx].getRequest());
593                if (preferred != null && !preferred.isEmpty()) {
594                    for (Section section : best[idx].getSections())
595                        if (preferred.contains(section)) {
596                            if (idx < maxIdx)
597                                bestSelected++;
598                        } else if (idx >= maxIdx)
599                            bestSelected--;
600                }
601            }
602            if (current[idx] != null && idx < maxIdx && current[idx].isCourseRequest()) {
603                Set<Section> preferred = getPreferredSections(current[idx].getRequest());
604                if (preferred != null && !preferred.isEmpty()) {
605                    for (Section section : current[idx].getSections())
606                        if (preferred.contains(section))
607                            currentSelected++;
608                }
609            }
610        }
611        if (currentSelected > bestSelected)
612            return true;
613        if (bestSelected > currentSelected)
614            return false;
615
616        // 3.5 maximize preferences
617        double bestSelectedConfigs = 0, currentSelectedConfigs = 0;
618        double bestSelectedSections = 0, currentSelectedSections = 0;
619        for (int idx = 0; idx < current.length; idx++) {
620            if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
621                bestSelectedSections += best[idx].percentSelectedSameSection();
622                bestSelectedConfigs += best[idx].percentSelectedSameConfig();
623                if (idx >= maxIdx) {
624                    bestSelectedSections -= 1.0;
625                    bestSelectedConfigs -= 1.0;
626                }
627            }
628            if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
629                currentSelectedSections += current[idx].percentSelectedSameSection();
630                currentSelectedConfigs += current[idx].percentSelectedSameConfig();
631            }
632        }
633        if (0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections > 0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections) return true;
634        if (0.3 * bestSelectedConfigs + 0.7 * bestSelectedSections > 0.3 * currentSelectedConfigs + 0.7 * currentSelectedSections) return false;
635        
636        // 4. avoid time overlaps
637        if (getModel().getTimeOverlaps() != null) {
638            int bestTimeOverlaps = 0, currentTimeOverlaps = 0;
639            for (int idx = 0; idx < current.length; idx++) {
640                if (best[idx] != null) {
641                    for (int x = 0; x < idx; x++) {
642                        if (best[x] != null)
643                            bestTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(best[x], best[idx]);
644                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
645                            bestTimeOverlaps += getModel().getTimeOverlaps()
646                                    .nrConflicts(
647                                            ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
648                                            best[idx]);
649                    }
650                }
651                if (current[idx] != null && idx < maxIdx) {
652                    for (int x = 0; x < idx; x++) {
653                        if (current[x] != null)
654                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(current[x], current[idx]);
655                        else if (getStudent().getRequests().get(x) instanceof FreeTimeRequest)
656                            currentTimeOverlaps += getModel().getTimeOverlaps().nrConflicts(
657                                    ((FreeTimeRequest) getStudent().getRequests().get(x)).createEnrollment(),
658                                    current[idx]);
659                    }
660                }
661            }
662            for (int idx = 0; idx < current.length; idx++) {
663                if (best[idx] != null && best[idx].getAssignments() != null && best[idx].isCourseRequest()) {
664                    bestTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(best[idx]);
665                }
666                if (current[idx] != null && idx < maxIdx && current[idx].getAssignments() != null && current[idx].isCourseRequest()) {
667                    currentTimeOverlaps += getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(current[idx]);
668                }
669            }
670            if (currentTimeOverlaps < bestTimeOverlaps)
671                return true;
672            if (bestTimeOverlaps < currentTimeOverlaps)
673                return false;
674        }
675
676        // 5. avoid distance conflicts
677        if (getModel().getDistanceConflict() != null) {
678            int bestDistanceConf = 0, currentDistanceConf = 0;
679            for (int idx = 0; idx < current.length; idx++) {
680                if (best[idx] != null) {
681                    for (int x = 0; x < idx; x++) {
682                        if (best[x] != null)
683                            bestDistanceConf += getModel().getDistanceConflict().nrConflicts(best[x], best[idx]);
684                    }
685                }
686                if (current[idx] != null && idx < maxIdx) {
687                    for (int x = 0; x < idx; x++) {
688                        if (current[x] != null)
689                            currentDistanceConf += getModel().getDistanceConflict().nrConflicts(current[x],
690                                    current[idx]);
691                    }
692                }
693            }
694            if (currentDistanceConf < bestDistanceConf)
695                return true;
696            if (bestDistanceConf < currentDistanceConf)
697                return false;
698        }
699
700        // 6. avoid no-time sections
701        int bestNoTime = 0, currentNoTime = 0;
702        for (int idx = 0; idx < current.length; idx++) {
703            if (best[idx] != null) {
704                for (Section section : best[idx].getSections())
705                    if (section.getTime() == null)
706                        bestNoTime++;
707            }
708            if (current[idx] != null && idx < maxIdx) {
709                for (Section section : current[idx].getSections())
710                    if (section.getTime() == null)
711                        currentNoTime++;
712            }
713        }
714        if (currentNoTime < bestNoTime)
715            return true;
716        if (bestNoTime < currentNoTime)
717            return false;
718
719        // 7. balance sections
720        double bestUnavailableSize = 0.0, currentUnavailableSize = 0.0;
721        int bestAltSectionsWithLimit = 0, currentAltSectionsWithLimit = 0;
722        for (int idx = 0; idx < current.length; idx++) {
723            if (best[idx] != null) {
724                for (Section section : best[idx].getSections()) {
725                    Subpart subpart = section.getSubpart();
726                    // skip unlimited and single section subparts
727                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
728                        continue;
729                    // average size
730                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
731                    // section is below average
732                    if (section.getLimit() < averageSize)
733                        bestUnavailableSize += (averageSize - section.getLimit()) / averageSize;
734                    bestAltSectionsWithLimit++;
735                }
736            }
737            if (current[idx] != null && idx < maxIdx) {
738                for (Section section : current[idx].getSections()) {
739                    Subpart subpart = section.getSubpart();
740                    // skip unlimited and single section subparts
741                    if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
742                        continue;
743                    // average size
744                    double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
745                    // section is below average
746                    if (section.getLimit() < averageSize)
747                        currentUnavailableSize += (averageSize - section.getLimit()) / averageSize;
748                    currentAltSectionsWithLimit++;
749                }
750            }
751        }
752        double bestUnavailableSizeFraction = (bestUnavailableSize > 0 ? bestUnavailableSize / bestAltSectionsWithLimit
753                : 0.0);
754        double currentUnavailableSizeFraction = (currentUnavailableSize > 0 ? currentUnavailableSize
755                / currentAltSectionsWithLimit : 0.0);
756        if (currentUnavailableSizeFraction < bestUnavailableSizeFraction)
757            return true;
758        if (bestUnavailableSizeFraction < currentUnavailableSizeFraction)
759            return false;
760
761        // 8. average penalty sections
762        double bestPenalty = 0.0, currentPenalty = 0.0;
763        for (int idx = 0; idx < current.length; idx++) {
764            if (best[idx] != null) {
765                for (Section section : best[idx].getSections())
766                    bestPenalty += section.getPenalty() / best[idx].getSections().size();
767                if (idx >= maxIdx && best[idx].isCourseRequest())
768                    bestPenalty -= ((CourseRequest) best[idx].getRequest()).getMinPenalty();
769            }
770            if (current[idx] != null && idx < maxIdx) {
771                for (Section section : current[idx].getSections())
772                    currentPenalty += section.getPenalty() / current[idx].getSections().size();
773            }
774        }
775        if (currentPenalty < bestPenalty)
776            return true;
777        if (bestPenalty < currentPenalty)
778            return false;
779
780        return true;
781    }
782
783    @Override
784    public double getTotalWeight(Assignment<Request, Enrollment> assignment, Enrollment[] enrollemnts) {
785        if (enrollemnts == null)
786            return 0.0;
787        double value = 0.0;
788        for (int idx = 0; idx < enrollemnts.length; idx++) {
789            if (enrollemnts[idx] != null)
790                value += getWeight(assignment, enrollemnts[idx], getDistanceConflicts(enrollemnts, idx),
791                        getTimeOverlappingConflicts(enrollemnts, idx));
792        }
793        return value;
794    }
795
796    @Override
797    public int compare(Assignment<Request, Enrollment> assignment, Enrollment e1, Enrollment e2) {
798        // 1. alternativity
799        if (e1.getPriority() < e2.getPriority())
800            return -1;
801        if (e1.getPriority() > e2.getPriority())
802            return 1;
803        
804        // 1.5 not available sections
805        int na1 = 0, na2 = 0;
806        for (Section section: e1.getSections())
807            if (section.getLimit() == 0) na1++;
808        for (Section section: e2.getSections())
809            if (section.getLimit() == 0) na2++;
810        if (na1 < na2) return -1;
811        if (na2 > na1) return -1;
812        
813        // 2. maximize number of penalties
814        double p1 = 0, p2 = 0;
815        for (Section section : e1.getSections())
816            p1 += getModel().getOverExpected(assignment, section, e1.getRequest());
817        for (Section section : e2.getSections())
818            p2 += getModel().getOverExpected(assignment, section, e2.getRequest());
819        if (p1 < p2)
820            return -1;
821        if (p2 < p1)
822            return 1;
823
824        // 3. maximize selection
825        if (e1.isCourseRequest()) {
826            Set<Section> preferred = getPreferredSections(e1.getRequest());
827            if (preferred != null && !preferred.isEmpty()) {
828                int s1 = 0, s2 = 0;
829                for (Section section : e1.getSections())
830                    if (preferred.contains(section))
831                        s1++;
832                for (Section section : e2.getSections())
833                    if (preferred.contains(section))
834                        s2++;
835                if (s2 > s1)
836                    return -1;
837                if (s1 > s2)
838                    return 1;
839            }
840        }
841        
842        // 3.5 maximize preferences
843        if (e1.isCourseRequest()) {
844            double s1 = 0.3 * e1.percentSelectedSameConfig() + 0.7 * e1.percentSelectedSameSection();
845            double s2 = 0.3 * e2.percentSelectedSameConfig() + 0.7 * e2.percentSelectedSameSection();
846            if (s1 > s2) return -1;
847            if (s2 > s1) return 1;
848        }
849
850        // 4. avoid time overlaps
851        if (getTimesToAvoid() == null) {
852            if (getModel().getTimeOverlaps() != null) {
853                int o1 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e1) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e1);
854                int o2 = getModel().getTimeOverlaps().nrFreeTimeConflicts(e2) + getModel().getTimeOverlaps().nrNotAvailableTimeConflicts(e2);
855                if (o1 < o2)
856                    return -1;
857                if (o2 < o1)
858                    return 1;
859            }
860        } else {
861            if (e1.getRequest().equals(e2.getRequest()) && e1.isCourseRequest()) {
862                double o1 = 0.0, o2 = 0.0;
863                for (Section s : e1.getSections()) {
864                    if (s.getTime() != null)
865                        for (TimeToAvoid avoid : getTimesToAvoid()) {
866                            if (avoid.priority() > e1.getPriority())
867                                o1 += avoid.overlap(s.getTime());
868                        }
869                }
870                for (Section s : e2.getSections()) {
871                    if (s.getTime() != null)
872                        for (TimeToAvoid avoid : getTimesToAvoid()) {
873                            if (avoid.priority() > e2.getPriority())
874                                o2 += avoid.overlap(s.getTime());
875                        }
876                }
877                if (o1 < o2)
878                    return -1;
879                if (o2 < o1)
880                    return 1;
881            }
882        }
883
884        // 5. avoid distance conflicts
885        if (getModel().getDistanceConflict() != null) {
886            int c1 = getModel().getDistanceConflict().nrConflicts(e1);
887            int c2 = getModel().getDistanceConflict().nrConflicts(e2);
888            if (c1 < c2)
889                return -1;
890            if (c2 < c1)
891                return 1;
892        }
893
894        // 6. avoid no-time sections
895        int n1 = 0, n2 = 0;
896        for (Section section : e1.getSections())
897            if (section.getTime() == null)
898                n1++;
899        for (Section section : e2.getSections())
900            if (section.getTime() == null)
901                n2++;
902        if (n1 < n2)
903            return -1;
904        if (n2 < n1)
905            return 1;
906
907        // 7. balance sections
908        double u1 = 0.0, u2 = 0.0;
909        int a1 = 0, a2 = 0;
910        for (Section section : e1.getSections()) {
911            Subpart subpart = section.getSubpart();
912            // skip unlimited and single section subparts
913            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
914                continue;
915            // average size
916            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
917            // section is below average
918            if (section.getLimit() < averageSize)
919                u1 += (averageSize - section.getLimit()) / averageSize;
920            a1++;
921        }
922        for (Section section : e2.getSections()) {
923            Subpart subpart = section.getSubpart();
924            // skip unlimited and single section subparts
925            if (subpart.getSections().size() <= 1 || subpart.getLimit() <= 0)
926                continue;
927            // average size
928            double averageSize = ((double) subpart.getLimit()) / subpart.getSections().size();
929            // section is below average
930            if (section.getLimit() < averageSize)
931                u2 += (averageSize - section.getLimit()) / averageSize;
932            a2++;
933        }
934        double f1 = (u1 > 0 ? u1 / a1 : 0.0);
935        double f2 = (u2 > 0 ? u2 / a2 : 0.0);
936        if (f1 < f2)
937            return -1;
938        if (f2 < f1)
939            return 1;
940
941        // 8. average penalty sections
942        double x1 = 0.0, x2 = 0.0;
943        for (Section section : e1.getSections())
944            x1 += section.getPenalty() / e1.getSections().size();
945        for (Section section : e2.getSections())
946            x2 += section.getPenalty() / e2.getSections().size();
947        if (x1 < x2)
948            return -1;
949        if (x2 < x1)
950            return 1;
951
952        return 0;
953    }
954
955    /**
956     * Time to be avoided.
957     */
958    protected static class TimeToAvoid {
959        private TimeLocation iTime;
960        private double iPenalty;
961        private int iPriority;
962
963        public TimeToAvoid(TimeLocation time, int penalty, int priority) {
964            iTime = time;
965            iPenalty = penalty;
966            iPriority = priority;
967        }
968
969        public int priority() {
970            return iPriority;
971        }
972
973        public double overlap(TimeLocation time) {
974            if (time.hasIntersection(iTime)) {
975                return iPenalty * (time.nrSharedDays(iTime) * time.nrSharedDays(iTime))
976                        / (iTime.getNrMeetings() * iTime.getLength());
977            } else {
978                return 0.0;
979            }
980        }
981
982        @Override
983        public String toString() {
984            return iTime.getLongName(true) + " (" + iPriority + "/" + iPenalty + ")";
985        }
986    }
987}