    001package net.sf.cpsolver.coursett.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashSet;
    006import java.util.List;
    007import java.util.Set;
    008
    009import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
    010import net.sf.cpsolver.coursett.criteria.StudentConflict;
    011import net.sf.cpsolver.ifs.util.Progress;
    012import net.sf.cpsolver.ifs.util.ToolBox;
    013
    014/**
    015 * Student sectioning (after a solution is found). <br>
    016 * <br>
    017 * In the current implementation, students are not re-sectioned during the
    018 * search, but a student re-sectioning algorithm is called after the solver is
    019 * finished or upon the user???s request. The re-sectioning is based on a local
    020 * search algorithm where the neighboring assignment is obtained from the
    021 * current assignment by applying one of the following moves:
    022 * <ul>
    023 * <li>Two students enrolled in the same course swap all of their class
    024 * assignments.
    025 * <li>A student is re-enrolled into classes associated with a course such that
    026 * the number of conflicts involving that student is minimized.
    027 * </ul>
    028 * The solver maintains a queue, initially containing all courses with multiple
    029 * classes. During each iteration, an improving move (i.e., a move decreasing
    030 * the overall number of student conflicts) is applied once discovered.
    031 * Re-sectioning is complete once no more improving moves are possible. Only
    032 * consistent moves (i.e., moves that respect class limits and other
    033 * constraints) are considered. Any additional courses having student conflicts
    034 * after a move is accepted are added to the queue. <br>
    035 * Since students are not re-sectioned during the timetabling search, the
    036 * computed number of student conflicts is really an upper bound on the actual
    037 * number that may exist afterward. To compensate for this during the search,
    038 * student conflicts between subparts with multiple classes are weighted lower
    039 * than conflicts between classes that meet at a single time (i.e., having
    040 * student conflicts that cannot be avoided by re-sectioning).
    041 *
    042 * @version CourseTT 1.2 (University Course Timetabling)<br>
    043 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    044 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    045 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    046 * <br>
    047 *          This library is free software; you can redistribute it and/or modify
    048 *          it under the terms of the GNU Lesser General Public License as
    049 *          published by the Free Software Foundation; either version 3 of the
    050 *          License, or (at your option) any later version. <br>
    051 * <br>
    052 *          This library is distributed in the hope that it will be useful, but
    053 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    054 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    055 *          Lesser General Public License for more details. <br>
    056 * <br>
    057 *          You should have received a copy of the GNU Lesser General Public
    058 *          License along with this library; if not see
    059 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    060 */
    061
    062public class FinalSectioning implements Runnable {
    063    private TimetableModel iModel = null;
    064    public static double sEps = 0.0001;
    065    private boolean iWeighStudents = false;
    066
    067    public FinalSectioning(TimetableModel model) {
    068        iModel = model;
    069        iWeighStudents = model.getProperties().getPropertyBoolean("General.WeightStudents", iWeighStudents);
    070    }
    071
    072    @Override
    073    public void run() {
    074        Progress p = Progress.getInstance(iModel);
    075        p.setStatus("Student Sectioning...");
    076        Collection<Lecture> variables = new ArrayList<Lecture>(iModel.variables());
    077        // include committed classes that have structure
    078        if (iModel.hasConstantVariables())
    079            for (Lecture lecture: iModel.constantVariables()) {
    080                // if (lecture.getParent() != null || (lecture.sameStudentsLectures()!= null && !lecture.sameStudentsLectures().isEmpty()))
    081                variables.add(lecture);
    082            }
    083        while (!variables.isEmpty()) {
    084            // sLogger.debug("Shifting students ...");
    085            p.setPhase("moving students ...", variables.size());
    086            HashSet<Lecture> lecturesToRecompute = new HashSet<Lecture>(variables.size());
    087
    088            for (Lecture lecture : variables) {
    089                if (lecture.getParent() == null) {
    090                    Configuration cfg = lecture.getConfiguration();
    091                    if (cfg != null && cfg.getAltConfigurations().size() > 1)
    092                        findAndPerformMoves(cfg, lecturesToRecompute);
    093                }
    094                // sLogger.debug("Shifting students for "+lecture);
    095                findAndPerformMoves(lecture, lecturesToRecompute);
    096                // sLogger.debug("Lectures to recompute: "+lects);
    097                p.incProgress();
    098            }
    099            // sLogger.debug("Shifting done, "+getViolatedStudentConflictsCounter().get()+" conflicts.");
    100            variables = lecturesToRecompute;
    101        }
    102    }
    103
    104    /**
    105     * Perform sectioning on the given lecture
    106     *
    107     * @param lecture
    108     *            given lecture
    109     * @param recursive
    110     *            recursively resection lectures affected by a student swap
    111     * @param configAsWell
    112     *            resection students between configurations as well
    113     **/
    114    public void resection(Lecture lecture, boolean recursive, boolean configAsWell) {
    115        HashSet<Lecture> variables = new HashSet<Lecture>();
    116        findAndPerformMoves(lecture, variables);
    117        if (configAsWell) {
    118            Configuration cfg = lecture.getConfiguration();
    119            if (cfg != null && cfg.getAltConfigurations().size() > 1)
    120                findAndPerformMoves(cfg, variables);
    121        }
    122        if (recursive) {
    123            while (!variables.isEmpty()) {
    124                HashSet<Lecture> lecturesToRecompute = new HashSet<Lecture>();
    125                for (Lecture l : variables) {
    126                    if (configAsWell && l.getParent() == null) {
    127                        Configuration cfg = l.getConfiguration();
    128                        if (cfg != null && cfg.getAltConfigurations().size() > 1)
    129                            findAndPerformMoves(cfg, lecturesToRecompute);
    130                    }
    131                    findAndPerformMoves(l, lecturesToRecompute);
    132                }
    133                variables = lecturesToRecompute;
    134            }
    135        }
    136    }
    137
    138    /**
    139     * Swap students between this and the same lectures (lectures which differ
    140     * only in the section)
    141     */
    142    public void findAndPerformMoves(Lecture lecture, HashSet<Lecture> lecturesToRecompute) {
    143        if (lecture.sameSubpartLectures() == null || lecture.getAssignment() == null)
    144            return;
    145
    146        if (lecture.getClassLimitConstraint() != null) {
    147            while (lecture.nrWeightedStudents() > sEps + lecture.minClassLimit()) {
    148                Move m = findAwayMove(lecture);
    149                if (m == null)
    150                    break;
    151                if (m.perform())
    152                    lecturesToRecompute.add(m.secondLecture());
    153            }
    154        } else if (!iWeighStudents) {
    155            while (true) {
    156                Move m = findAwayMove(lecture);
    157                if (m == null)
    158                    break;
    159                if (m.perform())
    160                    lecturesToRecompute.add(m.secondLecture());
    161            }
    162        }
    163
    164        Set<Student> conflictStudents = lecture.conflictStudents();
    165        if (conflictStudents == null || conflictStudents.isEmpty())
    166            return;
    167        // sLogger.debug("  conflicts:"+conflictStudents.size()+"/"+conflictStudents);
    168        // sLogger.debug("Solution before swap is "+iModel.getInfo()+".");
    169        if (lecture.sameSubpartLectures().size() > 1) {
    170            for (Student student : conflictStudents) {
    171                if (lecture.getAssignment() == null)
    172                        continue;
    173                Move m = findMove(lecture, student);
    174                if (m != null) {
    175                    if (m.perform())
    176                        lecturesToRecompute.add(m.secondLecture());
    177                }
    178            }
    179        } else {
    180            for (Student student : conflictStudents) {
    181                for (Lecture anotherLecture : lecture.conflictLectures(student)) {
    182                    if (anotherLecture.equals(lecture) || anotherLecture.sameSubpartLectures() == null
    183                            || anotherLecture.getAssignment() == null
    184                            || anotherLecture.sameSubpartLectures().size() <= 1)
    185                        continue;
    186                    lecturesToRecompute.add(anotherLecture);
    187                }
    188            }
    189        }
    190    }
    191
    192    public void findAndPerformMoves(Configuration configuration, HashSet<Lecture> lecturesToRecompute) {
    193        for (Student student : configuration.students()) {
    194            if (!configuration.hasConflict(student))
    195                continue;
    196
    197            MoveBetweenCfgs m = findMove(configuration, student);
    198
    199            if (m != null) {
    200                if (m.perform())
    201                    lecturesToRecompute.addAll(m.secondLectures());
    202            }
    203        }
    204    }
    205
    206    public Move findAwayMove(Lecture lecture) {
    207        List<Move> bestMoves = null;
    208        double bestDelta = 0;
    209        for (Student student : lecture.students()) {
    210            if (!student.canUnenroll(lecture))
    211                continue;
    212            for (Lecture sameLecture : lecture.sameSubpartLectures()) {
    213                double studentWeight = student.getOfferingWeight(sameLecture.getConfiguration());
    214                if (!student.canEnroll(sameLecture))
    215                    continue;
    216                if (sameLecture.equals(lecture) || sameLecture.getAssignment() == null)
    217                    continue;
    218                if (sameLecture.nrWeightedStudents() + studentWeight <= sEps + sameLecture.classLimit()) {
    219                    Move m = createMove(lecture, student, sameLecture, null);
    220                    if (m == null || m.isTabu())
    221                        continue;
    222                    double delta = m.getDelta();
    223                    if (delta < bestDelta) {
    224                        if (bestMoves == null)
    225                            bestMoves = new ArrayList<Move>();
    226                        else
    227                            bestMoves.clear();
    228                        bestMoves.add(m);
    229                        bestDelta = delta;
    230                    } else if (delta == bestDelta) {
    231                        if (bestMoves == null)
    232                            bestMoves = new ArrayList<Move>();
    233                        bestMoves.add(m);
    234                    }
    235                }
    236            }
    237        }
    238        if (bestDelta < -sEps && bestMoves != null) {
    239            Move m = ToolBox.random(bestMoves);
    240            return m;
    241        }
    242        return null;
    243    }
    244
    245    public Move findMove(Lecture lecture, Student student) {
    246        if (!student.canUnenroll(lecture)) return null;
    247        double bestDelta = 0;
    248        List<Move> bestMoves = null;
    249        double studentWeight = student.getOfferingWeight(lecture.getConfiguration());
    250        for (Lecture sameLecture : lecture.sameSubpartLectures()) { // sameStudentLectures
    251            if (!student.canEnroll(sameLecture))
    252                continue;
    253            if (sameLecture.equals(lecture) || sameLecture.getAssignment() == null)
    254                continue;
    255            if (sameLecture.nrWeightedStudents() + studentWeight <= sEps + sameLecture.classLimit()) {
    256                Move m = createMove(lecture, student, sameLecture, null);
    257                if (m == null || m.isTabu())
    258                    continue;
    259                double delta = m.getDelta();
    260                if (delta < bestDelta) {
    261                    if (bestMoves == null)
    262                        bestMoves = new ArrayList<Move>();
    263                    else
    264                        bestMoves.clear();
    265                    bestMoves.add(m);
    266                    bestDelta = delta;
    267                } else if (delta == bestDelta) {
    268                    if (bestMoves == null)
    269                        bestMoves = new ArrayList<Move>();
    270                    bestMoves.add(m);
    271                }
    272            }
    273            for (Student anotherStudent : sameLecture.students()) {
    274                if (!anotherStudent.canUnenroll(sameLecture) || !anotherStudent.canEnroll(lecture))
    275                    continue;
    276                double anotherStudentWeight = anotherStudent.getOfferingWeight(lecture.getConfiguration());
    277                if (anotherStudentWeight != studentWeight) {
    278                    if (sameLecture.nrWeightedStudents() - anotherStudentWeight + studentWeight > sEps
    279                            + sameLecture.classLimit())
    280                        continue;
    281                    if (lecture.nrWeightedStudents() - studentWeight + anotherStudentWeight > sEps
    282                            + lecture.classLimit())
    283                        continue;
    284                }
    285                if (bestDelta < -sEps && bestMoves != null && bestMoves.size() > 10)
    286                    break;
    287                Move m = createMove(lecture, student, sameLecture, anotherStudent);
    288                if (m == null || m.isTabu())
    289                    continue;
    290                double delta = m.getDelta();
    291                if (delta < bestDelta) {
    292                    if (bestMoves == null)
    293                        bestMoves = new ArrayList<Move>();
    294                    else
    295                        bestMoves.clear();
    296                    bestMoves.add(m);
    297                    bestDelta = delta;
    298                } else if (delta == bestDelta) {
    299                    if (bestMoves == null)
    300                        bestMoves = new ArrayList<Move>();
    301                    bestMoves.add(m);
    302                }
    303            }
    304            if (Math.abs(bestDelta) < sEps && bestMoves != null && bestMoves.size() > 10)
    305                break;
    306        }
    307        if (bestDelta < -sEps && bestMoves != null)
    308            return ToolBox.random(bestMoves);
    309        return null;
    310    }
    311
    312    public MoveBetweenCfgs findMove(Configuration config, Student student) {
    313        double bestDelta = 0;
    314        List<MoveBetweenCfgs> bestMoves = null;
    315        for (Configuration altConfig : config.getAltConfigurations()) {
    316            if (altConfig.equals(config))
    317                continue;
    318
    319            MoveBetweenCfgs m = createMove(config, student, altConfig, null);
    320            if (m != null && !m.isTabu()) {
    321                double delta = m.getDelta();
    322                if (delta < bestDelta) {
    323                    if (bestMoves == null)
    324                        bestMoves = new ArrayList<MoveBetweenCfgs>();
    325                    else
    326                        bestMoves.clear();
    327                    bestMoves.add(m);
    328                    bestDelta = delta;
    329                } else if (delta == bestDelta) {
    330                    if (bestMoves == null)
    331                        bestMoves = new ArrayList<MoveBetweenCfgs>();
    332                    bestMoves.add(m);
    333                }
    334            }
    335
    336            for (Student anotherStudent : altConfig.students()) {
    337                if (bestDelta < -sEps && bestMoves != null && bestMoves.size() > 10)
    338                    break;
    339
    340                m = createMove(config, student, altConfig, anotherStudent);
    341                if (m != null && !m.isTabu()) {
    342                    double delta = m.getDelta();
    343                    if (delta < bestDelta) {
    344                        if (bestMoves == null)
    345                            bestMoves = new ArrayList<MoveBetweenCfgs>();
    346                        else
    347                            bestMoves.clear();
    348                        bestMoves.add(m);
    349                        bestDelta = delta;
    350                    } else if (delta == bestDelta) {
    351                        if (bestMoves == null)
    352                            bestMoves = new ArrayList<MoveBetweenCfgs>();
    353                        bestMoves.add(m);
    354                    }
    355                }
    356            }
    357            if (Math.abs(bestDelta) < sEps && bestMoves != null && bestMoves.size() > 10)
    358                break;
    359        }
    360        if (bestDelta < -sEps && bestMoves != null)
    361            return ToolBox.random(bestMoves);
    362        return null;
    363    }
    364
    365    public Move createMove(Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent) {
    366        return createMove(firstLecture, firstStudent, secondLecture, secondStudent, null);
    367    }
    368
    369    public Move createMove(Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent, Move parentMove) {
    370        if (!firstStudent.canUnenroll(firstLecture) || !firstStudent.canEnroll(secondLecture))
    371            return null;
    372        if (secondStudent != null && (!secondStudent.canUnenroll(secondLecture) || !secondStudent.canEnroll(firstLecture)))
    373            return null;
    374        if (firstLecture.getParent() != null && secondLecture.getParent() == null)
    375            return null;
    376        if (firstLecture.getParent() == null && secondLecture.getParent() != null)
    377            return null;
    378
    379        Move move = new Move(firstLecture, firstStudent, secondLecture, secondStudent);
    380
    381        if (parentMove == null) {
    382            Lecture l1 = firstLecture, l2 = secondLecture;
    383            while (l1.getParent() != null && l2.getParent() != null && !l1.getParent().equals(l2.getParent())) {
    384                Lecture p1 = l1.getParent();
    385                Lecture p2 = l2.getParent();
    386                if (p1.getAssignment() == null || p2.getAssignment() == null) return null;
    387                double w1 = firstStudent.getOfferingWeight(p1.getConfiguration());
    388                double w2 = (secondStudent == null ? 0.0 : secondStudent.getOfferingWeight(p2.getConfiguration()));
    389                if (w1 != w2) {
    390                    if (p1.nrWeightedStudents() - w1 + w2 > sEps + p1.classLimit())
    391                        return null;
    392                    if (p2.nrWeightedStudents() - w2 + w1 > sEps + p2.classLimit())
    393                        return null;
    394                }
    395                if (firstStudent.canUnenroll(p2) && firstStudent.canEnroll(p1) && (secondStudent == null || (secondStudent.canUnenroll(p1) && secondStudent.canEnroll(p2)))) {
    396                    move.addChildMove(new Move(p1, firstStudent, p2, secondStudent));
    397                } else {
    398                    return null;
    399                }
    400                l1 = p1; l2 = p2;
    401            }
    402        }
    403
    404        if (firstLecture.hasAnyChildren() != secondLecture.hasAnyChildren())
    405            return null;
    406        if (firstLecture.hasAnyChildren()) {
    407            if (secondStudent != null) {
    408                for (Long subpartId: firstLecture.getChildrenSubpartIds()) {
    409                    Lecture firstChildLecture = firstLecture.getChild(firstStudent, subpartId);
    410                    Lecture secondChildLecture = secondLecture.getChild(secondStudent, subpartId);
    411                    if (firstChildLecture == null || secondChildLecture == null)
    412                        return null;
    413                    double firstStudentWeight = firstStudent.getOfferingWeight(firstChildLecture.getConfiguration());
    414                    double secondStudentWeight = secondStudent.getOfferingWeight(secondChildLecture.getConfiguration());
    415                    if (firstStudentWeight != secondStudentWeight) {
    416                        if (firstChildLecture.nrWeightedStudents() - firstStudentWeight + secondStudentWeight > sEps
    417                                + firstChildLecture.classLimit())
    418                            return null;
    419                        if (secondChildLecture.nrWeightedStudents() - secondStudentWeight + firstStudentWeight > sEps
    420                                + secondChildLecture.classLimit())
    421                            return null;
    422                    }
    423                    if (firstChildLecture.getAssignment() != null && secondChildLecture.getAssignment() != null) {
    424                        Move m = createMove(firstChildLecture, firstStudent, secondChildLecture, secondStudent, move);
    425                        if (m == null)
    426                            return null;
    427                        move.addChildMove(m);
    428                    } else
    429                        return null;
    430                }
    431            } else {
    432                for (Long subpartId: firstLecture.getChildrenSubpartIds()) {
    433                    Lecture firstChildLecture = firstLecture.getChild(firstStudent, subpartId);
    434                    if (firstChildLecture == null || firstChildLecture.getAssignment() == null)
    435                        return null;
    436                    double firstStudentWeight = firstStudent.getOfferingWeight(firstChildLecture.getConfiguration());
    437                    List<Lecture> secondChildLectures = secondLecture.getChildren(subpartId);
    438                    if (secondChildLectures == null || secondChildLectures.isEmpty())
    439                        return null;
    440                    List<Move> bestMoves = null;
    441                    double bestDelta = 0;
    442                    for (Lecture secondChildLecture : secondChildLectures) {
    443                        if (secondChildLecture.getAssignment() == null)
    444                            continue;
    445                        if (secondChildLecture.nrWeightedStudents() + firstStudentWeight > sEps
    446                                + secondChildLecture.classLimit())
    447                            continue;
    448                        Move m = createMove(firstChildLecture, firstStudent, secondChildLecture, secondStudent, move);
    449                        if (m == null)
    450                            continue;
    451                        double delta = m.getDelta();
    452                        if (bestMoves == null || delta < bestDelta) {
    453                            if (bestMoves == null)
    454                                bestMoves = new ArrayList<Move>();
    455                            else
    456                                bestMoves.clear();
    457                            bestMoves.add(m);
    458                            bestDelta = delta;
    459                        } else if (delta == bestDelta) {
    460                            bestMoves.add(m);
    461                        }
    462                    }
    463                    if (bestDelta >= 0 || bestMoves == null)
    464                        return null;
    465                    Move m = ToolBox.random(bestMoves);
    466                    move.addChildMove(m);
    467                }
    468            }
    469        }
    470        return move;
    471    }
    472
    473    public class Move {
    474        Lecture iFirstLecture = null;
    475        Student iFirstStudent = null;
    476        Lecture iSecondLecture = null;
    477        Student iSecondStudent = null;
    478        List<Move> iChildMoves = null;
    479
    480        private Move(Lecture firstLecture, Student firstStudent, Lecture secondLecture, Student secondStudent) {
    481            iFirstLecture = firstLecture;
    482            iFirstStudent = firstStudent;
    483            iSecondLecture = secondLecture;
    484            iSecondStudent = secondStudent;
    485        }
    486
    487        public Lecture firstLecture() {
    488            return iFirstLecture;
    489        }
    490
    491        public Student firstStudent() {
    492            return iFirstStudent;
    493        }
    494
    495        public Lecture secondLecture() {
    496            return iSecondLecture;
    497        }
    498
    499        public Student secondStudent() {
    500            return iSecondStudent;
    501        }
    502
    503        public void addChildMove(Move move) {
    504            if (iChildMoves == null)
    505                iChildMoves = new ArrayList<Move>();
    506            iChildMoves.add(move);
    507        }
    508
    509        public List<Move> getChildMoves() {
    510            return iChildMoves;
    511        }
    512
    513        public boolean perform() {
    514            double conflicts = firstLecture().getModel().getCriterion(StudentConflict.class).getValue();
    515            for (Lecture lecture : firstStudent().getLectures()) {
    516                if (lecture.equals(firstLecture()))
    517                    continue;
    518                JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture);
    519                if (jenrl == null)
    520                    continue;
    521                jenrl.decJenrl(firstStudent());
    522                if (jenrl.getNrStudents() == 0) {
    523                    Object[] vars = jenrl.variables().toArray();
    524                    for (int j = 0; j < vars.length; j++)
    525                        jenrl.removeVariable((Lecture) vars[j]);
    526                    iModel.removeConstraint(jenrl);
    527                }
    528            }
    529            if (secondStudent() != null) {
    530                for (Lecture lecture : secondStudent().getLectures()) {
    531                    if (lecture.equals(secondLecture()))
    532                        continue;
    533                    JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture);
    534                    if (jenrl == null)
    535                        continue;
    536                    jenrl.decJenrl(secondStudent());
    537                    if (jenrl.getNrStudents() == 0) {
    538                        Object[] vars = jenrl.variables().toArray();
    539                        for (int j = 0; j < vars.length; j++)
    540                            jenrl.removeVariable((Lecture) vars[j]);
    541                        iModel.removeConstraint(jenrl);
    542                    }
    543                }
    544            }
    545
    546            firstLecture().removeStudent(firstStudent());
    547            firstStudent().removeLecture(firstLecture());
    548            secondLecture().addStudent(firstStudent());
    549            firstStudent().addLecture(secondLecture());
    550            if (secondStudent() != null) {
    551                secondLecture().removeStudent(secondStudent());
    552                secondStudent().removeLecture(secondLecture());
    553                firstLecture().addStudent(secondStudent());
    554                secondStudent().addLecture(firstLecture());
    555            }
    556
    557            for (Lecture lecture : firstStudent().getLectures()) {
    558                if (lecture.equals(secondLecture()))
    559                    continue;
    560                JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture);
    561                if (jenrl == null) {
    562                    jenrl = new JenrlConstraint();
    563                    iModel.addConstraint(jenrl);
    564                    jenrl.addVariable(secondLecture());
    565                    jenrl.addVariable(lecture);
    566                    // sLogger.debug(getName()+": add jenr {conf="+jenrl.isInConflict()+", lect="+anotherLecture.getName()+", jenr="+jenrl+"}");
    567                }
    568                jenrl.incJenrl(firstStudent());
    569            }
    570            if (secondStudent() != null) {
    571                for (Lecture lecture : secondStudent().getLectures()) {
    572                    if (lecture.equals(firstLecture()))
    573                        continue;
    574                    JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture);
    575                    if (jenrl == null) {
    576                        jenrl = new JenrlConstraint();
    577                        iModel.addConstraint(jenrl);
    578                        jenrl.addVariable(lecture);
    579                        jenrl.addVariable(firstLecture());
    580                        // sLogger.debug(getName()+": add jenr {conf="+jenrl.isInConflict()+", lect="+anotherLecture.getName()+", jenr="+jenrl+"}");
    581                    }
    582                    jenrl.incJenrl(secondStudent());
    583                }
    584            }
    585
    586            if (getChildMoves() != null) {
    587                for (Move move : getChildMoves()) {
    588                    move.perform();
    589                }
    590            }
    591            // sLogger.debug("Solution after swap is "+iModel.getInfo()+".");
    592            return firstLecture().getModel().getCriterion(StudentConflict.class).getValue() < conflicts;
    593        }
    594
    595        public double getDelta() {
    596            double delta = 0;
    597            for (Lecture lecture : firstStudent().getLectures()) {
    598                if (lecture.getAssignment() == null || lecture.equals(firstLecture()))
    599                    continue;
    600                JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture);
    601                if (jenrl == null)
    602                    continue;
    603                if (jenrl.isInConflict())
    604                    delta -= jenrl.getJenrlWeight(firstStudent());
    605            }
    606            if (secondStudent() != null) {
    607                for (Lecture lecture : secondStudent().getLectures()) {
    608                    if (lecture.getAssignment() == null || lecture.equals(secondLecture()))
    609                        continue;
    610                    JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture);
    611                    if (jenrl == null)
    612                        continue;
    613                    if (jenrl.isInConflict())
    614                        delta -= jenrl.getJenrlWeight(secondStudent());
    615                }
    616            }
    617
    618            for (Lecture lecture : firstStudent().getLectures()) {
    619                if (lecture.getAssignment() == null || lecture.equals(firstLecture()))
    620                    continue;
    621                JenrlConstraint jenrl = secondLecture().jenrlConstraint(lecture);
    622                if (jenrl != null) {
    623                    if (jenrl.isInConflict())
    624                        delta += jenrl.getJenrlWeight(firstStudent());
    625                } else {
    626                    if (JenrlConstraint.isInConflict(secondLecture().getAssignment(), lecture.getAssignment(), iModel.getDistanceMetric()))
    627                        delta += firstStudent().getJenrlWeight(secondLecture(), lecture);
    628                }
    629            }
    630            if (secondStudent() != null) {
    631                for (Lecture lecture : secondStudent().getLectures()) {
    632                    if (lecture.getAssignment() == null || lecture.equals(secondLecture()))
    633                        continue;
    634                    JenrlConstraint jenrl = firstLecture().jenrlConstraint(lecture);
    635                    if (jenrl != null) {
    636                        if (jenrl.isInConflict())
    637                            delta += jenrl.getJenrlWeight(secondStudent());
    638                    } else {
    639                        if (JenrlConstraint.isInConflict(firstLecture().getAssignment(), lecture.getAssignment(), iModel.getDistanceMetric()))
    640                            delta += secondStudent().getJenrlWeight(firstLecture(), lecture);
    641                    }
    642                }
    643            }
    644
    645            Placement p1 = firstLecture().getAssignment();
    646            Placement p2 = secondLecture().getAssignment();
    647            delta += firstStudent().countConflictPlacements(p2) - firstStudent().countConflictPlacements(p1);
    648            if (secondStudent() != null)
    649                delta += secondStudent().countConflictPlacements(p1) - secondStudent().countConflictPlacements(p2);
    650
    651            if (getChildMoves() != null) {
    652                for (Move move : getChildMoves()) {
    653                    delta += move.getDelta();
    654                }
    655            }
    656            return delta;
    657        }
    658
    659        public boolean isTabu() {
    660            return false;
    661        }
    662
    663        @Override
    664        public String toString() {
    665            return "Move{" + firstStudent() + "/" + firstLecture() + " <-> " + secondStudent() + "/" + secondLecture()
    666                    + ", d=" + getDelta() + ", ch=" + getChildMoves() + "}";
    667
    668        }
    669
    670    }
    671
    672    public MoveBetweenCfgs createMove(Configuration firstConfig, Student firstStudent, Configuration secondConfig,
    673            Student secondStudent) {
    674        MoveBetweenCfgs m = new MoveBetweenCfgs(firstConfig, firstStudent, secondConfig, secondStudent);
    675
    676        for (Long subpartId: firstConfig.getTopSubpartIds()) {
    677            if (!addLectures(firstStudent, secondStudent, m.firstLectures(), firstConfig.getTopLectures(subpartId)))
    678                return null;
    679        }
    680
    681        for (Long subpartId: secondConfig.getTopSubpartIds()) {
    682            if (!addLectures(secondStudent, firstStudent, m.secondLectures(), secondConfig.getTopLectures(subpartId)))
    683                return null;
    684        }
    685
    686        return m;
    687    }
    688
    689    private boolean addLectures(Student student, Student newStudent, Set<Lecture> studentLectures,
    690            Collection<Lecture> lectures) {
    691        Lecture lecture = null;
    692        if (lectures == null)
    693            return false;
    694
    695        if (student != null) {
    696            for (Lecture l : lectures) {
    697                if (l.students().contains(student)) {
    698                    lecture = l;
    699                    if (!student.canUnenroll(lecture)) return false;
    700                    break;
    701                }
    702            }
    703        } else {
    704            int bestValue = 0;
    705            Lecture bestLecture = null;
    706            for (Lecture l : lectures) {
    707                int val = test(newStudent, l);
    708                if (val < 0)
    709                    continue;
    710                if (bestLecture == null || bestValue > val) {
    711                    bestValue = val;
    712                    bestLecture = l;
    713                }
    714            }
    715            lecture = bestLecture;
    716        }
    717
    718        if (lecture == null)
    719            return false;
    720        if (newStudent != null && !newStudent.canEnroll(lecture))
    721            return false;
    722        studentLectures.add(lecture);
    723        if (lecture.getChildrenSubpartIds() != null) {
    724            for (Long subpartId: lecture.getChildrenSubpartIds()) {
    725                if (!addLectures(student, newStudent, studentLectures, lecture.getChildren(subpartId)))
    726                    return false;
    727            }
    728        }
    729
    730        return true;
    731    }
    732
    733    public int test(Student student, Lecture lecture) {
    734        if (lecture.getAssignment() == null)
    735            return -1;
    736        double studentWeight = student.getOfferingWeight(lecture.getConfiguration());
    737        if (lecture.nrWeightedStudents() + studentWeight > sEps + lecture.classLimit())
    738            return -1;
    739        if (!student.canEnroll(lecture))
    740            return -1;
    741
    742        int test = 0;
    743        for (Lecture x : student.getLectures()) {
    744            if (x.getAssignment() == null)
    745                continue;
    746            if (JenrlConstraint.isInConflict(lecture.getAssignment(), x.getAssignment(), iModel.getDistanceMetric()))
    747                test++;
    748        }
    749        test += student.countConflictPlacements(lecture.getAssignment());
    750
    751        if (lecture.getChildrenSubpartIds() != null) {
    752            for (Long subpartId: lecture.getChildrenSubpartIds()) {
    753                int bestTest = -1;
    754                for (Lecture child : lecture.getChildren(subpartId)) {
    755                    int t = test(student, child);
    756                    if (t < 0)
    757                        continue;
    758                    if (bestTest < 0 || bestTest > t)
    759                        bestTest = t;
    760                }
    761                if (bestTest < 0)
    762                    return -1;
    763                test += bestTest;
    764            }
    765        }
    766        return test;
    767    }
    768
    769    public class MoveBetweenCfgs {
    770        Configuration iFirstConfig = null;
    771        Set<Lecture> iFirstLectures = new HashSet<Lecture>();
    772        Student iFirstStudent = null;
    773        Configuration iSecondConfig = null;
    774        Set<Lecture> iSecondLectures = new HashSet<Lecture>();
    775        Student iSecondStudent = null;
    776
    777        public MoveBetweenCfgs(Configuration firstConfig, Student firstStudent, Configuration secondConfig,
    778                Student secondStudent) {
    779            iFirstConfig = firstConfig;
    780            iFirstStudent = firstStudent;
    781            iSecondConfig = secondConfig;
    782            iSecondStudent = secondStudent;
    783        }
    784
    785        public Configuration firstConfiguration() {
    786            return iFirstConfig;
    787        }
    788
    789        public Student firstStudent() {
    790            return iFirstStudent;
    791        }
    792
    793        public Set<Lecture> firstLectures() {
    794            return iFirstLectures;
    795        }
    796
    797        public Configuration secondConfiguration() {
    798            return iSecondConfig;
    799        }
    800
    801        public Student secondStudent() {
    802            return iSecondStudent;
    803        }
    804
    805        public Set<Lecture> secondLectures() {
    806            return iSecondLectures;
    807        }
    808
    809        public boolean perform() {
    810            double conflicts = firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue();
    811            firstStudent().removeConfiguration(firstConfiguration());
    812            firstStudent().addConfiguration(secondConfiguration());
    813            for (Lecture lecture : firstStudent().getLectures()) {
    814
    815                for (Lecture firstLecture : firstLectures()) {
    816                    if (firstLecture.equals(lecture))
    817                        continue;
    818                    if (firstLectures().contains(lecture)
    819                            && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0)
    820                        continue;
    821
    822                    JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture);
    823                    if (jenrl == null)
    824                        continue;
    825                    jenrl.decJenrl(firstStudent());
    826                    if (jenrl.getNrStudents() == 0) {
    827                        Object[] vars = jenrl.variables().toArray();
    828                        for (int k = 0; k < vars.length; k++)
    829                            jenrl.removeVariable((Lecture) vars[k]);
    830                        iModel.removeConstraint(jenrl);
    831                    }
    832                }
    833            }
    834
    835            if (secondStudent() != null) {
    836                secondStudent().removeConfiguration(secondConfiguration());
    837                secondStudent().addConfiguration(firstConfiguration());
    838                for (Lecture lecture : secondStudent().getLectures()) {
    839
    840                    for (Lecture secondLecture : secondLectures()) {
    841                        if (secondLecture.equals(lecture))
    842                            continue;
    843                        if (secondLectures().contains(lecture)
    844                                && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0)
    845                            continue;
    846
    847                        JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture);
    848                        if (jenrl == null)
    849                            continue;
    850                        jenrl.decJenrl(secondStudent());
    851                        if (jenrl.getNrStudents() == 0) {
    852                            Object[] vars = jenrl.variables().toArray();
    853                            for (int k = 0; k < vars.length; k++)
    854                                jenrl.removeVariable((Lecture) vars[k]);
    855                            iModel.removeConstraint(jenrl);
    856                        }
    857                    }
    858                }
    859            }
    860
    861            for (Lecture firstLecture : firstLectures()) {
    862                firstLecture.removeStudent(firstStudent());
    863                firstStudent().removeLecture(firstLecture);
    864                if (secondStudent() != null) {
    865                    firstLecture.addStudent(secondStudent());
    866                    secondStudent().addLecture(firstLecture);
    867                }
    868            }
    869            for (Lecture secondLecture : secondLectures()) {
    870                secondLecture.addStudent(firstStudent());
    871                firstStudent().addLecture(secondLecture);
    872                if (secondStudent() != null) {
    873                    secondLecture.removeStudent(secondStudent());
    874                    secondStudent().removeLecture(secondLecture);
    875                }
    876            }
    877
    878            for (Lecture lecture : firstStudent().getLectures()) {
    879
    880                for (Lecture secondLecture : secondLectures()) {
    881                    if (secondLecture.equals(lecture))
    882                        continue;
    883                    if (secondLectures().contains(lecture)
    884                            && secondLecture.getClassId().compareTo(lecture.getClassId()) > 0)
    885                        continue;
    886
    887                    JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture);
    888                    if (jenrl == null) {
    889                        jenrl = new JenrlConstraint();
    890                        iModel.addConstraint(jenrl);
    891                        jenrl.addVariable(secondLecture);
    892                        jenrl.addVariable(lecture);
    893                    }
    894                    jenrl.incJenrl(firstStudent());
    895                }
    896            }
    897
    898            if (secondStudent() != null) {
    899                for (Lecture lecture : secondStudent().getLectures()) {
    900
    901                    for (Lecture firstLecture : firstLectures()) {
    902                        if (firstLecture.equals(lecture))
    903                            continue;
    904                        if (firstLectures().contains(lecture)
    905                                && firstLecture.getClassId().compareTo(lecture.getClassId()) > 0)
    906                            continue;
    907
    908                        JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture);
    909                        if (jenrl == null) {
    910                            jenrl = new JenrlConstraint();
    911                            iModel.addConstraint(jenrl);
    912                            jenrl.addVariable(firstLecture);
    913                            jenrl.addVariable(lecture);
    914                        }
    915                        jenrl.incJenrl(secondStudent());
    916                    }
    917                }
    918            }
    919            return firstLectures().iterator().next().getModel().getCriterion(StudentConflict.class).getValue() < conflicts;
    920        }
    921
    922        public double getDelta() {
    923            double delta = 0;
    924
    925            for (Lecture lecture : firstStudent().getLectures()) {
    926                if (lecture.getAssignment() == null)
    927                    continue;
    928
    929                for (Lecture firstLecture : firstLectures()) {
    930                    if (firstLecture.getAssignment() == null || firstLecture.equals(lecture))
    931                        continue;
    932                    JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture);
    933                    if (jenrl == null)
    934                        continue;
    935                    if (jenrl.isInConflict())
    936                        delta -= jenrl.getJenrlWeight(firstStudent());
    937                }
    938
    939                for (Lecture secondLecture : secondLectures()) {
    940                    if (secondLecture.getAssignment() == null || secondLecture.equals(lecture))
    941                        continue;
    942                    JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture);
    943                    if (jenrl != null) {
    944                        if (jenrl.isInConflict())
    945                            delta += jenrl.getJenrlWeight(firstStudent());
    946                    } else {
    947                        if (JenrlConstraint.isInConflict(secondLecture.getAssignment(), lecture.getAssignment(), iModel.getDistanceMetric()))
    948                            delta += firstStudent().getJenrlWeight(secondLecture, lecture);
    949                    }
    950                }
    951            }
    952
    953            if (secondStudent() != null) {
    954                for (Lecture lecture : secondStudent().getLectures()) {
    955                    if (lecture.getAssignment() == null)
    956                        continue;
    957
    958                    for (Lecture secondLecture : secondLectures()) {
    959                        if (secondLecture.getAssignment() == null || secondLecture.equals(lecture))
    960                            continue;
    961                        JenrlConstraint jenrl = secondLecture.jenrlConstraint(lecture);
    962                        if (jenrl == null)
    963                            continue;
    964                        if (jenrl.isInConflict())
    965                            delta -= jenrl.getJenrlWeight(secondStudent());
    966                    }
    967
    968                    for (Lecture firstLecture : firstLectures()) {
    969                        if (firstLecture.getAssignment() == null || firstLecture.equals(lecture))
    970                            continue;
    971                        JenrlConstraint jenrl = firstLecture.jenrlConstraint(lecture);
    972                        if (jenrl != null) {
    973                            if (jenrl.isInConflict())
    974                                delta += jenrl.getJenrlWeight(secondStudent());
    975                        } else {
    976                            if (JenrlConstraint.isInConflict(firstLecture.getAssignment(), lecture.getAssignment(), iModel.getDistanceMetric()))
    977                                delta += secondStudent().getJenrlWeight(firstLecture, lecture);
    978                        }
    979                    }
    980                }
    981            }
    982
    983            for (Lecture firstLecture : firstLectures()) {
    984                Placement p1 = firstLecture.getAssignment();
    985                if (p1 == null)
    986                    continue;
    987                delta -= firstStudent().countConflictPlacements(p1);
    988                if (secondStudent() != null)
    989                    delta += secondStudent().countConflictPlacements(p1);
    990            }
    991
    992            for (Lecture secondLecture : secondLectures()) {
    993                Placement p2 = secondLecture.getAssignment();
    994                if (p2 == null)
    995                    continue;
    996                delta += firstStudent().countConflictPlacements(p2);
    997                if (secondStudent() != null)
    998                    delta -= secondStudent().countConflictPlacements(p2);
    999            }
    1000
    1001            return delta;
    1002        }
    1003
    1004        public boolean isTabu() {
    1005            return false;
    1006        }
    1007
    1008        @Override
    1009        public String toString() {
    1010            return "Move{" + firstStudent() + "/" + firstConfiguration().getConfigId() + " <-> " + secondStudent()
    1011                    + "/" + secondConfiguration().getConfigId() + ", d=" + getDelta() + "}";
    1012        }
    1013
    1014    }
    1015}