001 package net.sf.cpsolver.exam.neighbours;
002
003 import java.text.DecimalFormat;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.Set;
007
008 import net.sf.cpsolver.exam.model.Exam;
009 import net.sf.cpsolver.exam.model.ExamPlacement;
010 import net.sf.cpsolver.exam.model.ExamRoomPlacement;
011 import net.sf.cpsolver.ifs.model.Neighbour;
012 /**
013 * Swap a room between two assigned exams.
014 * <br><br>
015 *
016 * @version
017 * ExamTT 1.1 (Examination Timetabling)<br>
018 * Copyright (C) 2008 Tomáš Müller<br>
019 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
020 * Lazenska 391, 76314 Zlin, Czech Republic<br>
021 * <br>
022 * This library is free software; you can redistribute it and/or
023 * modify it under the terms of the GNU Lesser General Public
024 * License as published by the Free Software Foundation; either
025 * version 2.1 of the License, or (at your option) any later version.
026 * <br><br>
027 * This library is distributed in the hope that it will be useful,
028 * but WITHOUT ANY WARRANTY; without even the implied warranty of
029 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
030 * Lesser General Public License for more details.
031 * <br><br>
032 * You should have received a copy of the GNU Lesser General Public
033 * License along with this library; if not, write to the Free Software
034 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
035 */
036 public class ExamRoomSwapNeighbour extends Neighbour {
037 private double iValue = 0;
038 private ExamPlacement iX1, iX2 = null;
039 private ExamRoomPlacement iR1, iR2 = null;
040
041 public ExamRoomSwapNeighbour(ExamPlacement placement, ExamRoomPlacement current, ExamRoomPlacement swap) {
042 if (placement.getRoomPlacements().contains(swap)) return; //not an actual swap
043 Exam exam = (Exam)placement.variable();
044 if (!swap.isAvailable(placement.getPeriod())) return; //room not available
045 if (!exam.checkDistributionConstraints(swap)) return; //a distribution constraint is violated
046 int size = 0;
047 for (Iterator i=placement.getRoomPlacements().iterator();i.hasNext();)
048 size += ((ExamRoomPlacement)i.next()).getSize(exam.hasAltSeating());
049 size -= current.getSize(exam.hasAltSeating());
050 size += swap.getSize(exam.hasAltSeating());
051 if (size<exam.getSize()) return; //new room is too small
052 ExamPlacement conflict = swap.getRoom().getPlacement(placement.getPeriod());
053 if (conflict==null) {
054 Set newRooms = new HashSet(placement.getRoomPlacements());
055 newRooms.remove(current);
056 newRooms.add(swap);
057 for (Iterator i=newRooms.iterator();i.hasNext();) {
058 ExamRoomPlacement r = (ExamRoomPlacement)i.next();
059 if (r.equals(swap)) continue;
060 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
061 i.remove(); size -= r.getSize(exam.hasAltSeating());
062 }
063 }
064 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
065 iValue = iX1.toDouble() - (exam.getAssignment()==null?0.0:exam.getAssignment().toDouble());
066 } else {
067 Exam x = (Exam)conflict.variable();
068 ExamRoomPlacement xNew = x.getRoomPlacement(current.getRoom());
069 if (xNew==null) return; //conflicting exam cannot be assigned in the current room
070 if (!x.checkDistributionConstraints(xNew)) return; //conflicting exam has a distribution constraint violated
071 int xSize = 0;
072 for (Iterator i=conflict.getRoomPlacements().iterator();i.hasNext();) {
073 xSize += ((ExamRoomPlacement)i.next()).getSize(x.hasAltSeating());
074 }
075 xSize -= swap.getSize(x.hasAltSeating());
076 xSize += current.getSize(x.hasAltSeating());
077 if (xSize < x.getSize()) return; //current room is too small for the conflicting exam
078 Set newRooms = new HashSet(placement.getRoomPlacements());
079 newRooms.remove(current);
080 newRooms.add(swap);
081 for (Iterator i=newRooms.iterator();i.hasNext();) {
082 ExamRoomPlacement r = (ExamRoomPlacement)i.next();
083 if (r.equals(swap)) continue;
084 if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
085 i.remove(); size -= r.getSize(exam.hasAltSeating());
086 }
087 }
088 iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
089 Set xRooms = new HashSet(conflict.getRoomPlacements());
090 xRooms.remove(x.getRoomPlacement(swap.getRoom()));
091 xRooms.add(xNew);
092 for (Iterator i=xRooms.iterator();i.hasNext();) {
093 ExamRoomPlacement r = (ExamRoomPlacement)i.next();
094 if (r.equals(swap)) continue;
095 if (xSize - r.getSize(x.hasAltSeating()) >= x.getSize()) {
096 i.remove(); xSize -= r.getSize(x.hasAltSeating());
097 }
098 }
099 iX2 = new ExamPlacement(x, conflict.getPeriodPlacement(), xRooms);
100 iValue = iX1.toDouble() - (exam.getAssignment()==null?0.0:exam.getAssignment().toDouble()) +
101 iX2.toDouble() - conflict.toDouble();
102 }
103 iR1 = current; iR2 = swap;
104 }
105
106 public boolean canDo() {
107 return iX1!=null;
108 }
109
110 public void assign(long iteration) {
111 if (iX2==null) {
112 iX1.variable().assign(iteration, iX1);
113 } else {
114 if (iX1.variable().getAssignment()!=null) iX1.variable().unassign(iteration);
115 iX2.variable().unassign(iteration);
116 iX1.variable().assign(iteration, iX1);
117 iX2.variable().assign(iteration, iX2);
118 }
119 }
120
121 public String toString() {
122 if (iX2==null) {
123 return iX1.variable().getAssignment()+ " -> "+ iX1.toString()+" / "+" (value:"+value()+")";
124 } else {
125 return iX1.variable().getName()+": "+iR1.getRoom()+" <-> "+iR2.getRoom()+" (w "+iX2.variable().getName()+", value:"+value()+")";
126 }
127 }
128
129 protected static String toString(double[] x, double[] y) {
130 DecimalFormat df = new DecimalFormat("0.00");
131 StringBuffer s = new StringBuffer();
132 for (int i=0;i<x.length;i++) {
133 if (i>0) s.append(",");
134 s.append(df.format(x[i]-y[i]));
135 }
136 return "["+s.toString()+"]";
137 }
138
139 public double value() {
140 return iValue;
141 }
142 }