001    package net.sf.cpsolver.exam.neighbours;
002    
003    import java.text.DecimalFormat;
004    import java.util.ArrayList;
005    import java.util.HashSet;
006    import java.util.Iterator;
007    import java.util.List;
008    import java.util.Set;
009    
010    import net.sf.cpsolver.exam.model.Exam;
011    import net.sf.cpsolver.exam.model.ExamModel;
012    import net.sf.cpsolver.exam.model.ExamPlacement;
013    import net.sf.cpsolver.exam.model.ExamRoomPlacement;
014    import net.sf.cpsolver.exam.model.ExamRoomSharing;
015    import 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 Tomas Muller<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     */
040    public 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    }