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