    001package net.sf.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Enumeration;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Set;
    009
    010import net.sf.cpsolver.coursett.Constants;
    011import net.sf.cpsolver.coursett.criteria.BrokenTimePatterns;
    012import net.sf.cpsolver.coursett.criteria.UselessHalfHours;
    013import net.sf.cpsolver.coursett.model.Lecture;
    014import net.sf.cpsolver.coursett.model.Placement;
    015import net.sf.cpsolver.coursett.model.RoomSharingModel;
    016import net.sf.cpsolver.coursett.model.TimeLocation;
    017import net.sf.cpsolver.ifs.model.Constraint;
    018
    019/**
    020 * Room constraint. <br>
    021 * Classes with the same room can not overlap in time.
    022 *
    023 * @version CourseTT 1.2 (University Course Timetabling)<br>
    024 *          Copyright (C) 2006 - 2010 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 */
    042
    043public class RoomConstraint extends Constraint<Lecture, Placement> {
    044    private List<Placement>[] iResource;
    045    private Long iResourceId;
    046    private String iName;
    047    private Long iBuildingId;
    048    private int iCapacity = 0;
    049    private List<Placement>[] iAvailable = null;
    050    private boolean iConstraint = true;
    051
    052    private Double iPosX = null, iPosY = null;
    053    private boolean iIgnoreTooFar = false;
    054
    055    private RoomSharingModel iRoomSharingModel = null;
    056
    057    private Long iType = null;
    058    private int iLastUselessHalfHours = 0;
    059    private double iLastBrokenTimePatterns = 0;
    060
    061    /**
    062     * Constructor
    063     */
    064    @SuppressWarnings("unchecked")
    065    public RoomConstraint(Long id, String name, Long buildingId, int capacity, RoomSharingModel roomSharingModel,
    066            Double x, Double y, boolean ignoreTooFar, boolean constraint) {
    067        iResourceId = id;
    068        iName = name;
    069        iResource = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS];
    070        iBuildingId = buildingId;
    071        iCapacity = capacity;
    072        iConstraint = constraint;
    073        for (int i = 0; i < iResource.length; i++)
    074            iResource[i] = new ArrayList<Placement>(3);
    075        iRoomSharingModel = roomSharingModel;
    076        iPosX = x;
    077        iPosY = y;
    078        iIgnoreTooFar = ignoreTooFar;
    079    }
    080
    081    @SuppressWarnings("unchecked")
    082    public void setNotAvailable(Placement placement) {
    083        if (iAvailable == null) {
    084            iAvailable = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS];
    085            for (int i = 0; i < iResource.length; i++)
    086                iAvailable[i] = null;
    087        }
    088        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    089            int slot = e.nextElement();
    090            if (iAvailable[slot] == null)
    091                iAvailable[slot] = new ArrayList<Placement>(1);
    092            iAvailable[slot].add(placement);
    093        }
    094        for (Lecture lecture: variables())
    095            lecture.clearValueCache();
    096    }
    097
    098    public boolean isAvailable(int slot) {
    099        if (iAvailable != null && iAvailable[slot] != null && !iAvailable[slot].isEmpty())
    100            return false;
    101        if (getSharingModel() != null && getSharingModel().isNotAvailable(slot))
    102            return false;
    103        return true;
    104    }
    105
    106    public boolean isAvailable(Lecture lecture, TimeLocation time, Long scheduler) {
    107        if (iAvailable != null) {
    108            for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) {
    109                int slot = e.nextElement();
    110                if (iAvailable[slot] != null) {
    111                    for (Placement p : iAvailable[slot]) {
    112                        if (lecture.canShareRoom(p.variable()))
    113                            continue;
    114                        if (time.shareWeeks(p.getTimeLocation()))
    115                            return false;
    116                    }
    117                }
    118            }
    119        }
    120        if (getSharingModel() != null && !getSharingModel().isAvailable(time, scheduler))
    121            return false;
    122        return true;
    123    }
    124
    125    public List<Placement>[] getAvailableArray() {
    126        return iAvailable;
    127    }
    128
    129    public RoomSharingModel getSharingModel() {
    130        return iRoomSharingModel;
    131    }
    132
    133    /** Room id */
    134    public Long getResourceId() {
    135        return iResourceId;
    136    }
    137
    138    /** Building id */
    139    public Long getBuildingId() {
    140        return iBuildingId;
    141    }
    142
    143    /** Room name */
    144    @Override
    145    public String getName() {
    146        return iName;
    147    }
    148
    149    public String getRoomName() {
    150        return iName;
    151    }
    152
    153    /** Capacity */
    154    public int getCapacity() {
    155        return iCapacity;
    156    }
    157
    158    public Placement getPlacement(int slot, int day) {
    159        for (Placement p : iResource[slot]) {
    160            if (p.getTimeLocation().hasDay(day))
    161                return p;
    162        }
    163        return null;
    164    }
    165
    166    @Override
    167    public void computeConflicts(Placement placement, Set<Placement> conflicts) {
    168        if (!getConstraint())
    169            return;
    170        if (!placement.hasRoomLocation(getResourceId()))
    171            return;
    172        Lecture lecture = placement.variable();
    173        boolean canShareRoom = lecture.canShareRoom();
    174        int size = lecture.maxRoomUse();
    175        HashSet<Placement> skipPlacements = null;
    176        BitSet weekCode = placement.getTimeLocation().getWeekCode();
    177
    178        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    179            int slot = e.nextElement();
    180            for (Placement confPlacement : iResource[slot]) {
    181                if (!confPlacement.getTimeLocation().shareWeeks(weekCode))
    182                    continue;
    183                if (confPlacement.equals(lecture.getAssignment()))
    184                    continue;
    185                Lecture confLecture = confPlacement.variable();
    186                if (skipPlacements != null && skipPlacements.contains(confPlacement))
    187                    continue;
    188                if (canShareRoom && confPlacement.canShareRooms(placement)
    189                        && confLecture.maxRoomUse() + size <= getCapacity()) {
    190                    size += confLecture.maxRoomUse();
    191                    if (skipPlacements == null)
    192                        skipPlacements = new HashSet<Placement>();
    193                    skipPlacements.add(confPlacement);
    194                    continue;
    195                }
    196                conflicts.add(confPlacement);
    197            }
    198        }
    199    }
    200
    201    @Override
    202    public boolean inConflict(Placement placement) {
    203        if (!getConstraint())
    204            return false;
    205        Lecture lecture = placement.variable();
    206        if (!placement.hasRoomLocation(getResourceId()))
    207            return false;
    208        int size = lecture.maxRoomUse();
    209        HashSet<Placement> skipPlacements = null;
    210        BitSet weekCode = placement.getTimeLocation().getWeekCode();
    211
    212        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    213            int slot = e.nextElement();
    214            for (Placement confPlacement : iResource[slot]) {
    215                if (!confPlacement.getTimeLocation().shareWeeks(weekCode))
    216                    continue;
    217                if (confPlacement.equals(lecture.getAssignment()))
    218                    continue;
    219                Lecture confLecture = confPlacement.variable();
    220                if (skipPlacements != null && skipPlacements.contains(confPlacement))
    221                    continue;
    222                if (confPlacement.canShareRooms(placement) && confLecture.maxRoomUse() + size <= getCapacity()) {
    223                    size += confLecture.maxRoomUse();
    224                    if (skipPlacements == null)
    225                        skipPlacements = new HashSet<Placement>();
    226                    skipPlacements.add(confPlacement);
    227                    continue;
    228                }
    229                return true;
    230            }
    231        }
    232        return false;
    233    }
    234
    235    @Override
    236    public boolean isConsistent(Placement p1, Placement p2) {
    237        if (!getConstraint())
    238            return true;
    239        if (!p1.hasRoomLocation(getResourceId()))
    240            return false;
    241        if (!p2.hasRoomLocation(getResourceId()))
    242            return false;
    243        if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) {
    244            if (!p1.canShareRooms(p2) || (p1.variable()).maxRoomUse() + (p2.variable()).maxRoomUse() > getCapacity())
    245                return true;
    246        }
    247        return false;
    248    }
    249
    250    @Override
    251    public void assigned(long iteration, Placement placement) {
    252        super.assigned(iteration, placement);
    253        if (!placement.hasRoomLocation(getResourceId()))
    254            return;
    255        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    256            int slot = e.nextElement();
    257            iResource[slot].add(placement);
    258        }
    259        getModel().getCriterion(UselessHalfHours.class).inc(-iLastUselessHalfHours);
    260        iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this);
    261        getModel().getCriterion(UselessHalfHours.class).inc(iLastUselessHalfHours);
    262        getModel().getCriterion(BrokenTimePatterns.class).inc(-iLastBrokenTimePatterns);
    263        iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0;
    264        getModel().getCriterion(BrokenTimePatterns.class).inc(iLastBrokenTimePatterns);
    265    }
    266
    267    @Override
    268    public void unassigned(long iteration, Placement placement) {
    269        super.unassigned(iteration, placement);
    270        if (!placement.hasRoomLocation(getResourceId()))
    271            return;
    272        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    273            int slot = e.nextElement();
    274            iResource[slot].remove(placement);
    275        }
    276        getModel().getCriterion(UselessHalfHours.class).inc(-iLastUselessHalfHours);
    277        iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this);
    278        getModel().getCriterion(UselessHalfHours.class).inc(iLastUselessHalfHours);
    279        getModel().getCriterion(BrokenTimePatterns.class).inc(-iLastBrokenTimePatterns);
    280        iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0;
    281        getModel().getCriterion(BrokenTimePatterns.class).inc(iLastBrokenTimePatterns);
    282    }
    283
    284    /**
    285     * Lookup table getResource()[slot] -> lecture using this room placed in the
    286     * given time slot (null if empty)
    287     */
    288    public List<Placement> getResource(int slot) {
    289        return iResource[slot];
    290    }
    291
    292    public Placement[] getResourceOfWeek(int startDay) {
    293        Placement[] ret = new Placement[iResource.length];
    294        for (int i = 0; i < iResource.length; i++) {
    295            ret[i] = getPlacement(i, startDay + (i / Constants.SLOTS_PER_DAY));
    296        }
    297        return ret;
    298    }
    299
    300    /** Room usage */
    301    protected void printUsage(StringBuffer sb) {
    302        for (int slot = 0; slot < iResource.length; slot++) {
    303            for (Placement p : iResource[slot]) {
    304                int day = slot / Constants.SLOTS_PER_DAY;
    305                int time = slot * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN;
    306                int h = time / 60;
    307                int m = time % 60;
    308                String d = Constants.DAY_NAMES_SHORT[day];
    309                int slots = p.getTimeLocation().getLength();
    310                time += (30 * slots);
    311                int h2 = time / 60;
    312                int m2 = time % 60;
    313                sb.append(sb.length() == 0 ? "" : ",\n        ").append(
    314                        "[" + d + (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a") + "-"
    315                                + (h2 > 12 ? h2 - 12 : h2) + ":" + (m2 < 10 ? "0" : "") + m2 + (h2 >= 12 ? "p" : "a")
    316                                + "]=").append(p.variable().getName());
    317                slot += slots - 1;
    318                // sb.append(sb.length()==0?"":", ").append("s"+(slot+1)+"=").append(((Lecture)getResource()[slot]).getName());
    319            }
    320        }
    321    }
    322
    323    @Override
    324    public String toString() {
    325        return "Room " + getName();
    326    }
    327
    328    /** Position of the building */
    329    public void setCoordinates(Double x, Double y) {
    330        iPosX = x;
    331        iPosY = y;
    332    }
    333
    334    /** X-position of the building */
    335    public Double getPosX() {
    336        return iPosX;
    337    }
    338
    339    /** Y-position of the building */
    340    public Double getPosY() {
    341        return iPosY;
    342    }
    343
    344    public boolean getIgnoreTooFar() {
    345        return iIgnoreTooFar;
    346    }
    347
    348    public boolean getConstraint() {
    349        return iConstraint;
    350    }
    351
    352    public Long getType() {
    353        return iType;
    354    }
    355
    356    public void setType(Long type) {
    357        iType = type;
    358    }
    359}