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