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