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