001package net.sf.cpsolver.exam.model; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.List; 006import java.util.Set; 007 008import org.dom4j.Element; 009 010import net.sf.cpsolver.coursett.IdConvertor; 011import net.sf.cpsolver.ifs.model.Model; 012import net.sf.cpsolver.ifs.util.DataProperties; 013import 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 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 */ 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}