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