    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}