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