001package org.cpsolver.studentsct.extension; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collection; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.Iterator; 009import java.util.List; 010import java.util.Map; 011import java.util.Set; 012import java.util.concurrent.locks.ReentrantReadWriteLock; 013import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock; 014import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock; 015 016import org.apache.logging.log4j.Logger; 017import org.cpsolver.coursett.Constants; 018import org.cpsolver.coursett.model.Placement; 019import org.cpsolver.coursett.model.RoomLocation; 020import org.cpsolver.coursett.model.TimeLocation; 021import org.cpsolver.ifs.assignment.Assignment; 022import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 023import org.cpsolver.ifs.assignment.context.CanInheritContext; 024import org.cpsolver.ifs.assignment.context.ExtensionWithContext; 025import org.cpsolver.ifs.model.InfoProvider; 026import org.cpsolver.ifs.model.ModelListener; 027import org.cpsolver.ifs.solver.Solver; 028import org.cpsolver.ifs.util.DataProperties; 029import org.cpsolver.ifs.util.DistanceMetric; 030import org.cpsolver.studentsct.StudentSectioningModel; 031import org.cpsolver.studentsct.StudentSectioningModel.StudentSectioningModelContext; 032import org.cpsolver.studentsct.model.CourseRequest; 033import org.cpsolver.studentsct.model.Enrollment; 034import org.cpsolver.studentsct.model.FreeTimeRequest; 035import org.cpsolver.studentsct.model.Request; 036import org.cpsolver.studentsct.model.SctAssignment; 037import org.cpsolver.studentsct.model.Section; 038import org.cpsolver.studentsct.model.Student; 039import org.cpsolver.studentsct.model.Student.BackToBackPreference; 040import org.cpsolver.studentsct.model.Student.ModalityPreference; 041 042import org.cpsolver.studentsct.model.Unavailability; 043 044/** 045 * This extension computes student schedule quality using various matrices. 046 * It replaces {@link TimeOverlapsCounter} and {@link DistanceConflict} extensions. 047 * Besides of time and distance conflicts, it also counts cases when a student 048 * has a lunch break conflict, travel time during the day, it can prefer 049 * or discourage student class back-to-back and cases when a student has more than 050 * a given number of hours between the first and the last class on a day. 051 * See {@link StudentQuality.Type} for more details. 052 * 053 * <br> 054 * <br> 055 * 056 * @version StudentSct 1.3 (Student Sectioning)<br> 057 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 058 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 059 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 060 * <br> 061 * This library is free software; you can redistribute it and/or modify 062 * it under the terms of the GNU Lesser General Public License as 063 * published by the Free Software Foundation; either version 3 of the 064 * License, or (at your option) any later version. <br> 065 * <br> 066 * This library is distributed in the hope that it will be useful, but 067 * WITHOUT ANY WARRANTY; without even the implied warranty of 068 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 069 * Lesser General Public License for more details. <br> 070 * <br> 071 * You should have received a copy of the GNU Lesser General Public 072 * License along with this library; if not see 073 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 074 */ 075 076public class StudentQuality extends ExtensionWithContext<Request, Enrollment, StudentQuality.StudentQualityContext> implements ModelListener<Request, Enrollment>, CanInheritContext<Request, Enrollment, StudentQuality.StudentQualityContext>, InfoProvider<Request, Enrollment> { 077 private static Logger sLog = org.apache.logging.log4j.LogManager.getLogger(StudentQuality.class); 078 private Context iContext; 079 080 /** 081 * Constructor 082 * @param solver student scheduling solver 083 * @param properties solver configuration 084 */ 085 public StudentQuality(Solver<Request, Enrollment> solver, DataProperties properties) { 086 super(solver, properties); 087 if (solver != null) { 088 StudentSectioningModel model = (StudentSectioningModel) solver.currentSolution().getModel(); 089 iContext = new Context(model.getDistanceMetric(), properties); 090 model.setStudentQuality(this, false); 091 } else { 092 iContext = new Context(null, properties); 093 } 094 } 095 096 /** 097 * Constructor 098 * @param metrics distance metric 099 * @param properties solver configuration 100 */ 101 public StudentQuality(DistanceMetric metrics, DataProperties properties) { 102 super(null, properties); 103 iContext = new Context(metrics, properties); 104 } 105 106 /** 107 * Current distance metric 108 * @return distance metric 109 */ 110 public DistanceMetric getDistanceMetric() { 111 return iContext.getDistanceMetric(); 112 } 113 114 /** 115 * Is debugging enabled 116 * @return true when StudentQuality.Debug is true 117 */ 118 public boolean isDebug() { 119 return iContext.isDebug(); 120 } 121 122 /** 123 * Student quality context 124 */ 125 public Context getStudentQualityContext() { 126 return iContext; 127 } 128 129 /** 130 * Weighting types 131 */ 132 public static enum WeightType { 133 /** Penalty is incurred on the request with higher priority */ 134 HIGHER, 135 /** Penalty is incurred on the request with lower priority */ 136 LOWER, 137 /** Penalty is incurred on both requests */ 138 BOTH, 139 /** Penalty is incurred on the course request (for conflicts between course request and a free time) */ 140 REQUEST, 141 ; 142 } 143 144 /** 145 * Measured student qualities 146 * 147 */ 148 public static enum Type { 149 /** 150 * Time conflicts between two classes that is allowed. Time conflicts are penalized as shared time 151 * between two course requests proportional to the time of each, capped at one half of the time. 152 * This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 153 */ 154 CourseTimeOverlap(WeightType.BOTH, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 155 @Override 156 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 157 return r1 instanceof CourseRequest && r2 instanceof CourseRequest; 158 } 159 160 @Override 161 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 162 if (a1.getTime() == null || a2.getTime() == null) return false; 163 if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false; 164 return a1.getTime().hasIntersection(a2.getTime()); 165 } 166 167 @Override 168 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 169 if (!inConflict(cx, a1, a2)) return 0; 170 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 171 } 172 173 @Override 174 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 175 return new Nothing(); 176 } 177 178 @Override 179 public double getWeight(Context cx, Conflict c, Enrollment e) { 180 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / e.getNrSlots(), cx.getTimeOverlapMaxLimit()); 181 } 182 }), 183 /** 184 * Time conflict between class and a free time request. Free time conflicts are penalized as the time 185 * of a course request overlapping with a free time proportional to the time of the request, capped at one half 186 * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 187 */ 188 FreeTimeOverlap(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 189 @Override 190 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 191 return false; 192 } 193 194 @Override 195 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 196 if (a1.getTime() == null || a2.getTime() == null) return false; 197 return a1.getTime().hasIntersection(a2.getTime()); 198 } 199 200 @Override 201 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 202 if (!inConflict(cx, a1, a2)) return 0; 203 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 204 } 205 206 @Override 207 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 208 return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing()); 209 } 210 211 @Override 212 public double getWeight(Context cx, Conflict c, Enrollment e) { 213 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 214 } 215 }), 216 /** 217 * Student unavailability conflict. Time conflict between a class that the student is taking and a class that the student 218 * is teaching (if time conflicts are allowed). Unavailability conflicts are penalized as the time 219 * of a course request overlapping with an unavailability proportional to the time of the request, capped at one half 220 * of the time. This criterion is weighted by StudentWeights.TimeOverlapFactor, defaulting to 0.5. 221 */ 222 Unavailability(WeightType.REQUEST, "StudentWeights.TimeOverlapFactor", 0.5000, new Quality(){ 223 @Override 224 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 225 return false; 226 } 227 228 @Override 229 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 230 if (a1.getTime() == null || a2.getTime() == null) return false; 231 return a1.getTime().hasIntersection(a2.getTime()); 232 } 233 234 @Override 235 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 236 if (!inConflict(cx, a1, a2)) return 0; 237 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 238 } 239 240 @Override 241 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 242 return (e.isCourseRequest() ? new Unavailabilities(e.getStudent()) : new Nothing()); 243 } 244 245 @Override 246 public double getWeight(Context cx, Conflict c, Enrollment e) { 247 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 248 } 249 }), 250 /** 251 * Distance conflict. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false, 252 * distance conflicts are only considered between back-to-back classes (break time of the first 253 * class is shorter than the distance in minutes between the two classes). When 254 * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the 255 * two classes is also considered. 256 * This criterion is weighted by StudentWeights.DistanceConflict, defaulting to 0.01. 257 */ 258 Distance(WeightType.LOWER, "StudentWeights.DistanceConflict", 0.0100, new Quality(){ 259 @Override 260 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 261 return r1 instanceof CourseRequest && r2 instanceof CourseRequest; 262 } 263 264 @Override 265 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 266 Section s1 = (Section) sa1; 267 Section s2 = (Section) sa2; 268 if (s1.getPlacement() == null || s2.getPlacement() == null) 269 return false; 270 TimeLocation t1 = s1.getTime(); 271 TimeLocation t2 = s2.getTime(); 272 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 273 return false; 274 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 275 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 276 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 277 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 278 if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 279 return true; 280 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 281 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 282 if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 283 return true; 284 } 285 } else { 286 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 287 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 288 if (dist > t1.getBreakTime()) 289 return true; 290 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 291 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 292 if (dist > t2.getBreakTime()) 293 return true; 294 } 295 } 296 return false; 297 } 298 299 @Override 300 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 301 return inConflict(cx, a1, a2) ? 1 : 0; 302 } 303 304 @Override 305 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 306 return new Nothing(); 307 } 308 309 @Override 310 public double getWeight(Context cx, Conflict c, Enrollment e) { 311 return c.getPenalty(); 312 } 313 }), 314 /** 315 * Short distance conflict. Similar to distance conflicts but for students that require short 316 * distances. When Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to false, 317 * distance conflicts are only considered between back-to-back classes (travel time between the 318 * two classes is more than zero minutes). When 319 * Distances.ComputeDistanceConflictsBetweenNonBTBClasses is set to true, the distance between the 320 * two classes is also considered (break time is also ignored). 321 * This criterion is weighted by StudentWeights.ShortDistanceConflict, defaulting to 0.1. 322 */ 323 ShortDistance(WeightType.LOWER, "StudentWeights.ShortDistanceConflict", 0.1000, new Quality(){ 324 @Override 325 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 326 return student.isNeedShortDistances() && r1 instanceof CourseRequest && r2 instanceof CourseRequest; 327 } 328 329 @Override 330 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 331 Section s1 = (Section) sa1; 332 Section s2 = (Section) sa2; 333 if (s1.getPlacement() == null || s2.getPlacement() == null) 334 return false; 335 TimeLocation t1 = s1.getTime(); 336 TimeLocation t2 = s2.getTime(); 337 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 338 return false; 339 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 340 if (cx.getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) { 341 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 342 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 343 if (dist > Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 344 return true; 345 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 346 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 347 if (dist > Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 348 return true; 349 } 350 } else { 351 if (a1 + t1.getNrSlotsPerMeeting() == a2) { 352 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 353 if (dist > 0) return true; 354 } else if (a2 + t2.getNrSlotsPerMeeting() == a1) { 355 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 356 if (dist > 0) return true; 357 } 358 } 359 return false; 360 } 361 362 @Override 363 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 364 return inConflict(cx, a1, a2) ? 1 : 0; 365 } 366 367 @Override 368 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 369 return new Nothing(); 370 } 371 372 @Override 373 public double getWeight(Context cx, Conflict c, Enrollment e) { 374 return c.getPenalty(); 375 } 376 }), 377 /** 378 * Naive, yet effective approach for modeling student lunch breaks. It creates a conflict whenever there are 379 * two classes (of a student) overlapping with the lunch time which are one after the other with a break in 380 * between smaller than the requested lunch break. Lunch time is defined by StudentLunch.StartSlot and 381 * StudentLunch.EndStart properties (default is 11:00 am - 1:30 pm), with lunch break of at least 382 * StudentLunch.Length slots (default is 30 minutes). Such a conflict is weighted 383 * by StudentWeights.LunchBreakFactor, which defaults to 0.005. 384 */ 385 LunchBreak(WeightType.BOTH, "StudentWeights.LunchBreakFactor", 0.0050, new Quality() { 386 @Override 387 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 388 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 389 } 390 391 @Override 392 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 393 if (a1.getTime() == null || a2.getTime() == null) return false; 394 if (((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false; 395 if (a1.getTime().hasIntersection(a2.getTime())) return false; 396 TimeLocation t1 = a1.getTime(), t2 = a2.getTime(); 397 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 398 int s1 = t1.getStartSlot(), s2 = t2.getStartSlot(); 399 int e1 = t1.getStartSlot() + t1.getNrSlotsPerMeeting(), e2 = t2.getStartSlot() + t2.getNrSlotsPerMeeting(); 400 if (e1 + cx.getLunchLength() > s2 && e2 + cx.getLunchLength() > s1 && e1 > cx.getLunchStart() && cx.getLunchEnd() > s1 && e2 > cx.getLunchStart() && cx.getLunchEnd() > s2) 401 return true; 402 return false; 403 } 404 405 @Override 406 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 407 if (!inConflict(cx, a1, a2)) return 0; 408 return a1.getTime().nrSharedDays(a2.getTime()); 409 } 410 411 @Override 412 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 413 return new Nothing(); 414 } 415 416 @Override 417 public double getWeight(Context cx, Conflict c, Enrollment e) { 418 return c.getPenalty(); 419 } 420 }), 421 /** 422 * Naive, yet effective approach for modeling travel times. A conflict with the penalty 423 * equal to the distance in minutes occurs when two classes are less than TravelTime.MaxTravelGap 424 * time slots a part (defaults 1 hour), or when they are less then twice as long apart 425 * and the travel time is longer than the break time of the first class. 426 * Such a conflict is weighted by StudentWeights.TravelTimeFactor, which defaults to 0.001. 427 */ 428 TravelTime(WeightType.BOTH, "StudentWeights.TravelTimeFactor", 0.0010, new Quality() { 429 @Override 430 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 431 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 432 } 433 434 @Override 435 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 436 Section s1 = (Section) sa1; 437 Section s2 = (Section) sa2; 438 if (s1.getPlacement() == null || s2.getPlacement() == null) 439 return false; 440 TimeLocation t1 = s1.getTime(); 441 TimeLocation t2 = s2.getTime(); 442 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 443 return false; 444 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 445 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 446 int gap = a2 - (a1 + t1.getNrSlotsPerMeeting()); 447 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 448 return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime()); 449 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 450 int gap = a1 - (a2 + t2.getNrSlotsPerMeeting()); 451 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 452 return (gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime()); 453 } 454 return false; 455 } 456 457 @Override 458 public int penalty(Context cx, Student s, SctAssignment sa1, SctAssignment sa2) { 459 Section s1 = (Section) sa1; 460 Section s2 = (Section) sa2; 461 if (s1.getPlacement() == null || s2.getPlacement() == null) return 0; 462 TimeLocation t1 = s1.getTime(); 463 TimeLocation t2 = s2.getTime(); 464 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0; 465 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 466 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 467 int gap = a2 - (a1 + t1.getNrSlotsPerMeeting()); 468 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 469 if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t1.getBreakTime())) 470 return dist; 471 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 472 int gap = a1 - (a2 + t2.getNrSlotsPerMeeting()); 473 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2.getPlacement()); 474 if ((gap < cx.getMaxTravelGap() && dist > 0) || (gap < 2 * cx.getMaxTravelGap() && dist > t2.getBreakTime())) 475 return dist; 476 } 477 return 0; 478 } 479 480 @Override 481 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 482 return new Nothing(); 483 } 484 485 @Override 486 public double getWeight(Context cx, Conflict c, Enrollment e) { 487 return c.getPenalty(); 488 } 489 }), 490 /** 491 * A back-to-back conflict is there every time when a student has two classes that are 492 * back-to-back or less than StudentWeights.BackToBackDistance time slots apart (defaults to 30 minutes). 493 * Such a conflict is weighted by StudentWeights.BackToBackFactor, which 494 * defaults to -0.0001 (these conflicts are preferred by default, trying to avoid schedule gaps). 495 * NEW: Consider student's back-to-back preference. That is, students with no preference are ignored, and 496 * students that discourage back-to-backs have a negative weight on the conflict. 497 */ 498 BackToBack(WeightType.BOTH, "StudentWeights.BackToBackFactor", -0.0001, new Quality() { 499 @Override 500 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 501 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && 502 (student.getBackToBackPreference() == BackToBackPreference.BTB_PREFERRED || student.getBackToBackPreference() == BackToBackPreference.BTB_DISCOURAGED); 503 } 504 505 @Override 506 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 507 TimeLocation t1 = a1.getTime(); 508 TimeLocation t2 = a2.getTime(); 509 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 510 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 511 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 512 return dist <= cx.getBackToBackDistance(); 513 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 514 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 515 return dist <= cx.getBackToBackDistance(); 516 } 517 return false; 518 } 519 520 @Override 521 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 522 if (!inConflict(cx, a1, a2)) return 0; 523 if (s.getBackToBackPreference() == BackToBackPreference.BTB_PREFERRED) 524 return a1.getTime().nrSharedDays(a2.getTime()); 525 else if (s.getBackToBackPreference() == BackToBackPreference.BTB_DISCOURAGED) 526 return -a1.getTime().nrSharedDays(a2.getTime()); 527 else 528 return 0; 529 } 530 531 @Override 532 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 533 return new Nothing(); 534 } 535 536 @Override 537 public double getWeight(Context cx, Conflict c, Enrollment e) { 538 return c.getPenalty(); 539 } 540 }), 541 /** 542 * A work-day conflict is there every time when a student has two classes that are too 543 * far apart. This means that the time between the start of the first class and the end 544 * of the last class is more than WorkDay.WorkDayLimit (defaults to 6 hours). A penalty 545 * of one is incurred for every hour started over this limit. 546 * Such a conflict is weighted by StudentWeights.WorkDayFactor, which defaults to 0.01. 547 */ 548 WorkDay(WeightType.BOTH, "StudentWeights.WorkDayFactor", 0.0100, new Quality() { 549 @Override 550 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 551 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy(); 552 } 553 554 @Override 555 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 556 TimeLocation t1 = a1.getTime(); 557 TimeLocation t2 = a2.getTime(); 558 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 559 int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()); 560 return dist > cx.getWorkDayLimit(); 561 } 562 563 @Override 564 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 565 TimeLocation t1 = a1.getTime(); 566 TimeLocation t2 = a2.getTime(); 567 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0; 568 int dist = Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()); 569 if (dist > cx.getWorkDayLimit()) 570 return a1.getTime().nrSharedDays(a2.getTime()) * (dist - cx.getWorkDayLimit()); 571 else 572 return 0; 573 } 574 575 @Override 576 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 577 return new Nothing(); 578 } 579 580 @Override 581 public double getWeight(Context cx, Conflict c, Enrollment e) { 582 return c.getPenalty() / 12.0; 583 } 584 }), 585 TooEarly(WeightType.REQUEST, "StudentWeights.TooEarlyFactor", 0.0500, new Quality(){ 586 @Override 587 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 588 return false; 589 } 590 591 @Override 592 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 593 if (a1.getTime() == null || a2.getTime() == null) return false; 594 return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime()); 595 } 596 597 @Override 598 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 599 if (!inConflict(cx, a1, a2)) return 0; 600 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 601 } 602 603 @Override 604 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 605 return (e.isCourseRequest() && !e.getStudent().isDummy() ? new SingleTimeIterable(0, cx.getEarlySlot()) : new Nothing()); 606 } 607 608 @Override 609 public double getWeight(Context cx, Conflict c, Enrollment e) { 610 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 611 } 612 }), 613 TooLate(WeightType.REQUEST, "StudentWeights.TooLateFactor", 0.0250, new Quality(){ 614 @Override 615 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 616 return false; 617 } 618 619 @Override 620 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 621 if (a1.getTime() == null || a2.getTime() == null) return false; 622 return a1.getTime().shareDays(a2.getTime()) && a1.getTime().shareHours(a2.getTime()); 623 } 624 625 @Override 626 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 627 if (!inConflict(cx, a1, a2)) return 0; 628 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 629 } 630 631 @Override 632 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 633 return (e.isCourseRequest() && !e.getStudent().isDummy() ? new SingleTimeIterable(cx.getLateSlot(), 288) : new Nothing()); 634 } 635 636 @Override 637 public double getWeight(Context cx, Conflict c, Enrollment e) { 638 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 639 } 640 }), 641 /** 642 * There is a student modality preference conflict when a student that prefers online 643 * gets a non-online class ({@link Section#isOnline()} is false) or when a student that 644 * prefers non-online gets an online class (@{link Section#isOnline()} is true). 645 * Such a conflict is weighted by StudentWeights.ModalityFactor, which defaults to 0.05. 646 */ 647 Modality(WeightType.REQUEST, "StudentWeights.ModalityFactor", 0.0500, new Quality(){ 648 @Override 649 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 650 return false; 651 } 652 653 @Override 654 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 655 return a1.equals(a2); 656 } 657 658 @Override 659 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 660 return (inConflict(cx, a1, a2) ? 1 : 0); 661 } 662 663 @Override 664 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 665 if (!e.isCourseRequest() || e.getStudent().isDummy()) return new Nothing(); 666 if (e.getStudent().getModalityPreference() == ModalityPreference.ONLINE_PREFERRED) 667 return new Online(e, false); // face-to-face sections are conflicting 668 else if (e.getStudent().getModalityPreference() == ModalityPreference.ONILNE_DISCOURAGED) 669 return new Online(e, true); // online sections are conflicting 670 return new Nothing(); 671 } 672 673 @Override 674 public double getWeight(Context cx, Conflict c, Enrollment e) { 675 return ((double) c.getPenalty()) / ((double) e.getSections().size()); 676 } 677 }), 678 /** 679 * DRC: Time conflict between class and a free time request (for students with FT accommodation). 680 * Free time conflicts are penalized as the time of a course request overlapping with a free time 681 * proportional to the time of the request, capped at one half of the time. 682 * This criterion is weighted by Accommodations.FreeTimeOverlapFactor, defaulting to 0.5. 683 */ 684 AccFreeTimeOverlap(WeightType.REQUEST, "Accommodations.FreeTimeOverlapFactor", 0.5000, new Quality(){ 685 @Override 686 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 687 return false; 688 } 689 690 @Override 691 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 692 if (a1.getTime() == null || a2.getTime() == null) return false; 693 return a1.getTime().hasIntersection(a2.getTime()); 694 } 695 696 @Override 697 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 698 if (!inConflict(cx, a1, a2)) return 0; 699 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime()); 700 } 701 702 @Override 703 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 704 if (!e.getStudent().hasAccommodation(cx.getFreeTimeAccommodation())) return new Nothing(); 705 return (e.isCourseRequest() ? new FreeTimes(e.getStudent()) : new Nothing()); 706 } 707 708 @Override 709 public double getWeight(Context cx, Conflict c, Enrollment e) { 710 return Math.min(cx.getTimeOverlapMaxLimit() * c.getPenalty() / c.getE1().getNrSlots(), cx.getTimeOverlapMaxLimit()); 711 } 712 }), 713 /** 714 * DRC: A back-to-back conflict (for students with BTB accommodation) is there every time when a student has two classes that are NOT 715 * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes). 716 * Such a conflict is weighted by Accommodations.BackToBackFactor, which defaults to 0.001 717 */ 718 AccBackToBack(WeightType.BOTH, "Accommodations.BackToBackFactor", 0.001, new Quality() { 719 @Override 720 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 721 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBackToBackAccommodation()); 722 } 723 724 @Override 725 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 726 TimeLocation t1 = a1.getTime(); 727 TimeLocation t2 = a2.getTime(); 728 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 729 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 730 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 731 return dist > cx.getBackToBackDistance(); 732 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 733 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 734 return dist > cx.getBackToBackDistance(); 735 } 736 return false; 737 } 738 739 @Override 740 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 741 if (!inConflict(cx, a1, a2)) return 0; 742 return a1.getTime().nrSharedDays(a2.getTime()); 743 } 744 745 @Override 746 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 747 return new Nothing(); 748 } 749 750 @Override 751 public double getWeight(Context cx, Conflict c, Enrollment e) { 752 return c.getPenalty(); 753 } 754 }), 755 /** 756 * DRC: A not back-to-back conflict (for students with BBC accommodation) is there every time when a student has two classes that are 757 * back-to-back or less than Accommodations.BackToBackDistance time slots apart (defaults to 30 minutes). 758 * Such a conflict is weighted by Accommodations.BreaksBetweenClassesFactor, which defaults to 0.001. 759 */ 760 AccBreaksBetweenClasses(WeightType.BOTH, "Accommodations.BreaksBetweenClassesFactor", 0.001, new Quality() { 761 @Override 762 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 763 return r1 instanceof CourseRequest && r2 instanceof CourseRequest && !student.isDummy() && student.hasAccommodation(cx.getBreakBetweenClassesAccommodation()); 764 } 765 766 @Override 767 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { 768 TimeLocation t1 = a1.getTime(); 769 TimeLocation t2 = a2.getTime(); 770 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 771 if (t1.getStartSlot() + t1.getNrSlotsPerMeeting() <= t2.getStartSlot()) { 772 int dist = t2.getStartSlot() - (t1.getStartSlot() + t1.getNrSlotsPerMeeting()); 773 return dist <= cx.getBackToBackDistance(); 774 } else if (t2.getStartSlot() + t2.getNrSlotsPerMeeting() <= t1.getStartSlot()) { 775 int dist = t1.getStartSlot() - (t2.getStartSlot() + t2.getNrSlotsPerMeeting()); 776 return dist <= cx.getBackToBackDistance(); 777 } 778 return false; 779 } 780 781 @Override 782 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 783 if (!inConflict(cx, a1, a2)) return 0; 784 return a1.getTime().nrSharedDays(a2.getTime()); 785 } 786 787 @Override 788 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 789 return new Nothing(); 790 } 791 792 @Override 793 public double getWeight(Context cx, Conflict c, Enrollment e) { 794 return c.getPenalty(); 795 } 796 }), 797 /** 798 * Student unavailability distance conflict. Distance conflict between a class that the student is taking and a class that the student 799 * is teaching or attending in a different session. 800 * This criterion is weighted by StudentWeights.UnavailabilityDistanceConflict, defaulting to 0.1. 801 */ 802 UnavailabilityDistance(WeightType.REQUEST, "StudentWeights.UnavailabilityDistanceConflict", 0.100, new Quality(){ 803 @Override 804 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { 805 return false; 806 } 807 808 @Override 809 public boolean inConflict(Context cx, SctAssignment sa1, SctAssignment sa2) { 810 Section s1 = (Section) sa1; 811 Unavailability s2 = (Unavailability) sa2; 812 if (s1.getPlacement() == null || s2.getTime() == null || s2.getNrRooms() == 0) 813 return false; 814 TimeLocation t1 = s1.getTime(); 815 TimeLocation t2 = s2.getTime(); 816 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) 817 return false; 818 int a1 = t1.getStartSlot(), a2 = t2.getStartSlot(); 819 if (a1 + t1.getNrSlotsPerMeeting() <= a2) { 820 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2); 821 if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength())) 822 return true; 823 } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) { 824 int dist = cx.getDistanceInMinutes(s1.getPlacement(), s2); 825 if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength())) 826 return true; 827 } 828 return false; 829 } 830 831 @Override 832 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { 833 if (!inConflict(cx, a1, a2)) return 0; 834 return a1.getTime().nrSharedDays(a2.getTime()); 835 } 836 837 @Override 838 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { 839 return (e.isCourseRequest() ? new Unavailabilities(e.getStudent()) : new Nothing()); 840 } 841 842 @Override 843 public double getWeight(Context cx, Conflict c, Enrollment e) { 844 return c.getPenalty(); 845 } 846 }), 847 ; 848 849 private WeightType iType; 850 private Quality iQuality; 851 private String iWeightName; 852 private double iWeightDefault; 853 Type(WeightType type, String weightName, double weightDefault, Quality quality) { 854 iQuality = quality; 855 iType = type; 856 iWeightName = weightName; 857 iWeightDefault = weightDefault; 858 } 859 860 861 public boolean isApplicable(Context cx, Student student, Request r1, Request r2) { return iQuality.isApplicable(cx, student, r1, r2); } 862 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2) { return iQuality.inConflict(cx, a1, a2); } 863 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2) { return iQuality.penalty(cx, s, a1, a2); } 864 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e) { return iQuality.other(cx, e); } 865 public double getWeight(Context cx, Conflict c, Enrollment e) { return iQuality.getWeight(cx, c, e); } 866 public String getName() { return name().replaceAll("(?<=[^A-Z0-9])([A-Z0-9])"," $1"); } 867 public String getAbbv() { return getName().replaceAll("[a-z ]",""); } 868 public WeightType getType() { return iType; } 869 public String getWeightName() { return iWeightName; } 870 public double getWeightDefault() { return iWeightDefault; } 871 } 872 873 /** 874 * Schedule quality interface 875 */ 876 public static interface Quality { 877 /** 878 * Check if the metric is applicable for the given student, between the given two requests 879 */ 880 public boolean isApplicable(Context cx, Student student, Request r1, Request r2); 881 /** 882 * When applicable, is there a conflict between two sections 883 */ 884 public boolean inConflict(Context cx, SctAssignment a1, SctAssignment a2); 885 /** 886 * When in conflict, what is the penalisation 887 */ 888 public int penalty(Context cx, Student s, SctAssignment a1, SctAssignment a2); 889 /** 890 * Enumerate other section assignments applicable for the given enrollment (e.g., student unavailabilities) 891 */ 892 public Iterable<? extends SctAssignment> other(Context cx, Enrollment e); 893 /** 894 * Base weight of the given conflict and enrollment. Typically based on the {@link Conflict#getPenalty()}, but 895 * change to be between 0.0 and 1.0. For example, for time conflicts, a percentage of share is used. 896 */ 897 public double getWeight(Context cx, Conflict c, Enrollment e); 898 } 899 900 /** 901 * Penalisation of the given type between two enrollments of a student. 902 */ 903 public int penalty(Type type, Enrollment e1, Enrollment e2) { 904 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return 0; 905 int cnt = 0; 906 for (SctAssignment s1 : e1.getAssignments()) { 907 for (SctAssignment s2 : e2.getAssignments()) { 908 cnt += type.penalty(iContext, e1.getStudent(), s1, s2); 909 } 910 } 911 return cnt; 912 } 913 914 /** 915 * Conflicss of the given type between two enrollments of a student. 916 */ 917 public Set<Conflict> conflicts(Type type, Enrollment e1, Enrollment e2) { 918 Set<Conflict> ret = new HashSet<Conflict>(); 919 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) return ret; 920 for (SctAssignment s1 : e1.getAssignments()) { 921 for (SctAssignment s2 : e2.getAssignments()) { 922 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 923 if (penalty != 0) 924 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2)); 925 } 926 } 927 return ret; 928 } 929 930 /** 931 * Conflicts of any type between two enrollments of a student. 932 */ 933 public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) { 934 Set<Conflict> ret = new HashSet<Conflict>(); 935 for (Type type: iContext.getTypes()) { 936 if (!e1.getStudent().equals(e2.getStudent()) || !type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e2.getRequest())) continue; 937 for (SctAssignment s1 : e1.getAssignments()) { 938 for (SctAssignment s2 : e2.getAssignments()) { 939 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 940 if (penalty != 0) 941 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e2, s2)); 942 } 943 } 944 } 945 return ret; 946 } 947 948 /** 949 * Conflicts of the given type between classes of a single enrollment (or with free times, unavailabilities, etc.) 950 */ 951 public Set<Conflict> conflicts(Type type, Enrollment e1) { 952 Set<Conflict> ret = new HashSet<Conflict>(); 953 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 954 for (SctAssignment s1 : e1.getAssignments()) { 955 if (applicable) { 956 for (SctAssignment s2 : e1.getAssignments()) { 957 if (s1.getId() < s2.getId()) { 958 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 959 if (penalty != 0) 960 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2)); 961 } 962 } 963 } 964 for (SctAssignment s2: type.other(iContext, e1)) { 965 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 966 if (penalty != 0) 967 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2)); 968 } 969 } 970 return ret; 971 } 972 973 /** 974 * Conflicts of any type between classes of a single enrollment (or with free times, unavailabilities, etc.) 975 */ 976 public Set<Conflict> conflicts(Enrollment e1) { 977 Set<Conflict> ret = new HashSet<Conflict>(); 978 for (Type type: iContext.getTypes()) { 979 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 980 for (SctAssignment s1 : e1.getAssignments()) { 981 if (applicable) { 982 for (SctAssignment s2 : e1.getAssignments()) { 983 if (s1.getId() < s2.getId()) { 984 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 985 if (penalty != 0) 986 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, e1, s2)); 987 } 988 } 989 } 990 for (SctAssignment s2: type.other(iContext, e1)) { 991 int penalty = type.penalty(iContext, e1.getStudent(), s1, s2); 992 if (penalty != 0) 993 ret.add(new Conflict(e1.getStudent(), type, penalty, e1, s1, s2)); 994 } 995 } 996 } 997 return ret; 998 } 999 1000 /** 1001 * Penalty of given type between classes of a single enrollment (or with free times, unavailabilities, etc.) 1002 */ 1003 public int penalty(Type type, Enrollment e1) { 1004 int penalty = 0; 1005 boolean applicable = type.isApplicable(iContext, e1.getStudent(), e1.getRequest(), e1.getRequest()); 1006 for (SctAssignment s1 : e1.getAssignments()) { 1007 if (applicable) { 1008 for (SctAssignment s2 : e1.getAssignments()) { 1009 if (s1.getId() < s2.getId()) { 1010 penalty += type.penalty(iContext, e1.getStudent(), s1, s2); 1011 } 1012 } 1013 } 1014 for (SctAssignment s2: type.other(iContext, e1)) { 1015 penalty += type.penalty(iContext, e1.getStudent(), s1, s2); 1016 } 1017 } 1018 return penalty; 1019 } 1020 1021 /** 1022 * Check whether the given type is applicable for the student and the two requests. 1023 */ 1024 public boolean isApplicable(Type type, Student student, Request r1, Request r2) { 1025 return type.isApplicable(iContext, student, r1, r2); 1026 } 1027 1028 /** 1029 * Total penalisation of given type 1030 */ 1031 public int getTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1032 return getContext(assignment).getTotalPenalty(type); 1033 } 1034 1035 /** 1036 * Total penalisation of given types 1037 */ 1038 public int getTotalPenalty(Assignment<Request, Enrollment> assignment, Type... types) { 1039 int ret = 0; 1040 for (Type type: types) 1041 ret += getContext(assignment).getTotalPenalty(type); 1042 return ret; 1043 } 1044 1045 /** 1046 * Re-check total penalization for the given assignment 1047 */ 1048 public void checkTotalPenalty(Assignment<Request, Enrollment> assignment) { 1049 for (Type type: iContext.getTypes()) 1050 checkTotalPenalty(type, assignment); 1051 } 1052 1053 /** 1054 * Re-check total penalization for the given assignment and conflict type 1055 */ 1056 public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1057 getContext(assignment).checkTotalPenalty(type, assignment); 1058 } 1059 1060 /** 1061 * All conflicts of the given type for the given assignment 1062 */ 1063 public Set<Conflict> getAllConflicts(Type type, Assignment<Request, Enrollment> assignment) { 1064 return getContext(assignment).getAllConflicts(type); 1065 } 1066 1067 /** 1068 * All conflicts of the any type for the enrollment (including conflicts with other enrollments of the student) 1069 */ 1070 public Set<Conflict> allConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1071 Set<Conflict> conflicts = new HashSet<Conflict>(); 1072 for (Type t: iContext.getTypes()) { 1073 conflicts.addAll(conflicts(t, enrollment)); 1074 for (Request request : enrollment.getStudent().getRequests()) { 1075 if (request.equals(enrollment.getRequest()) || assignment.getValue(request) == null) continue; 1076 conflicts.addAll(conflicts(t, enrollment, assignment.getValue(request))); 1077 } 1078 } 1079 return conflicts; 1080 } 1081 1082 @Override 1083 public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1084 getContext(assignment).beforeAssigned(assignment, iteration, value); 1085 } 1086 1087 @Override 1088 public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1089 getContext(assignment).afterAssigned(assignment, iteration, value); 1090 } 1091 1092 @Override 1093 public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1094 getContext(assignment).afterUnassigned(assignment, iteration, value); 1095 } 1096 1097 /** A representation of a time overlapping conflict */ 1098 public class Conflict { 1099 private Type iType; 1100 private int iPenalty; 1101 private Student iStudent; 1102 private SctAssignment iA1, iA2; 1103 private Enrollment iE1, iE2; 1104 private int iHashCode; 1105 1106 /** 1107 * Constructor 1108 * 1109 * @param student related student 1110 * @param type conflict type 1111 * @param penalty conflict penalization, e.g., the number of slots in common between the two conflicting sections 1112 * @param e1 first enrollment 1113 * @param a1 first conflicting section 1114 * @param e2 second enrollment 1115 * @param a2 second conflicting section 1116 */ 1117 public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, Enrollment e2, SctAssignment a2) { 1118 iStudent = student; 1119 if (a1.compareById(a2) < 0 ) { 1120 iA1 = a1; 1121 iA2 = a2; 1122 iE1 = e1; 1123 iE2 = e2; 1124 } else { 1125 iA1 = a2; 1126 iA2 = a1; 1127 iE1 = e2; 1128 iE2 = e1; 1129 } 1130 iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode(); 1131 iType = type; 1132 iPenalty = penalty; 1133 } 1134 1135 public Conflict(Student student, Type type, int penalty, Enrollment e1, SctAssignment a1, SctAssignment a2) { 1136 this(student, type, penalty, e1, a1, a2 instanceof FreeTimeRequest ? ((FreeTimeRequest)a2).createEnrollment() : a2 instanceof Unavailability ? ((Unavailability)a2).createEnrollment() : e1, a2); 1137 1138 } 1139 1140 /** Related student 1141 * @return student 1142 **/ 1143 public Student getStudent() { 1144 return iStudent; 1145 } 1146 1147 /** First section 1148 * @return first section 1149 **/ 1150 public SctAssignment getS1() { 1151 return iA1; 1152 } 1153 1154 /** Second section 1155 * @return second section 1156 **/ 1157 public SctAssignment getS2() { 1158 return iA2; 1159 } 1160 1161 /** First request 1162 * @return first request 1163 **/ 1164 public Request getR1() { 1165 return iE1.getRequest(); 1166 } 1167 1168 /** First request weight 1169 * @return first request weight 1170 **/ 1171 public double getR1Weight() { 1172 return (iE1.getRequest() == null ? 0.0 : iE1.getRequest().getWeight()); 1173 } 1174 1175 /** Second request weight 1176 * @return second request weight 1177 **/ 1178 public double getR2Weight() { 1179 return (iE2.getRequest() == null ? 0.0 : iE2.getRequest().getWeight()); 1180 } 1181 1182 /** Second request 1183 * @return second request 1184 **/ 1185 public Request getR2() { 1186 return iE2.getRequest(); 1187 } 1188 1189 /** First enrollment 1190 * @return first enrollment 1191 **/ 1192 public Enrollment getE1() { 1193 return iE1; 1194 } 1195 1196 /** Second enrollment 1197 * @return second enrollment 1198 **/ 1199 public Enrollment getE2() { 1200 return iE2; 1201 } 1202 1203 @Override 1204 public int hashCode() { 1205 return iHashCode; 1206 } 1207 1208 /** Conflict penalty, e.g., the number of overlapping slots against the number of slots of the smallest section 1209 * @return conflict penalty 1210 **/ 1211 public int getPenalty() { 1212 return iPenalty; 1213 } 1214 1215 /** Other enrollment of the conflict */ 1216 public Enrollment getOther(Enrollment enrollment) { 1217 return (getE1().getRequest().equals(enrollment.getRequest()) ? getE2() : getE1()); 1218 } 1219 1220 /** Weight of the conflict on the given enrollment */ 1221 public double getWeight(Enrollment e) { 1222 return iType.getWeight(iContext, this, e); 1223 } 1224 1225 /** Weight of the conflict on both enrollment (sum) */ 1226 public double getWeight() { 1227 return (iType.getWeight(iContext, this, iE1) + iType.getWeight(iContext, this, iE2)) / 2.0; 1228 } 1229 1230 /** Conflict type 1231 * @return conflict type; 1232 */ 1233 public Type getType() { 1234 return iType; 1235 } 1236 1237 @Override 1238 public boolean equals(Object o) { 1239 if (o == null || !(o instanceof Conflict)) return false; 1240 Conflict c = (Conflict) o; 1241 return getType() == c.getType() && getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2()); 1242 } 1243 1244 @Override 1245 public String toString() { 1246 return getStudent() + ": (" + getType() + ", p:" + getPenalty() + ") " + getS1() + " -- " + getS2(); 1247 } 1248 } 1249 1250 /** 1251 * Context holding parameters and distance cache. See {@link Type} for the list of available parameters. 1252 */ 1253 public static class Context { 1254 private List<Type> iTypes = null; 1255 private DistanceMetric iDistanceMetric = null; 1256 private boolean iDebug = false; 1257 protected double iTimeOverlapMaxLimit = 0.5000; 1258 private int iLunchStart, iLunchEnd, iLunchLength, iMaxTravelGap, iWorkDayLimit, iBackToBackDistance, iEarlySlot, iLateSlot, iAccBackToBackDistance; 1259 private String iFreeTimeAccommodation = "FT", iBackToBackAccommodation = "BTB", iBreakBetweenClassesAccommodation = "BBC"; 1260 private ReentrantReadWriteLock iLock = new ReentrantReadWriteLock(); 1261 1262 public Context(DistanceMetric dm, DataProperties config) { 1263 iDistanceMetric = (dm == null ? new DistanceMetric(config) : dm); 1264 iDebug = config.getPropertyBoolean("StudentQuality.Debug", false); 1265 iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit); 1266 iLunchStart = config.getPropertyInt("StudentLunch.StartSlot", (11 * 60) / 5); 1267 iLunchEnd = config.getPropertyInt("StudentLunch.EndStart", (13 * 60) / 5); 1268 iLunchLength = config.getPropertyInt("StudentLunch.Length", 30 / 5); 1269 iMaxTravelGap = config.getPropertyInt("TravelTime.MaxTravelGap", 12); 1270 iWorkDayLimit = config.getPropertyInt("WorkDay.WorkDayLimit", 6 * 12); 1271 iBackToBackDistance = config.getPropertyInt("StudentWeights.BackToBackDistance", 6); 1272 iAccBackToBackDistance = config.getPropertyInt("Accommodations.BackToBackDistance", 6); 1273 iEarlySlot = config.getPropertyInt("WorkDay.EarlySlot", 102); 1274 iLateSlot = config.getPropertyInt("WorkDay.LateSlot", 210); 1275 iFreeTimeAccommodation = config.getProperty("Accommodations.FreeTimeReference", iFreeTimeAccommodation); 1276 iBackToBackAccommodation = config.getProperty("Accommodations.BackToBackReference", iBackToBackAccommodation); 1277 iBreakBetweenClassesAccommodation = config.getProperty("Accommodations.BreakBetweenClassesReference", iBreakBetweenClassesAccommodation); 1278 iTypes = new ArrayList<Type>(); 1279 for (Type t: Type.values()) 1280 if (config.getPropertyDouble(t.getWeightName(), t.getWeightDefault()) != 0.0) 1281 iTypes.add(t); 1282 } 1283 1284 public DistanceMetric getDistanceMetric() { 1285 return iDistanceMetric; 1286 } 1287 1288 public boolean isDebug() { return iDebug; } 1289 1290 public double getTimeOverlapMaxLimit() { return iTimeOverlapMaxLimit; } 1291 public int getLunchStart() { return iLunchStart; } 1292 public int getLunchEnd() { return iLunchEnd; } 1293 public int getLunchLength() { return iLunchLength; } 1294 public int getMaxTravelGap() { return iMaxTravelGap; } 1295 public int getWorkDayLimit() { return iWorkDayLimit; } 1296 public int getBackToBackDistance() { return iBackToBackDistance; } 1297 public int getAccBackToBackDistance() { return iAccBackToBackDistance; } 1298 public int getEarlySlot() { return iEarlySlot; } 1299 public int getLateSlot() { return iLateSlot; } 1300 public String getFreeTimeAccommodation() { return iFreeTimeAccommodation; } 1301 public String getBackToBackAccommodation() { return iBackToBackAccommodation; } 1302 public String getBreakBetweenClassesAccommodation() { return iBreakBetweenClassesAccommodation; } 1303 public List<Type> getTypes() { return iTypes; } 1304 1305 private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>(); 1306 protected Integer getDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2) { 1307 ReadLock lock = iLock.readLock(); 1308 lock.lock(); 1309 try { 1310 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 1311 return other2distance == null ? null : other2distance.get(r2.getId()); 1312 } finally { 1313 lock.unlock(); 1314 } 1315 } 1316 1317 protected void setDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2, Integer distance) { 1318 WriteLock lock = iLock.writeLock(); 1319 lock.lock(); 1320 try { 1321 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 1322 if (other2distance == null) { 1323 other2distance = new HashMap<Long, Integer>(); 1324 iDistanceCache.put(r1.getId(), other2distance); 1325 } 1326 other2distance.put(r2.getId(), distance); 1327 } finally { 1328 lock.unlock(); 1329 } 1330 } 1331 1332 protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) { 1333 if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1); 1334 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar()) 1335 return 0; 1336 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null) 1337 return iDistanceMetric.getMaxTravelDistanceInMinutes(); 1338 Integer distance = getDistanceInMinutesFromCache(r1, r2); 1339 if (distance == null) { 1340 distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY()); 1341 setDistanceInMinutesFromCache(r1, r2, distance); 1342 } 1343 return distance; 1344 } 1345 1346 public int getDistanceInMinutes(Placement p1, Placement p2) { 1347 if (p1.isMultiRoom()) { 1348 if (p2.isMultiRoom()) { 1349 int dist = 0; 1350 for (RoomLocation r1 : p1.getRoomLocations()) { 1351 for (RoomLocation r2 : p2.getRoomLocations()) { 1352 dist = Math.max(dist, getDistanceInMinutes(r1, r2)); 1353 } 1354 } 1355 return dist; 1356 } else { 1357 if (p2.getRoomLocation() == null) 1358 return 0; 1359 int dist = 0; 1360 for (RoomLocation r1 : p1.getRoomLocations()) { 1361 dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation())); 1362 } 1363 return dist; 1364 } 1365 } else if (p2.isMultiRoom()) { 1366 if (p1.getRoomLocation() == null) 1367 return 0; 1368 int dist = 0; 1369 for (RoomLocation r2 : p2.getRoomLocations()) { 1370 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2)); 1371 } 1372 return dist; 1373 } else { 1374 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 1375 return 0; 1376 return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation()); 1377 } 1378 } 1379 1380 public int getDistanceInMinutes(Placement p1, Unavailability p2) { 1381 if (p1.isMultiRoom()) { 1382 int dist = 0; 1383 for (RoomLocation r1 : p1.getRoomLocations()) { 1384 for (RoomLocation r2 : p2.getRooms()) { 1385 dist = Math.max(dist, getDistanceInMinutes(r1, r2)); 1386 } 1387 } 1388 return dist; 1389 } else { 1390 if (p1.getRoomLocation() == null) 1391 return 0; 1392 int dist = 0; 1393 for (RoomLocation r2 : p2.getRooms()) { 1394 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2)); 1395 } 1396 return dist; 1397 } 1398 } 1399 } 1400 1401 /** 1402 * Assignment context 1403 */ 1404 public class StudentQualityContext implements AssignmentConstraintContext<Request, Enrollment> { 1405 private int[] iTotalPenalty = null; 1406 private Set<Conflict>[] iAllConflicts = null; 1407 private Request iOldVariable = null; 1408 private Enrollment iUnassignedValue = null; 1409 1410 @SuppressWarnings("unchecked") 1411 public StudentQualityContext(Assignment<Request, Enrollment> assignment) { 1412 iTotalPenalty = new int[Type.values().length]; 1413 for (Type t: iContext.getTypes()) 1414 iTotalPenalty[t.ordinal()] = countTotalPenalty(t, assignment); 1415 if (iContext.isDebug()) { 1416 iAllConflicts = new Set[Type.values().length]; 1417 for (Type t: iContext.getTypes()) 1418 iAllConflicts[t.ordinal()] = computeAllConflicts(t, assignment); 1419 } 1420 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1421 for (Type t: iContext.getTypes()) 1422 for (Conflict c: computeAllConflicts(t, assignment)) cx.add(assignment, c); 1423 } 1424 1425 @SuppressWarnings("unchecked") 1426 public StudentQualityContext(StudentQualityContext parent) { 1427 iTotalPenalty = new int[Type.values().length]; 1428 for (Type t: iContext.getTypes()) 1429 iTotalPenalty[t.ordinal()] = parent.iTotalPenalty[t.ordinal()]; 1430 if (iContext.isDebug()) { 1431 iAllConflicts = new Set[Type.values().length]; 1432 for (Type t: iContext.getTypes()) 1433 iAllConflicts[t.ordinal()] = new HashSet<Conflict>(parent.iAllConflicts[t.ordinal()]); 1434 } 1435 } 1436 1437 @Override 1438 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1439 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1440 for (Type type: iContext.getTypes()) { 1441 iTotalPenalty[type.ordinal()] += allPenalty(type, assignment, value); 1442 for (Conflict c: allConflicts(type, assignment, value)) 1443 cx.add(assignment, c); 1444 } 1445 if (iContext.isDebug()) { 1446 sLog.debug("A:" + value.variable() + " := " + value); 1447 for (Type type: iContext.getTypes()) { 1448 int inc = allPenalty(type, assignment, value); 1449 if (inc != 0) { 1450 sLog.debug("-- " + type + " +" + inc + " A: " + value.variable() + " := " + value); 1451 for (Conflict c: allConflicts(type, assignment, value)) { 1452 sLog.debug(" -- " + c); 1453 iAllConflicts[type.ordinal()].add(c); 1454 inc -= c.getPenalty(); 1455 } 1456 if (inc != 0) { 1457 sLog.error(type + ": Different penalty for the assigned value (difference: " + inc + ")!"); 1458 } 1459 } 1460 } 1461 } 1462 } 1463 1464 /** 1465 * Called when a value is unassigned from a variable. Internal number of 1466 * time overlapping conflicts is updated, see 1467 * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}. 1468 */ 1469 @Override 1470 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1471 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1472 for (Type type: iContext.getTypes()) { 1473 iTotalPenalty[type.ordinal()] -= allPenalty(type, assignment, value); 1474 for (Conflict c: allConflicts(type, assignment, value)) 1475 cx.remove(assignment, c); 1476 } 1477 if (iContext.isDebug()) { 1478 sLog.debug("U:" + value.variable() + " := " + value); 1479 for (Type type: iContext.getTypes()) { 1480 int dec = allPenalty(type, assignment, value); 1481 if (dec != 0) { 1482 sLog.debug("-- " + type + " -" + dec + " U: " + value.variable() + " := " + value); 1483 for (Conflict c: allConflicts(type, assignment, value)) { 1484 sLog.debug(" -- " + c); 1485 iAllConflicts[type.ordinal()].remove(c); 1486 dec -= c.getPenalty(); 1487 } 1488 if (dec != 0) { 1489 sLog.error(type + ":Different penalty for the unassigned value (difference: " + dec + ")!"); 1490 } 1491 } 1492 } 1493 } 1494 } 1495 1496 /** 1497 * Called before a value is assigned to a variable. 1498 * @param assignment current assignment 1499 * @param iteration current iteration 1500 * @param value value to be assigned 1501 */ 1502 public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1503 if (value != null) { 1504 Enrollment old = assignment.getValue(value.variable()); 1505 if (old != null) { 1506 iUnassignedValue = old; 1507 unassigned(assignment, old); 1508 } 1509 iOldVariable = value.variable(); 1510 } 1511 } 1512 1513 /** 1514 * Called after a value is assigned to a variable. 1515 * @param assignment current assignment 1516 * @param iteration current iteration 1517 * @param value value that was assigned 1518 */ 1519 public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1520 iOldVariable = null; 1521 iUnassignedValue = null; 1522 if (value != null) { 1523 assigned(assignment, value); 1524 } 1525 } 1526 1527 /** 1528 * Called after a value is unassigned from a variable. 1529 * @param assignment current assignment 1530 * @param iteration current iteration 1531 * @param value value that was unassigned 1532 */ 1533 public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1534 if (value != null && !value.equals(iUnassignedValue)) { 1535 unassigned(assignment, value); 1536 } 1537 } 1538 1539 public Set<Conflict> getAllConflicts(Type type) { 1540 return iAllConflicts[type.ordinal()]; 1541 } 1542 1543 public int getTotalPenalty(Type type) { 1544 return iTotalPenalty[type.ordinal()]; 1545 } 1546 1547 public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1548 int total = countTotalPenalty(type, assignment); 1549 if (total != iTotalPenalty[type.ordinal()]) { 1550 sLog.error(type + " penalty does not match for (actual: " + total + ", count: " + iTotalPenalty[type.ordinal()] + ")!"); 1551 iTotalPenalty[type.ordinal()] = total; 1552 if (iContext.isDebug()) { 1553 Set<Conflict> conflicts = computeAllConflicts(type, assignment); 1554 for (Conflict c: conflicts) { 1555 if (!iAllConflicts[type.ordinal()].contains(c)) 1556 sLog.debug(" +add+ " + c); 1557 } 1558 for (Conflict c: iAllConflicts[type.ordinal()]) { 1559 if (!conflicts.contains(c)) 1560 sLog.debug(" -rem- " + c); 1561 } 1562 for (Conflict c: conflicts) { 1563 for (Conflict d: iAllConflicts[type.ordinal()]) { 1564 if (c.equals(d) && c.getPenalty() != d.getPenalty()) { 1565 sLog.debug(" -dif- " + c + " (other: " + d.getPenalty() + ")"); 1566 } 1567 } 1568 } 1569 iAllConflicts[type.ordinal()] = conflicts; 1570 } 1571 } 1572 } 1573 1574 public int countTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1575 int total = 0; 1576 for (Request r1 : getModel().variables()) { 1577 Enrollment e1 = assignment.getValue(r1); 1578 if (e1 == null || r1.equals(iOldVariable)) continue; 1579 for (Request r2 : r1.getStudent().getRequests()) { 1580 Enrollment e2 = assignment.getValue(r2); 1581 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1582 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1583 total += penalty(type, e1, e2); 1584 } 1585 } 1586 total += penalty(type, e1); 1587 } 1588 return total; 1589 } 1590 1591 public Set<Conflict> computeAllConflicts(Type type, Assignment<Request, Enrollment> assignment) { 1592 Set<Conflict> ret = new HashSet<Conflict>(); 1593 for (Request r1 : getModel().variables()) { 1594 Enrollment e1 = assignment.getValue(r1); 1595 if (e1 == null || r1.equals(iOldVariable)) continue; 1596 for (Request r2 : r1.getStudent().getRequests()) { 1597 Enrollment e2 = assignment.getValue(r2); 1598 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1599 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1600 ret.addAll(conflicts(type, e1, e2)); 1601 } 1602 } 1603 ret.addAll(conflicts(type, e1)); 1604 } 1605 return ret; 1606 } 1607 1608 public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Student student) { 1609 Set<Conflict> ret = new HashSet<Conflict>(); 1610 for (Request r1 : student.getRequests()) { 1611 Enrollment e1 = assignment.getValue(r1); 1612 if (e1 == null) continue; 1613 for (Request r2 : student.getRequests()) { 1614 Enrollment e2 = assignment.getValue(r2); 1615 if (e2 != null && r1.getId() < r2.getId()) { 1616 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1617 ret.addAll(conflicts(type, e1, e2)); 1618 } 1619 } 1620 ret.addAll(conflicts(type, e1)); 1621 } 1622 return ret; 1623 } 1624 1625 public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1626 Set<Conflict> ret = new HashSet<Conflict>(); 1627 for (Request request : enrollment.getStudent().getRequests()) { 1628 if (request.equals(enrollment.getRequest())) continue; 1629 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1630 ret.addAll(conflicts(type, enrollment, assignment.getValue(request))); 1631 } 1632 } 1633 ret.addAll(conflicts(type, enrollment)); 1634 return ret; 1635 } 1636 1637 public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Student student) { 1638 int penalty = 0; 1639 for (Request r1 : student.getRequests()) { 1640 Enrollment e1 = assignment.getValue(r1); 1641 if (e1 == null) continue; 1642 for (Request r2 : student.getRequests()) { 1643 Enrollment e2 = assignment.getValue(r2); 1644 if (e2 != null && r1.getId() < r2.getId()) { 1645 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1646 penalty += penalty(type, e1, e2); 1647 } 1648 } 1649 penalty += penalty(type, e1); 1650 } 1651 return penalty; 1652 } 1653 1654 public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1655 int penalty = 0; 1656 for (Request request : enrollment.getStudent().getRequests()) { 1657 if (request.equals(enrollment.getRequest())) continue; 1658 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1659 if (type.isApplicable(iContext, enrollment.getStudent(), enrollment.variable(), request)) 1660 penalty += penalty(type, enrollment, assignment.getValue(request)); 1661 } 1662 } 1663 penalty += penalty(type, enrollment); 1664 return penalty; 1665 } 1666 } 1667 1668 @Override 1669 public StudentQualityContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 1670 return new StudentQualityContext(assignment); 1671 } 1672 1673 @Override 1674 public StudentQualityContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, StudentQualityContext parentContext) { 1675 return new StudentQualityContext(parentContext); 1676 } 1677 1678 /** Empty iterator */ 1679 public static class Nothing implements Iterable<SctAssignment> { 1680 @Override 1681 public Iterator<SctAssignment> iterator() { 1682 return new Iterator<SctAssignment>() { 1683 @Override 1684 public SctAssignment next() { return null; } 1685 @Override 1686 public boolean hasNext() { return false; } 1687 @Override 1688 public void remove() { throw new UnsupportedOperationException(); } 1689 }; 1690 } 1691 } 1692 1693 /** Unavailabilities of a student */ 1694 public static class Unavailabilities implements Iterable<Unavailability> { 1695 private Student iStudent; 1696 public Unavailabilities(Student student) { iStudent = student; } 1697 @Override 1698 public Iterator<Unavailability> iterator() { return iStudent.getUnavailabilities().iterator(); } 1699 } 1700 1701 private static class SingleTime implements SctAssignment { 1702 private TimeLocation iTime = null; 1703 1704 public SingleTime(int start, int end) { 1705 iTime = new TimeLocation(0x7f, start, end-start, 0, 0.0, 0, null, null, new BitSet(), 0); 1706 } 1707 1708 @Override 1709 public TimeLocation getTime() { return iTime; } 1710 @Override 1711 public List<RoomLocation> getRooms() { return null; } 1712 @Override 1713 public int getNrRooms() { return 0; } 1714 @Override 1715 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1716 @Override 1717 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1718 @Override 1719 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { return null; } 1720 @Override 1721 public boolean isAllowOverlap() { return false; } 1722 @Override 1723 public long getId() { return -1;} 1724 @Override 1725 public int compareById(SctAssignment a) { return 0; } 1726 1727 @Override 1728 public boolean isOverlapping(SctAssignment assignment) { 1729 return assignment.getTime() != null && getTime().shareDays(assignment.getTime()) && getTime().shareHours(assignment.getTime()); 1730 } 1731 1732 @Override 1733 public boolean isOverlapping(Set<? extends SctAssignment> assignments) { 1734 for (SctAssignment assignment : assignments) { 1735 if (isOverlapping(assignment)) return true; 1736 } 1737 return false; 1738 } 1739 } 1740 1741 /** Early/late time */ 1742 public static class SingleTimeIterable implements Iterable<SingleTime> { 1743 private SingleTime iTime = null; 1744 public SingleTimeIterable(int start, int end) { 1745 if (start < end) 1746 iTime = new SingleTime(start, end); 1747 1748 } 1749 @Override 1750 public Iterator<SingleTime> iterator() { 1751 return new Iterator<SingleTime>() { 1752 @Override 1753 public SingleTime next() { 1754 SingleTime ret = iTime; iTime = null; return ret; 1755 } 1756 @Override 1757 public boolean hasNext() { return iTime != null; } 1758 @Override 1759 public void remove() { throw new UnsupportedOperationException(); } 1760 }; 1761 } 1762 } 1763 1764 /** Free times of a student */ 1765 public static class FreeTimes implements Iterable<FreeTimeRequest> { 1766 private Student iStudent; 1767 public FreeTimes(Student student) { 1768 iStudent = student; 1769 } 1770 1771 @Override 1772 public Iterator<FreeTimeRequest> iterator() { 1773 return new Iterator<FreeTimeRequest>() { 1774 Iterator<Request> i = iStudent.getRequests().iterator(); 1775 FreeTimeRequest next = null; 1776 boolean hasNext = nextFreeTime(); 1777 1778 private boolean nextFreeTime() { 1779 while (i.hasNext()) { 1780 Request r = i.next(); 1781 if (r instanceof FreeTimeRequest) { 1782 next = (FreeTimeRequest)r; 1783 return true; 1784 } 1785 } 1786 return false; 1787 } 1788 1789 @Override 1790 public FreeTimeRequest next() { 1791 try { 1792 return next; 1793 } finally { 1794 hasNext = nextFreeTime(); 1795 } 1796 } 1797 @Override 1798 public boolean hasNext() { return hasNext; } 1799 @Override 1800 public void remove() { throw new UnsupportedOperationException(); } 1801 }; 1802 } 1803 } 1804 1805 /** Online (or not-online) classes of an enrollment */ 1806 public static class Online implements Iterable<Section> { 1807 private Enrollment iEnrollment; 1808 private boolean iOnline; 1809 public Online(Enrollment enrollment, boolean online) { 1810 iEnrollment = enrollment; 1811 iOnline = online; 1812 } 1813 1814 protected boolean skip(Section section) { 1815 return iOnline != section.isOnline(); 1816 } 1817 1818 @Override 1819 public Iterator<Section> iterator() { 1820 return new Iterator<Section>() { 1821 Iterator<Section> i = iEnrollment.getSections().iterator(); 1822 Section next = null; 1823 boolean hasNext = nextSection(); 1824 1825 private boolean nextSection() { 1826 while (i.hasNext()) { 1827 Section r = i.next(); 1828 if (!skip(r)) { 1829 next = r; 1830 return true; 1831 } 1832 } 1833 return false; 1834 } 1835 1836 @Override 1837 public Section next() { 1838 try { 1839 return next; 1840 } finally { 1841 hasNext = nextSection(); 1842 } 1843 } 1844 @Override 1845 public boolean hasNext() { return hasNext; } 1846 @Override 1847 public void remove() { throw new UnsupportedOperationException(); } 1848 }; 1849 } 1850 } 1851 1852 @Override 1853 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 1854 StudentQualityContext cx = getContext(assignment); 1855 if (iContext.isDebug()) 1856 for (Type type: iContext.getTypes()) 1857 info.put("[Schedule Quality] " + type.getName(), String.valueOf(cx.getTotalPenalty(type))); 1858 } 1859 1860 @Override 1861 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 1862 } 1863 1864 public String toString(Assignment<Request, Enrollment> assignment) { 1865 String ret = ""; 1866 StudentQualityContext cx = getContext(assignment); 1867 for (Type type: iContext.getTypes()) { 1868 int p = cx.getTotalPenalty(type); 1869 if (p != 0) { 1870 ret += (ret.isEmpty() ? "" : ", ") + type.getAbbv() + ": " + p; 1871 } 1872 } 1873 return ret; 1874 } 1875 1876 public boolean hasDistanceConflict(Student student, Section s1, Section s2) { 1877 if (student.isNeedShortDistances()) 1878 return Type.ShortDistance.inConflict(iContext, s1, s2); 1879 else 1880 return Type.Distance.inConflict(iContext, s1, s2); 1881 } 1882}