001package org.cpsolver.studentsct.model; 002 003import java.util.HashMap; 004import java.util.HashSet; 005import java.util.Map; 006import java.util.Set; 007 008import org.cpsolver.ifs.assignment.Assignment; 009import org.cpsolver.ifs.assignment.context.AbstractClassWithContext; 010import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 011import org.cpsolver.ifs.assignment.context.CanInheritContext; 012import org.cpsolver.ifs.model.Model; 013import org.cpsolver.studentsct.reservation.Reservation; 014 015/** 016 * Representation of a group of students requesting the same course that 017 * should be scheduled in the same set of sections.<br> 018 * <br> 019 * 020 * @version StudentSct 1.3 (Student Sectioning)<br> 021 * Copyright (C) 2015 Tomáš Müller<br> 022 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 023 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 024 * <br> 025 * This library is free software; you can redistribute it and/or modify 026 * it under the terms of the GNU Lesser General Public License as 027 * published by the Free Software Foundation; either version 3 of the 028 * License, or (at your option) any later version. <br> 029 * <br> 030 * This library is distributed in the hope that it will be useful, but 031 * WITHOUT ANY WARRANTY; without even the implied warranty of 032 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 033 * Lesser General Public License for more details. <br> 034 * <br> 035 * You should have received a copy of the GNU Lesser General Public 036 * License along with this library; if not see 037 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 038 */ 039public class RequestGroup extends AbstractClassWithContext<Request, Enrollment, RequestGroup.RequestGroupContext> 040 implements CanInheritContext<Request, Enrollment, RequestGroup.RequestGroupContext>{ 041 private long iId = -1; 042 private String iName = null; 043 private Course iCourse; 044 private Set<CourseRequest> iRequests = new HashSet<CourseRequest>(); 045 private double iTotalWeight = 0.0; 046 047 /** 048 * Creates request group. Pair (id, course) must be unique. 049 * @param id identification of the group 050 * @param name group name 051 * @param course course for which the group is created (only course requests for this course can be of this group) 052 */ 053 public RequestGroup(long id, String name, Course course) { 054 iId = id; 055 iName = name; 056 iCourse = course; 057 iCourse.getRequestGroups().add(this); 058 } 059 060 /** 061 * Add course request to the group. It has to contain the course of this group {@link RequestGroup#getCourse()}. 062 * This is done automatically by {@link CourseRequest#addRequestGroup(RequestGroup)}. 063 * @param request course request to be added to this group 064 */ 065 public void addRequest(CourseRequest request) { 066 if (iRequests.add(request)) 067 iTotalWeight += request.getWeight(); 068 } 069 070 /** 071 * Remove course request from the group. This is done automatically by {@link CourseRequest#removeRequestGroup(RequestGroup)}. 072 * @param request course request to be removed from this group 073 */ 074 public void removeRequest(CourseRequest request) { 075 if (iRequests.remove(request)) 076 iTotalWeight -= request.getWeight(); 077 } 078 079 /** 080 * Return the set of course requests that are associated with this group. 081 * @return course requests of this group 082 */ 083 public Set<CourseRequest> getRequests() { 084 return iRequests; 085 } 086 087 /** 088 * Total weight (using {@link CourseRequest#getWeight()}) of the course requests of this group 089 * @return total weight of course requests in this group 090 */ 091 public double getTotalWeight() { 092 return iTotalWeight; 093 } 094 095 /** 096 * Request group id 097 * @return request group id 098 */ 099 public long getId() { 100 return iId; 101 } 102 103 /** 104 * Request group name 105 * @return request group name 106 */ 107 public String getName() { 108 return iName; 109 } 110 111 /** 112 * Course associated with this group. Only course requests for this course can be of this group. 113 * @return course of this request group 114 */ 115 public Course getCourse() { 116 return iCourse; 117 } 118 119 @Override 120 public boolean equals(Object o) { 121 if (o == null || !(o instanceof RequestGroup)) return false; 122 return getId() == ((RequestGroup)o).getId() && getCourse().getId() == ((RequestGroup)o).getCourse().getId(); 123 } 124 125 @Override 126 public int hashCode() { 127 return (int) (iId ^ (iCourse.getId() >>> 32)); 128 } 129 130 /** Called when an enrollment is assigned to a request of this request group */ 131 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 132 getContext(assignment).assigned(assignment, enrollment); 133 } 134 135 /** Called when an enrollment is unassigned from a request of this request group */ 136 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 137 getContext(assignment).unassigned(assignment, enrollment); 138 } 139 140 /** 141 * Enrollment weight -- weight of all requests which have an enrollment that 142 * is of this request group, excluding the given one. See 143 * {@link Request#getWeight()}. 144 * @param assignment current assignment 145 * @param excludeRequest course request to ignore, if any 146 * @return enrollment weight 147 */ 148 public double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 149 return getContext(assignment).getEnrollmentWeight(assignment, excludeRequest); 150 } 151 152 /** 153 * Section weight -- weight of all requests which have an enrollment that 154 * is of this request group and that includes the given section, excluding the given one. See 155 * {@link Request#getWeight()}. 156 * @param assignment current assignment 157 * @param section section in question 158 * @param excludeRequest course request to ignore, if any 159 * @return enrollment weight 160 */ 161 public double getSectionWeight(Assignment<Request, Enrollment> assignment, Section section, Request excludeRequest) { 162 return getContext(assignment).getSectionWeight(assignment, section, excludeRequest); 163 } 164 165 /** 166 * Return how much is the given enrollment similar to other enrollments of this group. 167 * @param assignment current assignment 168 * @param enrollment enrollment in question 169 * @param bestRatio how much of the weight should be used on estimation of the enrollment potential 170 * (considering that students of this group that are not yet enrolled can take the same enrollment) 171 * @param fillRatio how much of the weight should be used in estimation how well are the sections of this enrollments going to be filled 172 * (bestRatio + fillRatio <= 1.0) 173 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 174 */ 175 public double getEnrollmentSpread(Assignment<Request, Enrollment> assignment, Enrollment enrollment, double bestRatio, double fillRatio) { 176 return getContext(assignment).getEnrollmentSpread(assignment, enrollment, bestRatio, fillRatio); 177 } 178 179 /** 180 * Return average section spread of this group. It reflects the probability of two students of this group 181 * being enrolled in the same section. 182 * @param assignment current assignment 183 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 184 */ 185 public double getAverageSpread(Assignment<Request, Enrollment> assignment) { 186 return getContext(assignment).getAverageSpread(); 187 } 188 189 /** 190 * Return section spread of this group. It reflects the probability of two students of this group 191 * being enrolled in this section. 192 * @param assignment current assignment 193 * @param section given section 194 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 195 */ 196 public double getSectionSpread(Assignment<Request, Enrollment> assignment, Section section) { 197 return getContext(assignment).getSectionSpread(section); 198 } 199 200 public class RequestGroupContext implements AssignmentConstraintContext<Request, Enrollment> { 201 private Set<Enrollment> iEnrollments = null; 202 private double iEnrollmentWeight = 0.0; 203 private Map<Long, Double> iSectionWeight = null; 204 private boolean iReadOnly = false; 205 206 public RequestGroupContext(Assignment<Request, Enrollment> assignment) { 207 iEnrollments = new HashSet<Enrollment>(); 208 iSectionWeight = new HashMap<Long, Double>(); 209 for (CourseRequest request: getCourse().getRequests()) { 210 if (request.getRequestGroups().contains(RequestGroup.this)) { 211 Enrollment enrollment = assignment.getValue(request); 212 if (enrollment != null && getCourse().equals(enrollment.getCourse())) 213 assigned(assignment, enrollment); 214 } 215 } 216 } 217 218 public RequestGroupContext(RequestGroupContext parent) { 219 iEnrollmentWeight = parent.iEnrollmentWeight; 220 iEnrollments = parent.iEnrollments; 221 iSectionWeight = parent.iSectionWeight; 222 iReadOnly = true; 223 } 224 225 /** Called when an enrollment is assigned to a request of this request group */ 226 @Override 227 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 228 if (iReadOnly) { 229 iEnrollments = new HashSet<Enrollment>(iEnrollments); 230 iSectionWeight = new HashMap<Long, Double>(iSectionWeight); 231 iReadOnly = false; 232 } 233 if (iEnrollments.add(enrollment)) { 234 iEnrollmentWeight += enrollment.getRequest().getWeight(); 235 for (Section section: enrollment.getSections()) { 236 Double weight = iSectionWeight.get(section.getId()); 237 iSectionWeight.put(section.getId(), enrollment.getRequest().getWeight() + (weight == null ? 0.0 : weight.doubleValue())); 238 } 239 } 240 } 241 242 /** Called when an enrollment is unassigned from a request of this request group */ 243 @Override 244 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 245 if (iReadOnly) { 246 iEnrollments = new HashSet<Enrollment>(iEnrollments); 247 iSectionWeight = new HashMap<Long, Double>(iSectionWeight); 248 iReadOnly = false; 249 } 250 if (iEnrollments.remove(enrollment)) { 251 iEnrollmentWeight -= enrollment.getRequest().getWeight(); 252 for (Section section: enrollment.getSections()) { 253 Double weight = iSectionWeight.get(section.getId()); 254 iSectionWeight.put(section.getId(), weight - enrollment.getRequest().getWeight()); 255 } 256 } 257 } 258 259 /** Set of assigned enrollments 260 * @return assigned enrollments of this request group 261 **/ 262 public Set<Enrollment> getEnrollments() { 263 return iEnrollments; 264 } 265 266 /** 267 * Enrollment weight -- weight of all requests which have an enrollment that 268 * is of this request group, excluding the given one. See 269 * {@link Request#getWeight()}. 270 * @param assignment current assignment 271 * @param excludeRequest course request to ignore, if any 272 * @return enrollment weight 273 */ 274 public double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 275 double weight = iEnrollmentWeight; 276 if (excludeRequest != null) { 277 Enrollment enrollment = assignment.getValue(excludeRequest); 278 if (enrollment!= null && iEnrollments.contains(enrollment)) 279 weight -= excludeRequest.getWeight(); 280 } 281 return weight; 282 } 283 284 /** 285 * Section weight -- weight of all requests which have an enrollment that 286 * is of this request group and that includes the given section, excluding the given one. See 287 * {@link Request#getWeight()}. 288 * @param assignment current assignment 289 * @param section section in question 290 * @param excludeRequest course request to ignore, if any 291 * @return enrollment weight 292 */ 293 public double getSectionWeight(Assignment<Request, Enrollment> assignment, Section section, Request excludeRequest) { 294 Double weight = iSectionWeight.get(section.getId()); 295 if (excludeRequest != null && weight != null) { 296 Enrollment enrollment = assignment.getValue(excludeRequest); 297 if (enrollment!= null && iEnrollments.contains(enrollment) && enrollment.getSections().contains(section)) 298 weight -= excludeRequest.getWeight(); 299 } 300 return (weight == null ? 0.0 : weight.doubleValue()); 301 } 302 303 /** 304 * Return space available in the given section 305 * @param assignment current assignment 306 * @param section section to check 307 * @param enrollment enrollment in question 308 * @return check section reservations, if present; use unreserved space otherwise 309 */ 310 private double getAvailableSpace(Assignment<Request, Enrollment> assignment, Section section, Enrollment enrollment) { 311 Reservation reservation = enrollment.getReservation(); 312 Set<Section> sections = (reservation == null ? null : reservation.getSections(section.getSubpart())); 313 if (reservation != null && sections != null && sections.contains(section) && !reservation.isExpired()) { 314 double sectionAvailable = (section.getLimit() < 0 ? Double.MAX_VALUE : section.getLimit() - section.getEnrollmentWeight(assignment, enrollment.getRequest())); 315 double reservationAvailable = reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()); 316 return Math.min(sectionAvailable, reservationAvailable) + (reservation.mustBeUsed() ? 0.0 : section.getUnreservedSpace(assignment, enrollment.getRequest())); 317 } else { 318 return section.getUnreservedSpace(assignment, enrollment.getRequest()); 319 } 320 } 321 322 /** 323 * Return how much is the given enrollment (which is not part of the request group) creating an issue for this request group 324 * @param assignment current assignment 325 * @param enrollment enrollment in question 326 * @param bestRatio how much of the weight should be used on estimation of the enrollment potential 327 * (considering that students of this group that are not yet enrolled can take the same enrollment) 328 * @param fillRatio how much of the weight should be used in estimation how well are the sections of this enrollments going to be filled 329 * (bestRatio + fillRatio <= 1.0) 330 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 331 */ 332 public double getEnrollmentSpread(Assignment<Request, Enrollment> assignment, Enrollment enrollment, double bestRatio, double fillRatio) { 333 if (iTotalWeight <= 1.0) return 1.0; 334 335 // enrollment weight (excluding the given enrollment) 336 double totalEnrolled = getEnrollmentWeight(assignment, enrollment.getRequest()); 337 double totalRemaining = iTotalWeight - totalEnrolled; 338 339 // section weight (also excluding the given enrollment) 340 Enrollment e = assignment.getValue(enrollment.getRequest()); 341 double enrollmentPairs = 0.0, bestPairs = 0.0, fill = 0.0; 342 for (Section section: enrollment.getSections()) { 343 double potential = Math.max(Math.min(totalRemaining, getAvailableSpace(assignment, section, enrollment)), enrollment.getRequest().getWeight()); 344 Double enrolled = iSectionWeight.get(section.getId()); 345 if (enrolled != null) { 346 if (e != null && e.getSections().contains(section)) 347 enrolled -= enrollment.getRequest().getWeight(); 348 potential += enrolled; 349 enrollmentPairs += enrolled * (enrolled + 1.0); 350 } 351 bestPairs += potential * (potential - 1.0); 352 if (section.getLimit() > potential) { 353 fill += potential / section.getLimit(); 354 } else { 355 fill += 1.0; 356 } 357 } 358 double pEnrl = (totalEnrolled < 1.0 ? 0.0 : (enrollmentPairs / enrollment.getSections().size()) / (totalEnrolled * (totalEnrolled + 1.0))); 359 double pBest = (bestPairs / enrollment.getSections().size()) / (iTotalWeight * (iTotalWeight - 1.0)); 360 double pFill = fill / enrollment.getSections().size(); 361 362 return (1.0 - bestRatio - fillRatio) * pEnrl + bestRatio * pBest + fillRatio * pFill; 363 } 364 365 /** 366 * Return average section spread of this group. It reflects the probability of two students of this group 367 * being enrolled in the same section. 368 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 369 */ 370 public double getAverageSpread() { 371 // none or just one enrollment -> all the same 372 if (iEnrollmentWeight <= 1.0) return 1.0; 373 374 double weight = 0.0; 375 for (Config config: getCourse().getOffering().getConfigs()) { 376 double pairs = 0.0; 377 for (Subpart subpart: config.getSubparts()) 378 for (Section section: subpart.getSections()) { 379 Double enrollment = iSectionWeight.get(section.getId()); 380 if (enrollment != null && enrollment > 1.0) 381 pairs += enrollment * (enrollment - 1); 382 } 383 weight += (pairs / config.getSubparts().size()) / (iEnrollmentWeight * (iEnrollmentWeight - 1.0)); 384 } 385 return weight; 386 } 387 388 /** 389 * Return section spread of this group. It reflects the probability of two students of this group 390 * being enrolled in this section. 391 * @param section given section 392 * @return 1.0 if all enrollments have the same sections as the given one, 0.0 if there is no match at all 393 */ 394 public double getSectionSpread(Section section) { 395 Double w = iSectionWeight.get(section.getId()); 396 if (w != null && w > 1.0) { 397 return (w * (w - 1.0)) / (iEnrollmentWeight * (iEnrollmentWeight - 1.0)); 398 } else { 399 return 0.0; 400 } 401 } 402 } 403 404 @Override 405 public RequestGroupContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 406 return new RequestGroupContext(assignment); 407 } 408 409 @Override 410 public RequestGroupContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, RequestGroupContext parentContext) { 411 return new RequestGroupContext(parentContext); 412 } 413 414 @Override 415 public Model<Request, Enrollment> getModel() { 416 return getCourse().getModel(); 417 } 418}