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