001    package net.sf.cpsolver.exam.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.List;
006    import java.util.Set;
007    
008    import org.dom4j.Element;
009    
010    import net.sf.cpsolver.coursett.IdConvertor;
011    import net.sf.cpsolver.ifs.model.Model;
012    import net.sf.cpsolver.ifs.util.DataProperties;
013    import net.sf.cpsolver.ifs.util.ToolBox;
014    
015    /**
016     * Abstract room sharing model. Defines when and under what conditions two or more exams can share a room.<br>
017     * <br>
018     * 
019     * @version ExamTT 1.2 (Examination Timetabling)<br>
020     *          Copyright (C) 2008 - 2012 Tomas Muller<br>
021     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
022     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
023     * <br>
024     *          This library is free software; you can redistribute it and/or modify
025     *          it under the terms of the GNU Lesser General Public License as
026     *          published by the Free Software Foundation; either version 3 of the
027     *          License, or (at your option) any later version. <br>
028     * <br>
029     *          This library is distributed in the hope that it will be useful, but
030     *          WITHOUT ANY WARRANTY; without even the implied warranty of
031     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
032     *          Lesser General Public License for more details. <br>
033     * <br>
034     *          You should have received a copy of the GNU Lesser General Public
035     *          License along with this library; if not see
036     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
037     */
038    public abstract class ExamRoomSharing  {
039        
040        public ExamRoomSharing(Model<Exam, ExamPlacement> model, DataProperties config) {}
041            
042        /**
043         * True if given examination can not be placed in the same room at the same period as the other examinations
044         * @param exam examination placement in question
045         * @param other exams currently assigned in the room at the requested period
046         * @param room examination room in questions
047         * @return true if there is a conflict
048         */
049        public boolean inConflict(ExamPlacement exam, Collection<ExamPlacement> other, ExamRoom room) {
050            if (exam.getRoomPlacements().size() != 1)
051                return !other.isEmpty();
052            
053            return inConflict(exam.variable(), other, room);
054        }
055        
056        /**
057         * True if given examination can not be placed in the same room at the same period as the other examinations
058         * @param exam examination in question
059         * @param other exams currently assigned in the room at the requested period
060         * @param room examination room in questions
061         * @return true if there is a conflict
062         */
063        public boolean inConflict(Exam exam, Collection<ExamPlacement> other, ExamRoom room) {
064            int total = exam.getSize();
065            boolean altSeating = exam.hasAltSeating();
066            for (ExamPlacement x: other) {
067                if (x.variable().equals(exam)) continue;
068                if (x.getRoomPlacements().size() != 1) return true; // already split into multiple rooms
069                if (!canShareRoom(exam, x.variable())) return true; // sharing not allowed between the pair
070                total += x.variable().getSize();
071                if (x.variable().hasAltSeating()) altSeating = true;
072            }
073            
074            return total > (altSeating ? room.getAltSize() : room.getSize()); // check size limit
075        }
076        
077        /**
078         * Compute conflicting placement for the case when a given examination needs to be placed in the same room at the same period as the other examinations
079         * @param exam examination placement in question
080         * @param other exams currently assigned in the room at the requested period
081         * @param room examination room in questions
082         */
083        public void computeConflicts(ExamPlacement exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
084            // more than one room is required -> no sharing
085            if (exam.getRoomPlacements().size() != 1) {
086                conflicts.addAll(other);
087                return;
088            }
089            
090            computeConflicts(exam.variable(), other, room, conflicts);
091        }
092        
093        /**
094         * Compute conflicting placement for the case when a given examination needs to be placed in the same room at the same period as the other examinations
095         * @param exam examination in question
096         * @param other exams currently assigned in the room at the requested period
097         * @param room examination room in questions
098         */
099        public void computeConflicts(Exam exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
100            int total = exam.getSize();
101            boolean altSeating = exam.hasAltSeating();
102            List<ExamPlacement> adepts = new ArrayList<ExamPlacement>();
103            for (ExamPlacement x: other) {
104                if (x.variable().equals(exam)) continue;
105                // already split into multiple rooms
106                if (x.getRoomPlacements().size() != 1) {
107                    conflicts.add(x); continue;
108                }
109                // sharing not allowed between the pair
110                if (!canShareRoom(exam, x.variable())) {
111                    conflicts.add(x); continue;
112                }
113                if (x.variable().hasAltSeating()) altSeating = true;
114                total += x.variable().getSize();
115                adepts.add(x);
116            }
117            
118            // fix the total size if needed
119            while (total > (altSeating ? room.getAltSize() : room.getSize()) && !adepts.isEmpty()) {
120                ExamPlacement x = ToolBox.random(adepts);
121                adepts.remove(x);
122                conflicts.add(x);
123                total -= x.variable().getSize();
124            }
125        }
126    
127        
128        /**
129         * True if given two exams can share a room
130         */
131        public abstract boolean canShareRoom(Exam x1, Exam x2);
132        
133        /**
134         * Save sharing information (if needed) for a given exam
135         */
136        public void save(Exam exam, Element element, IdConvertor idConvertor) {}
137        
138        /**
139         * Load sharing information (if needed) for a given exam
140         */
141        public void load(Exam exam, Element element) {}
142    }