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