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