001    package net.sf.cpsolver.coursett.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashSet;
006    import java.util.List;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
010    import net.sf.cpsolver.coursett.criteria.StudentConflict;
011    import net.sf.cpsolver.ifs.util.Progress;
012    import 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 Tomas Muller<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    
062    public 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    }