001package org.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collection; 006import java.util.HashSet; 007import java.util.HashMap; 008import java.util.List; 009import java.util.Locale; 010import java.util.Map; 011import java.util.Set; 012 013import org.cpsolver.coursett.Constants; 014import org.cpsolver.coursett.constraint.ClassLimitConstraint; 015import org.cpsolver.coursett.constraint.DepartmentSpreadConstraint; 016import org.cpsolver.coursett.constraint.FlexibleConstraint; 017import org.cpsolver.coursett.constraint.GroupConstraint; 018import org.cpsolver.coursett.constraint.InstructorConstraint; 019import org.cpsolver.coursett.constraint.JenrlConstraint; 020import org.cpsolver.coursett.constraint.RoomConstraint; 021import org.cpsolver.coursett.constraint.SpreadConstraint; 022import org.cpsolver.coursett.criteria.BackToBackInstructorPreferences; 023import org.cpsolver.coursett.criteria.BrokenTimePatterns; 024import org.cpsolver.coursett.criteria.DepartmentBalancingPenalty; 025import org.cpsolver.coursett.criteria.DistributionPreferences; 026import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion; 027import org.cpsolver.coursett.criteria.Perturbations; 028import org.cpsolver.coursett.criteria.RoomPreferences; 029import org.cpsolver.coursett.criteria.RoomViolations; 030import org.cpsolver.coursett.criteria.SameSubpartBalancingPenalty; 031import org.cpsolver.coursett.criteria.StudentCommittedConflict; 032import org.cpsolver.coursett.criteria.StudentConflict; 033import org.cpsolver.coursett.criteria.StudentDistanceConflict; 034import org.cpsolver.coursett.criteria.StudentHardConflict; 035import org.cpsolver.coursett.criteria.StudentOverlapConflict; 036import org.cpsolver.coursett.criteria.TimePreferences; 037import org.cpsolver.coursett.criteria.TimeViolations; 038import org.cpsolver.coursett.criteria.TooBigRooms; 039import org.cpsolver.coursett.criteria.UselessHalfHours; 040import org.cpsolver.coursett.criteria.placement.DeltaTimePreference; 041import org.cpsolver.coursett.criteria.placement.HardConflicts; 042import org.cpsolver.coursett.criteria.placement.PotentialHardConflicts; 043import org.cpsolver.coursett.criteria.placement.WeightedHardConflicts; 044import org.cpsolver.ifs.assignment.Assignment; 045import org.cpsolver.ifs.constant.ConstantModel; 046import org.cpsolver.ifs.criteria.Criterion; 047import org.cpsolver.ifs.model.Constraint; 048import org.cpsolver.ifs.model.GlobalConstraint; 049import org.cpsolver.ifs.model.InfoProvider; 050import org.cpsolver.ifs.model.WeakeningConstraint; 051import org.cpsolver.ifs.solution.Solution; 052import org.cpsolver.ifs.termination.TerminationCondition; 053import org.cpsolver.ifs.util.DataProperties; 054import org.cpsolver.ifs.util.DistanceMetric; 055 056 057/** 058 * Timetable model. 059 * 060 * @version CourseTT 1.3 (University Course Timetabling)<br> 061 * Copyright (C) 2006 - 2014 Tomas Muller<br> 062 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 063 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 064 * <br> 065 * This library is free software; you can redistribute it and/or modify 066 * it under the terms of the GNU Lesser General Public License as 067 * published by the Free Software Foundation; either version 3 of the 068 * License, or (at your option) any later version. <br> 069 * <br> 070 * This library is distributed in the hope that it will be useful, but 071 * WITHOUT ANY WARRANTY; without even the implied warranty of 072 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 073 * Lesser General Public License for more details. <br> 074 * <br> 075 * You should have received a copy of the GNU Lesser General Public 076 * License along with this library; if not see 077 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 078 */ 079 080public class TimetableModel extends ConstantModel<Lecture, Placement> { 081 private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class); 082 private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", 083 new java.text.DecimalFormatSymbols(Locale.US)); 084 085 private List<InstructorConstraint> iInstructorConstraints = new ArrayList<InstructorConstraint>(); 086 private List<JenrlConstraint> iJenrlConstraints = new ArrayList<JenrlConstraint>(); 087 private List<RoomConstraint> iRoomConstraints = new ArrayList<RoomConstraint>(); 088 private List<DepartmentSpreadConstraint> iDepartmentSpreadConstraints = new ArrayList<DepartmentSpreadConstraint>(); 089 private List<SpreadConstraint> iSpreadConstraints = new ArrayList<SpreadConstraint>(); 090 private List<GroupConstraint> iGroupConstraints = new ArrayList<GroupConstraint>(); 091 private List<ClassLimitConstraint> iClassLimitConstraints = new ArrayList<ClassLimitConstraint>(); 092 private List<FlexibleConstraint> iFlexibleConstraints = new ArrayList<FlexibleConstraint>(); 093 private DataProperties iProperties = null; 094 private int iYear = -1; 095 private List<BitSet> iWeeks = null; 096 private boolean iOnFlySectioning = false; 097 098 private HashSet<Student> iAllStudents = new HashSet<Student>(); 099 100 private DistanceMetric iDistanceMetric = null; 101 102 private StudentSectioning iStudentSectioning = null; 103 private List<StudentGroup> iStudentGroups = new ArrayList<StudentGroup>(); 104 105 @SuppressWarnings("unchecked") 106 public TimetableModel(DataProperties properties) { 107 super(); 108 iProperties = properties; 109 iDistanceMetric = new DistanceMetric(properties); 110 if (properties.getPropertyBoolean("OnFlySectioning.Enabled", false)) { 111 addModelListener(new OnFlySectioning(this)); iOnFlySectioning = true; 112 } 113 String criteria = properties.getProperty("General.Criteria", 114 // Objectives 115 StudentConflict.class.getName() + ";" + 116 StudentDistanceConflict.class.getName() + ";" + 117 StudentHardConflict.class.getName() + ";" + 118 StudentCommittedConflict.class.getName() + ";" + 119 StudentOverlapConflict.class.getName() + ";" + 120 UselessHalfHours.class.getName() + ";" + 121 BrokenTimePatterns.class.getName() + ";" + 122 TooBigRooms.class.getName() + ";" + 123 TimePreferences.class.getName() + ";" + 124 RoomPreferences.class.getName() + ";" + 125 DistributionPreferences.class.getName() + ";" + 126 SameSubpartBalancingPenalty.class.getName() + ";" + 127 DepartmentBalancingPenalty.class.getName() + ";" + 128 BackToBackInstructorPreferences.class.getName() + ";" + 129 Perturbations.class.getName() + ";" + 130 // Additional placement selection criteria 131 // AssignmentCount.class.getName() + ";" + 132 DeltaTimePreference.class.getName() + ";" + 133 HardConflicts.class.getName() + ";" + 134 PotentialHardConflicts.class.getName() + ";" + 135 FlexibleConstraintCriterion.class.getName() + ";" + 136 WeightedHardConflicts.class.getName()); 137 // Interactive mode -- count time / room violations 138 if (properties.getPropertyBoolean("General.InteractiveMode", false)) 139 criteria += ";" + TimeViolations.class.getName() + ";" + RoomViolations.class.getName(); 140 // Additional (custom) criteria 141 criteria += ";" + properties.getProperty("General.AdditionalCriteria", ""); 142 for (String criterion: criteria.split("\\;")) { 143 if (criterion == null || criterion.isEmpty()) continue; 144 try { 145 Class<Criterion<Lecture, Placement>> clazz = (Class<Criterion<Lecture, Placement>>)Class.forName(criterion); 146 Criterion<Lecture, Placement> c = clazz.newInstance(); 147 c.configure(properties); 148 addCriterion(c); 149 } catch (Exception e) { 150 sLogger.error("Unable to use " + criterion + ": " + e.getMessage()); 151 } 152 } 153 try { 154 String studentSectioningClassName = properties.getProperty("StudentSectioning.Class", DefaultStudentSectioning.class.getName()); 155 Class<?> studentSectioningClass = Class.forName(studentSectioningClassName); 156 iStudentSectioning = (StudentSectioning)studentSectioningClass.getConstructor(TimetableModel.class).newInstance(this); 157 } catch (Exception e) { 158 sLogger.error("Failed to load custom student sectioning class: " + e.getMessage()); 159 iStudentSectioning = new DefaultStudentSectioning(this); 160 } 161 if (iStudentSectioning instanceof InfoProvider<?, ?>) { 162 getInfoProviders().add((InfoProvider<Lecture, Placement>)iStudentSectioning); 163 } 164 } 165 166 public DistanceMetric getDistanceMetric() { 167 return iDistanceMetric; 168 } 169 170 /** 171 * Returns interface to the student sectioning functions needed during course timetabling. 172 * Defaults to an instance of {@link DefaultStudentSectioning}, can be changed using the StudentSectioning.Class parameter. 173 * @return student sectioning 174 */ 175 public StudentSectioning getStudentSectioning() { 176 return iStudentSectioning; 177 } 178 179 public DataProperties getProperties() { 180 return iProperties; 181 } 182 183 /** 184 * Student final sectioning (switching students between sections of the same 185 * class in order to minimize overall number of student conflicts) 186 * @param assignment current assignment 187 * @param termination optional termination condition 188 */ 189 public void switchStudents(Assignment<Lecture, Placement> assignment, TerminationCondition<Lecture, Placement> termination) { 190 getStudentSectioning().switchStudents(new Solution<Lecture, Placement>(this, assignment), termination); 191 } 192 193 /** 194 * Student final sectioning (switching students between sections of the same 195 * class in order to minimize overall number of student conflicts) 196 * @param assignment current assignment 197 */ 198 public void switchStudents(Assignment<Lecture, Placement> assignment) { 199 getStudentSectioning().switchStudents(new Solution<Lecture, Placement>(this, assignment), null); 200 } 201 202 public Map<String, String> getBounds(Assignment<Lecture, Placement> assignment) { 203 Map<String, String> ret = new HashMap<String, String>(); 204 ret.put("Room preferences min", "" + getCriterion(RoomPreferences.class).getBounds(assignment)[0]); 205 ret.put("Room preferences max", "" + getCriterion(RoomPreferences.class).getBounds(assignment)[1]); 206 ret.put("Time preferences min", "" + getCriterion(TimePreferences.class).getBounds(assignment)[0]); 207 ret.put("Time preferences max", "" + getCriterion(TimePreferences.class).getBounds(assignment)[1]); 208 ret.put("Distribution preferences min", "" + getCriterion(DistributionPreferences.class).getBounds(assignment)[0]); 209 ret.put("Distribution preferences max", "" + getCriterion(DistributionPreferences.class).getBounds(assignment)[1]); 210 if (getProperties().getPropertyBoolean("General.UseDistanceConstraints", false)) { 211 ret.put("Back-to-back instructor preferences max", "" + getCriterion(BackToBackInstructorPreferences.class).getBounds(assignment)[1]); 212 } 213 ret.put("Too big rooms max", "" + getCriterion(TooBigRooms.class).getBounds(assignment)[0]); 214 ret.put("Useless half-hours", "" + getCriterion(UselessHalfHours.class).getBounds(assignment)[0]); 215 return ret; 216 } 217 218 /** Global info */ 219 @Override 220 public Map<String, String> getInfo(Assignment<Lecture, Placement> assignment) { 221 Map<String, String> ret = super.getInfo(assignment); 222 ret.put("Memory usage", getMem()); 223 224 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class); 225 Criterion<Lecture, Placement> rv = getCriterion(RoomViolations.class); 226 ret.put("Room preferences", getPerc(rp.getValue(assignment), rp.getBounds(assignment)[0], rp.getBounds(assignment)[1]) + "% (" + Math.round(rp.getValue(assignment)) + ")" 227 + (rv != null && rv.getValue(assignment) >= 0.5 ? " [hard:" + Math.round(rv.getValue(assignment)) + "]" : "")); 228 229 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class); 230 Criterion<Lecture, Placement> tv = getCriterion(TimeViolations.class); 231 ret.put("Time preferences", getPerc(tp.getValue(assignment), tp.getBounds(assignment)[0], tp.getBounds(assignment)[1]) + "% (" + sDoubleFormat.format(tp.getValue(assignment)) + ")" 232 + (tv != null && tv.getValue(assignment) >= 0.5 ? " [hard:" + Math.round(tv.getValue(assignment)) + "]" : "")); 233 234 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class); 235 ret.put("Distribution preferences", getPerc(dp.getValue(assignment), dp.getBounds(assignment)[0], dp.getBounds(assignment)[1]) + "% (" + sDoubleFormat.format(dp.getValue(assignment)) + ")"); 236 237 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class); 238 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class); 239 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class); 240 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class); 241 ret.put("Student conflicts", Math.round(scc.getValue(assignment) + sc.getValue(assignment)) + 242 " [committed:" + Math.round(scc.getValue(assignment)) + 243 ", distance:" + Math.round(sdc.getValue(assignment)) + 244 ", hard:" + Math.round(shc.getValue(assignment)) + "]"); 245 246 if (!getSpreadConstraints().isEmpty()) { 247 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class); 248 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(assignment), ip.getBounds(assignment)[0], ip.getBounds(assignment)[1]) + "% (" + Math.round(ip.getValue(assignment)) + ")"); 249 } 250 251 if (!getDepartmentSpreadConstraints().isEmpty()) { 252 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class); 253 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue(assignment))); 254 } 255 256 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class); 257 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue(assignment))); 258 259 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class); 260 ret.put("Too big rooms", getPercRev(tbr.getValue(assignment), tbr.getBounds(assignment)[1], tbr.getBounds(assignment)[0]) + "% (" + Math.round(tbr.getValue(assignment)) + ")"); 261 262 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class); 263 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class); 264 265 ret.put("Useless half-hours", getPercRev(uh.getValue(assignment) + bt.getValue(assignment), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds(assignment)[0]) + 266 "% (" + Math.round(uh.getValue(assignment)) + " + " + Math.round(bt.getValue(assignment)) + ")"); 267 return ret; 268 } 269 270 @Override 271 public Map<String, String> getInfo(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 272 Map<String, String> ret = super.getInfo(assignment, variables); 273 274 ret.put("Memory usage", getMem()); 275 276 Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class); 277 ret.put("Room preferences", getPerc(rp.getValue(assignment, variables), rp.getBounds(assignment, variables)[0], rp.getBounds(assignment, variables)[1]) + "% (" + Math.round(rp.getValue(assignment, variables)) + ")"); 278 279 Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class); 280 ret.put("Time preferences", getPerc(tp.getValue(assignment, variables), tp.getBounds(assignment, variables)[0], tp.getBounds(assignment, variables)[1]) + "% (" + sDoubleFormat.format(tp.getValue(assignment, variables)) + ")"); 281 282 Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class); 283 ret.put("Distribution preferences", getPerc(dp.getValue(assignment, variables), dp.getBounds(assignment, variables)[0], dp.getBounds(assignment, variables)[1]) + "% (" + sDoubleFormat.format(dp.getValue(assignment, variables)) + ")"); 284 285 Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class); 286 Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class); 287 Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class); 288 Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class); 289 ret.put("Student conflicts", Math.round(scc.getValue(assignment, variables) + sc.getValue(assignment, variables)) + 290 " [committed:" + Math.round(scc.getValue(assignment, variables)) + 291 ", distance:" + Math.round(sdc.getValue(assignment, variables)) + 292 ", hard:" + Math.round(shc.getValue(assignment, variables)) + "]"); 293 294 if (!getSpreadConstraints().isEmpty()) { 295 Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class); 296 ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(assignment, variables), ip.getBounds(assignment, variables)[0], ip.getBounds(assignment, variables)[1]) + "% (" + Math.round(ip.getValue(assignment, variables)) + ")"); 297 } 298 299 if (!getDepartmentSpreadConstraints().isEmpty()) { 300 Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class); 301 ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue(assignment, variables))); 302 } 303 304 Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class); 305 ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue(assignment, variables))); 306 307 Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class); 308 ret.put("Too big rooms", getPercRev(tbr.getValue(assignment, variables), tbr.getBounds(assignment, variables)[1], tbr.getBounds(assignment, variables)[0]) + "% (" + Math.round(tbr.getValue(assignment, variables)) + ")"); 309 310 Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class); 311 Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class); 312 313 ret.put("Useless half-hours", getPercRev(uh.getValue(assignment, variables) + bt.getValue(assignment, variables), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds(assignment, variables)[0]) + 314 "% (" + Math.round(uh.getValue(assignment, variables)) + " + " + Math.round(bt.getValue(assignment, variables)) + ")"); 315 return ret; 316 } 317 318 @Override 319 public void addConstraint(Constraint<Lecture, Placement> constraint) { 320 super.addConstraint(constraint); 321 if (constraint instanceof InstructorConstraint) { 322 iInstructorConstraints.add((InstructorConstraint) constraint); 323 } else if (constraint instanceof JenrlConstraint) { 324 iJenrlConstraints.add((JenrlConstraint) constraint); 325 } else if (constraint instanceof RoomConstraint) { 326 iRoomConstraints.add((RoomConstraint) constraint); 327 } else if (constraint instanceof DepartmentSpreadConstraint) { 328 iDepartmentSpreadConstraints.add((DepartmentSpreadConstraint) constraint); 329 } else if (constraint instanceof SpreadConstraint) { 330 iSpreadConstraints.add((SpreadConstraint) constraint); 331 } else if (constraint instanceof ClassLimitConstraint) { 332 iClassLimitConstraints.add((ClassLimitConstraint) constraint); 333 } else if (constraint instanceof GroupConstraint) { 334 iGroupConstraints.add((GroupConstraint) constraint); 335 } else if (constraint instanceof FlexibleConstraint) { 336 iFlexibleConstraints.add((FlexibleConstraint) constraint); 337 } 338 } 339 340 @Override 341 public void removeConstraint(Constraint<Lecture, Placement> constraint) { 342 super.removeConstraint(constraint); 343 if (constraint instanceof InstructorConstraint) { 344 iInstructorConstraints.remove(constraint); 345 } else if (constraint instanceof JenrlConstraint) { 346 iJenrlConstraints.remove(constraint); 347 } else if (constraint instanceof RoomConstraint) { 348 iRoomConstraints.remove(constraint); 349 } else if (constraint instanceof DepartmentSpreadConstraint) { 350 iDepartmentSpreadConstraints.remove(constraint); 351 } else if (constraint instanceof SpreadConstraint) { 352 iSpreadConstraints.remove(constraint); 353 } else if (constraint instanceof ClassLimitConstraint) { 354 iClassLimitConstraints.remove(constraint); 355 } else if (constraint instanceof GroupConstraint) { 356 iGroupConstraints.remove(constraint); 357 } else if (constraint instanceof FlexibleConstraint) { 358 iFlexibleConstraints.remove(constraint); 359 } 360 } 361 362 /** The list of all instructor constraints 363 * @return list of instructor constraints 364 **/ 365 public List<InstructorConstraint> getInstructorConstraints() { 366 return iInstructorConstraints; 367 } 368 369 /** The list of all group constraints 370 * @return list of group (distribution) constraints 371 **/ 372 public List<GroupConstraint> getGroupConstraints() { 373 return iGroupConstraints; 374 } 375 376 /** The list of all jenrl constraints 377 * @return list of join enrollment constraints 378 **/ 379 public List<JenrlConstraint> getJenrlConstraints() { 380 return iJenrlConstraints; 381 } 382 383 /** The list of all room constraints 384 * @return list of room constraints 385 **/ 386 public List<RoomConstraint> getRoomConstraints() { 387 return iRoomConstraints; 388 } 389 390 /** The list of all departmental spread constraints 391 * @return list of department spread constraints 392 **/ 393 public List<DepartmentSpreadConstraint> getDepartmentSpreadConstraints() { 394 return iDepartmentSpreadConstraints; 395 } 396 397 public List<SpreadConstraint> getSpreadConstraints() { 398 return iSpreadConstraints; 399 } 400 401 public List<ClassLimitConstraint> getClassLimitConstraints() { 402 return iClassLimitConstraints; 403 } 404 405 public List<FlexibleConstraint> getFlexibleConstraints() { 406 return iFlexibleConstraints; 407 } 408 409 @Override 410 public double getTotalValue(Assignment<Lecture, Placement> assignment) { 411 double ret = 0; 412 for (Criterion<Lecture, Placement> criterion: getCriteria()) 413 ret += criterion.getWeightedValue(assignment); 414 return ret; 415 } 416 417 @Override 418 public double getTotalValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) { 419 double ret = 0; 420 for (Criterion<Lecture, Placement> criterion: getCriteria()) 421 ret += criterion.getWeightedValue(assignment, variables); 422 return ret; 423 } 424 425 public int getYear() { 426 return iYear; 427 } 428 429 public void setYear(int year) { 430 iYear = year; 431 } 432 433 public Set<Student> getAllStudents() { 434 return iAllStudents; 435 } 436 437 public void addStudent(Student student) { 438 iAllStudents.add(student); 439 } 440 441 public void removeStudent(Student student) { 442 iAllStudents.remove(student); 443 } 444 445 /** 446 * Returns amount of allocated memory. 447 * 448 * @return amount of allocated memory to be written in the log 449 */ 450 public static synchronized String getMem() { 451 Runtime rt = Runtime.getRuntime(); 452 return sDoubleFormat.format(((double) (rt.totalMemory() - rt.freeMemory())) / 1048576) + "M"; 453 } 454 455 456 /** 457 * Returns the set of conflicting variables with this value, if it is 458 * assigned to its variable. Conflicts with constraints that implement 459 * {@link WeakeningConstraint} are ignored. 460 * @param assignment current assignment 461 * @param value placement that is being considered 462 * @return computed conflicting assignments 463 */ 464 public Set<Placement> conflictValuesSkipWeakeningConstraints(Assignment<Lecture, Placement> assignment, Placement value) { 465 Set<Placement> conflictValues = new HashSet<Placement>(); 466 for (Constraint<Lecture, Placement> constraint : value.variable().hardConstraints()) { 467 if (constraint instanceof WeakeningConstraint) continue; 468 if (constraint instanceof GroupConstraint) 469 ((GroupConstraint)constraint).computeConflictsNoForwardCheck(assignment, value, conflictValues); 470 else 471 constraint.computeConflicts(assignment, value, conflictValues); 472 } 473 for (GlobalConstraint<Lecture, Placement> constraint : globalConstraints()) { 474 if (constraint instanceof WeakeningConstraint) continue; 475 constraint.computeConflicts(assignment, value, conflictValues); 476 } 477 return conflictValues; 478 } 479 480 /** 481 * The method creates date patterns (bitsets) which represent the weeks of a 482 * semester. 483 * 484 * @return a list of BitSets which represents the weeks of a semester. 485 */ 486 public List<BitSet> getWeeks() { 487 if (iWeeks == null) { 488 String defaultDatePattern = getProperties().getProperty("DatePattern.CustomDatePattern", null); 489 if (defaultDatePattern == null){ 490 defaultDatePattern = getProperties().getProperty("DatePattern.Default"); 491 } 492 BitSet fullTerm = null; 493 if (defaultDatePattern == null) { 494 // Take the date pattern that is being used most often 495 Map<Long, Integer> counter = new HashMap<Long, Integer>(); 496 int max = 0; String name = null; Long id = null; 497 for (Lecture lecture: variables()) { 498 if (lecture.isCommitted()) continue; 499 for (TimeLocation time: lecture.timeLocations()) { 500 if (time.getWeekCode() != null && time.getDatePatternId() != null) { 501 int count = 1; 502 if (counter.containsKey(time.getDatePatternId())) 503 count += counter.get(time.getDatePatternId()); 504 counter.put(time.getDatePatternId(), count); 505 if (count > max) { 506 max = count; fullTerm = time.getWeekCode(); name = time.getDatePatternName(); id = time.getDatePatternId(); 507 } 508 } 509 } 510 } 511 sLogger.info("Using date pattern " + name + " (id " + id + ") as the default."); 512 } else { 513 // Create default date pattern 514 fullTerm = new BitSet(defaultDatePattern.length()); 515 for (int i = 0; i < defaultDatePattern.length(); i++) { 516 if (defaultDatePattern.charAt(i) == 49) { 517 fullTerm.set(i); 518 } 519 } 520 } 521 522 if (fullTerm == null) return null; 523 524 iWeeks = new ArrayList<BitSet>(); 525 if (getProperties().getPropertyBoolean("DatePattern.ShiftWeeks", false)) { 526 // Cut date pattern into weeks (each week takes 7 consecutive bits, starting on the next positive bit) 527 for (int i = fullTerm.nextSetBit(0); i < fullTerm.length(); ) { 528 if (!fullTerm.get(i)) { 529 i++; continue; 530 } 531 BitSet w = new BitSet(i + 7); 532 for (int j = 0; j < 7; j++) 533 if (fullTerm.get(i + j)) w.set(i + j); 534 iWeeks.add(w); 535 i += 7; 536 } 537 } else { 538 // Cut date pattern into weeks (each week takes 7 consecutive bits starting on the first bit of the default date pattern, no pauses between weeks) 539 for (int i = fullTerm.nextSetBit(0); i < fullTerm.length(); ) { 540 BitSet w = new BitSet(i + 7); 541 for (int j = 0; j < 7; j++) 542 if (fullTerm.get(i + j)) w.set(i + j); 543 iWeeks.add(w); 544 i += 7; 545 } 546 } 547 } 548 return iWeeks; 549 } 550 551 public List<StudentGroup> getStudentGroups() { return iStudentGroups; } 552 public void addStudentGroup(StudentGroup group) { iStudentGroups.add(group); } 553 554 Map<Student, Set<Lecture>> iBestEnrollment = null; 555 @Override 556 public void saveBest(Assignment<Lecture, Placement> assignment) { 557 super.saveBest(assignment); 558 if (iOnFlySectioning) { 559 if (iBestEnrollment == null) 560 iBestEnrollment = new HashMap<Student, Set<Lecture>>(); 561 else 562 iBestEnrollment.clear(); 563 for (Student student: getAllStudents()) 564 iBestEnrollment.put(student, new HashSet<Lecture>(student.getLectures())); 565 } 566 } 567 568 /** 569 * Increment {@link JenrlConstraint} between the given two classes by the given student 570 */ 571 protected void incJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) { 572 if (l1.equals(l2)) return; 573 JenrlConstraint jenrl = l1.jenrlConstraint(l2); 574 if (jenrl == null) { 575 jenrl = new JenrlConstraint(); 576 jenrl.addVariable(l1); 577 jenrl.addVariable(l2); 578 addConstraint(jenrl); 579 } 580 jenrl.incJenrl(assignment, student); 581 } 582 583 /** 584 * Decrement {@link JenrlConstraint} between the given two classes by the given student 585 */ 586 protected void decJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) { 587 if (l1.equals(l2)) return; 588 JenrlConstraint jenrl = l1.jenrlConstraint(l2); 589 if (jenrl != null) { 590 jenrl.decJenrl(assignment, student); 591 } 592 } 593 594 @Override 595 public void restoreBest(Assignment<Lecture, Placement> assignment) { 596 if (iOnFlySectioning && iBestEnrollment != null) { 597 598 // unassign changed classes 599 for (Lecture lecture: variables()) { 600 Placement placement = assignment.getValue(lecture); 601 if (placement != null && !placement.equals(lecture.getBestAssignment())) 602 assignment.unassign(0, lecture); 603 } 604 605 for (Map.Entry<Student, Set<Lecture>> entry: iBestEnrollment.entrySet()) { 606 Student student = entry.getKey(); 607 Set<Lecture> lectures = entry.getValue(); 608 Set<Configuration> configs = new HashSet<Configuration>(); 609 for (Lecture lecture: lectures) 610 if (lecture.getConfiguration() != null) configs.add(lecture.getConfiguration()); 611 612 // drop student from classes that are not in the best enrollment 613 for (Lecture lecture: new ArrayList<Lecture>(student.getLectures())) { 614 if (lectures.contains(lecture)) continue; // included in best 615 for (Lecture other: student.getLectures()) 616 decJenrl(assignment, student, lecture, other); 617 lecture.removeStudent(assignment, student); 618 student.removeLecture(lecture); 619 if (lecture.getConfiguration() != null && !configs.contains(lecture.getConfiguration())) 620 student.removeConfiguration(lecture.getConfiguration()); 621 } 622 623 // add student to classes that are in the best enrollment 624 for (Lecture lecture: lectures) { 625 if (student.getLectures().contains(lecture)) continue; // already in 626 for (Lecture other: student.getLectures()) 627 incJenrl(assignment, student, lecture, other); 628 lecture.addStudent(assignment, student); 629 student.addLecture(lecture); 630 student.addConfiguration(lecture.getConfiguration()); 631 } 632 } 633 // remove empty joint enrollments 634 for (JenrlConstraint jenrl: new ArrayList<JenrlConstraint>(getJenrlConstraints())) { 635 if (jenrl.getNrStudents() == 0) { 636 jenrl.getContext(assignment).unassigned(assignment, null); 637 Object[] vars = jenrl.variables().toArray(); 638 for (int k = 0; k < vars.length; k++) 639 jenrl.removeVariable((Lecture) vars[k]); 640 removeConstraint(jenrl); 641 } 642 } 643 } 644 super.restoreBest(assignment); 645 } 646}