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