    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}