001    package net.sf.cpsolver.exam.neighbours;
002    
003    import java.text.DecimalFormat;
004    import java.util.HashSet;
005    import java.util.Iterator;
006    import java.util.Set;
007    
008    import net.sf.cpsolver.exam.model.Exam;
009    import net.sf.cpsolver.exam.model.ExamPlacement;
010    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
011    import net.sf.cpsolver.ifs.model.Neighbour;
012    
013    /**
014     * Swap a room between two assigned exams. <br>
015     * <br>
016     * 
017     * @version ExamTT 1.2 (Examination Timetabling)<br>
018     *          Copyright (C) 2008 - 2010 Tomas Muller<br>
019     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
020     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
021     * <br>
022     *          This library is free software; you can redistribute it and/or modify
023     *          it under the terms of the GNU Lesser General Public License as
024     *          published by the Free Software Foundation; either version 3 of the
025     *          License, or (at your option) any later version. <br>
026     * <br>
027     *          This library is distributed in the hope that it will be useful, but
028     *          WITHOUT ANY WARRANTY; without even the implied warranty of
029     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
030     *          Lesser General Public License for more details. <br>
031     * <br>
032     *          You should have received a copy of the GNU Lesser General Public
033     *          License along with this library; if not see
034     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
035     */
036    public class ExamRoomSwapNeighbour extends Neighbour<Exam, ExamPlacement> {
037        private double iValue = 0;
038        private ExamPlacement iX1, iX2 = null;
039        private ExamRoomPlacement iR1, iR2 = null;
040    
041        public ExamRoomSwapNeighbour(ExamPlacement placement, ExamRoomPlacement current, ExamRoomPlacement swap) {
042            if (placement.getRoomPlacements().contains(swap))
043                return; // not an actual swap
044            Exam exam = placement.variable();
045            if (!swap.isAvailable(placement.getPeriod()))
046                return; // room not available
047            if (!exam.checkDistributionConstraints(swap))
048                return; // a distribution constraint is violated
049            int size = 0;
050            for (ExamRoomPlacement r : placement.getRoomPlacements())
051                size += r.getSize(exam.hasAltSeating());
052            size -= current.getSize(exam.hasAltSeating());
053            size += swap.getSize(exam.hasAltSeating());
054            if (size < exam.getSize())
055                return; // new room is too small
056            ExamPlacement conflict = swap.getRoom().getPlacement(placement.getPeriod());
057            if (conflict == null) {
058                Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements());
059                newRooms.remove(current);
060                newRooms.add(swap);
061                for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) {
062                    ExamRoomPlacement r = i.next();
063                    if (r.equals(swap))
064                        continue;
065                    if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
066                        i.remove();
067                        size -= r.getSize(exam.hasAltSeating());
068                    }
069                }
070                iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
071                iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble());
072            } else {
073                Exam x = conflict.variable();
074                ExamRoomPlacement xNew = x.getRoomPlacement(current.getRoom());
075                if (xNew == null)
076                    return; // conflicting exam cannot be assigned in the current
077                            // room
078                if (!x.checkDistributionConstraints(xNew))
079                    return; // conflicting exam has a distribution constraint
080                            // violated
081                int xSize = 0;
082                for (ExamRoomPlacement r : conflict.getRoomPlacements()) {
083                    xSize += r.getSize(x.hasAltSeating());
084                }
085                xSize -= swap.getSize(x.hasAltSeating());
086                xSize += current.getSize(x.hasAltSeating());
087                if (xSize < x.getSize())
088                    return; // current room is too small for the conflicting exam
089                Set<ExamRoomPlacement> newRooms = new HashSet<ExamRoomPlacement>(placement.getRoomPlacements());
090                newRooms.remove(current);
091                newRooms.add(swap);
092                for (Iterator<ExamRoomPlacement> i = newRooms.iterator(); i.hasNext();) {
093                    ExamRoomPlacement r = i.next();
094                    if (r.equals(swap))
095                        continue;
096                    if (size - r.getSize(exam.hasAltSeating()) >= exam.getSize()) {
097                        i.remove();
098                        size -= r.getSize(exam.hasAltSeating());
099                    }
100                }
101                iX1 = new ExamPlacement(exam, placement.getPeriodPlacement(), newRooms);
102                Set<ExamRoomPlacement> xRooms = new HashSet<ExamRoomPlacement>(conflict.getRoomPlacements());
103                xRooms.remove(x.getRoomPlacement(swap.getRoom()));
104                xRooms.add(xNew);
105                for (Iterator<ExamRoomPlacement> i = xRooms.iterator(); i.hasNext();) {
106                    ExamRoomPlacement r = i.next();
107                    if (r.equals(swap))
108                        continue;
109                    if (xSize - r.getSize(x.hasAltSeating()) >= x.getSize()) {
110                        i.remove();
111                        xSize -= r.getSize(x.hasAltSeating());
112                    }
113                }
114                iX2 = new ExamPlacement(x, conflict.getPeriodPlacement(), xRooms);
115                iValue = iX1.toDouble() - (exam.getAssignment() == null ? 0.0 : exam.getAssignment().toDouble())
116                        + iX2.toDouble() - conflict.toDouble();
117            }
118            iR1 = current;
119            iR2 = swap;
120        }
121    
122        public boolean canDo() {
123            return iX1 != null;
124        }
125    
126        @Override
127        public void assign(long iteration) {
128            if (iX2 == null) {
129                iX1.variable().assign(iteration, iX1);
130            } else {
131                if (iX1.variable().getAssignment() != null)
132                    iX1.variable().unassign(iteration);
133                iX2.variable().unassign(iteration);
134                iX1.variable().assign(iteration, iX1);
135                iX2.variable().assign(iteration, iX2);
136            }
137        }
138    
139        @Override
140        public String toString() {
141            if (iX2 == null) {
142                return iX1.variable().getAssignment() + " -> " + iX1.toString() + " / " + " (value:" + value() + ")";
143            } else {
144                return iX1.variable().getName() + ": " + iR1.getRoom() + " <-> " + iR2.getRoom() + " (w "
145                        + iX2.variable().getName() + ", value:" + value() + ")";
146            }
147        }
148    
149        protected static String toString(double[] x, double[] y) {
150            DecimalFormat df = new DecimalFormat("0.00");
151            StringBuffer s = new StringBuffer();
152            for (int i = 0; i < x.length; i++) {
153                if (i > 0)
154                    s.append(",");
155                s.append(df.format(x[i] - y[i]));
156            }
157            return "[" + s.toString() + "]";
158        }
159    
160        @Override
161        public double value() {
162            return iValue;
163        }
164    }