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.getUnavailabilityDistanceInMinutes(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.getUnavailabilityDistanceInMinutes(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 private Integer iUnavailabilityMaxTravelTime = null; 1262 private DistanceMetric iUnavailabilityDistanceMetric = null; 1263 1264 public Context(DistanceMetric dm, DataProperties config) { 1265 iDistanceMetric = (dm == null ? new DistanceMetric(config) : dm); 1266 iDebug = config.getPropertyBoolean("StudentQuality.Debug", false); 1267 iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit); 1268 iLunchStart = config.getPropertyInt("StudentLunch.StartSlot", (11 * 60) / 5); 1269 iLunchEnd = config.getPropertyInt("StudentLunch.EndStart", (13 * 60) / 5); 1270 iLunchLength = config.getPropertyInt("StudentLunch.Length", 30 / 5); 1271 iMaxTravelGap = config.getPropertyInt("TravelTime.MaxTravelGap", 12); 1272 iWorkDayLimit = config.getPropertyInt("WorkDay.WorkDayLimit", 6 * 12); 1273 iBackToBackDistance = config.getPropertyInt("StudentWeights.BackToBackDistance", 6); 1274 iAccBackToBackDistance = config.getPropertyInt("Accommodations.BackToBackDistance", 6); 1275 iEarlySlot = config.getPropertyInt("WorkDay.EarlySlot", 102); 1276 iLateSlot = config.getPropertyInt("WorkDay.LateSlot", 210); 1277 iFreeTimeAccommodation = config.getProperty("Accommodations.FreeTimeReference", iFreeTimeAccommodation); 1278 iBackToBackAccommodation = config.getProperty("Accommodations.BackToBackReference", iBackToBackAccommodation); 1279 iBreakBetweenClassesAccommodation = config.getProperty("Accommodations.BreakBetweenClassesReference", iBreakBetweenClassesAccommodation); 1280 iTypes = new ArrayList<Type>(); 1281 for (Type t: Type.values()) 1282 if (config.getPropertyDouble(t.getWeightName(), t.getWeightDefault()) != 0.0) 1283 iTypes.add(t); 1284 iUnavailabilityMaxTravelTime = config.getPropertyInteger("Distances.UnavailabilityMaxTravelTimeInMinutes", null); 1285 if (iUnavailabilityMaxTravelTime != null && iUnavailabilityMaxTravelTime != iDistanceMetric.getMaxTravelDistanceInMinutes()) { 1286 iUnavailabilityDistanceMetric = new DistanceMetric(iDistanceMetric); 1287 iUnavailabilityDistanceMetric.setMaxTravelDistanceInMinutes(iUnavailabilityMaxTravelTime); 1288 iUnavailabilityDistanceMetric.setComputeDistanceConflictsBetweenNonBTBClasses(true); 1289 } 1290 } 1291 1292 public DistanceMetric getDistanceMetric() { 1293 return iDistanceMetric; 1294 } 1295 1296 public DistanceMetric getUnavailabilityDistanceMetric() { 1297 return (iUnavailabilityDistanceMetric == null ? iDistanceMetric : iUnavailabilityDistanceMetric); 1298 } 1299 1300 public boolean isDebug() { return iDebug; } 1301 1302 public double getTimeOverlapMaxLimit() { return iTimeOverlapMaxLimit; } 1303 public int getLunchStart() { return iLunchStart; } 1304 public int getLunchEnd() { return iLunchEnd; } 1305 public int getLunchLength() { return iLunchLength; } 1306 public int getMaxTravelGap() { return iMaxTravelGap; } 1307 public int getWorkDayLimit() { return iWorkDayLimit; } 1308 public int getBackToBackDistance() { return iBackToBackDistance; } 1309 public int getAccBackToBackDistance() { return iAccBackToBackDistance; } 1310 public int getEarlySlot() { return iEarlySlot; } 1311 public int getLateSlot() { return iLateSlot; } 1312 public String getFreeTimeAccommodation() { return iFreeTimeAccommodation; } 1313 public String getBackToBackAccommodation() { return iBackToBackAccommodation; } 1314 public String getBreakBetweenClassesAccommodation() { return iBreakBetweenClassesAccommodation; } 1315 public List<Type> getTypes() { return iTypes; } 1316 1317 private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>(); 1318 protected Integer getDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2) { 1319 ReadLock lock = iLock.readLock(); 1320 lock.lock(); 1321 try { 1322 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 1323 return other2distance == null ? null : other2distance.get(r2.getId()); 1324 } finally { 1325 lock.unlock(); 1326 } 1327 } 1328 1329 protected void setDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2, Integer distance) { 1330 WriteLock lock = iLock.writeLock(); 1331 lock.lock(); 1332 try { 1333 Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId()); 1334 if (other2distance == null) { 1335 other2distance = new HashMap<Long, Integer>(); 1336 iDistanceCache.put(r1.getId(), other2distance); 1337 } 1338 other2distance.put(r2.getId(), distance); 1339 } finally { 1340 lock.unlock(); 1341 } 1342 } 1343 1344 protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) { 1345 if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1); 1346 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar()) 1347 return 0; 1348 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null) 1349 return iDistanceMetric.getMaxTravelDistanceInMinutes(); 1350 Integer distance = getDistanceInMinutesFromCache(r1, r2); 1351 if (distance == null) { 1352 distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY()); 1353 setDistanceInMinutesFromCache(r1, r2, distance); 1354 } 1355 return distance; 1356 } 1357 1358 public int getDistanceInMinutes(Placement p1, Placement p2) { 1359 if (p1.isMultiRoom()) { 1360 if (p2.isMultiRoom()) { 1361 int dist = 0; 1362 for (RoomLocation r1 : p1.getRoomLocations()) { 1363 for (RoomLocation r2 : p2.getRoomLocations()) { 1364 dist = Math.max(dist, getDistanceInMinutes(r1, r2)); 1365 } 1366 } 1367 return dist; 1368 } else { 1369 if (p2.getRoomLocation() == null) 1370 return 0; 1371 int dist = 0; 1372 for (RoomLocation r1 : p1.getRoomLocations()) { 1373 dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation())); 1374 } 1375 return dist; 1376 } 1377 } else if (p2.isMultiRoom()) { 1378 if (p1.getRoomLocation() == null) 1379 return 0; 1380 int dist = 0; 1381 for (RoomLocation r2 : p2.getRoomLocations()) { 1382 dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2)); 1383 } 1384 return dist; 1385 } else { 1386 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 1387 return 0; 1388 return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation()); 1389 } 1390 } 1391 1392 private Map<Long, Map<Long, Integer>> iUnavailabilityDistanceCache = new HashMap<Long, Map<Long,Integer>>(); 1393 protected Integer getUnavailabilityDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2) { 1394 ReadLock lock = iLock.readLock(); 1395 lock.lock(); 1396 try { 1397 Map<Long, Integer> other2distance = iUnavailabilityDistanceCache.get(r1.getId()); 1398 return other2distance == null ? null : other2distance.get(r2.getId()); 1399 } finally { 1400 lock.unlock(); 1401 } 1402 } 1403 1404 protected void setUnavailabilityDistanceInMinutesFromCache(RoomLocation r1, RoomLocation r2, Integer distance) { 1405 WriteLock lock = iLock.writeLock(); 1406 lock.lock(); 1407 try { 1408 Map<Long, Integer> other2distance = iUnavailabilityDistanceCache.get(r1.getId()); 1409 if (other2distance == null) { 1410 other2distance = new HashMap<Long, Integer>(); 1411 iUnavailabilityDistanceCache.put(r1.getId(), other2distance); 1412 } 1413 other2distance.put(r2.getId(), distance); 1414 } finally { 1415 lock.unlock(); 1416 } 1417 } 1418 1419 protected int getUnavailabilityDistanceInMinutes(RoomLocation r1, RoomLocation r2) { 1420 if (iUnavailabilityDistanceMetric == null) return getDistanceInMinutes(r1, r2); 1421 if (r1.getId().compareTo(r2.getId()) > 0) return getUnavailabilityDistanceInMinutes(r2, r1); 1422 if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar()) 1423 return 0; 1424 if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null) 1425 return iUnavailabilityDistanceMetric.getMaxTravelDistanceInMinutes(); 1426 Integer distance = getUnavailabilityDistanceInMinutesFromCache(r1, r2); 1427 if (distance == null) { 1428 distance = iUnavailabilityDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY()); 1429 setUnavailabilityDistanceInMinutesFromCache(r1, r2, distance); 1430 } 1431 return distance; 1432 } 1433 1434 public int getUnavailabilityDistanceInMinutes(Placement p1, Unavailability p2) { 1435 if (p1.isMultiRoom()) { 1436 int dist = 0; 1437 for (RoomLocation r1 : p1.getRoomLocations()) { 1438 for (RoomLocation r2 : p2.getRooms()) { 1439 dist = Math.max(dist, getUnavailabilityDistanceInMinutes(r1, r2)); 1440 } 1441 } 1442 return dist; 1443 } else { 1444 if (p1.getRoomLocation() == null) 1445 return 0; 1446 int dist = 0; 1447 for (RoomLocation r2 : p2.getRooms()) { 1448 dist = Math.max(dist, getUnavailabilityDistanceInMinutes(p1.getRoomLocation(), r2)); 1449 } 1450 return dist; 1451 } 1452 } 1453 } 1454 1455 /** 1456 * Assignment context 1457 */ 1458 public class StudentQualityContext implements AssignmentConstraintContext<Request, Enrollment> { 1459 private int[] iTotalPenalty = null; 1460 private Set<Conflict>[] iAllConflicts = null; 1461 private Request iOldVariable = null; 1462 private Enrollment iUnassignedValue = null; 1463 1464 @SuppressWarnings("unchecked") 1465 public StudentQualityContext(Assignment<Request, Enrollment> assignment) { 1466 iTotalPenalty = new int[Type.values().length]; 1467 for (Type t: iContext.getTypes()) 1468 iTotalPenalty[t.ordinal()] = countTotalPenalty(t, assignment); 1469 if (iContext.isDebug()) { 1470 iAllConflicts = new Set[Type.values().length]; 1471 for (Type t: iContext.getTypes()) 1472 iAllConflicts[t.ordinal()] = computeAllConflicts(t, assignment); 1473 } 1474 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1475 for (Type t: iContext.getTypes()) 1476 for (Conflict c: computeAllConflicts(t, assignment)) cx.add(assignment, c); 1477 } 1478 1479 @SuppressWarnings("unchecked") 1480 public StudentQualityContext(StudentQualityContext parent) { 1481 iTotalPenalty = new int[Type.values().length]; 1482 for (Type t: iContext.getTypes()) 1483 iTotalPenalty[t.ordinal()] = parent.iTotalPenalty[t.ordinal()]; 1484 if (iContext.isDebug()) { 1485 iAllConflicts = new Set[Type.values().length]; 1486 for (Type t: iContext.getTypes()) 1487 iAllConflicts[t.ordinal()] = new HashSet<Conflict>(parent.iAllConflicts[t.ordinal()]); 1488 } 1489 } 1490 1491 @Override 1492 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1493 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1494 for (Type type: iContext.getTypes()) { 1495 iTotalPenalty[type.ordinal()] += allPenalty(type, assignment, value); 1496 for (Conflict c: allConflicts(type, assignment, value)) 1497 cx.add(assignment, c); 1498 } 1499 if (iContext.isDebug()) { 1500 sLog.debug("A:" + value.variable() + " := " + value); 1501 for (Type type: iContext.getTypes()) { 1502 int inc = allPenalty(type, assignment, value); 1503 if (inc != 0) { 1504 sLog.debug("-- " + type + " +" + inc + " A: " + value.variable() + " := " + value); 1505 for (Conflict c: allConflicts(type, assignment, value)) { 1506 sLog.debug(" -- " + c); 1507 iAllConflicts[type.ordinal()].add(c); 1508 inc -= c.getPenalty(); 1509 } 1510 if (inc != 0) { 1511 sLog.error(type + ": Different penalty for the assigned value (difference: " + inc + ")!"); 1512 } 1513 } 1514 } 1515 } 1516 } 1517 1518 /** 1519 * Called when a value is unassigned from a variable. Internal number of 1520 * time overlapping conflicts is updated, see 1521 * {@link TimeOverlapsCounter#getTotalNrConflicts(Assignment)}. 1522 */ 1523 @Override 1524 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment value) { 1525 StudentSectioningModelContext cx = ((StudentSectioningModel)getModel()).getContext(assignment); 1526 for (Type type: iContext.getTypes()) { 1527 iTotalPenalty[type.ordinal()] -= allPenalty(type, assignment, value); 1528 for (Conflict c: allConflicts(type, assignment, value)) 1529 cx.remove(assignment, c); 1530 } 1531 if (iContext.isDebug()) { 1532 sLog.debug("U:" + value.variable() + " := " + value); 1533 for (Type type: iContext.getTypes()) { 1534 int dec = allPenalty(type, assignment, value); 1535 if (dec != 0) { 1536 sLog.debug("-- " + type + " -" + dec + " U: " + value.variable() + " := " + value); 1537 for (Conflict c: allConflicts(type, assignment, value)) { 1538 sLog.debug(" -- " + c); 1539 iAllConflicts[type.ordinal()].remove(c); 1540 dec -= c.getPenalty(); 1541 } 1542 if (dec != 0) { 1543 sLog.error(type + ":Different penalty for the unassigned value (difference: " + dec + ")!"); 1544 } 1545 } 1546 } 1547 } 1548 } 1549 1550 /** 1551 * Called before a value is assigned to a variable. 1552 * @param assignment current assignment 1553 * @param iteration current iteration 1554 * @param value value to be assigned 1555 */ 1556 public void beforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1557 if (value != null) { 1558 Enrollment old = assignment.getValue(value.variable()); 1559 if (old != null) { 1560 iUnassignedValue = old; 1561 unassigned(assignment, old); 1562 } 1563 iOldVariable = value.variable(); 1564 } 1565 } 1566 1567 /** 1568 * Called after a value is assigned to a variable. 1569 * @param assignment current assignment 1570 * @param iteration current iteration 1571 * @param value value that was assigned 1572 */ 1573 public void afterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1574 iOldVariable = null; 1575 iUnassignedValue = null; 1576 if (value != null) { 1577 assigned(assignment, value); 1578 } 1579 } 1580 1581 /** 1582 * Called after a value is unassigned from a variable. 1583 * @param assignment current assignment 1584 * @param iteration current iteration 1585 * @param value value that was unassigned 1586 */ 1587 public void afterUnassigned(Assignment<Request, Enrollment> assignment, long iteration, Enrollment value) { 1588 if (value != null && !value.equals(iUnassignedValue)) { 1589 unassigned(assignment, value); 1590 } 1591 } 1592 1593 public Set<Conflict> getAllConflicts(Type type) { 1594 return iAllConflicts[type.ordinal()]; 1595 } 1596 1597 public int getTotalPenalty(Type type) { 1598 return iTotalPenalty[type.ordinal()]; 1599 } 1600 1601 public void checkTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1602 int total = countTotalPenalty(type, assignment); 1603 if (total != iTotalPenalty[type.ordinal()]) { 1604 sLog.error(type + " penalty does not match for (actual: " + total + ", count: " + iTotalPenalty[type.ordinal()] + ")!"); 1605 iTotalPenalty[type.ordinal()] = total; 1606 if (iContext.isDebug()) { 1607 Set<Conflict> conflicts = computeAllConflicts(type, assignment); 1608 for (Conflict c: conflicts) { 1609 if (!iAllConflicts[type.ordinal()].contains(c)) 1610 sLog.debug(" +add+ " + c); 1611 } 1612 for (Conflict c: iAllConflicts[type.ordinal()]) { 1613 if (!conflicts.contains(c)) 1614 sLog.debug(" -rem- " + c); 1615 } 1616 for (Conflict c: conflicts) { 1617 for (Conflict d: iAllConflicts[type.ordinal()]) { 1618 if (c.equals(d) && c.getPenalty() != d.getPenalty()) { 1619 sLog.debug(" -dif- " + c + " (other: " + d.getPenalty() + ")"); 1620 } 1621 } 1622 } 1623 iAllConflicts[type.ordinal()] = conflicts; 1624 } 1625 } 1626 } 1627 1628 public int countTotalPenalty(Type type, Assignment<Request, Enrollment> assignment) { 1629 int total = 0; 1630 for (Request r1 : getModel().variables()) { 1631 Enrollment e1 = assignment.getValue(r1); 1632 if (e1 == null || r1.equals(iOldVariable)) continue; 1633 for (Request r2 : r1.getStudent().getRequests()) { 1634 Enrollment e2 = assignment.getValue(r2); 1635 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1636 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1637 total += penalty(type, e1, e2); 1638 } 1639 } 1640 total += penalty(type, e1); 1641 } 1642 return total; 1643 } 1644 1645 public Set<Conflict> computeAllConflicts(Type type, Assignment<Request, Enrollment> assignment) { 1646 Set<Conflict> ret = new HashSet<Conflict>(); 1647 for (Request r1 : getModel().variables()) { 1648 Enrollment e1 = assignment.getValue(r1); 1649 if (e1 == null || r1.equals(iOldVariable)) continue; 1650 for (Request r2 : r1.getStudent().getRequests()) { 1651 Enrollment e2 = assignment.getValue(r2); 1652 if (e2 != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) { 1653 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1654 ret.addAll(conflicts(type, e1, e2)); 1655 } 1656 } 1657 ret.addAll(conflicts(type, e1)); 1658 } 1659 return ret; 1660 } 1661 1662 public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Student student) { 1663 Set<Conflict> ret = new HashSet<Conflict>(); 1664 for (Request r1 : student.getRequests()) { 1665 Enrollment e1 = assignment.getValue(r1); 1666 if (e1 == null) continue; 1667 for (Request r2 : student.getRequests()) { 1668 Enrollment e2 = assignment.getValue(r2); 1669 if (e2 != null && r1.getId() < r2.getId()) { 1670 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1671 ret.addAll(conflicts(type, e1, e2)); 1672 } 1673 } 1674 ret.addAll(conflicts(type, e1)); 1675 } 1676 return ret; 1677 } 1678 1679 public Set<Conflict> allConflicts(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1680 Set<Conflict> ret = new HashSet<Conflict>(); 1681 for (Request request : enrollment.getStudent().getRequests()) { 1682 if (request.equals(enrollment.getRequest())) continue; 1683 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1684 ret.addAll(conflicts(type, enrollment, assignment.getValue(request))); 1685 } 1686 } 1687 ret.addAll(conflicts(type, enrollment)); 1688 return ret; 1689 } 1690 1691 public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Student student) { 1692 int penalty = 0; 1693 for (Request r1 : student.getRequests()) { 1694 Enrollment e1 = assignment.getValue(r1); 1695 if (e1 == null) continue; 1696 for (Request r2 : student.getRequests()) { 1697 Enrollment e2 = assignment.getValue(r2); 1698 if (e2 != null && r1.getId() < r2.getId()) { 1699 if (type.isApplicable(iContext, r1.getStudent(), r1, r2)) 1700 penalty += penalty(type, e1, e2); 1701 } 1702 } 1703 penalty += penalty(type, e1); 1704 } 1705 return penalty; 1706 } 1707 1708 public int allPenalty(Type type, Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 1709 int penalty = 0; 1710 for (Request request : enrollment.getStudent().getRequests()) { 1711 if (request.equals(enrollment.getRequest())) continue; 1712 if (assignment.getValue(request) != null && !request.equals(iOldVariable)) { 1713 if (type.isApplicable(iContext, enrollment.getStudent(), enrollment.variable(), request)) 1714 penalty += penalty(type, enrollment, assignment.getValue(request)); 1715 } 1716 } 1717 penalty += penalty(type, enrollment); 1718 return penalty; 1719 } 1720 } 1721 1722 @Override 1723 public StudentQualityContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 1724 return new StudentQualityContext(assignment); 1725 } 1726 1727 @Override 1728 public StudentQualityContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, StudentQualityContext parentContext) { 1729 return new StudentQualityContext(parentContext); 1730 } 1731 1732 /** Empty iterator */ 1733 public static class Nothing implements Iterable<SctAssignment> { 1734 @Override 1735 public Iterator<SctAssignment> iterator() { 1736 return new Iterator<SctAssignment>() { 1737 @Override 1738 public SctAssignment next() { return null; } 1739 @Override 1740 public boolean hasNext() { return false; } 1741 @Override 1742 public void remove() { throw new UnsupportedOperationException(); } 1743 }; 1744 } 1745 } 1746 1747 /** Unavailabilities of a student */ 1748 public static class Unavailabilities implements Iterable<Unavailability> { 1749 private Student iStudent; 1750 public Unavailabilities(Student student) { iStudent = student; } 1751 @Override 1752 public Iterator<Unavailability> iterator() { return iStudent.getUnavailabilities().iterator(); } 1753 } 1754 1755 private static class SingleTime implements SctAssignment { 1756 private TimeLocation iTime = null; 1757 1758 public SingleTime(int start, int end) { 1759 iTime = new TimeLocation(0x7f, start, end-start, 0, 0.0, 0, null, null, new BitSet(), 0); 1760 } 1761 1762 @Override 1763 public TimeLocation getTime() { return iTime; } 1764 @Override 1765 public List<RoomLocation> getRooms() { return null; } 1766 @Override 1767 public int getNrRooms() { return 0; } 1768 @Override 1769 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1770 @Override 1771 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {} 1772 @Override 1773 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { return null; } 1774 @Override 1775 public boolean isAllowOverlap() { return false; } 1776 @Override 1777 public long getId() { return -1;} 1778 @Override 1779 public int compareById(SctAssignment a) { return 0; } 1780 1781 @Override 1782 public boolean isOverlapping(SctAssignment assignment) { 1783 return assignment.getTime() != null && getTime().shareDays(assignment.getTime()) && getTime().shareHours(assignment.getTime()); 1784 } 1785 1786 @Override 1787 public boolean isOverlapping(Set<? extends SctAssignment> assignments) { 1788 for (SctAssignment assignment : assignments) { 1789 if (isOverlapping(assignment)) return true; 1790 } 1791 return false; 1792 } 1793 } 1794 1795 /** Early/late time */ 1796 public static class SingleTimeIterable implements Iterable<SingleTime> { 1797 private SingleTime iTime = null; 1798 public SingleTimeIterable(int start, int end) { 1799 if (start < end) 1800 iTime = new SingleTime(start, end); 1801 1802 } 1803 @Override 1804 public Iterator<SingleTime> iterator() { 1805 return new Iterator<SingleTime>() { 1806 @Override 1807 public SingleTime next() { 1808 SingleTime ret = iTime; iTime = null; return ret; 1809 } 1810 @Override 1811 public boolean hasNext() { return iTime != null; } 1812 @Override 1813 public void remove() { throw new UnsupportedOperationException(); } 1814 }; 1815 } 1816 } 1817 1818 /** Free times of a student */ 1819 public static class FreeTimes implements Iterable<FreeTimeRequest> { 1820 private Student iStudent; 1821 public FreeTimes(Student student) { 1822 iStudent = student; 1823 } 1824 1825 @Override 1826 public Iterator<FreeTimeRequest> iterator() { 1827 return new Iterator<FreeTimeRequest>() { 1828 Iterator<Request> i = iStudent.getRequests().iterator(); 1829 FreeTimeRequest next = null; 1830 boolean hasNext = nextFreeTime(); 1831 1832 private boolean nextFreeTime() { 1833 while (i.hasNext()) { 1834 Request r = i.next(); 1835 if (r instanceof FreeTimeRequest) { 1836 next = (FreeTimeRequest)r; 1837 return true; 1838 } 1839 } 1840 return false; 1841 } 1842 1843 @Override 1844 public FreeTimeRequest next() { 1845 try { 1846 return next; 1847 } finally { 1848 hasNext = nextFreeTime(); 1849 } 1850 } 1851 @Override 1852 public boolean hasNext() { return hasNext; } 1853 @Override 1854 public void remove() { throw new UnsupportedOperationException(); } 1855 }; 1856 } 1857 } 1858 1859 /** Online (or not-online) classes of an enrollment */ 1860 public static class Online implements Iterable<Section> { 1861 private Enrollment iEnrollment; 1862 private boolean iOnline; 1863 public Online(Enrollment enrollment, boolean online) { 1864 iEnrollment = enrollment; 1865 iOnline = online; 1866 } 1867 1868 protected boolean skip(Section section) { 1869 return iOnline != section.isOnline(); 1870 } 1871 1872 @Override 1873 public Iterator<Section> iterator() { 1874 return new Iterator<Section>() { 1875 Iterator<Section> i = iEnrollment.getSections().iterator(); 1876 Section next = null; 1877 boolean hasNext = nextSection(); 1878 1879 private boolean nextSection() { 1880 while (i.hasNext()) { 1881 Section r = i.next(); 1882 if (!skip(r)) { 1883 next = r; 1884 return true; 1885 } 1886 } 1887 return false; 1888 } 1889 1890 @Override 1891 public Section next() { 1892 try { 1893 return next; 1894 } finally { 1895 hasNext = nextSection(); 1896 } 1897 } 1898 @Override 1899 public boolean hasNext() { return hasNext; } 1900 @Override 1901 public void remove() { throw new UnsupportedOperationException(); } 1902 }; 1903 } 1904 } 1905 1906 @Override 1907 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) { 1908 StudentQualityContext cx = getContext(assignment); 1909 if (iContext.isDebug()) 1910 for (Type type: iContext.getTypes()) 1911 info.put("[Schedule Quality] " + type.getName(), String.valueOf(cx.getTotalPenalty(type))); 1912 } 1913 1914 @Override 1915 public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) { 1916 } 1917 1918 public String toString(Assignment<Request, Enrollment> assignment) { 1919 String ret = ""; 1920 StudentQualityContext cx = getContext(assignment); 1921 for (Type type: iContext.getTypes()) { 1922 int p = cx.getTotalPenalty(type); 1923 if (p != 0) { 1924 ret += (ret.isEmpty() ? "" : ", ") + type.getAbbv() + ": " + p; 1925 } 1926 } 1927 return ret; 1928 } 1929 1930 public boolean hasDistanceConflict(Student student, Section s1, Section s2) { 1931 if (student.isNeedShortDistances()) 1932 return Type.ShortDistance.inConflict(iContext, s1, s2); 1933 else 1934 return Type.Distance.inConflict(iContext, s1, s2); 1935 } 1936}