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}