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