001 package net.sf.cpsolver.exam.neighbours;
002
003 import java.text.DecimalFormat;
004 import java.util.ArrayList;
005 import java.util.HashSet;
006 import java.util.Iterator;
007 import java.util.List;
008 import java.util.Set;
009
010 import net.sf.cpsolver.exam.model.Exam;
011 import net.sf.cpsolver.exam.model.ExamModel;
012 import net.sf.cpsolver.exam.model.ExamPlacement;
013 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
014 import net.sf.cpsolver.exam.model.ExamRoomSharing;
015 import net.sf.cpsolver.ifs.model.Neighbour;
016
017 /**
018 * Swap a room between two assigned exams. <br>
019 * <br>
020 *
021 * @version ExamTT 1.2 (Examination Timetabling)<br>
022 * Copyright (C) 2008 - 2010 Tomas Muller<br>
023 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
024 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
025 * <br>
026 * This library is free software; you can redistribute it and/or modify
027 * it under the terms of the GNU Lesser General Public License as
028 * published by the Free Software Foundation; either version 3 of the
029 * License, or (at your option) any later version. <br>
030 * <br>
031 * This library is distributed in the hope that it will be useful, but
032 * WITHOUT ANY WARRANTY; without even the implied warranty of
033 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
034 * Lesser General Public License for more details. <br>
035 * <br>
036 * You should have received a copy of the GNU Lesser General Public
037 * License along with this library; if not see
038 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
039 */
040 public class ExamRoomSwapNeighbour extends Neighbour<Exam, ExamPlacement> {
041 private double iValue = 0;
042 private ExamPlacement iX1, iX2 = null;
043 private ExamRoomPlacement iR1, iR2 = null;
044
045 public ExamRoomSwapNeighbour(ExamPlacement placement, ExamRoomPlacement current, ExamRoomPlacement swap) {
046 if (placement.getRoomPlacements().contains(swap))
047 return; // not an actual swap
048 Exam exam = placement.variable();
049 if (!swap.isAvailable(placement.getPeriod()))
050 return; // room not available
051 if (!exam.checkDistributionConstraints(swap))
052 return; // a distribution constraint is violated
053 int size = 0;
054 for (ExamRoomPlacement r : placement.getRoomPlacements())
055 size += r.getSize(exam.hasAltSeating());
056 size -= current.getSize(exam.hasAltSeating());
057 size += swap.getSize(exam.hasAltSeating());
058 if (size < exam.getSize())
059 return; // new room is too small
060 ExamPlacement conflict = null;
061 ExamRoomSharing rs = ((ExamModel)exam.getModel()).getRoomSharing();
062 if (rs != null && placement.getRoomPlacements().size() == 1) {
063 Set<ExamPlacement> x = new HashSet<ExamPlacement>();
064 rs.computeConflicts(exam, swap.getRoom().getPlacements(placement.getPeriod()), swap.getRoom(), x);
065 if (x.size() > 1) return;
066 else if (x.size() == 1) conflict = x.iterator().next();
067 } else {
068 List<ExamPlacement> conf = swap.getRoom().getPlacements(placement.getPeriod());
069 if (conf.size() > 1) return;
070 else if (conf.size() == 1) conflict = conf.get(0);
071 }
072 if (conflict == null) {
073 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements());
074 newRooms.remove(current);
075 newRooms.add(swap);
076 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) {
077 ExamRoomPlacement r = i.next();
078 if (r.equals(swap))
079 continue;
080 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
081 i.remove();
082 size -= r.getSize(exam.hasAltSeating());
083 }
084 }
085 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
086 iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble());
087 } else {
088 Exam x = conflict.variable();
089 ExamRoomPlacement xNew = x.getRoomPlacement(current.getRoom());
090 if (xNew == null)
091 return; // conflicting exam cannot be assigned in the current
092 // room
093 if (!x.checkDistributionConstraints(xNew))
094 return; // conflicting exam has a distribution constraint
095 // violated
096 int xSize = 0;
097 for (ExamRoomPlacement r : conflict.getRoomPlacements()) {
098 xSize += r.getSize(x.hasAltSeating());
099 }
100 xSize -= swap.getSize(x.hasAltSeating());
101 xSize += current.getSize(x.hasAltSeating());
102 if (xSize < x.getSize())
103 return; // current room is too small for the conflicting exam
104 if (rs != null) {
105 List<ExamPlacement> other = new ArrayList<ExamPlacement>(current.getRoom().getPlacements(conflict.getPeriod()));
106 other.remove(placement);
107 if (!other.isEmpty() && conflict.getRoomPlacements().size() > 1) return;
108 if (rs.inConflict(x, other, current.getRoom())) return;
109 }
110 Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements());
111 newRooms.remove(current);
112 newRooms.add(swap);
113 for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) {
114 ExamRoomPlacement r = i.next();
115 if (r.equals(swap))
116 continue;
117 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
118 i.remove();
119 size -= r.getSize(exam.hasAltSeating());
120 }
121 }
122 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
123 Set<ExamRoomPlacement> xRooms = new HashSet<ExamRoomPlacement>(conflict.getRoomPlacements());
124 xRooms.remove(x.getRoomPlacement(swap.getRoom()));
125 xRooms.add(xNew);
126 for (Iterator<ExamRoomPlacement> i = xRooms.iterator(); i.hasNext();) {
127 ExamRoomPlacement r = i.next();
128 if (r.equals(swap))
129 continue;
130 if (xSize - r.getSize(x.hasAltSeating()) >= x.getSize()) {
131 i.remove();
132 xSize -= r.getSize(x.hasAltSeating());
133 }
134 }
135 iX2 = new ExamPlacement(x, conflict.getPeriodPlacement(), xRooms);
136 iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble())
137 + iX2.toDouble() - conflict.toDouble();
138 }
139 iR1 = current;
140 iR2 = swap;
141 }
142
143 public boolean canDo() {
144 return iX1 != null;
145 }
146
147 @Override
148 public void assign(long iteration) {
149 if (iX2 == null) {
150 iX1.variable().assign(iteration, iX1);
151 } else {
152 if (iX1.variable().getAssignment() != null)
153 iX1.variable().unassign(iteration);
154 iX2.variable().unassign(iteration);
155 iX1.variable().assign(iteration, iX1);
156 iX2.variable().assign(iteration, iX2);
157 }
158 }
159
160 @Override
161 public String toString() {
162 if (iX2 == null) {
163 return iX1.variable().getAssignment() + " -> " + iX1.toString() + " / " + " (value:" + value() + ")";
164 } else {
165 return iX1.variable().getName() + ": " + iR1.getRoom() + " <-> " + iR2.getRoom() + " (w "
166 + iX2.variable().getName() + ", value:" + value() + ")";
167 }
168 }
169
170 protected static String toString(double[] x, double[] y) {
171 DecimalFormat df = new DecimalFormat("0.00");
172 StringBuffer s = new StringBuffer();
173 for (int i = 0; i < x.length; i++) {
174 if (i > 0)
175 s.append(",");
176 s.append(df.format(x[i] - y[i]));
177 }
178 return "[" + s.toString() + "]";
179 }
180
181 @Override
182 public double value() {
183 return iValue;
184 }
185 }