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