    001package org.cpsolver.coursett.sectioning;
    002
    003import java.util.ArrayList;
    004import java.util.Arrays;
    005import java.util.Collections;
    006import java.util.Comparator;
    007import java.util.HashMap;
    008import java.util.HashSet;
    009import java.util.LinkedList;
    010import java.util.List;
    011import java.util.Map;
    012import java.util.Map.Entry;
    013import java.util.Queue;
    014import java.util.Set;
    015import java.util.TreeSet;
    016
    017import org.cpsolver.coursett.constraint.JenrlConstraint;
    018import org.cpsolver.coursett.criteria.StudentConflict;
    019import org.cpsolver.coursett.model.Configuration;
    020import org.cpsolver.coursett.model.Lecture;
    021import org.cpsolver.coursett.model.Placement;
    022import org.cpsolver.coursett.model.Student;
    023import org.cpsolver.coursett.model.StudentGroup;
    024import org.cpsolver.coursett.model.TimetableModel;
    025import org.cpsolver.ifs.assignment.Assignment;
    026import org.cpsolver.ifs.criteria.Criterion;
    027import org.cpsolver.ifs.util.JProf;
    028
    029/**
    030 * A model representing student enrollments of a course. Branch &amp; bound algorithm
    031 * is used to propose best possible enrollment of all students into the given course.
    032 *
    033 *
    034 * @author  Tomáš Müller
    035 * @version CourseTT 1.3 (University Course Timetabling)<br>
    036 *          Copyright (C) 2017 Tomáš Müller<br>
    037 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    038 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    039 * <br>
    040 *          This library is free software; you can redistribute it and/or modify
    041 *          it under the terms of the GNU Lesser General Public License as
    042 *          published by the Free Software Foundation; either version 3 of the
    043 *          License, or (at your option) any later version. <br>
    044 * <br>
    045 *          This library is distributed in the hope that it will be useful, but
    046 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    047 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    048 *          Lesser General Public License for more details. <br>
    049 * <br>
    050 *          You should have received a copy of the GNU Lesser General Public
    051 *          License along with this library; if not see
    052 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    053 */
    054public class SctModel {
    055    public static double sEps = 0.0001;
    056    private long iTimeOut = 1000;
    057    private boolean iUseCriteria = true;
    058    private TimetableModel iModel;
    059    private Assignment<Lecture, Placement> iAssignment;
    060    private List<StudentConflict> iStudentConflictCriteria = null;
    061    private List<Configuration> iConfigurations = null;
    062    private List<SctStudent> iStudents = null;
    063    private Long iOfferingId = null;
    064    private Map<Long, Double> iLimits = new HashMap<Long, Double>();
    065    private Map<Long, Map<Long, Set<Lecture>>> iSubparts = new HashMap<Long, Map<Long, Set<Lecture>>>();
    066    private boolean iTimeOutReached = false;
    067    private boolean iGroupFirst = false;
    068
    069    /**
    070     * Constructor
    071     * @param model course timetabling model
    072     * @param assignment current assignment
    073     */
    074    public SctModel(TimetableModel model, Assignment<Lecture, Placement> assignment) {
    075        iModel = model;
    076        iAssignment = assignment;
    077        iTimeOut = model.getProperties().getPropertyLong("SctSectioning.TimeOut", 1000);
    078        iUseCriteria = model.getProperties().getPropertyBoolean("SctSectioning.UseCriteria", true);
    079        iGroupFirst = model.getProperties().getPropertyBoolean("SctSectioning.GroupFirst", false);
    080    }
    081
    082    /**
    083     * List of student conflict criteria
    084     */
    085    public List<StudentConflict> getStudentConflictCriteria() {
    086        if (!iUseCriteria) return null;
    087        if (iStudentConflictCriteria == null && iModel != null) {
    088            iStudentConflictCriteria = new ArrayList<StudentConflict>();
    089            for (Criterion<Lecture, Placement> criterion: iModel.getCriteria())
    090                if (criterion instanceof StudentConflict)
    091                    iStudentConflictCriteria.add((StudentConflict)criterion);
    092        }
    093        return iStudentConflictCriteria;
    094    }
    095
    096    /**
    097     * All configuration of the selected offering
    098     */
    099    public List<Configuration> getConfigurations() { return iConfigurations; }
    100
    101    /**
    102     * Select an offering for the model
    103     */
    104    public void setConfiguration(Configuration config) {
    105        iConfigurations = new ArrayList<Configuration>();
    106        iConfigurations.add(config);
    107        iOfferingId = config.getOfferingId();
    108        if (config.getAltConfigurations() != null)
    109            for (Configuration alt: config.getAltConfigurations())
    110                if (!alt.equals(config)) iConfigurations.add(alt);
    111        iStudents = new ArrayList<SctStudent>();
    112        Set<Long> studentIds = new HashSet<Long>();
    113        for (Configuration c: iConfigurations)
    114            for (Lecture l: c.getTopLectures(c.getTopSubpartIds().iterator().next())) {
    115                for (Student s: l.students()) {
    116                    if (studentIds.add(s.getId()))
    117                        iStudents.add(new SctStudent(this, s));
    118                }
    119            }
    120        for (Student student: getTimetableModel().getAllStudents())
    121            if (student.hasOffering(getOfferingId()))
    122                if (studentIds.add(student.getId()))
    123                    iStudents.add(new SctStudent(this, student));
    124        Collections.sort(iStudents);
    125    }
    126
    127    /**
    128     * List of scheduling subparts and their classes of the given configuration
    129     */
    130    public Map<Long, Set<Lecture>> getSubparts(Configuration configuration) {
    131        Map<Long, Set<Lecture>> subparts = iSubparts.get(configuration.getConfigId());
    132        if (subparts == null) {
    133            subparts = new HashMap<Long, Set<Lecture>>();
    134            Queue<Lecture> queue = new LinkedList<Lecture>();
    135            for (Map.Entry<Long, Set<Lecture>> e: configuration.getTopLectures().entrySet()) {
    136                subparts.put(e.getKey(), e.getValue());
    137                queue.addAll(e.getValue());
    138            }
    139            Lecture lecture = null;
    140            while ((lecture = queue.poll()) != null) {
    141                if (lecture.getChildren() != null)
    142                    for (Map.Entry<Long, List<Lecture>> e: lecture.getChildren().entrySet()) {
    143                        Set<Lecture> lectures = subparts.get(e.getKey());
    144                        if (lectures == null) {
    145                            lectures = new HashSet<Lecture>(e.getValue());
    146                            subparts.put(e.getKey(), lectures);
    147                        } else {
    148                            lectures.addAll(e.getValue());
    149                        }
    150                        queue.addAll(e.getValue());
    151                    }
    152            }
    153            iSubparts.put(configuration.getConfigId(), subparts);
    154        }
    155        return subparts;
    156    }
    157
    158    /**
    159     * Selected offering id
    160     */
    161    public Long getOfferingId() { return iOfferingId; }
    162
    163    /**
    164     * Course timetabling model
    165     */
    166    public TimetableModel getTimetableModel() { return iModel; }
    167
    168    /**
    169     * Current assignment
    170     */
    171    public Assignment<Lecture, Placement> getAssignment() { return iAssignment; }
    172
    173    /**
    174     * Enrollment of the given class
    175     */
    176    private double getEnrollment(Lecture lecture, Map<Long, Double> limits) {
    177        Double enrollment = limits.get(lecture.getClassId());
    178        return enrollment == null ? 0.0 : enrollment.doubleValue();
    179    }
    180
    181    /**
    182     * Increment enrollment of the given class
    183     */
    184    private void incEnrollment(Lecture lecture, Map<Long, Double> limits, double weight) {
    185        Double enrollment = limits.get(lecture.getClassId());
    186        limits.put(lecture.getClassId(), (enrollment == null ? 0.0 : enrollment.doubleValue()) + weight);
    187    }
    188
    189    /**
    190     * Increment enrollment of all classes of the given classes
    191     */
    192    private void incEnrollment(SctStudent student, SctEnrollment enrollment, Map<Long, Double> limits, Map<Long, Map<Long, Match>> matches) {
    193        for (Lecture lecture: enrollment.getLectures())
    194            incEnrollment(lecture, limits, student.getOfferingWeight());
    195        for (StudentGroup group: student.getStudent().getGroups()) {
    196            Map<Long, Match> match = matches.get(group.getId());
    197            if (match == null) { match = new HashMap<Long, Match>(); matches.put(group.getId(), match); }
    198            for (Lecture lecture: enrollment.getLectures()) {
    199                Match m = match.get(lecture.getSchedulingSubpartId());
    200                if (m == null) { m = new Match(group, lecture); match.put(lecture.getSchedulingSubpartId(), m); }
    201                m.inc(lecture);
    202            }
    203        }
    204    }
    205
    206    /**
    207     * Decrement enrollment of all classes of the given classes
    208     */
    209    private void decEnrollment(SctStudent student, SctEnrollment enrollment, Map<Long, Double> limits, Map<Long, Map<Long, Match>> matches) {
    210        for (Lecture lecture: enrollment.getLectures())
    211            incEnrollment(lecture, limits, -student.getOfferingWeight());
    212        for (StudentGroup group: student.getStudent().getGroups()) {
    213            Map<Long, Match> match = matches.get(group.getId());
    214            if (match == null) { match = new HashMap<Long, Match>(); matches.put(group.getId(), match); }
    215            for (Lecture lecture: enrollment.getLectures()) {
    216                Match m = match.get(lecture.getSchedulingSubpartId());
    217                if (m == null) { m = new Match(group, lecture); match.put(lecture.getSchedulingSubpartId(), m); }
    218                m.dec(lecture);
    219            }
    220        }
    221    }
    222
    223    /**
    224     * Class limit
    225     */
    226    private double getLimit(Lecture lecture) {
    227        Double limit = iLimits.get(lecture.getClassId());
    228        if (limit == null) {
    229            limit = Math.max(lecture.classLimit(getAssignment()), lecture.nrWeightedStudents()) - sEps;
    230            iLimits.put(lecture.getClassId(), limit);
    231        }
    232        return limit;
    233    }
    234
    235    /**
    236     * Check if all classes of the given enrollment are available (the limit is not breached)
    237     */
    238    private boolean isAvailable(SctStudent student, SctEnrollment enrollment, Map<Long, Double> limits) {
    239        for (Lecture lecture: enrollment.getLectures())
    240            if (getEnrollment(lecture, limits) > getLimit(lecture)) return false;
    241        return true;
    242    }
    243
    244    /**
    245     * Group weight of the given enrollments
    246     */
    247    private double group(SctEnrollment[] enrollments) {
    248        Map<Long, Map<Long, Match>> matches = new HashMap<Long, Map<Long, Match>>();
    249        for (SctEnrollment enrollment: enrollments) {
    250            if (enrollment == null) continue;
    251            for (StudentGroup group: enrollment.getStudent().getStudent().getGroups()) {
    252                Map<Long, Match> match = matches.get(group.getId());
    253                if (match == null) { match = new HashMap<Long, Match>(); matches.put(group.getId(), match); }
    254                for (Lecture lecture: enrollment.getLectures()) {
    255                    Match m = match.get(lecture.getSchedulingSubpartId());
    256                    if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
    257                    m.inc(lecture);
    258                }
    259            }
    260        }
    261        double ret = 0.0;
    262        for (Map<Long, Match> match: matches.values()) {
    263            for (Match m: match.values())
    264                ret += m.value();
    265        }
    266        return ret;
    267    }
    268
    269    /**
    270     * Group weight of the given enrollments (up until the given index, computing bound for students above the index)
    271     */
    272    protected double group(SctEnrollment[] enrollments, int index,  Map<Long, Double> limits, Map<Long, Map<Long, Match>> matches) {
    273        // Map<Long, Map<Long, Match>> matches = new HashMap<Long, Map<Long, Match>>();
    274        Map<Long, UnMatched> unmatched = new HashMap<Long, UnMatched>();
    275        for (int i = index; i < iStudents.size(); i++) {
    276            SctStudent student = iStudents.get(i);
    277            for (StudentGroup group: student.getStudent().getGroups()) {
    278                UnMatched m = unmatched.get(group.getId());
    279                if (m == null) { m = new UnMatched(group); unmatched.put(group.getId(), m); }
    280                m.incBound(student);
    281            }
    282            /*
    283            if (i < index) {
    284                SctEnrollment enrollment = enrollments[i];
    285                if (enrollment == null) continue;
    286                for (StudentGroup group: student.getStudent().getGroups()) {
    287                    Map<Long, Match> match = matches.get(group.getId());
    288                    if (match == null) { match = new HashMap<Long, Match>(); matches.put(group.getId(), match); }
    289                    for (Lecture lecture: enrollment.getLectures()) {
    290                        Match m = match.get(lecture.getSchedulingSubpartId());
    291                        if (m == null) { m = new Match(group, lecture.getConfiguration()); match.put(lecture.getSchedulingSubpartId(), m); }
    292                        m.inc(lecture);
    293                    }
    294                }
    295            } else {
    296                for (StudentGroup group: student.getStudent().getGroups()) {
    297                    Map<Long, Match> match = matches.get(group.getId());
    298                    if (match == null) {
    299                        UnMatched m = unmatched.get(group.getId());
    300                        if (m == null) { m = new UnMatched(group); unmatched.put(group.getId(), m); }
    301                        m.incBound();
    302                        continue;
    303                    }
    304                    boolean increased = false;
    305                    for (Configuration configuration: iConfigurations) {
    306                        for (Long subpartId: getSubparts(configuration).keySet()) {
    307                            Match m = match.get(subpartId);
    308                            if (m != null && m.incBound()) increased = true;
    309                        }
    310                        if (increased) break;
    311                    }
    312                    if (!increased) {
    313                        UnMatched m = unmatched.get(group.getId());
    314                        if (m == null) { m = new UnMatched(group); unmatched.put(group.getId(), m); }
    315                        m.incBound();
    316                    }
    317                }
    318            }*/
    319        }
    320        double ret = 0.0;
    321        for (Map.Entry<Long, Map<Long, Match>> match: matches.entrySet()) {
    322            for (Match m: match.getValue().values())
    323                ret += m.value(unmatched.remove(match.getKey()), limits);
    324        }
    325        for (UnMatched m: unmatched.values()) {
    326            ret += m.value();
    327        }
    328        return ret;
    329    }
    330
    331    /**
    332     * Compute best possible enrollment of students into the given offering
    333     */
    334    public void computeSolution(SctSolution solution, int index, SctEnrollment[] enrollments, Map<Long, Double> limits, Map<Long, Map<Long, Match>> match, double totalConflicts, long t0) {
    335        if (iTimeOutReached) return;
    336        if (JProf.currentTimeMillis() - t0 > iTimeOut) {
    337            iTimeOutReached = true; return;
    338        }
    339        if (index < iStudents.size()) {
    340            if (!solution.checkBound(index, enrollments, totalConflicts, limits, match)) return;
    341            SctStudent student = iStudents.get(index);
    342            for (SctEnrollment enrollment: student.getEnrollments(new SctEnrollmentComparator(limits, match, index))) {
    343                if (!isAvailable(student, enrollment, limits)) continue;
    344                enrollments[index] = enrollment;
    345                incEnrollment(student, enrollment, limits, match);
    346                computeSolution(solution, index + 1, enrollments, limits, match, totalConflicts + enrollment.getConflictWeight(), t0);
    347                decEnrollment(student, enrollment, limits, match);
    348            }
    349        } else {
    350            if (solution.isBetter(enrollments, totalConflicts))
    351                solution.record(enrollments, totalConflicts);
    352        }
    353    }
    354
    355    /**
    356     * Compute best possible enrollment of students into the given offering
    357     */
    358    public SctSolution computeSolution() {
    359        SctSolution solution = currentSolution();
    360        iTimeOutReached = false;
    361        computeSolution(solution, 0, new SctEnrollment[iStudents.size()], new HashMap<Long, Double>(), new HashMap<Long, Map<Long, Match>>(), 0.0, JProf.currentTimeMillis());
    362        return solution;
    363    }
    364
    365    /**
    366     * Was time out reached while {@link SctModel#computeSolution()} was called?
    367     */
    368    public boolean isTimeOutReached() { return iTimeOutReached; }
    369
    370    public SctSolution currentSolution() {
    371        SctEnrollment[] enrollments = new SctEnrollment[iStudents.size()];
    372        for (int index = 0; index < iStudents.size(); index++)
    373            enrollments[index] = iStudents.get(index).getCurrentEnrollment(true);
    374        return new SctSolution(enrollments);
    375    }
    376
    377    /**
    378     * Decrement {@link JenrlConstraint} between the given two classes by the given student
    379     */
    380    protected void decJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    381        if (l1.equals(l2)) return;
    382        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    383        if (jenrl != null) {
    384            jenrl.decJenrl(assignment, student);
    385            /*
    386            if (jenrl.getNrStudents() == 0) {
    387                jenrl.getContext(assignment).unassigned(assignment, null);
    388                Object[] vars = jenrl.variables().toArray();
    389                for (int k = 0; k < vars.length; k++)
    390                    jenrl.removeVariable((Lecture) vars[k]);
    391                iModel.removeConstraint(jenrl);
    392            }
    393            */
    394        }
    395    }
    396
    397    /**
    398     * Increment {@link JenrlConstraint} between the given two classes by the given student
    399     */
    400    protected void incJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    401        if (l1.equals(l2)) return;
    402        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    403        if (jenrl == null) {
    404            jenrl = new JenrlConstraint();
    405            jenrl.addVariable(l1);
    406            jenrl.addVariable(l2);
    407            iModel.addConstraint(jenrl);
    408        }
    409        jenrl.incJenrl(assignment, student);
    410    }
    411
    412    /**
    413     * Unassign all previous enrollments into the given offering
    414     */
    415    public void unassign() {
    416        for (SctStudent student: iStudents) {
    417            Configuration configuration = null;
    418            for (Lecture lecture: student.getCurrentEnrollment(false).getLectures()) {
    419                if (configuration == null) configuration = lecture.getConfiguration();
    420                for (Lecture other: student.getStudent().getLectures())
    421                    decJenrl(getAssignment(), student.getStudent(), lecture, other);
    422                lecture.removeStudent(getAssignment(), student.getStudent());
    423                student.getStudent().removeLecture(lecture);
    424            }
    425            if (configuration != null)
    426                student.getStudent().removeConfiguration(configuration);
    427        }
    428    }
    429
    430    /**
    431     * Assign given solution
    432     */
    433    public void assign(SctSolution solution) {
    434        for (int index = 0; index < iStudents.size(); index++) {
    435            SctStudent student = iStudents.get(index);
    436            Configuration configuration = null;
    437            SctEnrollment enrollment = solution.iEnrollments[index];
    438            if (enrollment == null) continue;
    439            for (Lecture lecture: enrollment.getLectures()) {
    440                if (configuration == null) configuration = lecture.getConfiguration();
    441                for (Lecture other: student.getStudent().getLectures())
    442                    incJenrl(getAssignment(), student.getStudent(), lecture, other);
    443                lecture.addStudent(getAssignment(), student.getStudent());
    444                student.getStudent().addLecture(lecture);
    445            }
    446            if (configuration != null)
    447                student.getStudent().addConfiguration(configuration);
    448        }
    449    }
    450
    451    /**
    452     * Enrollment solution. Represent enrollments of all students into the given course.
    453     */
    454    class SctSolution {
    455        private double iWeight = 0.0;
    456        private double iGroup = 0.0;
    457        private SctEnrollment[] iEnrollments = null;
    458
    459        /**
    460         * Constructor (for empty solution)
    461         */
    462        public SctSolution() {}
    463
    464        /**
    465         * Constructor (for given solution)
    466         * @param enrollments given solution
    467         */
    468        public SctSolution(SctEnrollment[] enrollments) {
    469            iEnrollments = enrollments;
    470            iWeight = 0.0;
    471            for (SctEnrollment enrollment: enrollments)
    472                if (enrollment != null) iWeight += enrollment.getConflictWeight();
    473            iGroup = group(enrollments);
    474        }
    475
    476        /**
    477         * Compare two solutions
    478         */
    479        public boolean isBetter(SctEnrollment[] solution, double weight) {
    480            if (iGroupFirst) {
    481                if (iEnrollments == null) return true;
    482                double gr = group(solution);
    483                return gr > iGroup || (gr == iGroup && weight < iWeight);
    484            } else {
    485                return iEnrollments == null || weight < iWeight || (weight == iWeight && group(solution) > iGroup);
    486            }
    487        }
    488
    489        /**
    490         * Compare two solutions
    491         */
    492        public boolean isBetter(SctSolution other) {
    493            if (iGroupFirst) {
    494                if (iEnrollments == null) return true;
    495                return other.getGroup() < iGroup || (other.getGroup() == iGroup && iWeight < other.getWeight());
    496            } else {
    497                return iEnrollments != null && (iWeight < other.getWeight() || (other.getWeight() == iWeight && other.getGroup() < iGroup));
    498            }
    499        }
    500
    501        /**
    502         * Record given solution
    503         */
    504        public void record(SctEnrollment[] solution, double weight) {
    505            iEnrollments = Arrays.copyOf(solution, solution.length);
    506            iWeight = weight;
    507            iGroup = group(solution);
    508        }
    509
    510        /**
    511         * Check bounds (false means no better solution exists by extending the given solution)
    512         */
    513        public boolean checkBound(int index, SctEnrollment[] solution, double weight, Map<Long, Double> limits, Map<Long, Map<Long, Match>> match) {
    514            if (iEnrollments == null) return true;
    515            if (iGroupFirst) {
    516                double gr = group(solution, index, limits, match);
    517                if (gr == iGroup) {
    518                    double guess = weight;
    519                    for (int i = index; i < iStudents.size(); i++) {
    520                        SctStudent student = iStudents.get(i);
    521                        SctEnrollment enrollment = null;
    522                        for (SctEnrollment e: student.getEnrollments()) {
    523                            if (isAvailable(student, e, limits)) { enrollment = e; break; }
    524                        }
    525                        if (enrollment == null) return false;
    526                        guess += enrollment.getConflictWeight();
    527                        if (guess >= iWeight) break;
    528                    }
    529                    return guess < iWeight;
    530                }
    531                return gr > iGroup;
    532            } else {
    533                double guess = weight;
    534                for (int i = index; i < iStudents.size(); i++) {
    535                    SctStudent student = iStudents.get(i);
    536                    SctEnrollment enrollment = null;
    537                    for (SctEnrollment e: student.getEnrollments()) {
    538                        if (isAvailable(student, e, limits)) { enrollment = e; break; }
    539                    }
    540                    if (enrollment == null) return false;
    541                    guess += enrollment.getConflictWeight();
    542                    if (guess > iWeight) break;
    543                }
    544                return (guess < iWeight || (guess == iWeight && group(solution, index, limits, match) > iGroup));
    545            }
    546        }
    547
    548        /**
    549         * Individual student enrollments
    550         */
    551        public SctEnrollment[] getEnrollments() { return iEnrollments; }
    552        /**
    553         * Overall conflict weight
    554         */
    555        public double getWeight() { return iWeight; }
    556        /**
    557         * Overall group weight
    558         */
    559        public double getGroup() { return iGroup; }
    560        /**
    561         * False if empty
    562         */
    563        public boolean isValid() { return iEnrollments != null; }
    564    }
    565
    566    /**
    567     * Matching students within a scheduling subpart (for student group weight computation)
    568     */
    569    private class Match {
    570        private int iTotal = 0;
    571        private Map<Lecture, Integer> iMatch = new HashMap<Lecture, Integer>();
    572        private double iFraction = 1.0;
    573
    574        /**
    575         * Constructor
    576         * @param group student group
    577         */
    578        Match(StudentGroup group, Lecture lecture) {
    579            this(group, lecture.getConfiguration());
    580            for (Lecture l: lecture.sameSubpartLectures())
    581                iMatch.put(l, 0);
    582        }
    583
    584        Match(StudentGroup group, Configuration config) {
    585            iTotal = group.countStudents(getOfferingId());
    586            iFraction = 1.0 / getSubparts(config).size();
    587        }
    588
    589        /**
    590         * Increment given lecture
    591         */
    592        void inc(Lecture lecture) {
    593            Integer val = iMatch.get(lecture);
    594            iMatch.put(lecture, 1 + (val == null ? 0 : val.intValue()));
    595        }
    596
    597        /**
    598         * Decrement given lecture
    599         */
    600        void dec(Lecture lecture) {
    601            Integer val = iMatch.get(lecture);
    602            iMatch.put(lecture, (val == null ? 0 : val.intValue()) - 1);
    603        }
    604
    605        /**
    606         * Returns counter for the given lecture
    607         */
    608        int get(Lecture lecture) {
    609            Integer val = iMatch.get(lecture);
    610            return val == null ? 0 : val.intValue();
    611        }
    612
    613        /**
    614         * Value (an overall probability of two students being in the same lecture)
    615         */
    616        double value(UnMatched u, final Map<Long, Double> limits) {
    617            if (iTotal <= 1) return iFraction;
    618            if (u == null || u.getNotMatched() == 0) return value();
    619            double value = 0.0;
    620            int unmatched = u.getNotMatched();
    621            double remains = u.getEnrollmentWeight();
    622            double avgWeight = remains / unmatched;
    623            TreeSet<Map.Entry<Lecture, Integer>> entries = new TreeSet<Map.Entry<Lecture, Integer>>(new Comparator<Map.Entry<Lecture, Integer>>() {
    624                @Override
    625                public int compare(Entry<Lecture, Integer> e1, Entry<Lecture, Integer> e2) {
    626                    if (e1.getValue() > e2.getValue()) return -1;
    627                    if (e1.getValue() < e2.getValue()) return 1;
    628                    double r1 = getLimit(e1.getKey()) - getEnrollment(e1.getKey(), limits);
    629                    double r2 = getLimit(e2.getKey()) - getEnrollment(e2.getKey(), limits);
    630                    int cmp = Double.compare(r2, r1);
    631                    if (cmp != 0) return cmp;
    632                    return e1.getKey().compareTo(e2.getKey());
    633                }
    634            });
    635            entries.addAll(iMatch.entrySet());
    636            for (Map.Entry<Lecture, Integer> entry: entries) {
    637                Integer m = entry.getValue();
    638                if (unmatched > 0) {
    639                    double enroll = Math.min(remains, getLimit(entry.getKey()) - getEnrollment(entry.getKey(), limits));
    640                    int inc = (int)Math.round(enroll / avgWeight);
    641                    if (inc > 0) {
    642                        m += inc;
    643                        unmatched -= inc;
    644                        remains -= enroll;
    645                    }
    646                }
    647                if (m > 1)
    648                    value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0));
    649            }
    650            if (unmatched > 1)
    651                value += (unmatched * (unmatched - 1.0)) / (iTotal * (iTotal - 1.0));
    652            return value * iFraction;
    653        }
    654
    655        double value() {
    656            if (iTotal <= 1) return iFraction;
    657            double value = 0.0;
    658            for (Integer m: iMatch.values())
    659                if (m > 1) {
    660                    value += (m * (m - 1.0)) / (iTotal * (iTotal - 1.0));
    661                }
    662            return value * iFraction;
    663        }
    664
    665        @Override
    666        public String toString() {
    667            return iTotal + "/" + iMatch + "[" + value() + "]";
    668        }
    669    }
    670
    671    /**
    672     * Matching students within a scheduling subpart (for student group weight computation)
    673     */
    674    private class UnMatched {
    675        private int iTotal = 0;
    676        private int iNotMatched = 0;
    677        private double iEnrollmentWeight = 0.0;
    678
    679        /**
    680         * Constructor
    681         * @param group student group
    682         */
    683        UnMatched(StudentGroup group) {
    684            iTotal = group.countStudents(getOfferingId());
    685        }
    686
    687        /**
    688         * Increment bound (a student gets into the best possible class)
    689         */
    690        void incBound(SctStudent student) {
    691            iNotMatched ++;
    692            iEnrollmentWeight += student.getStudent().getOfferingWeight(getOfferingId());
    693        }
    694
    695        /**
    696         * Value (an overall probability of two students being in the same lecture)
    697         */
    698        double value() {
    699            if (iTotal <= 1) return 1.0;
    700            if (iNotMatched > 1)
    701                return (iNotMatched * (iNotMatched - 1.0)) / (iTotal * (iTotal - 1.0));
    702            return 0.0;
    703        }
    704
    705        int getNotMatched() { return iNotMatched; }
    706
    707        public double getEnrollmentWeight() { return iEnrollmentWeight; }
    708
    709        @Override
    710        public String toString() {
    711            return iTotal + "/" + iNotMatched;
    712        }
    713    }
    714
    715    private class SctEnrollmentComparator implements Comparator<SctEnrollment> {
    716        private Map<Long, Double> limits;
    717        private Map<Long, Map<Long, Match>> matches;
    718        private int index;
    719
    720        SctEnrollmentComparator(Map<Long, Double> limits, Map<Long, Map<Long, Match>> match, int index) {
    721            this.limits = limits; this.matches = match; this.index = index;
    722        }
    723
    724        public int compareByGroup(SctEnrollment e1, SctEnrollment e2) {
    725            double m1 = 0, m2 = 0;
    726            for (StudentGroup g: e1.getStudent().getStudent().getGroups()) {
    727                int remaining = 0;
    728                int total = g.countStudents(getOfferingId());
    729                double remainingWeight = 0.0;
    730                for (int i = index; i < iStudents.size(); i++) {
    731                    SctStudent student = iStudents.get(i);
    732                    if (student.getStudent().hasGroup(g)) {
    733                        remaining++;
    734                        remainingWeight += student.getStudent().getOfferingWeight(getOfferingId());
    735                    }
    736                }
    737                double avgWeight = remainingWeight / remaining;
    738                Map<Long, Match> match = matches.get(g.getId());
    739                for (Lecture lecture: e1.getLectures()) {
    740                    Match m = (match == null ? null : match.get(lecture.getSchedulingSubpartId()));
    741                    double fraction = 1.0 / getSubparts(lecture.getConfiguration()).size();
    742                    int a = (m == null ? 0 : m.get(lecture));
    743                    double enroll = Math.min(remainingWeight, getLimit(lecture) - getEnrollment(lecture, limits));
    744                    a += (int)Math.round(enroll / avgWeight);
    745                    m1 += fraction * (a * (a - 1)) / ((total * (total - 1)));
    746                }
    747                for (Lecture lecture: e2.getLectures()) {
    748                    Match m = (match == null ? null : match.get(lecture.getSchedulingSubpartId()));
    749                    double fraction = 1.0 / getSubparts(lecture.getConfiguration()).size();
    750                    int a = (m == null ? 0 : m.get(lecture));
    751                    double enroll = Math.min(remainingWeight, getLimit(lecture) - getEnrollment(lecture, limits));
    752                    a += (int)Math.round(enroll / avgWeight);
    753                    m2 += fraction * (a * (a - 1)) / ((total * (total - 1)));
    754                }
    755            }
    756            if (m1 != m2) return m1 > m2 ? -1 : 1;
    757            return 0;
    758        }
    759
    760        @Override
    761        public int compare(SctEnrollment e1, SctEnrollment e2) {
    762            if (iGroupFirst) {
    763                int cmp = compareByGroup(e1, e2);
    764                if (cmp != 0) return cmp;
    765                cmp = Double.compare(e1.getConflictWeight(), e2.getConflictWeight());
    766                if (cmp != 0) return cmp;
    767            } else {
    768                int cmp = Double.compare(e1.getConflictWeight(), e2.getConflictWeight());
    769                if (cmp != 0) return cmp;
    770                cmp = compareByGroup(e1, e2);
    771                if (cmp != 0) return cmp;
    772            }
    773            return e1.getId().compareTo(e2.getId());
    774        }
    775
    776    }
    777}