001package net.sf.cpsolver.exam.neighbours; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.HashSet; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Set; 009 010import net.sf.cpsolver.exam.model.Exam; 011import net.sf.cpsolver.exam.model.ExamModel; 012import net.sf.cpsolver.exam.model.ExamPlacement; 013import net.sf.cpsolver.exam.model.ExamRoomPlacement; 014import net.sf.cpsolver.exam.model.ExamRoomSharing; 015import 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 Tomáš Müller<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 */ 040public 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}