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}