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}