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