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