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