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