    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 MaxBlock constraint checks for too big blocks of back-to-back classes of an instructor.<br>
    023 * It has two parameters: a maximal length of a back-to-back block that is allowed and a minimal length of a break between two classes not to be considered in the same block.<br>
    024 * Reference _MaxBlock:120:30_ translates to a maximal block of at most 2 hours (120 minutes) with classes not more than 30 minutes a part.<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 MaxBlockFlexibleConstraint extends FlexibleConstraint {
    045
    046    // max number of slots between to classes to be considered Back-To-Back
    047    private int iMaxBreakBetweenBTB;
    048    // max length of a block of classes taught Back-To-Back
    049    protected int iMaxBlockSlotsBTB;
    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 MaxBlockFlexibleConstraint(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 = "_(MaxBlock):([0-9]+):([0-9]+)_";
    067        pattern = Pattern.compile(patternString);
    068        matcher = pattern.matcher(reference);
    069        if (matcher.find()) {
    070            iMaxBlockSlotsBTB = Integer.parseInt(matcher.group(2))/Constants.SLOT_LENGTH_MIN;
    071            iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3))/Constants.SLOT_LENGTH_MIN;
    072            iConstraintType = FlexibleConstraint.FlexibleConstraintType.MAXBLOCK_BACKTOBACK;
    073        }
    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        // constraint is checked for every day in week
    085        for (int dayCode : Constants.DAY_CODES) {
    086            // constraint is checked for every week in semester (or for the whole semester)
    087            for (BitSet week : weeks) {
    088                boolean isProblem = false;
    089                do {
    090                    isProblem = false;
    091                    // each blocks contains placements which are BTB
    092                    List<Block> blocks = getBlocks(assignment, dayCode, conflicts, value, null, week);
    093                    for (Block block : blocks) {
    094                        // if the block is not affected by the current placement, continue
    095                        if (!block.getPlacements().contains(value)){
    096                            continue;
    097                        }
    098                        Set<Placement> adepts = new HashSet<Placement>();
    099                        // if there is only 1 placement in block, the block cannot be shortened
    100                        // if placements of a block start at the same time, they intersect
    101                        // this solves problem when between 2 classes is required MEET_TOGETHER
    102                        if (block.getNbrPlacements() == 1 || block.haveSameStartTime())
    103                            continue;
    104                        // if block is longer than maximum size, some of its placements are conflicts
    105                        if (block.getLengthInSlots() > iMaxBlockSlotsBTB) {
    106                            // classes from block are potential conflicts
    107                            adepts.addAll(block.getPlacements());
    108                            // do not set currently assigned value as conflict
    109                            adepts.remove(value);
    110                            isProblem = true;
    111                            // pick random placement
    112                            Placement conflict = ToolBox.random(adepts);
    113                            if (conflict != null) {
    114                                conflicts.add(conflict);
    115                            }
    116                        }
    117                    }
    118                } while (isProblem);
    119            }
    120        }
    121    }
    122
    123    public List<Block> getBlocks(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    124        List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
    125        Collections.sort(toBeSorted, new PlacementTimeComparator());
    126
    127        return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB);
    128    }
    129
    130    @Override
    131    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    132        List<BitSet> weeks = getWeeks();
    133
    134        int violatedBlocks = 0;
    135        for (int dayCode : Constants.DAY_CODES) {
    136            for (BitSet week : weeks) {
    137                List<Block> blocks = getBlocks(assignment, dayCode, null, null, assignments, week);
    138                for (Block block : blocks) {
    139                    if (block.getNbrPlacements() == 1 || block.haveSameStartTime())
    140                        continue;
    141                    // violated if there is a block containing more than one
    142                    // class longer than iMaxBlockSlotsBTB
    143                    if (block.getLengthInSlots() > iMaxBlockSlotsBTB) {
    144                        int blockLengthPenalty = block.getLengthInSlots() / iMaxBlockSlotsBTB;
    145                        violatedBlocks += blockLengthPenalty;
    146                    }
    147                }
    148            }
    149        }
    150        return violatedBlocks;
    151    }
    152
    153}