001    package net.sf.cpsolver.coursett.criteria;
002    
003    import java.util.Collection;
004    import java.util.HashSet;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.coursett.Constants;
008    import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
009    import net.sf.cpsolver.coursett.model.Lecture;
010    import net.sf.cpsolver.coursett.model.Placement;
011    import net.sf.cpsolver.coursett.model.Student;
012    import net.sf.cpsolver.coursett.model.TimeLocation;
013    import net.sf.cpsolver.coursett.model.TimetableModel;
014    import net.sf.cpsolver.ifs.solver.Solver;
015    import net.sf.cpsolver.ifs.util.DistanceMetric;
016    
017    /**
018     * Student conflicts. This criterion counts student conflicts between classes. A conflict
019     * occurs when two classes that are attended by the same student (or students) are overlapping
020     * in time or place back-to-back in rooms that are too far a part. The combinations of classes
021     * that share students are maintained by {@link JenrlConstraint}.  
022     * <br>
023     * 
024     * @version CourseTT 1.2 (University Course Timetabling)<br>
025     *          Copyright (C) 2006 - 2011 Tomas Muller<br>
026     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028     * <br>
029     *          This library is free software; you can redistribute it and/or modify
030     *          it under the terms of the GNU Lesser General Public License as
031     *          published by the Free Software Foundation; either version 3 of the
032     *          License, or (at your option) any later version. <br>
033     * <br>
034     *          This library is distributed in the hope that it will be useful, but
035     *          WITHOUT ANY WARRANTY; without even the implied warranty of
036     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037     *          Lesser General Public License for more details. <br>
038     * <br>
039     *          You should have received a copy of the GNU Lesser General Public
040     *          License along with this library; if not see
041     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042     */
043    public class StudentConflict extends TimetablingCriterion {
044        protected boolean iIncludeConflicts = false;
045        
046        public StudentConflict() {
047            iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned;
048        }
049        
050        @Override
051        public boolean init(Solver<Lecture, Placement> solver) {
052            iIncludeConflicts = solver.getProperties().getPropertyBoolean("StudentConflict.IncludeConflicts", false);
053            return super.init(solver);
054        }
055        
056        @Override
057        public String getPlacementSelectionWeightName() {
058            return null;
059        }
060    
061        @Override
062        public double getValue() {
063            return super.getValue();
064        }
065        
066        public DistanceMetric getMetrics() {
067            return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
068        }
069    
070        public static boolean overlaps(Placement p1, Placement p2) {
071            return p1 != null && p2 != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()) && (!p1.variable().isCommitted() || !p2.variable().isCommitted());
072        }
073        
074        protected double jointEnrollment(JenrlConstraint jenrl) {
075            return jenrl.jenrl();
076        }
077        
078        public static boolean distance(DistanceMetric m, Placement p1, Placement p2) {
079            if (m == null && p1 != null) m = ((TimetableModel)p1.variable().getModel()).getDistanceMetric();
080            if (m == null && p2 != null) m = ((TimetableModel)p2.variable().getModel()).getDistanceMetric();
081            if (p1 == null || p2 == null || m == null) return false;
082            if (p1.variable().isCommitted() && p2.variable().isCommitted()) return false;
083            TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
084            if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
085            if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
086                if (t1.getStartSlot() + t1.getLength() <= t2.getStartSlot()) {
087                    return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength());
088                } else if (t2.getStartSlot() + t2.getLength() <= t1.getStartSlot()) {
089                    return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength());
090                }
091            } else {
092                if (t1.getStartSlot() + t1.getLength() == t2.getStartSlot()) {
093                    return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime();
094                } else if (t2.getStartSlot() + t2.getLength() == t1.getStartSlot()) {
095                    return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime();
096                }
097            }
098            return false;
099        }
100        
101        public static boolean ignore(Placement p1, Placement p2) {
102            return p1 != null && p2 != null && p1.variable().isToIgnoreStudentConflictsWith(p2.variable());
103        }
104        
105        public static boolean ignore(Lecture l1, Lecture l2) {
106            return l1 != null && l2 != null && l1.isToIgnoreStudentConflictsWith(l2);
107        }
108        
109        public static boolean committed(Placement p1, Placement p2) {
110            return p1 != null && p2 != null && committed(p1.variable(), p2.variable());
111        }
112        
113        public static boolean committed(Lecture l1, Lecture l2) {
114            return l1 != null && l2 != null && (l1.isCommitted() || l2.isCommitted()) && (!l1.isCommitted() || !l2.isCommitted());
115        }
116        
117        public static boolean applicable(Placement p1, Placement p2) {
118            return p1 != null && p2 != null && applicable(p1.variable(), p2.variable());
119        }
120        
121        public static boolean applicable(Lecture l1, Lecture l2) {
122            return l1 != null && l2 != null && (!l1.isCommitted() || !l2.isCommitted());
123        }
124    
125        public static boolean hard(Placement p1, Placement p2) {
126            return p1 != null && p2 != null && hard(p1.variable(), p2.variable());
127        }
128        
129        public static boolean hard(Lecture l1, Lecture l2) {
130            return l1 != null && l2 != null && l1.isSingleSection() && l2.isSingleSection() && (!l1.isCommitted() || !l2.isCommitted());
131        }
132        
133        public boolean isApplicable(Lecture l1, Lecture l2) {
134            return !ignore(l1, l2) && applicable(l1, l2) && !committed(l1, l2); // exclude committed and outside student conflicts
135        }
136    
137        public boolean inConflict(Placement p1, Placement p2) {
138            return !ignore(p1, p2) && (overlaps(p1, p2) || distance(getMetrics(), p1, p2)) && isApplicable(p1.variable(), p2.variable());
139        }
140        
141        @Override
142        public double getValue(Placement value, Set<Placement> conflicts) {
143            double ret = 0.0;
144            for (JenrlConstraint jenrl: value.variable().jenrlConstraints()) {
145                Placement another = jenrl.another(value.variable()).getAssignment();
146                if (another == null) continue;
147                if (conflicts != null && conflicts.contains(another)) continue;
148                if (inConflict(value, another))
149                    ret += jointEnrollment(jenrl);
150            }
151            if (iIncludeConflicts && conflicts != null)
152                for (Placement conflict: conflicts) {
153                    for (JenrlConstraint jenrl: conflict.variable().jenrlConstraints()) {
154                        Placement another = jenrl.another(conflict.variable()).getAssignment();
155                        if (another == null || another.variable().equals(value.variable())) continue;
156                        if (conflicts != null && conflicts.contains(another)) continue;
157                        if (inConflict(conflict, another))
158                            ret -= jointEnrollment(jenrl);
159                    }
160                }
161            return ret;
162        }
163        
164        @Override
165        public double getValue(Collection<Lecture> variables) {
166            double ret = 0.0;
167            Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
168            for (Lecture lect: variables) {
169                if (lect.getAssignment() == null) continue;
170                for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
171                    if (!constraints.add(jenrl)) continue;
172                    if (!jenrl.another(lect).isCommitted() && !variables.contains(jenrl.another(lect))) continue;
173                    if (inConflict(lect.getAssignment(), jenrl.another(lect).getAssignment()))
174                        ret += jointEnrollment(jenrl);
175                }
176            }
177            return ret;
178        }
179    
180        @Override
181        public double[] getBounds() {
182            double[] bounds = { 0.0, 0.0 };
183            for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints())
184                if (isApplicable(jenrl.first(), jenrl.second()))
185                    bounds[0] += jointEnrollment(jenrl);
186            return bounds;
187        }
188        
189        @Override
190        public double[] getBounds(Collection<Lecture> variables) {
191            double[] bounds = { 0.0, 0.0 };
192            Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
193            for (Lecture lect: variables) {
194                if (lect.getAssignment() == null) continue;
195                for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
196                    if (isApplicable(jenrl.first(), jenrl.second()) && constraints.add(jenrl) && (jenrl.another(lect).isCommitted() || variables.contains(jenrl.another(lect))))
197                        bounds[0] += jointEnrollment(jenrl);
198                }
199            }
200            return bounds;
201        }
202        
203        public void incJenrl(JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) {
204            if (inConflict(jenrl.first().getAssignment(), jenrl.second().getAssignment()))
205                iValue += studentWeight;
206        }
207        
208        @Override
209        public void bestRestored() {
210            super.bestRestored();
211            iValue = getValue(getModel().variables());
212        }
213    }