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