001package org.cpsolver.exam.model;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.List;
006import java.util.Set;
007
008import org.cpsolver.coursett.IdConvertor;
009import org.cpsolver.ifs.model.Model;
010import org.cpsolver.ifs.util.DataProperties;
011import org.cpsolver.ifs.util.ToolBox;
012import org.dom4j.Element;
013
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.3 (Examination Timetabling)<br>
020 *          Copyright (C) 2008 - 2014 Tomáš Müller<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 */
038public 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     * @param conflicts set of conflicting assignments
083     */
084    public void computeConflicts(ExamPlacement exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
085        // more than one room is required -> no sharing
086        if (exam.getRoomPlacements().size() != 1) {
087            conflicts.addAll(other);
088            return;
089        }
090        
091        computeConflicts(exam.variable(), other, room, conflicts);
092    }
093    
094    /**
095     * 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
096     * @param exam examination in question
097     * @param other exams currently assigned in the room at the requested period
098     * @param room examination room in questions
099     * @param conflicts set of conflicting assignments
100     */
101    public void computeConflicts(Exam exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
102        int total = exam.getSize();
103        boolean altSeating = exam.hasAltSeating();
104        List<ExamPlacement> adepts = new ArrayList<ExamPlacement>();
105        for (ExamPlacement x: other) {
106            if (x.variable().equals(exam)) continue;
107            // already split into multiple rooms
108            if (x.getRoomPlacements().size() != 1) {
109                conflicts.add(x); continue;
110            }
111            // sharing not allowed between the pair
112            if (!canShareRoom(exam, x.variable())) {
113                conflicts.add(x); continue;
114            }
115            if (x.variable().hasAltSeating()) altSeating = true;
116            total += x.variable().getSize();
117            adepts.add(x);
118        }
119        
120        // fix the total size if needed
121        while (total > (altSeating ? room.getAltSize() : room.getSize()) && !adepts.isEmpty()) {
122            ExamPlacement x = ToolBox.random(adepts);
123            adepts.remove(x);
124            conflicts.add(x);
125            total -= x.variable().getSize();
126        }
127    }
128
129    
130    /**
131     * True if given two exams can share a room
132     * @param x1 first exam
133     * @param x2 second exam
134     * @return true if the two exams can share a room
135     */
136    public abstract boolean canShareRoom(Exam x1, Exam x2);
137    
138    /**
139     * Save sharing information (if needed) for a given exam
140     * @param exam exam in question
141     * @param element XML exam element to include sharing information
142     * @param idConvertor id converter
143     */
144    public void save(Exam exam, Element element, IdConvertor idConvertor) {}
145    
146    /**
147     * Load sharing information (if needed) for a given exam
148     * @param exam exam in question
149     * @param element XML exam element including sharing information
150     */
151    public void load(Exam exam, Element element) {}
152}