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