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.List;
008    import java.util.Map;
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.model.WeakeningConstraint;
017    import net.sf.cpsolver.ifs.util.ToolBox;
018    
019    /**
020     * 
021     * The MaxBreaks constraint limits the number of blocks of non back-to-back classes of an instructor on a day.<br>
022     * It has two parameters: a maximal number of breaks and a minimal length of a break between two classes not to be considered in the same block.<br>
023     * Reference _MaxBreaks:1:30_ translates to a maximum number of one break (two blocks) on a day of classes not more than 30 minutes a part.<br>
024     * 
025     * @version CourseTT 1.2 (University Course Timetabling)<br>
026     *          Copyright (C) 2013 Tomas Muller<br>
027     * <br>
028     *          This library is free software; you can redistribute it and/or modify
029     *          it under the terms of the GNU Lesser General Public License as
030     *          published by the Free Software Foundation; either version 3 of the
031     *          License, or (at your option) any later version. <br>
032     * <br>
033     *          This library is distributed in the hope that it will be useful, but
034     *          WITHOUT ANY WARRANTY; without even the implied warranty of
035     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
036     *          Lesser General Public License for more details. <br>
037     * <br>
038     *          You should have received a copy of the GNU Lesser General Public
039     *          License along with this library; if not see
040     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
041     */
042    public class MaxBreaksFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
043        private int iMaxBreakBetweenBTB;
044        private int iMaxBlocksOnADay;
045        private Map<Lecture, Placement> iWeakAssignment = new HashMap<Lecture, Placement>();
046        
047        public MaxBreaksFlexibleConstraint(Long id, String owner, String preference, String reference) {
048            super(id, owner, preference, reference);     
049    
050            Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_BREAKS.getPattern()).matcher(reference);
051            if (matcher.find()) {                
052                iMaxBlocksOnADay = 1 + Integer.parseInt(matcher.group(2));
053                iMaxBreakBetweenBTB = Integer.parseInt(matcher.group(3)) / Constants.SLOT_LENGTH_MIN;
054                iConstraintType = FlexibleConstraintType.MAX_BREAKS;           
055            }   
056        }
057    
058        public List<Block> getBlocks(int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {     
059            List<Placement> toBeSorted = new ArrayList<Placement>(getRelevantPlacements(dayCode, conflicts, value, assignments, week));
060            Collections.sort(toBeSorted, new PlacementTimeComparator());  
061            
062            return mergeToBlocks(toBeSorted, iMaxBreakBetweenBTB);
063        } 
064    
065        @Override
066        public double getNrViolations(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
067            int penalty = 0;
068            // constraint is checked for every day in week
069            for (int dayCode : Constants.DAY_CODES) {
070                // constraint is checked for every week in semester (or for the whole semester)
071                for (BitSet week : getWeeks()) {
072                    // each blocks contains placements which are BTB
073                    List<Block> blocks = getBlocks(dayCode, null, null, assignments, week);
074                    // too many blocks -> increase penalty
075                    if (blocks.size() > iMaxBlocksOnADay)
076                        penalty += (blocks.size() - iMaxBlocksOnADay) * (blocks.size() - iMaxBlocksOnADay);
077                }
078            }
079            return penalty;
080        }
081    
082        @Override
083        public void computeConflicts(Placement value, Set<Placement> conflicts) {
084            if (!isHard()) return;
085            
086            if (value.equals(iWeakAssignment.get(value.variable()))) {
087                for (Lecture v: variables())
088                    if (v.getAssignment() == null && !v.equals(value.variable())) {
089                        // incomplete and week -- do not check for conflicts just yet
090                        return;
091                    }
092            }
093            
094            // constraint is checked for every day in week
095            for (int dayCode : Constants.DAY_CODES) {
096                if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
097                // constraint is checked for every week in semester (or for the whole semester)
098                for (BitSet week : getWeeks()) {
099                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
100                    // each blocks contains placements which are BTB
101                    List<Block> blocks = getBlocks(dayCode, conflicts, value, null, week);
102                    while (blocks.size() > iMaxBlocksOnADay) {
103                        // too many blocks -> identify adepts for unassignment
104                        List<Block> adepts = new ArrayList<Block>(); int size = 0;
105                        for (Block block: blocks) {
106                            if (block.getPlacements().contains(value)) continue; // skip block containing given value
107                            // select adepts of the smallest size
108                            if (adepts.isEmpty() || size > block.getPlacements().size()) {
109                                adepts.clear();
110                                adepts.add(block);
111                                size = block.getPlacements().size();
112                            } else if (size == block.getPlacements().size()) {
113                                adepts.add(block);
114                            }
115                        }
116                        
117                        // pick one randomly
118                        Block block = ToolBox.random(adepts);
119                        blocks.remove(block);
120                        for (Placement conflict: block.getPlacements())
121                            if (conflict.equals(conflict.variable().getAssignment()))
122                                conflicts.add(conflict);
123                    }
124                }
125            }
126        }
127    
128        @Override
129        public void weaken() {
130        }
131    
132        @Override
133        public void weaken(Placement value) {
134            if (isHard())
135                iWeakAssignment.put(value.variable(), value);
136        }
137        
138        @Override
139        public void assigned(long iteration, Placement value) {
140            super.assigned(iteration, value);
141            if (isHard())
142                iWeakAssignment.remove(value.variable());
143        }
144    }