001package org.cpsolver.studentsct.extension;
002
003import java.util.HashSet;
004import java.util.Set;
005
006import org.apache.log4j.Logger;
007import org.cpsolver.ifs.assignment.Assignment;
008import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
009import org.cpsolver.ifs.assignment.context.ExtensionWithContext;
010import org.cpsolver.ifs.solver.Solver;
011import org.cpsolver.ifs.util.DataProperties;
012import org.cpsolver.studentsct.StudentSectioningModel;
013import org.cpsolver.studentsct.StudentSectioningModel.StudentSectioningModelContext;
014import org.cpsolver.studentsct.model.Enrollment;
015import org.cpsolver.studentsct.model.FreeTimeRequest;
016import org.cpsolver.studentsct.model.Request;
017import org.cpsolver.studentsct.model.SctAssignment;
018import org.cpsolver.studentsct.model.Section;
019import org.cpsolver.studentsct.model.Student;
020
021
022/**
023 * This extension computes time overlaps. Only sections that allow overlaps
024 * (see {@link SctAssignment#isAllowOverlap()}) can overlap. This class counts
025 * how many overlapping slots there are so that this number can be minimized.
026 * 
027 * <br>
028 * <br>
029 * 
030 * @version StudentSct 1.3 (Student Sectioning)<br>
031 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
032 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
033 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
034 * <br>
035 *          This library is free software; you can redistribute it and/or modify
036 *          it under the terms of the GNU Lesser General Public License as
037 *          published by the Free Software Foundation; either version 3 of the
038 *          License, or (at your option) any later version. <br>
039 * <br>
040 *          This library is distributed in the hope that it will be useful, but
041 *          WITHOUT ANY WARRANTY; without even the implied warranty of
042 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
043 *          Lesser General Public License for more details. <br>
044 * <br>
045 *          You should have received a copy of the GNU Lesser General Public
046 *          License along with this library; if not see
047 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
048 */
049
050public class TimeOverlapsCounter extends ExtensionWithContext<Request, Enrollment, TimeOverlapsCounter.TimeOverlapsCounterContext> {
051    private static Logger sLog = Logger.getLogger(TimeOverlapsCounter.class);
052    /** Debug flag */
053    public static boolean sDebug = false;
054
055    /**
056     * Constructor. Beside of other things, this constructor also uses
057     * {@link StudentSectioningModel#setTimeOverlaps(TimeOverlapsCounter)} to
058     * set the this instance to the model.
059     * 
060     * @param solver
061     *            constraint solver
062     * @param properties
063     *            configuration
064     */
065    public TimeOverlapsCounter(Solver<Request, Enrollment> solver, DataProperties properties) {
066        super(solver, properties);
067        if (solver != null)
068            ((StudentSectioningModel) solver.currentSolution().getModel()).setTimeOverlaps(this);
069    }
070
071    @Override
072    public String toString() {
073        return "TimeOverlaps";
074    }
075
076    /**
077     * Return true if the given two assignments are overlapping.
078     * 
079     * @param a1
080     *            an assignment
081     * @param a2
082     *            an assignment
083     * @return true, if the given sections are in an overlapping conflict
084     */
085    public boolean inConflict(SctAssignment a1, SctAssignment a2) {
086        if (a1.getTime() == null || a2.getTime() == null) return false;
087        if (a1 instanceof Section && a2 instanceof Section && ((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false;
088        return a1.getTime().hasIntersection(a2.getTime());
089    }
090    
091    /**
092     * If the two sections are overlapping, return the number of slots of the overlap.
093     * 
094     * @param a1
095     *            an assignment
096     * @param a2
097     *            an assignment
098     * @return the number of overlapping slots against the number of slots of the smallest section
099     */
100    public int share(SctAssignment a1, SctAssignment a2) {
101        if (!inConflict(a1, a2)) return 0;
102        return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
103    }
104
105
106    /**
107     * Return number of time overlapping conflicts that are between two enrollments. It
108     * is the total share between pairs of assignments of these enrollments that are in a
109     * time overlap.
110     * 
111     * @param e1
112     *            an enrollment
113     * @param e2
114     *            an enrollment
115     * @return number of time overlapping conflict between given enrollments
116     */
117    public int nrConflicts(Enrollment e1, Enrollment e2) {
118        if (!e1.getStudent().equals(e2.getStudent())) return 0;
119        if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return 0;
120        int cnt = 0;
121        for (SctAssignment s1 : e1.getAssignments()) {
122            for (SctAssignment s2 : e2.getAssignments()) {
123                if (inConflict(s1, s2))
124                    cnt += share(s1, s2);
125            }
126        }
127        return cnt;
128    }
129
130    /**
131     * Return a set of time overlapping conflicts ({@link Conflict} objects) between
132     * given (course) enrollments.
133     * 
134     * @param e1
135     *            an enrollment
136     * @param e2
137     *            an enrollment
138     * @return list of time overlapping conflicts that are between assignment of the
139     *         given enrollments
140     */
141    public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
142        Set<Conflict> ret = new HashSet<Conflict>();
143        if (!e1.getStudent().equals(e2.getStudent())) return ret;
144        if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return ret;
145        for (SctAssignment s1 : e1.getAssignments()) {
146            for (SctAssignment s2 : e2.getAssignments()) {
147                if (inConflict(s1, s2))
148                    ret.add(new Conflict(e1.getStudent(), share(s1, s2), e1, s1, e2, s2));
149            }
150        }
151        return ret;
152    }
153
154    /**
155     * Total sum of all free time conflict of the given enrollment.
156     * @param enrollment given enrollment
157     * @return number of all free time conflicts of the given enrollment
158     */
159    public int nrFreeTimeConflicts(Enrollment enrollment) {
160        if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
161        int cnt = 0;
162        for (Request request : enrollment.getStudent().getRequests()) {
163            if (request instanceof FreeTimeRequest) {
164                FreeTimeRequest ft = (FreeTimeRequest)request;
165                for (SctAssignment section: enrollment.getAssignments())
166                    cnt += share(section, ft);
167            }
168        }
169        return cnt;
170    }
171    
172    /**
173     * Return a set of free time conflict of the given enrollment.
174     * @param enrollment given enrollment
175     * @return set of all free time conflicts of the given enrollment
176     */
177    public Set<Conflict> freeTimeConflicts(Enrollment enrollment) {
178        Set<Conflict> ret = new HashSet<Conflict>();
179        if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
180        for (Request request : enrollment.getStudent().getRequests()) {
181            if (request instanceof FreeTimeRequest) {
182                FreeTimeRequest ft = (FreeTimeRequest)request;
183                for (SctAssignment section: enrollment.getAssignments()) {
184                    if (inConflict(section, ft))
185                        ret.add(new Conflict(enrollment.getStudent(), share(section, ft), enrollment, section, ft.createEnrollment(), ft));
186                }
187            }
188        }
189        return ret;
190    }
191
192    /** Actual number of all time overlapping conflicts 
193     * @param assignment current assignment
194     * @return total number of time overlapping conflicts
195     **/
196    public int getTotalNrConflicts(Assignment<Request, Enrollment> assignment) {
197        return getContext(assignment).getTotalNrConflicts();
198    }
199    
200    public void checkTotalNrConflicts(Assignment<Request, Enrollment> assignment) {
201        getContext(assignment).checkTotalNrConflicts(assignment);
202    }
203
204    /**
205     * Return a set of all time overlapping conflicts ({@link Conflict} objects).
206     * @param assignment current assignment
207     * @return set of all time overlapping conflicts in the assignment
208     */
209    public Set<Conflict> getAllConflicts(Assignment<Request, Enrollment> assignment) {
210        return getContext(assignment).getAllConflicts();
211    }
212
213    /**
214     * Called before a value is assigned to a variable.
215     */
216    @Override
217    public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
218        getContext(assignment).beforeAssigned(assignment, iteration, value);
219    }
220
221    /**
222     * Called after a value is assigned to a variable.
223     */
224    @Override
225    public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
226        getContext(assignment).afterAssigned(assignment, iteration, value);
227    }
228
229    /**
230     * Called after a value is unassigned from a variable.
231     */
232    @Override
233    public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
234        getContext(assignment).afterUnassigned(assignment, iteration, value);
235    }
236
237    /** A representation of a time overlapping conflict */
238    public static class Conflict {
239        private int iShare;
240        private Student iStudent;
241        private SctAssignment iA1, iA2;
242        private Enrollment iE1, iE2;
243        private int iHashCode;
244
245        /**
246         * Constructor
247         * 
248         * @param student
249         *            related student
250         * @param share number of slots in common between the two conflicting sections
251         * @param e1 first enrollment
252         * @param a1
253         *            first conflicting section
254         * @param e2 second enrollment
255         * @param a2
256         *            second conflicting section
257         */
258        public Conflict(Student student, int share, Enrollment e1, SctAssignment a1, Enrollment e2, SctAssignment a2) {
259            iStudent = student;
260            if (a1.compareById(a2) < 0 ) {
261                iA1 = a1;
262                iA2 = a2;
263                iE1 = e1;
264                iE2 = e2;
265            } else {
266                iA1 = a2;
267                iA2 = a1;
268                iE1 = e2;
269                iE2 = e1;
270            }
271            iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode();
272            iShare = share;
273        }
274
275        /** Related student
276         * @return student
277         **/
278        public Student getStudent() {
279            return iStudent;
280        }
281
282        /** First section
283         * @return first section
284         **/
285        public SctAssignment getS1() {
286            return iA1;
287        }
288
289        /** Second section
290         * @return second section
291         **/
292        public SctAssignment getS2() {
293            return iA2;
294        }
295
296        /** First request
297         * @return first request
298         **/
299        public Request getR1() {
300            return iE1.getRequest();
301        }
302        
303        /** Second request
304         * @return second request
305         **/
306        public Request getR2() {
307            return iE2.getRequest();
308        }
309        
310        /** First enrollment
311         * @return first enrollment
312         **/
313        public Enrollment getE1() {
314            return iE1;
315        }
316
317        /** Second enrollment
318         * @return second enrollment
319         **/
320        public Enrollment getE2() {
321            return iE2;
322        }
323        
324        @Override
325        public int hashCode() {
326            return iHashCode;
327        }
328
329        /** The number of overlapping slots against the number of slots of the smallest section
330         * @return number of overlapping slots between the two sections 
331         **/
332        public int getShare() {
333            return iShare;
334        }
335
336        @Override
337        public boolean equals(Object o) {
338            if (o == null || !(o instanceof Conflict)) return false;
339            Conflict c = (Conflict) o;
340            return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
341        }
342
343        @Override
344        public String toString() {
345            return getStudent() + ": (s:" + getShare() + ") " + getS1() + " -- " + getS2();
346        }
347    }
348    
349    /**
350     * The set of all conflicts ({@link Conflict} objects) of the given
351     * enrollment and other enrollments that are assigned to the same student.
352     * @param assignment current assignment
353     * @param enrollment given enrollment
354     * @return all conflicts of the given enrollment
355     */
356    public Set<Conflict> allConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
357        Set<Conflict> ret = new HashSet<Conflict>();
358        if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
359        for (Request request : enrollment.getStudent().getRequests()) {
360            if (request.equals(enrollment.getRequest())) continue;
361            Enrollment other = assignment.getValue(request);
362            if (request instanceof FreeTimeRequest) {
363                FreeTimeRequest ft = (FreeTimeRequest)request;
364                ret.addAll(conflicts(enrollment, ft.createEnrollment()));
365                continue;
366            } else if (other != null) {
367                ret.addAll(conflicts(enrollment, other));
368            }
369        }
370        return ret;
371    }
372    
373    public class TimeOverlapsCounterContext implements AssignmentConstraintContext<Request, Enrollment> {
374        private int iTotalNrConflicts = 0;
375        private Set<Conflict> iAllConflicts = new HashSet<Conflict>();
376        private Request iOldVariable = null;
377        private Enrollment iUnassignedValue = null;
378
379        public TimeOverlapsCounterContext(Assignment<Request, Enrollment> assignment) {
380            iTotalNrConflicts = countTotalNrConflicts(assignment);
381            if (sDebug)
382                iAllConflicts = computeAllConflicts(assignment);
383            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
384            for (Conflict c: computeAllConflicts(assignment))
385                cx.add(assignment, c);
386        }
387
388        /**
389         * Called when a value is assigned to a variable. Internal number of
390         * time overlapping conflicts is updated, see
391         * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}.
392         */
393        @Override
394        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment value) {
395            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
396            for (Conflict c: allConflicts(assignment, value)) {
397                iTotalNrConflicts += c.getShare();
398                cx.add(assignment, c);
399            }
400            if (sDebug) {
401                sLog.debug("A:" + value.variable() + " := " + value);
402                int inc = nrAllConflicts(assignment, value);
403                if (inc != 0) {
404                    sLog.debug("-- TOC+" + inc + " A: " + value.variable() + " := " + value);
405                    for (Conflict c: allConflicts(assignment, value)) {
406                        sLog.debug("  -- " + c);
407                        iAllConflicts.add(c);
408                        inc -= c.getShare();
409                    }
410                    if (inc != 0) {
411                        sLog.error("Different number of conflicts for the assigned value (difference: " + inc + ")!");
412                    }
413                }
414            }
415        }
416
417        /**
418         * Called when a value is unassigned from a variable. Internal number of
419         * time overlapping conflicts is updated, see
420         * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}.
421         */
422        @Override
423        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment value) {
424            StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment);
425            for (Conflict c: allConflicts(assignment, value)) {
426                iTotalNrConflicts -= c.getShare();
427                cx.remove(assignment, c);
428            }
429            if (sDebug) {
430                sLog.debug("U:" + value.variable() + " := " + value);
431                int dec = nrAllConflicts(assignment, value);
432                if (dec != 0) {
433                    sLog.debug("-- TOC-" + dec + " U: " + value.variable() + " := " + value);
434                    for (Conflict c: allConflicts(assignment, value)) {
435                        sLog.debug("  -- " + c);
436                        iAllConflicts.remove(c);
437                        dec -= c.getShare();
438                    }
439                    if (dec != 0) {
440                        sLog.error("Different number of conflicts for the unassigned value (difference: " + dec + ")!");
441                    }
442                }
443            }
444        }
445        
446        /**
447         * Called before a value is assigned to a variable.
448         * @param assignment current assignment
449         * @param iteration current iteration
450         * @param value value to be assigned
451         */
452        public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
453            if (value != null) {
454                Enrollment old = assignment.getValue(value.variable());
455                if (old != null) {
456                    iUnassignedValue = old;
457                    unassigned(assignment, old);
458                }
459                iOldVariable = value.variable();
460            }
461        }
462
463        /**
464         * Called after a value is assigned to a variable.
465         * @param assignment current assignment
466         * @param iteration current iteration
467         * @param value value that was assigned
468         */
469        public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
470            iOldVariable = null;
471            iUnassignedValue = null;
472            if (value != null) {
473                assigned(assignment, value);
474            }
475        }
476
477        /**
478         * Called after a value is unassigned from a variable.
479         * @param assignment current assignment
480         * @param iteration current iteration
481         * @param value value that was unassigned
482         */
483        public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) {
484            if (value != null && !value.equals(iUnassignedValue)) {
485                unassigned(assignment, value);
486            }
487        }
488        
489        /**
490         * Return a set of all time overlapping conflicts ({@link Conflict} objects).
491         * @return all conflicts
492         */
493        public Set<Conflict> getAllConflicts() {
494            return iAllConflicts;
495        }
496        
497        /** Actual number of all time overlapping conflicts
498         * @return total number of all conflicts
499         **/
500        public int getTotalNrConflicts() {
501            return iTotalNrConflicts;
502        }
503        
504        public void checkTotalNrConflicts(Assignment<Request, Enrollment> assignment) {
505            int total = countTotalNrConflicts(assignment);
506            if (total != iTotalNrConflicts) {
507                sLog.error("Number of conflicts does not match (actual: " + total + ", count: " + iTotalNrConflicts + ")!");
508                iTotalNrConflicts = total;
509                if (sDebug) {
510                    Set<Conflict> conflicts = computeAllConflicts(assignment);
511                    for (Conflict c: conflicts) {
512                        if (!iAllConflicts.contains(c))
513                            sLog.debug("  +add+ " + c);
514                    }
515                    for (Conflict c: iAllConflicts) {
516                        if (!conflicts.contains(c))
517                            sLog.debug("  -rem- " + c);
518                    }
519                    for (Conflict c: conflicts) {
520                        for (Conflict d: iAllConflicts) {
521                            if (c.equals(d) && c.getShare() != d.getShare()) {
522                                sLog.debug("  -dif- " + c + " (other: " + d.getShare() + ")");
523                            }
524                        }
525                    }                
526                    iAllConflicts = conflicts;
527                    // getSolver().stopSolver(false);
528                }
529            }
530        }
531        
532        /**
533         * Compute the actual number of all time overlapping conflicts. Should be equal to
534         * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}.
535         * @param assignment current assignment
536         * @return counted number of all time conflicts in the assignment
537         */
538        public int countTotalNrConflicts(Assignment<Request, Enrollment> assignment) {
539            int total = 0;
540            for (Request r1 : getModel().variables()) {
541                Enrollment e1 = assignment.getValue(r1);
542                if (e1 == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
543                    continue;
544                for (Request r2 : r1.getStudent().getRequests()) {
545                    Enrollment e2 = assignment.getValue(r2);
546                    if (r2 instanceof FreeTimeRequest) {
547                        FreeTimeRequest ft = (FreeTimeRequest)r2;
548                        total += nrConflicts(e1, ft.createEnrollment());
549                    } else if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
550                        total += nrConflicts(e1, e2);
551                    }
552                }
553            }
554            return total;
555        }
556
557        /**
558         * Compute a set of all time overlapping conflicts ({@link Conflict} objects).
559         * @param assignment current assignment
560         * @return set of all time conflicts in the assignment
561         */
562        public Set<Conflict> computeAllConflicts(Assignment<Request, Enrollment> assignment) {
563            Set<Conflict> ret = new HashSet<Conflict>();
564            for (Request r1 : getModel().variables()) {
565                Enrollment e1 = assignment.getValue(r1);
566                if (e1 == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
567                    continue;
568                for (Request r2 : r1.getStudent().getRequests()) {
569                    Enrollment e2 = assignment.getValue(r2);
570                    if (r2 instanceof FreeTimeRequest) {
571                        FreeTimeRequest ft = (FreeTimeRequest)r2;
572                        ret.addAll(conflicts(e1, ft.createEnrollment()));
573                    } else if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
574                        ret.addAll(conflicts(e1, e2));
575                    }                    
576                }
577            }
578            return ret;
579        }
580
581        /**
582         * The set of all conflicts ({@link Conflict} objects) of the given
583         * enrollment and other enrollments that are assigned to the same student.
584         * @param assignment current assignment
585         * @param enrollment given enrollment
586         * @return set of all conflict of the given enrollment
587         */
588        public Set<Conflict> allConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
589            Set<Conflict> ret = new HashSet<Conflict>();
590            if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
591            for (Request request : enrollment.getStudent().getRequests()) {
592                if (request.equals(enrollment.getRequest())) continue;
593                if (request instanceof FreeTimeRequest) {
594                    FreeTimeRequest ft = (FreeTimeRequest)request;
595                    ret.addAll(conflicts(enrollment, ft.createEnrollment()));
596                    continue;
597                } else if (assignment.getValue(request) != null && !request.equals(iOldVariable)) {
598                    ret.addAll(conflicts(enrollment, assignment.getValue(request)));
599                }
600            }
601            return ret;
602        }
603        
604        /**
605         * Total sum of all conflict of the given enrollment and other enrollments
606         * that are assigned to the same student.
607         * @param assignment current assignment
608         * @param enrollment given enrollment
609         * @return number of all conflict of the given enrollment
610         */
611        public int nrAllConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
612            if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
613            int cnt = 0;
614            for (Request request : enrollment.getStudent().getRequests()) {
615                if (request.equals(enrollment.getRequest())) continue;
616                if (request instanceof FreeTimeRequest) {
617                    FreeTimeRequest ft = (FreeTimeRequest)request;
618                    cnt += nrConflicts(enrollment, ft.createEnrollment());
619                } else if (assignment.getValue(request) != null && !request.equals(iOldVariable)) {
620                    cnt += nrConflicts(enrollment, assignment.getValue(request));
621                }
622            }
623            return cnt;
624        }
625    }
626
627    @Override
628    public TimeOverlapsCounterContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
629        return new TimeOverlapsCounterContext(assignment);
630    }
631}