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