001package org.cpsolver.coursett.criteria; 002 003import java.util.List; 004 005import org.cpsolver.coursett.Constants; 006import org.cpsolver.coursett.constraint.RoomConstraint.RoomConstraintContext; 007import org.cpsolver.coursett.model.Placement; 008import org.cpsolver.coursett.model.TimeLocation; 009import org.cpsolver.ifs.util.DataProperties; 010 011 012/** 013 * Useless half-hours. This criterion counts cases when there is an empty half hour in a room. 014 * Such half-hours should be generally avoided as usually any class takes more than half an hour. 015 * <br> 016 * 017 * @version CourseTT 1.3 (University Course Timetabling)<br> 018 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 019 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 020 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 021 * <br> 022 * This library is free software; you can redistribute it and/or modify 023 * it under the terms of the GNU Lesser General Public License as 024 * published by the Free Software Foundation; either version 3 of the 025 * License, or (at your option) any later version. <br> 026 * <br> 027 * This library is distributed in the hope that it will be useful, but 028 * WITHOUT ANY WARRANTY; without even the implied warranty of 029 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 030 * Lesser General Public License for more details. <br> 031 * <br> 032 * You should have received a copy of the GNU Lesser General Public 033 * License along with this library; if not see 034 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 035 */ 036public class UselessHalfHours extends BrokenTimePatterns { 037 038 @Override 039 public double getWeightDefault(DataProperties config) { 040 return Constants.sPreferenceLevelStronglyDiscouraged * config.getPropertyDouble("Comparator.UselessSlotWeight", 0.1); 041 } 042 043 @Override 044 public String getPlacementSelectionWeightName() { 045 return "Placement.UselessSlotsWeight"; 046 } 047 048 @Override 049 protected double penalty(RoomConstraintContext rc) { 050 return countUselessSlotsHalfHours(rc); 051 } 052 053 @Override 054 protected double penalty(RoomConstraintContext rc, Placement value) { 055 return countUselessSlotsHalfHours(rc, value); 056 } 057 058 private static boolean isEmpty(RoomConstraintContext rc, int slot, Placement placement) { 059 List<Placement> assigned = rc.getPlacements(slot); 060 return assigned.isEmpty() || (placement != null && assigned.size() == 1 && assigned.get(0).variable().equals(placement.variable())); 061 } 062 063 064 private static boolean isUselessBefore(RoomConstraintContext rc, int slot, Placement placement) { 065 int s = slot % Constants.SLOTS_PER_DAY; 066 if (s - 1 < 0 || s + 6 >= Constants.SLOTS_PER_DAY) 067 return false; 068 return (!isEmpty(rc, slot - 1, placement) && 069 isEmpty(rc, slot + 0, placement) && 070 isEmpty(rc, slot + 1, placement) && 071 isEmpty(rc, slot + 2, placement) && 072 isEmpty(rc, slot + 3, placement) && 073 isEmpty(rc, slot + 4, placement) && 074 isEmpty(rc, slot + 5, placement) && 075 isEmpty(rc, slot + 6, placement)); 076 } 077 078 private static boolean isUselessAfter(RoomConstraintContext rc, int slot, Placement placement) { 079 int s = slot % Constants.SLOTS_PER_DAY; 080 if (s - 1 < 0 || s + 6 >= Constants.SLOTS_PER_DAY) 081 return false; 082 return (isEmpty(rc, slot - 1, placement) && 083 isEmpty(rc, slot + 0, placement) && 084 isEmpty(rc, slot + 1, placement) && 085 isEmpty(rc, slot + 2, placement) && 086 isEmpty(rc, slot + 3, placement) && 087 isEmpty(rc, slot + 4, placement) && 088 isEmpty(rc, slot + 5, placement) && 089 !isEmpty(rc, slot + 6, placement)); 090 } 091 092 private static boolean isUseless(RoomConstraintContext rc, int slot, Placement placement) { 093 int s = slot % Constants.SLOTS_PER_DAY; 094 if (s - 1 < 0 || s + 6 >= Constants.SLOTS_PER_DAY) 095 return false; 096 return (!isEmpty(rc, slot - 1, placement) && 097 isEmpty(rc, slot + 0, placement) && 098 isEmpty(rc, slot + 1, placement) && 099 isEmpty(rc, slot + 2, placement) && 100 isEmpty(rc, slot + 3, placement) && 101 isEmpty(rc, slot + 4, placement) && 102 isEmpty(rc, slot + 5, placement) && 103 !isEmpty(rc, slot + 6, placement)); 104 } 105 106 /** Number of useless half hours for this room 107 * @param rc room constraint assignment context 108 * @param placement placement that is being considered 109 * @return number of useless slots caused by the given placement 110 **/ 111 protected static int countUselessSlotsHalfHours(RoomConstraintContext rc, Placement placement) { 112 int ret = 0; 113 TimeLocation time = placement.getTimeLocation(); 114 int slot = time.getStartSlot() % Constants.SLOTS_PER_DAY; 115 int days = time.getDayCode(); 116 for (int d = 0; d < Constants.NR_DAYS; d++) { 117 if ((Constants.DAY_CODES[d] & days) == 0) 118 continue; 119 if (isUselessBefore(rc, d * Constants.SLOTS_PER_DAY + slot - 6, placement)) 120 ret ++; 121 if (isUselessAfter(rc, d * Constants.SLOTS_PER_DAY + slot + time.getNrSlotsPerMeeting(), placement)) 122 ret ++; 123 if (time.getNrSlotsPerMeeting() == 6 && isUseless(rc, d * Constants.SLOTS_PER_DAY + slot, placement)) 124 ret --; 125 } 126 return ret; 127 } 128 129 private static boolean isUseless(RoomConstraintContext rc, int slot) { 130 int s = slot % Constants.SLOTS_PER_DAY; 131 if (s - 1 < 0 || s + 6 >= Constants.SLOTS_PER_DAY) 132 return false; 133 return (!rc.getPlacements(slot - 1).isEmpty() && 134 rc.getPlacements(slot + 0).isEmpty() && 135 rc.getPlacements(slot + 1).isEmpty() && 136 rc.getPlacements(slot + 2).isEmpty() && 137 rc.getPlacements(slot + 3).isEmpty() && 138 rc.getPlacements(slot + 4).isEmpty() && 139 rc.getPlacements(slot + 5).isEmpty() && 140 !rc.getPlacements(slot + 6).isEmpty()); 141 } 142 143 /** Number of useless slots for this room 144 * @param rc room constraint assignment context 145 * @return current penalty for the given room 146 **/ 147 public static int countUselessSlotsHalfHours(RoomConstraintContext rc) { 148 int ret = 0; 149 for (int d = 0; d < Constants.NR_DAYS; d++) { 150 for (int s = 0; s < Constants.SLOTS_PER_DAY; s++) { 151 int slot = d * Constants.SLOTS_PER_DAY + s; 152 if (isUseless(rc, slot)) 153 ret++; 154 } 155 } 156 return ret; 157 } 158}