001    package net.sf.cpsolver.coursett.constraint;
002    
003    import java.util.ArrayList;
004    import java.util.BitSet;
005    import java.util.Collections;
006    import java.util.HashMap;
007    import java.util.HashSet;
008    import java.util.List;
009    import java.util.Set;
010    import java.util.regex.Matcher;
011    import java.util.regex.Pattern;
012    
013    import net.sf.cpsolver.coursett.Constants;
014    import net.sf.cpsolver.coursett.model.Lecture;
015    import net.sf.cpsolver.coursett.model.Placement;
016    import 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     */
041    public 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    }