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}