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