    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Collection;
    006import java.util.Enumeration;
    007import java.util.HashSet;
    008import java.util.List;
    009import java.util.Set;
    010
    011import org.cpsolver.coursett.Constants;
    012import org.cpsolver.coursett.criteria.BrokenTimePatterns;
    013import org.cpsolver.coursett.criteria.UselessHalfHours;
    014import org.cpsolver.coursett.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.coursett.model.RoomSharingModel;
    017import org.cpsolver.coursett.model.TimeLocation;
    018import org.cpsolver.coursett.model.TimetableModel;
    019import org.cpsolver.ifs.assignment.Assignment;
    020import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    021import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
    022import org.cpsolver.ifs.model.Model;
    023import org.cpsolver.ifs.util.DataProperties;
    024
    025
    026/**
    027 * Room constraint. <br>
    028 * Classes with the same room can not overlap in time.
    029 *
    030 * @version CourseTT 1.3 (University Course Timetabling)<br>
    031 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    032 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    033 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    034 * <br>
    035 *          This library is free software; you can redistribute it and/or modify
    036 *          it under the terms of the GNU Lesser General Public License as
    037 *          published by the Free Software Foundation; either version 3 of the
    038 *          License, or (at your option) any later version. <br>
    039 * <br>
    040 *          This library is distributed in the hope that it will be useful, but
    041 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    042 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    043 *          Lesser General Public License for more details. <br>
    044 * <br>
    045 *          You should have received a copy of the GNU Lesser General Public
    046 *          License along with this library; if not see
    047 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    048 */
    049
    050public class RoomConstraint extends ConstraintWithContext<Lecture, Placement, RoomConstraint.RoomConstraintContext> {
    051    private Long iResourceId;
    052    private String iName;
    053    private Long iBuildingId;
    054    private int iCapacity = 0;
    055    private List<Placement>[] iAvailable = null;
    056    private boolean iConstraint = true;
    057
    058    private Double iPosX = null, iPosY = null;
    059    private boolean iIgnoreTooFar = false;
    060
    061    private RoomSharingModel iRoomSharingModel = null;
    062
    063    private Long iType = null;
    064    private int iDayOfWeekOffset = 0;
    065
    066    /**
    067     * Constructor
    068     * @param id room unique id
    069     * @param name room name
    070     * @param buildingId building unique id
    071     * @param capacity room size
    072     * @param roomSharingModel room sharing model
    073     * @param x X-coordinate (latitude)
    074     * @param y Y-coordinate (longitude)
    075     * @param ignoreTooFar ignore distances if set to true
    076     * @param constraint hard constraint if true (classes cannot overlap in this room)
    077     */
    078    public RoomConstraint(Long id, String name, Long buildingId, int capacity, RoomSharingModel roomSharingModel,
    079            Double x, Double y, boolean ignoreTooFar, boolean constraint) {
    080        iResourceId = id;
    081        iName = name;
    082        iBuildingId = buildingId;
    083        iCapacity = capacity;
    084        iConstraint = constraint;
    085        iRoomSharingModel = roomSharingModel;
    086        iPosX = x;
    087        iPosY = y;
    088        iIgnoreTooFar = ignoreTooFar;
    089    }
    090
    091    @Override
    092    public void setModel(Model<Lecture, Placement> model) {
    093        super.setModel(model);
    094        if (model != null) {
    095            DataProperties config = ((TimetableModel)model).getProperties();
    096            iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0);
    097        }
    098    }
    099
    100    @SuppressWarnings("unchecked")
    101    public void setNotAvailable(Placement placement) {
    102        if (iAvailable == null) {
    103            iAvailable = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS];
    104            for (int i = 0; i < iAvailable.length; i++)
    105                iAvailable[i] = null;
    106        }
    107        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    108            int slot = e.nextElement();
    109            if (iAvailable[slot] == null)
    110                iAvailable[slot] = new ArrayList<Placement>(1);
    111            iAvailable[slot].add(placement);
    112        }
    113        for (Lecture lecture: variables())
    114            lecture.clearValueCache();
    115    }
    116
    117    public boolean isAvailable(int slot) {
    118        if (getConstraint() && iAvailable != null && iAvailable[slot] != null && !iAvailable[slot].isEmpty())
    119            return false;
    120        if (getSharingModel() != null && getSharingModel().isNotAvailable(slot))
    121            return false;
    122        return true;
    123    }
    124
    125    public boolean isAvailable(Lecture lecture, TimeLocation time, Long scheduler) {
    126        if (iAvailable != null && getConstraint()) {
    127            for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) {
    128                int slot = e.nextElement();
    129                if (iAvailable[slot] != null) {
    130                    for (Placement p : iAvailable[slot]) {
    131                        if (lecture.canShareRoom(p.variable()))
    132                            continue;
    133                        if (time.shareWeeks(p.getTimeLocation()))
    134                            return false;
    135                    }
    136                }
    137            }
    138        }
    139        if (getSharingModel() != null && !getSharingModel().isAvailable(time, scheduler))
    140            return false;
    141        return true;
    142    }
    143
    144    public List<Placement>[] getAvailableArray() {
    145        return iAvailable;
    146    }
    147
    148    public RoomSharingModel getSharingModel() {
    149        return iRoomSharingModel;
    150    }
    151
    152    /** Room id
    153     * @return room unique id
    154     **/
    155    public Long getResourceId() {
    156        return iResourceId;
    157    }
    158
    159    /** Building id
    160     * @return building unique id
    161     **/
    162    public Long getBuildingId() {
    163        return iBuildingId;
    164    }
    165
    166    /** Room name */
    167    @Override
    168    public String getName() {
    169        return iName;
    170    }
    171
    172    public String getRoomName() {
    173        return iName;
    174    }
    175
    176    /** Capacity
    177     * @return room size
    178     **/
    179    public int getCapacity() {
    180        return iCapacity;
    181    }
    182
    183    @Override
    184    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) {
    185        if (!getConstraint())
    186            return;
    187        if (!placement.hasRoomLocation(getResourceId()))
    188            return;
    189        Lecture lecture = placement.variable();
    190        Placement current = assignment.getValue(lecture);
    191        Set<Placement> shared = null;
    192        BitSet weekCode = placement.getTimeLocation().getWeekCode();
    193        RoomConstraintContext context = getContext(assignment);
    194
    195        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    196            int slot = e.nextElement();
    197            for (Placement confPlacement : context.getPlacements(slot)) {
    198                if (!confPlacement.getTimeLocation().shareWeeks(weekCode))
    199                    continue;
    200                if (confPlacement.equals(current))
    201                    continue;
    202                if (shared != null && shared.contains(confPlacement))
    203                    continue;
    204                if (confPlacement.canShareRooms(placement) && checkRoomSize(placement, shared, confPlacement)) {
    205                    if (shared == null) shared = new HashSet<Placement>();
    206                    shared.add(confPlacement);
    207                    continue;
    208                }
    209                conflicts.add(confPlacement);
    210            }
    211        }
    212    }
    213
    214    public boolean checkRoomSize(Placement placement, Collection<Placement> other, Placement extra) {
    215        int day = -1;
    216        TimeLocation t1 = placement.getTimeLocation();
    217        while ((day = t1.getWeekCode().nextSetBit(1 + day)) >= 0) {
    218            int dow = (day + iDayOfWeekOffset) % 7;
    219            if ((t1.getDayCode() & Constants.DAY_CODES[dow]) == 0) continue;
    220            if (extra != null) {
    221                TimeLocation t2 = extra.getTimeLocation();
    222                if (!t2.hasDay(day) || (t2.getDayCode() & Constants.DAY_CODES[dow]) == 0) continue;
    223            }
    224            for (int i = 0; i < t1.getLength(); i++) {
    225                int slot = t1.getStartSlot() + i;
    226                int size = placement.variable().maxRoomUse();
    227                if (extra != null) {
    228                    TimeLocation t2 = extra.getTimeLocation();
    229                    if (t2.getStartSlot() <= slot && slot < t2.getStartSlot() + t2.getLength())
    230                        size += extra.variable().maxRoomUse();
    231                    else
    232                        continue;
    233                }
    234                if (other != null)
    235                    for (Placement p: other) {
    236                        TimeLocation t2 = p.getTimeLocation();
    237                        if (t2.hasDay(day) && (t2.getDayCode() & Constants.DAY_CODES[dow]) != 0 && t2.getStartSlot() <= slot && slot < t2.getStartSlot() + t2.getLength())
    238                            size += p.variable().maxRoomUse();
    239                    }
    240                if (size > getCapacity()) {
    241                    return false;
    242                }
    243            }
    244        }
    245        return true;
    246    }
    247
    248    public boolean checkRoomSize(Placement placement, Collection<Placement> other) {
    249        return checkRoomSize(placement, other, null);
    250    }
    251
    252    @Override
    253    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) {
    254        if (!getConstraint())
    255            return false;
    256        if (!placement.hasRoomLocation(getResourceId()))
    257            return false;
    258        Lecture lecture = placement.variable();
    259        Placement current = assignment.getValue(lecture);
    260        Set<Placement> shared = null;
    261        BitSet weekCode = placement.getTimeLocation().getWeekCode();
    262        RoomConstraintContext context = getContext(assignment);
    263
    264        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    265            int slot = e.nextElement();
    266            for (Placement confPlacement : context.getPlacements(slot)) {
    267                if (!confPlacement.getTimeLocation().shareWeeks(weekCode))
    268                    continue;
    269                if (confPlacement.equals(current))
    270                    continue;
    271                if (shared != null && shared.contains(confPlacement))
    272                    continue;
    273                if (confPlacement.canShareRooms(placement) && checkRoomSize(placement, shared, confPlacement)) {
    274                    if (shared == null) shared = new HashSet<Placement>();
    275                    shared.add(confPlacement);
    276                    continue;
    277                }
    278                return true;
    279            }
    280        }
    281        return false;
    282    }
    283
    284    @Override
    285    public boolean isConsistent(Placement p1, Placement p2) {
    286        if (!getConstraint())
    287            return true;
    288        if (!p1.hasRoomLocation(getResourceId()))
    289            return false;
    290        if (!p2.hasRoomLocation(getResourceId()))
    291            return false;
    292        if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) {
    293            if (!p1.canShareRooms(p2) || (p1.variable()).maxRoomUse() + (p2.variable()).maxRoomUse() > getCapacity())
    294                return true;
    295        }
    296        return false;
    297    }
    298
    299    @Override
    300    public void assigned(Assignment<Lecture, Placement> assignment, long iteration, Placement placement) {
    301        if (placement.hasRoomLocation(getResourceId()))
    302            super.assigned(assignment, iteration, placement);
    303    }
    304
    305    @Override
    306    public void unassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement placement) {
    307        if (placement.hasRoomLocation(getResourceId()))
    308            super.unassigned(assignment, iteration, placement);
    309    }
    310
    311    /**
    312     * Lookup table getResource()[slot] &rarr; lecture using this room placed in the
    313     * given time slot (null if empty)
    314     * @param assignment current assignment
    315     * @param slot time slot
    316     * @return list of placements in the room in the given time
    317     */
    318    public List<Placement> getResource(Assignment<Lecture, Placement> assignment, int slot) {
    319        return getContext(assignment).getPlacements(slot);
    320    }
    321
    322    public Placement[] getResourceOfWeek(Assignment<Lecture, Placement> assignment, int startDay) {
    323        return getContext(assignment).getResourceOfWeek(startDay);
    324    }
    325
    326    @Override
    327    public String toString() {
    328        return "Room " + getName();
    329    }
    330
    331    /** Position of the building
    332     * @param x X-coordinate (latitude)
    333     * @param y Y-coordinate (longitude)
    334     **/
    335    public void setCoordinates(Double x, Double y) {
    336        iPosX = x;
    337        iPosY = y;
    338    }
    339
    340    /** X-position of the building
    341     * @return X-coordinate (latitude)
    342     **/
    343    public Double getPosX() {
    344        return iPosX;
    345    }
    346
    347    /** Y-position of the building
    348     * @return Y-coordinate (longitude)
    349     **/
    350    public Double getPosY() {
    351        return iPosY;
    352    }
    353
    354    public boolean getIgnoreTooFar() {
    355        return iIgnoreTooFar;
    356    }
    357
    358    public boolean getConstraint() {
    359        return iConstraint;
    360    }
    361
    362    public Long getType() {
    363        return iType;
    364    }
    365
    366    public void setType(Long type) {
    367        iType = type;
    368    }
    369
    370    @Override
    371    public RoomConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    372        return new RoomConstraintContext(assignment);
    373    }
    374
    375    public class RoomConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
    376        private List<Placement>[] iResource;
    377        private int iLastUselessHalfHours = 0;
    378        private double iLastBrokenTimePatterns = 0;
    379
    380        @SuppressWarnings("unchecked")
    381        public RoomConstraintContext(Assignment<Lecture, Placement> assignment) {
    382            iResource = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS];
    383            for (int i = 0; i < iResource.length; i++)
    384                iResource[i] = new ArrayList<Placement>(3);
    385            for (Lecture lecture: variables()) {
    386                Placement placement = assignment.getValue(lecture);
    387                if (placement != null && placement.hasRoomLocation(getResourceId())) {
    388                    for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    389                        int slot = e.nextElement();
    390                        iResource[slot].add(placement);
    391                    }
    392                }
    393            }
    394            iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this);
    395            getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours);
    396            iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0;
    397            getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns);
    398        }
    399
    400        @Override
    401        public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) {
    402            if (!placement.hasRoomLocation(getResourceId()))
    403                return;
    404            for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    405                int slot = e.nextElement();
    406                iResource[slot].add(placement);
    407            }
    408            getModel().getCriterion(UselessHalfHours.class).inc(assignment, -iLastUselessHalfHours);
    409            iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this);
    410            getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours);
    411            getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, -iLastBrokenTimePatterns);
    412            iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0;
    413            getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns);
    414        }
    415
    416        @Override
    417        public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) {
    418            if (!placement.hasRoomLocation(getResourceId()))
    419                return;
    420            for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
    421                int slot = e.nextElement();
    422                iResource[slot].remove(placement);
    423            }
    424            getModel().getCriterion(UselessHalfHours.class).inc(assignment, -iLastUselessHalfHours);
    425            iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this);
    426            getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours);
    427            getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, -iLastBrokenTimePatterns);
    428            iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0;
    429            getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns);
    430        }
    431
    432        public List<Placement> getPlacements(int slot) { return iResource[slot]; }
    433
    434        public Placement getPlacement(int slot, int day) {
    435            for (Placement p : iResource[slot]) {
    436                if (p.getTimeLocation().hasDay(day))
    437                    return p;
    438            }
    439            return null;
    440        }
    441
    442        public Placement[] getResourceOfWeek(int startDay) {
    443            Placement[] ret = new Placement[iResource.length];
    444            for (int i = 0; i < iResource.length; i++) {
    445                ret[i] = getPlacement(i, startDay + (i / Constants.SLOTS_PER_DAY));
    446            }
    447            return ret;
    448        }
    449
    450        public boolean inConflict(Lecture lecture, TimeLocation time) {
    451            for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) {
    452                int slot = e.nextElement();
    453                for (Placement confPlacement : getPlacements(slot)) {
    454                    if (!confPlacement.getTimeLocation().shareWeeks(time.getWeekCode())) continue;
    455                    if (confPlacement.variable().equals(lecture)) continue;
    456                    if (!confPlacement.variable().canShareRoom(lecture)) return true;
    457                }
    458            }
    459            return false;
    460        }
    461
    462    }
    463}