001 package net.sf.cpsolver.exam.model; 002 003 import java.util.ArrayList; 004 import java.util.Collection; 005 import java.util.Collections; 006 import java.util.Comparator; 007 import java.util.HashSet; 008 import java.util.HashMap; 009 import java.util.Iterator; 010 import java.util.List; 011 import java.util.Locale; 012 import java.util.Map; 013 import java.util.Set; 014 import java.util.TreeSet; 015 016 import net.sf.cpsolver.ifs.model.Constraint; 017 import net.sf.cpsolver.ifs.model.Model; 018 import net.sf.cpsolver.ifs.model.Variable; 019 import net.sf.cpsolver.ifs.util.Progress; 020 import net.sf.cpsolver.ifs.util.ToolBox; 021 022 import org.apache.log4j.Logger; 023 024 /** 025 * Representation of an exam (problem variable). Each exam has defined a length 026 * (in minutes), type (whether it is a section or a course exam), seating type 027 * (whether it requires normal or alternate seating) and a maximal number of 028 * rooms. If the maximal number of rooms is zero, the exam will be timetabled 029 * only in time (it does not require a room). <br> 030 * <br> 031 * An exam can be only assigned to a period {@link ExamPeriod} that is long 032 * enough (see {@link ExamPeriod#getLength()}) and that is available for the 033 * exam (see {@link Exam#getPeriodPlacements()}). <br> 034 * <br> 035 * A set of rooms that are available in the given period (see 036 * {@link ExamRoom#isAvailable(ExamPeriod)}, 037 * {@link ExamRoomPlacement#isAvailable(ExamPeriod)}), and which together cover 038 * the size of exam (number of students attending the exam) has to be assigned 039 * to an exam. Based on the type of seating (see {@link Exam#hasAltSeating()}), 040 * either room sizes (see {@link ExamRoom#getSize()}) or alternative seating 041 * sizes (see {@link ExamRoom#getAltSize()}) are used. An exam has a list of 042 * available rooms with their penalties assiciated with (see 043 * {@link Exam#getRoomPlacements()}). <br> 044 * <br> 045 * Various penalties for an assignment of a period or a set of rooms may apply. 046 * See {@link ExamPlacement} for more details. <br> 047 * <br> 048 * 049 * @version ExamTT 1.2 (Examination Timetabling)<br> 050 * Copyright (C) 2008 - 2010 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 public class Exam extends Variable<Exam, ExamPlacement> { 069 private static boolean sAlterMaxSize = false; 070 private static Logger sLog = Logger.getLogger(Exam.class); 071 protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00", 072 new java.text.DecimalFormatSymbols(Locale.US)); 073 074 private ArrayList<ExamStudent> iStudents = new ArrayList<ExamStudent>(); 075 private ArrayList<ExamInstructor> iInstructors = new ArrayList<ExamInstructor>(); 076 private ArrayList<ExamDistributionConstraint> iDistConstraints = new ArrayList<ExamDistributionConstraint>(); 077 078 private boolean iAllowDirectConflicts = true; 079 080 private String iName = null; 081 private int iLength = 0; 082 private int iMaxRooms = 0; 083 private int iMinSize = 0; 084 private boolean iAltSeating = false; 085 private int iAveragePeriod = -1; 086 private Integer iSize = null; 087 private Integer iPrintOffset = null; 088 089 private ArrayList<ExamOwner> iOwners = new ArrayList<ExamOwner>(); 090 private List<ExamPeriodPlacement> iPeriodPlacements = null; 091 private List<ExamRoomPlacement> iRoomPlacements = null; 092 093 /** 094 * Constructor 095 * 096 * @param id 097 * exam unique id 098 * @param length 099 * exam length in minutes 100 * @param altSeating 101 * true if alternative seating is requested 102 * @param maxRooms 103 * maximum number of rooms to be used 104 * @param minSize 105 * minimal size of rooms into which an exam can be assigned (see 106 * {@link Exam#getSize()}) 107 * @param periodPlacements 108 * list of periods and their penalties 109 * {@link ExamPeriodPlacement} into which an exam can be assigned 110 * @param roomPlacements 111 * list of rooms and their penalties {@link ExamRoomPlacement} 112 * into which an exam can be assigned 113 */ 114 public Exam(long id, String name, int length, boolean altSeating, int maxRooms, int minSize, 115 java.util.List<ExamPeriodPlacement> periodPlacements, java.util.List<ExamRoomPlacement> roomPlacements) { 116 super(); 117 iId = id; 118 iName = name; 119 iLength = length; 120 iAltSeating = altSeating; 121 iMaxRooms = maxRooms; 122 iMinSize = minSize; 123 iPeriodPlacements = new ArrayList<ExamPeriodPlacement>(periodPlacements); 124 Collections.sort(iPeriodPlacements, new Comparator<ExamPeriodPlacement>() { 125 @Override 126 public int compare(ExamPeriodPlacement p1, ExamPeriodPlacement p2) { 127 return p1.getPeriod().compareTo(p2.getPeriod()); 128 } 129 }); 130 iRoomPlacements = new ArrayList<ExamRoomPlacement>(roomPlacements); 131 Collections.sort(iRoomPlacements, new Comparator<ExamRoomPlacement>() { 132 @Override 133 public int compare(ExamRoomPlacement p1, ExamRoomPlacement p2) { 134 int cmp = -Double.compare(p1.getSize(hasAltSeating()), p2.getSize(hasAltSeating())); 135 if (cmp != 0) 136 return cmp; 137 return p1.getRoom().compareTo(p2.getRoom()); 138 } 139 }); 140 } 141 142 /** 143 * Exam size, it is bigger from {@link Exam#getMinSize()} and the number of 144 * students enrolled into the exam {@link Exam#getStudents()}. If 145 * {@link Exam#getMaxRooms()} is greater than zero, an exam must be assigned 146 * into rooms which overall size (or alternative seating size if 147 * {@link Exam#hasAltSeating()}) must be equal or greater than this size. 148 */ 149 public int getSize() { 150 return (iSize == null ? Math.max(iMinSize, getStudents().size()) : iSize.intValue()); 151 } 152 153 /** 154 * Override exam size with given value (revert to default when null) 155 */ 156 public void setSizeOverride(Integer size) { 157 iSize = size; 158 } 159 160 /** 161 * Override exam size with given value (revert to default when null) 162 */ 163 public Integer getSizeOverride() { 164 return iSize; 165 } 166 167 /** 168 * Print offset -- for reporting purposes 169 */ 170 public Integer getPrintOffset() { 171 return iPrintOffset; 172 } 173 174 /** 175 * Print offset -- for reporting purposes 176 */ 177 public void setPrintOffset(Integer printOffset) { 178 iPrintOffset = printOffset; 179 } 180 181 /** 182 * Minimal exam size, see {@link Exam#getSize()} 183 */ 184 public int getMinSize() { 185 return iMinSize; 186 } 187 188 /** 189 * Minimal exam size, see {@link Exam#getSize()} 190 */ 191 public void setMinSize(int minSize) { 192 iMinSize = minSize; 193 } 194 195 /** 196 * Values (assignment of a period and a set of rooms) 197 * 198 * @return list of {@link ExamPlacement} 199 */ 200 @Override 201 public List<ExamPlacement> values() { 202 if (super.values() == null) 203 init(); 204 return super.values(); 205 } 206 207 /** 208 * Return list of possible room placements. 209 * 210 * @return list of {@link ExamRoomPlacement} 211 */ 212 public List<ExamRoomPlacement> getRoomPlacements() { 213 return iRoomPlacements; 214 } 215 216 /** 217 * Return list of possible period placements. 218 * 219 * @return list of {@link ExamPeriodPlacement} 220 */ 221 public List<ExamPeriodPlacement> getPeriodPlacements() { 222 return iPeriodPlacements; 223 } 224 225 /** 226 * Initialize exam's domain. 227 */ 228 private boolean init() { 229 if (sAlterMaxSize && iRoomPlacements.size() > 50) { 230 ExamRoomPlacement med = iRoomPlacements.get(Math.min(50, iRoomPlacements.size() / 2)); 231 setMaxRooms(Math.min(getMaxRooms(), 1 + getSize() / med.getSize(hasAltSeating()))); 232 } 233 ArrayList<ExamPlacement> values = new ArrayList<ExamPlacement>(); 234 if (getMaxRooms() == 0) { 235 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 236 values.add(new ExamPlacement(this, periodPlacement, new HashSet<ExamRoomPlacement>())); 237 } 238 } else { 239 if (getRoomPlacements().isEmpty()) { 240 sLog.error(" Exam " + getName() + " has no rooms."); 241 setValues(new ArrayList<ExamPlacement>(0)); 242 return false; 243 } 244 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 245 TreeSet<RoomSet> roomSets = new TreeSet<RoomSet>(); 246 genRoomSets(periodPlacement.getPeriod(), Math.min(100, iRoomPlacements.size()), roomSets, 0, 247 getMaxRooms(), new HashSet<ExamRoomPlacement>(), 0, 0); 248 for (RoomSet roomSet : roomSets) { 249 values.add(new ExamPlacement(this, periodPlacement, roomSet.rooms())); 250 } 251 } 252 } 253 if (values.isEmpty()) 254 sLog.error("Exam " + getName() + " has no placement."); 255 setValues(values); 256 return !values.isEmpty(); 257 } 258 259 private void genRoomSets(ExamPeriod period, int maxRoomSets, TreeSet<RoomSet> roomSets, int roomIdx, int maxRooms, 260 Set<ExamRoomPlacement> roomsSoFar, int sizeSoFar, int penaltySoFar) { 261 ExamModel model = (ExamModel) getModel(); 262 if (sizeSoFar >= getSize()) { 263 double penalty = model.getRoomSplitWeight() * (roomsSoFar.size() - 1) * (roomsSoFar.size() - 1) 264 + model.getRoomSizeWeight() * (sizeSoFar - getSize()) + model.getRoomWeight() * penaltySoFar; 265 if (roomSets.size() >= maxRoomSets) { 266 RoomSet last = roomSets.last(); 267 if (penalty < last.penalty()) { 268 roomSets.remove(last); 269 roomSets.add(new RoomSet(roomsSoFar, penalty)); 270 } 271 } else 272 roomSets.add(new RoomSet(roomsSoFar, penalty)); 273 return; 274 } 275 if (!roomSets.isEmpty()) { 276 RoomSet roomSet = roomSets.first(); 277 maxRooms = Math.min(maxRooms, (1 + roomSet.rooms().size()) - roomsSoFar.size()); 278 } 279 if (maxRooms == 0) 280 return; 281 int sizeBound = sizeSoFar; 282 for (int i = 0; i < maxRooms && roomIdx + i < iRoomPlacements.size(); i++) 283 sizeBound += iRoomPlacements.get(roomIdx + i).getSize(hasAltSeating()); 284 while (roomIdx < iRoomPlacements.size()) { 285 if (sizeBound < getSize()) 286 break; 287 ExamRoomPlacement room = iRoomPlacements.get(roomIdx); 288 if (!room.isAvailable(period)) 289 continue; 290 roomsSoFar.add(room); 291 genRoomSets(period, maxRoomSets, roomSets, roomIdx + 1, maxRooms - 1, roomsSoFar, sizeSoFar 292 + room.getSize(hasAltSeating()), penaltySoFar + room.getPenalty(period)); 293 roomsSoFar.remove(room); 294 sizeBound -= room.getSize(hasAltSeating()); 295 if (roomIdx + maxRooms < iRoomPlacements.size()) 296 sizeBound += iRoomPlacements.get(roomIdx + maxRooms).getSize(hasAltSeating()); 297 roomIdx++; 298 if (roomSets.size() == maxRoomSets) { 299 RoomSet last = roomSets.last(); 300 if (last.rooms().size() < roomsSoFar.size() + 1) 301 return; 302 } 303 } 304 } 305 306 private class RoomSet implements Comparable<RoomSet> { 307 private Set<ExamRoomPlacement> iRooms; 308 private double iPenalty; 309 310 public RoomSet(Set<ExamRoomPlacement> rooms, double penalty) { 311 iRooms = new HashSet<ExamRoomPlacement>(rooms); 312 iPenalty = penalty; 313 } 314 315 public Set<ExamRoomPlacement> rooms() { 316 return iRooms; 317 } 318 319 public double penalty() { 320 return iPenalty; 321 } 322 323 public int compareTo(Set<ExamRoomPlacement> rooms, double penalty) { 324 int cmp = Double.compare(iRooms.size(), rooms.size()); 325 if (cmp != 0) 326 return cmp; 327 cmp = Double.compare(penalty(), penalty); 328 if (cmp != 0) 329 return cmp; 330 return rooms().toString().compareTo(rooms.toString()); 331 } 332 333 @Override 334 public int compareTo(RoomSet r) { 335 return compareTo(r.rooms(), r.penalty()); 336 } 337 } 338 339 /** 340 * True if alternative seating is required ({@link ExamRoom#getAltSize()} is 341 * to be used), false if normal seating is required ( 342 * {@link ExamRoom#getSize()} is to be used). 343 * 344 * @return true if alternative seating is required, false otherwise 345 */ 346 public boolean hasAltSeating() { 347 return iAltSeating; 348 } 349 350 /** 351 * Length of the exam in minutes. The assigned period has to be of the same 352 * or greater length. 353 * 354 * @return length of the exam in minutes 355 */ 356 public int getLength() { 357 return iLength; 358 } 359 360 /** 361 * Set average period. This represents an average period that the exam was 362 * assigned to in the past. If set, it is used in exam rotation penalty 363 * {@link ExamPlacement#getRotationPenalty()} in order to put more weight on 364 * exams that were badly assigned last time(s) and ensuring some form of 365 * fairness. 366 * 367 * @param period 368 * average period 369 */ 370 public void setAveragePeriod(int period) { 371 iAveragePeriod = period; 372 } 373 374 /** 375 * Average period. This represents an average period that the exam was 376 * assigned to in the past. If set, it is used in exam rotation penalty 377 * {@link ExamPlacement#getRotationPenalty()} in order to put more weight on 378 * exams that were badly assigned last time(s) and ensuring some form of 379 * fairness. 380 * 381 * @return average period 382 */ 383 public int getAveragePeriod() { 384 return iAveragePeriod; 385 } 386 387 /** 388 * True if there is an average period assigned to the exam. This represents 389 * an average period that the exam was assigned to in the past. If set, it 390 * is used in exam rotation penalty 391 * {@link ExamPlacement#getRotationPenalty()} in order to put more weight on 392 * exams that were badly assigned last time(s) and ensuring some form of 393 * fairness. 394 */ 395 public boolean hasAveragePeriod() { 396 return iAveragePeriod >= 0; 397 } 398 399 /** 400 * True if a direct student conflict is allowed, see 401 * {@link ExamStudent#canConflict(Exam, Exam)} 402 * 403 * @return true if a direct student conflict is allowed 404 */ 405 public boolean isAllowDirectConflicts() { 406 return iAllowDirectConflicts; 407 } 408 409 /** 410 * Set whether a direct student conflict is allowed, see 411 * {@link ExamStudent#canConflict(Exam, Exam)} 412 * 413 * @param allowDirectConflicts 414 * true if a direct student conflict is allowed 415 */ 416 public void setAllowDirectConflicts(boolean allowDirectConflicts) { 417 iAllowDirectConflicts = allowDirectConflicts; 418 } 419 420 /** 421 * Adds a constraint. Called automatically when the constraint is added to 422 * the model, i.e., {@link Model#addConstraint(Constraint)} is called. 423 * 424 * @param constraint 425 * added constraint 426 */ 427 @Override 428 public void addContstraint(Constraint<Exam, ExamPlacement> constraint) { 429 if (constraint instanceof ExamStudent) 430 iStudents.add((ExamStudent) constraint); 431 if (constraint instanceof ExamDistributionConstraint) 432 iDistConstraints.add((ExamDistributionConstraint) constraint); 433 if (constraint instanceof ExamInstructor) 434 iInstructors.add((ExamInstructor) constraint); 435 super.addContstraint(constraint); 436 } 437 438 /** 439 * Removes a constraint. Called automatically when the constraint is removed 440 * from the model, i.e., {@link Model#removeConstraint(Constraint)} is 441 * called. 442 * 443 * @param constraint 444 * added constraint 445 */ 446 @Override 447 public void removeContstraint(Constraint<Exam, ExamPlacement> constraint) { 448 if (constraint instanceof ExamStudent) 449 iStudents.remove(constraint); 450 if (constraint instanceof ExamDistributionConstraint) 451 iDistConstraints.remove(constraint); 452 if (constraint instanceof ExamInstructor) 453 iInstructors.remove(constraint); 454 super.removeContstraint(constraint); 455 } 456 457 /** 458 * List of students that are enrolled in the exam 459 * 460 * @return list of {@link ExamStudent} 461 */ 462 public List<ExamStudent> getStudents() { 463 return iStudents; 464 } 465 466 /** 467 * List of distribution constraints that this exam is involved in 468 * 469 * @return list of {@link ExamDistributionConstraint} 470 */ 471 public List<ExamDistributionConstraint> getDistributionConstraints() { 472 return iDistConstraints; 473 } 474 475 /** 476 * List of instructors that are assigned to this exam 477 * 478 * @return list of {@link ExamInstructor} 479 */ 480 public List<ExamInstructor> getInstructors() { 481 return iInstructors; 482 } 483 484 /** 485 * Check all distribution constraint that this exam is involved in 486 * 487 * @param period 488 * a period to be assigned to this exam 489 * @return true, if there is no assignment of some other exam in conflict 490 * with the given period 491 */ 492 public boolean checkDistributionConstraints(ExamPeriodPlacement period) { 493 for (ExamDistributionConstraint dc : iDistConstraints) { 494 if (!dc.isHard()) 495 continue; 496 boolean before = true; 497 for (Exam exam : dc.variables()) { 498 if (exam.equals(this)) { 499 before = false; 500 continue; 501 } 502 ExamPlacement placement = exam.getAssignment(); 503 if (placement == null) 504 continue; 505 switch (dc.getType()) { 506 case ExamDistributionConstraint.sDistSamePeriod: 507 if (period.getIndex() != placement.getPeriod().getIndex()) 508 return false; 509 break; 510 case ExamDistributionConstraint.sDistDifferentPeriod: 511 if (period.getIndex() == placement.getPeriod().getIndex()) 512 return false; 513 break; 514 case ExamDistributionConstraint.sDistPrecedence: 515 if (before) { 516 if (period.getIndex() <= placement.getPeriod().getIndex()) 517 return false; 518 } else { 519 if (period.getIndex() >= placement.getPeriod().getIndex()) 520 return false; 521 } 522 break; 523 case ExamDistributionConstraint.sDistPrecedenceRev: 524 if (before) { 525 if (period.getIndex() >= placement.getPeriod().getIndex()) 526 return false; 527 } else { 528 if (period.getIndex() <= placement.getPeriod().getIndex()) 529 return false; 530 } 531 break; 532 } 533 } 534 } 535 return true; 536 } 537 538 /** 539 * Check all distribution constraint that this exam is involved in 540 * 541 * @param room 542 * a room to be assigned to this exam 543 * @return true, if there is no assignment of some other exam in conflict 544 * with the given room 545 */ 546 public boolean checkDistributionConstraints(ExamRoomPlacement room) { 547 for (ExamDistributionConstraint dc : iDistConstraints) { 548 if (!dc.isHard()) 549 continue; 550 for (Exam exam : dc.variables()) { 551 if (exam.equals(this)) 552 continue; 553 ExamPlacement placement = exam.getAssignment(); 554 if (placement == null) 555 continue; 556 switch (dc.getType()) { 557 case ExamDistributionConstraint.sDistSameRoom: 558 if (!placement.getRoomPlacements().contains(room)) 559 return false; 560 break; 561 case ExamDistributionConstraint.sDistDifferentRoom: 562 if (placement.getRoomPlacements().contains(room)) 563 return false; 564 break; 565 } 566 } 567 } 568 return true; 569 } 570 571 /** 572 * Check all soft distribution constraint that this exam is involved in 573 * 574 * @param room 575 * a room to be assigned to this exam 576 * @return sum of penalties of violated distribution constraints 577 */ 578 public int getDistributionConstraintPenalty(ExamRoomPlacement room) { 579 int penalty = 0; 580 for (ExamDistributionConstraint dc : iDistConstraints) { 581 if (dc.isHard()) 582 continue; 583 for (Exam exam : dc.variables()) { 584 if (exam.equals(this)) 585 continue; 586 ExamPlacement placement = exam.getAssignment(); 587 if (placement == null) 588 continue; 589 switch (dc.getType()) { 590 case ExamDistributionConstraint.sDistSameRoom: 591 if (!placement.getRoomPlacements().contains(room)) 592 penalty += dc.getWeight(); 593 break; 594 case ExamDistributionConstraint.sDistDifferentRoom: 595 if (placement.getRoomPlacements().contains(room)) 596 penalty += dc.getWeight(); 597 break; 598 } 599 } 600 } 601 return penalty; 602 } 603 604 /** 605 * Maximal number of rooms that can be assigned to the exam 606 * 607 * @return maximal number of rooms that can be assigned to the exam 608 */ 609 public int getMaxRooms() { 610 return iMaxRooms; 611 } 612 613 /** 614 * Set maximal number of rooms that can be assigned to the exam 615 * 616 * @param maxRooms 617 * maximal number of rooms that can be assigned to the exam 618 */ 619 public void setMaxRooms(int maxRooms) { 620 iMaxRooms = maxRooms; 621 } 622 623 /** 624 * Find best available rooms for the exam in the given period. First of all, 625 * it tries to find the minimal number of rooms that cover the size of the 626 * exam. Among these, a set of rooms of total smallest size is preferred. If 627 * the original room is available and of enough size, it is returned. All 628 * necessary checks are made (availability of rooms, room penalties, room 629 * sizes etc.). 630 * 631 * @param period 632 * given period. 633 * @return best available rooms for the exam in the given period, null if 634 * there is no valid assignment 635 */ 636 public Set<ExamRoomPlacement> findBestAvailableRooms(ExamPeriodPlacement period) { 637 if (getMaxRooms() == 0) 638 return new HashSet<ExamRoomPlacement>(); 639 double sw = ((ExamModel) getModel()).getRoomSizeWeight(); 640 double pw = ((ExamModel) getModel()).getRoomWeight(); 641 double cw = ((ExamModel) getModel()).getDistributionWeight(); 642 loop: for (int nrRooms = 1; nrRooms <= getMaxRooms(); nrRooms++) { 643 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 644 int size = 0; 645 while (rooms.size() < nrRooms && size < getSize()) { 646 int minSize = (getSize() - size) / (nrRooms - rooms.size()); 647 ExamRoomPlacement best = null; 648 double bestWeight = 0; 649 int bestSize = 0; 650 for (ExamRoomPlacement room : getRoomPlacements()) { 651 if (!room.isAvailable(period.getPeriod())) 652 continue; 653 if (room.getRoom().getPlacement(period.getPeriod()) != null) 654 continue; 655 if (rooms.contains(room)) 656 continue; 657 if (!checkDistributionConstraints(room)) 658 continue; 659 int s = room.getSize(hasAltSeating()); 660 if (s < minSize) 661 break; 662 int p = room.getPenalty(period.getPeriod()); 663 double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(room); 664 double d = 0; 665 if (!rooms.isEmpty()) { 666 for (ExamRoomPlacement r : rooms) { 667 d += r.getDistanceInMeters(room); 668 } 669 w += d / rooms.size(); 670 } 671 if (best == null || bestWeight > w) { 672 best = room; 673 bestSize = s; 674 bestWeight = w; 675 } 676 } 677 if (best == null) 678 continue loop; 679 rooms.add(best); 680 size += bestSize; 681 } 682 if (size >= getSize()) 683 return rooms; 684 } 685 return null; 686 } 687 688 /** 689 * Randomly find a set of available rooms for the exam in the given period. 690 * First of all, it tries to find the minimal number of rooms that cover the 691 * size of the exam. Among these, a set of rooms of total smallest size is 692 * preferred. All necessary checks are made (availability of rooms, room 693 * penalties, room sizes etc.). 694 * 695 * @param period 696 * given period. 697 * @return randomly computed set of available rooms for the exam in the 698 * given period, null if there is no valid assignment 699 */ 700 public Set<ExamRoomPlacement> findRoomsRandom(ExamPeriodPlacement period) { 701 return findRoomsRandom(period, true); 702 } 703 704 /** 705 * Randomly find a set of available rooms for the exam in the given period. 706 * First of all, it tries to find the minimal number of rooms that cover the 707 * size of the exam. Among these, a set of rooms of total smallest size is 708 * preferred. All necessary checks are made (availability of rooms, room 709 * penalties, room sizes etc.). 710 * 711 * @param period 712 * given period. 713 * @param checkConflicts 714 * if false, room and distribution conflicts are not checked 715 * @return randomly computed set of available rooms for the exam in the 716 * given period, null if there is no valid assignment 717 */ 718 public Set<ExamRoomPlacement> findRoomsRandom(ExamPeriodPlacement period, boolean checkConflicts) { 719 if (getMaxRooms() == 0) 720 return new HashSet<ExamRoomPlacement>(); 721 HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>(); 722 int size = 0; 723 loop: while (rooms.size() < getMaxRooms()) { 724 int rx = ToolBox.random(getRoomPlacements().size()); 725 int minSize = (getSize() - size + (getMaxRooms() - rooms.size() - 1)) / (getMaxRooms() - rooms.size()); 726 for (int r = 0; r < getRoomPlacements().size(); r++) { 727 ExamRoomPlacement room = getRoomPlacements().get((r + rx) % getRoomPlacements().size()); 728 int s = room.getSize(hasAltSeating()); 729 if (s < minSize) 730 continue; 731 if (!room.isAvailable(period.getPeriod())) 732 continue; 733 if (checkConflicts && room.getRoom().getPlacement(period.getPeriod()) != null) 734 continue; 735 if (rooms.contains(room)) 736 continue; 737 if (checkConflicts && !checkDistributionConstraints(room)) 738 continue; 739 size += s; 740 rooms.add(room); 741 if (size >= getSize()) { 742 for (Iterator<ExamRoomPlacement> j = rooms.iterator(); j.hasNext();) { 743 ExamRoomPlacement rp = j.next(); 744 if (size - rp.getSize(hasAltSeating()) >= getSize()) { 745 j.remove(); 746 size -= rp.getSize(hasAltSeating()); 747 } 748 } 749 return rooms; 750 } 751 continue loop; 752 } 753 break; 754 } 755 return null; 756 } 757 758 private HashSet<Exam> iCorrelatedExams = null; 759 760 /** 761 * Number of exams that are correlated with this exam (there is at least one 762 * student attending both exams). 763 * 764 * @return number of correlated exams 765 */ 766 public int nrStudentCorrelatedExams() { 767 if (iCorrelatedExams == null) { 768 iCorrelatedExams = new HashSet<Exam>(); 769 for (ExamStudent student : iStudents) { 770 iCorrelatedExams.addAll(student.variables()); 771 } 772 iCorrelatedExams.remove(this); 773 } 774 return iCorrelatedExams.size(); 775 } 776 777 private Integer iEstimatedDomainSize = null; 778 779 private int estimatedDomainSize() { 780 if (iEstimatedDomainSize == null) { 781 int periods = getPeriodPlacements().size(); 782 int rooms = -1; 783 int split = 0; 784 while (rooms < split && split <= getMaxRooms()) { 785 rooms = 0; 786 split++; 787 for (ExamRoomPlacement room : getRoomPlacements()) { 788 if (room.getSize(hasAltSeating()) >= (getSize() / split)) 789 rooms++; 790 } 791 } 792 iEstimatedDomainSize = new Integer(periods * rooms / split); 793 } 794 return iEstimatedDomainSize.intValue(); 795 } 796 797 /** 798 * An exam with more correlated exams is preferred ( 799 * {@link Exam#nrStudentCorrelatedExams()}). If it is the same, ratio number 800 * of students / number of available periods is used. If the same, exam ids 801 * are used. 802 */ 803 @Override 804 public int compareTo(Exam o) { 805 Exam e = o; 806 int cmp = Double.compare(estimatedDomainSize(), e.estimatedDomainSize()); 807 if (cmp != 0) 808 return cmp; 809 cmp = -Double.compare(nrStudentCorrelatedExams(), e.nrStudentCorrelatedExams()); 810 if (cmp != 0) 811 return cmp; 812 cmp = -Double.compare(((double) getSize()) / getPeriodPlacements().size(), ((double) e.getSize()) 813 / e.getPeriodPlacements().size()); 814 if (cmp != 0) 815 return cmp; 816 return super.compareTo(o); 817 } 818 819 /** 820 * True, if there is a student of this exam (that does not have direct 821 * conflicts allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that 822 * attends some other exam in the given period. 823 * 824 * @param period 825 * a period 826 * @return true if there is a student conflict 827 */ 828 public boolean hasStudentConflictWithPreAssigned(ExamPeriod period) { 829 for (ExamStudent s : getStudents()) { 830 for (Exam exam : s.getExams(period)) { 831 if (exam.equals(this)) 832 continue; 833 if (s.canConflict(this, exam)) 834 continue; 835 } 836 } 837 return false; 838 } 839 840 /** 841 * Number of students of this exam (that does not have direct conflicts 842 * allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that attend 843 * some other exam in the given period. 844 * 845 * @param period 846 * a period 847 * @return number of direct student conflicts that are prohibited 848 */ 849 public int countStudentConflicts(ExamPeriodPlacement period) { 850 int conf = 0; 851 for (ExamStudent s : getStudents()) { 852 for (Exam exam : s.getExams(period.getPeriod())) { 853 if (exam.equals(this)) 854 continue; 855 if (s.canConflict(this, exam)) 856 continue; 857 conf++; 858 } 859 } 860 return conf; 861 } 862 863 /** 864 * List of exams that are assigned to the given period and share one or more 865 * students with this exam (that does not have direct conflicts allowed, see 866 * {@link ExamStudent#canConflict(Exam, Exam)}). 867 * 868 * @param period 869 * a period 870 * @return list of {@link Exam} (other than this exam, that are placed in 871 * the given period and create prohibited direct conflicts) 872 */ 873 public HashSet<Exam> getStudentConflicts(ExamPeriod period) { 874 HashSet<Exam> conf = new HashSet<Exam>(); 875 for (ExamStudent s : getStudents()) { 876 for (Exam exam : s.getExams(period)) { 877 if (exam.equals(this)) 878 continue; 879 if (!s.canConflict(this, exam)) 880 conf.add(exam); 881 } 882 } 883 return conf; 884 } 885 886 /** 887 * Allow all direct student conflict for the given period (see 888 * {@link ExamStudent#canConflict(Exam, Exam)}). 889 * 890 * @param period 891 * a period 892 */ 893 public void allowAllStudentConflicts(ExamPeriod period) { 894 for (ExamStudent s : getStudents()) { 895 for (Exam exam : s.getExams(period)) { 896 if (exam.equals(this)) 897 continue; 898 exam.setAllowDirectConflicts(true); 899 setAllowDirectConflicts(true); 900 s.setAllowDirectConflicts(true); 901 } 902 } 903 } 904 905 /** 906 * String representation 907 * 908 * @return exam id (periods: number of periods, rooms: number of rooms, 909 * student: number of students, maxRooms: max rooms[, alt if 910 * alternate seating is required]) 911 */ 912 @Override 913 public String toString() { 914 return getName() + " (periods:" + getPeriodPlacements().size() + ", rooms:" + getRoomPlacements().size() 915 + ", size:" + getSize() + " ,maxRooms:" + getMaxRooms() + (hasAltSeating() ? ", alt" : "") + ")"; 916 } 917 918 /** Exam name */ 919 @Override 920 public String getName() { 921 return (hasName() ? iName : String.valueOf(getId())); 922 } 923 924 /** Exam name */ 925 public void setName(String name) { 926 iName = name; 927 } 928 929 /** Exam name */ 930 public boolean hasName() { 931 return iName != null && iName.length() > 0; 932 } 933 934 private HashMap<Exam, List<ExamStudent>> iJenrls = null; 935 936 /** 937 * Joint enrollments 938 * 939 * @return table {@link Exam} (an exam that has at least one student in 940 * common with this exam) -> {@link List} (list of students in 941 * common) 942 */ 943 public Map<Exam, List<ExamStudent>> getJointEnrollments() { 944 if (iJenrls != null) 945 return iJenrls; 946 iJenrls = new HashMap<Exam, List<ExamStudent>>(); 947 for (ExamStudent student : getStudents()) { 948 for (Exam other : student.variables()) { 949 if (other.equals(this)) 950 continue; 951 List<ExamStudent> students = iJenrls.get(other); 952 if (students == null) { 953 students = new ArrayList<ExamStudent>(); 954 iJenrls.put(other, students); 955 } 956 students.add(student); 957 } 958 } 959 return iJenrls; 960 } 961 962 /** 963 * Courses and/or sections that are having this exam 964 * 965 * @return list of {@link ExamOwner} 966 */ 967 public List<ExamOwner> getOwners() { 968 return iOwners; 969 } 970 971 /** 972 * Courses/sections of this exam into which the given student is enrolled 973 * into 974 * 975 * @param student 976 * a student that is enrolled into this exam 977 * @return list of courses/sections {@link ExamOwner} which are having this 978 * exam with the given student enrolled in 979 */ 980 public Collection<ExamOwner> getOwners(ExamStudent student) { 981 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 982 for (ExamOwner owner : iOwners) { 983 if (owner.getStudents().contains(student)) 984 ret.add(owner); 985 } 986 return ret; 987 } 988 989 /** 990 * Courses/sections of this exam into which the given instructor is enrolled 991 * into 992 * 993 * @param instructor 994 * an instructor that is enrolled into this exam 995 * @return list of courses/sections {@link ExamOwner} which are having this 996 * exam with the given instructor enrolled in 997 */ 998 public Collection<ExamOwner> getOwners(ExamInstructor instructor) { 999 Collection<ExamOwner> ret = new ArrayList<ExamOwner>(); 1000 for (ExamOwner owner : iOwners) { 1001 if (owner.getIntructors().contains(instructor)) 1002 ret.add(owner); 1003 } 1004 return ret; 1005 } 1006 1007 /** 1008 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1009 * it is available for this exam, null otherwise. 1010 */ 1011 public ExamPeriodPlacement getPeriodPlacement(Long periodId) { 1012 for (ExamPeriodPlacement periodPlacement : iPeriodPlacements) { 1013 if (periodPlacement.getId().equals(periodId)) 1014 return periodPlacement; 1015 } 1016 return null; 1017 } 1018 1019 /** 1020 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1021 * is available for this exam, null otherwise. 1022 */ 1023 public ExamRoomPlacement getRoomPlacement(long roomId) { 1024 for (ExamRoomPlacement roomPlacement : iRoomPlacements) { 1025 if (roomPlacement.getId() == roomId) 1026 return roomPlacement; 1027 } 1028 return null; 1029 } 1030 1031 /** 1032 * Returns appropriate {@link ExamPeriodPlacement} for the given period, if 1033 * it is available for this exam, null otherwise. 1034 */ 1035 public ExamPeriodPlacement getPeriodPlacement(ExamPeriod period) { 1036 for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) { 1037 if (periodPlacement.getPeriod().equals(period)) 1038 return periodPlacement; 1039 } 1040 return null; 1041 } 1042 1043 /** 1044 * Returns appropriate {@link ExamRoomPlacement} for the given room, if it 1045 * is available for this exam, null otherwise. 1046 */ 1047 public ExamRoomPlacement getRoomPlacement(ExamRoom room) { 1048 for (ExamRoomPlacement roomPlacement : getRoomPlacements()) { 1049 if (roomPlacement.getRoom().equals(room)) 1050 return roomPlacement; 1051 } 1052 return null; 1053 } 1054 1055 /** Return true if there are some values in the domain of this variable */ 1056 @Override 1057 public boolean hasValues() { 1058 return !getPeriodPlacements().isEmpty() && (getMaxRooms() == 0 || !getRoomPlacements().isEmpty()); 1059 } 1060 1061 @Override 1062 public void assign(long iteration, ExamPlacement placement) { 1063 if (getMaxRooms() > 0) { 1064 int size = 0; 1065 for (ExamRoomPlacement room : placement.getRoomPlacements()) { 1066 size += room.getSize(hasAltSeating()); 1067 } 1068 if (size < getSize() && !placement.getRoomPlacements().isEmpty()) { 1069 Progress.getInstance(getModel()).warn( 1070 "Selected room(s) are too small " + size + "<" + getSize() + " (" + getName() + " " 1071 + placement.getName() + ")"); 1072 } 1073 } 1074 super.assign(iteration, placement); 1075 } 1076 }