    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Collections;
    006import java.util.HashMap;
    007import java.util.HashSet;
    008import java.util.List;
    009import java.util.Set;
    010import java.util.regex.Matcher;
    011import java.util.regex.Pattern;
    012
    013import org.cpsolver.coursett.Constants;
    014import org.cpsolver.coursett.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.ifs.assignment.Assignment;
    017import org.cpsolver.ifs.util.ToolBox;
    018
    019
    020/**
    021 *
    022 * The Break constraint checks for instructor lunch break or a break in general in between the given classes.<br>
    023 * It has three parameters: a start and an end time of a window in which the break is required / preferred, and a minimal length of a break that is needed.<br>
    024 * Reference _Break:132:162:30_ translates to a break of at least 30 minutes between 11 am (slot 132) and 1:30 pm (slot 162).<br>
    025 *
    026 * @version CourseTT 1.3 (University Course Timetabling)<br>
    027 *          Copyright (C) 2013 Matej Lukac<br>
    028 * <br>
    029 *          This library is free software; you can redistribute it and/or modify
    030 *          it under the terms of the GNU Lesser General Public License as
    031 *          published by the Free Software Foundation; either version 3 of the
    032 *          License, or (at your option) any later version. <br>
    033 * <br>
    034 *          This library is distributed in the hope that it will be useful, but
    035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    037 *          Lesser General Public License for more details. <br>
    038 * <br>
    039 *          You should have received a copy of the GNU Lesser General Public
    040 *          License along with this library; if not see
    041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    042 */
    043public class BreakFlexibleConstraint extends FlexibleConstraint {
    044
    045    // LunchBreak constraint parameters
    046    private int iBreakStart;
    047    private int iBreakEnd;
    048    private int iBreakLength;
    049
    050    /**
    051     *
    052     * @param id constraint unique id
    053     * @param owner identifier of distribution preference the constraint was created for
    054     * @param preference time preference ("R" for required, "P" for prohibited, "-2",
    055     *            "-1", "1", "2" for soft preference)
    056     * @param reference parameters of the constraint in String form
    057     */
    058    public BreakFlexibleConstraint(Long id, String owner, String preference, String reference) {
    059        super(id, owner, preference, reference);
    060
    061        Pattern pattern = null;
    062        Matcher matcher = null;
    063
    064        // recognize Break constraint
    065        String patternString = "_(Break):([0-9]+):([0-9]+):([0-9]+)_";
    066        pattern = Pattern.compile(patternString);
    067        matcher = pattern.matcher(reference);
    068        if (matcher.find()) {
    069            iBreakStart = Integer.parseInt(matcher.group(2));
    070            iBreakEnd = Integer.parseInt(matcher.group(3));
    071            iBreakLength = Integer.parseInt(matcher.group(4))/Constants.SLOT_LENGTH_MIN;
    072            iConstraintType = FlexibleConstraintType.BREAK;
    073        }
    074    }
    075
    076    @Override
    077    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    078        if (!isHard())
    079            return;
    080
    081        List<BitSet> weeks = getWeeks();
    082
    083        // checks only placements in the break time
    084        if (value.getTimeLocation().getStartSlot() <= iBreakEnd
    085                && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iBreakStart) {
    086
    087            for (int dayCode : Constants.DAY_CODES) {
    088                // checks only days affected by the placement
    089                if ((value.getTimeLocation().getDayCode() & dayCode) != 0) {
    090                    // constraint is checked for every week in semester (or for the whole semester)
    091                    for (BitSet week : weeks) {
    092                        boolean isProblem = false;
    093                        do {
    094                            Set<Placement> adepts = new HashSet<Placement>();
    095                            // each blocks contains placements which are BTB
    096                            // placements are BTB if there is less time between them than the minimal break length
    097                            List<Block> blocks = getBreakBlocks(assignment, dayCode, conflicts, value, null, week);
    098                            // determine possible conflicts from blocks' placements
    099                            getAdeptsLunchBreak(blocks, adepts);
    100                            if (adepts.isEmpty())
    101                                isProblem = false;
    102                            // currently assigned value shouldn't be added to conflicts if possible
    103                            if (adepts.size() >= 2)
    104                                adepts.remove(value);
    105                            // pick random placement
    106                            Placement conflict = ToolBox.random(adepts);
    107                            if (conflict != null) {
    108                                conflicts.add(conflict);
    109                            }
    110                        } while (isProblem);
    111                    }
    112                }
    113            }
    114        }
    115    }
    116
    117    /**
    118     * Creates a list of consecutive blocks with back-to-back classes.
    119     * @param assignment current assignment
    120     * @param dayCode days of week
    121     * @param conflicts conflicting assignment
    122     * @param value placement in question
    123     * @param assignments other considered assignments
    124     * @param week selected week
    125     * @return classes merged into blocks
    126     */
    127    public List<Block> getBreakBlocks(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    128
    129        List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
    130        Collections.sort(toBeSorted, new PlacementTimeComparator());
    131
    132        return mergeToBlocks(toBeSorted, iBreakLength);
    133    }
    134
    135
    136
    137    /**
    138     * Method adds Placements from blocks to adepts if there is a possibility, that the placement caused constraint violation
    139     *
    140     * @param blocks placements in
    141     * @param adepts
    142     */
    143    private void getAdeptsLunchBreak(List<Block> blocks, Set<Placement> adepts) {
    144        List<Block> matchingBlocks = new ArrayList<Block>();
    145        for(Block block: blocks){
    146            // if block intersects with break interval, it will be used in conflict selection
    147            if (block.getStartSlotCurrentBlock() <= iBreakEnd && block.getEndSlotCurrentBlock() >= iBreakStart) matchingBlocks.add(block);
    148        }
    149        int size = matchingBlocks.size();
    150        // if there is none block intersecting with break interval, the constraint is satisfied
    151        // if there are at least 2 blocks intersecting with break interval, the constraint is satisfied,
    152        // because there must be a space between them, otherwise they would be in one block
    153        // if there is only one block intersecting with break interval, constraint might not be satisfied
    154        if (size == 1) {
    155            Block block = matchingBlocks.get(0);
    156            // check whether the block leaves enough space for break
    157            if (block.getStartSlotCurrentBlock() - iBreakStart >= iBreakLength || iBreakEnd - block.getEndSlotCurrentBlock() >= iBreakLength){
    158                return;
    159            // if it doesn't
    160            }else{
    161                // every placement intersecting with break interval might be potential conflict
    162                for (Placement p: block.getPlacements()){
    163                    if ( p.getTimeLocation().getStartSlot() <= iBreakEnd && p.getTimeLocation().getStartSlot()+ p.getTimeLocation().getLength() >= iBreakStart){
    164                        adepts.add(p);
    165                    }
    166                }
    167            }
    168        }
    169    }
    170
    171    @Override
    172    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
    173        List<BitSet> weeks = getWeeks();
    174
    175        int violatedDays = 0;
    176        for (int dayCode : Constants.DAY_CODES) {
    177            weekIteration: for (BitSet week : weeks) {
    178                Set<Placement> adepts = new HashSet<Placement>();
    179                List<Block> blocks = getBreakBlocks(assignment, dayCode, null, null, assignments, week);
    180                getAdeptsLunchBreak(blocks, adepts);
    181                if (!adepts.isEmpty())
    182                    violatedDays++;
    183                break weekIteration;
    184            }
    185        }
    186        return violatedDays;
    187    }
    188
    189}