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