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