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