    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.Collection;
    004import java.util.Comparator;
    005import java.util.List;
    006import java.util.Set;
    007import java.util.TreeSet;
    008
    009import org.cpsolver.coursett.model.Lecture;
    010import org.cpsolver.coursett.model.Placement;
    011import org.cpsolver.ifs.assignment.Assignment;
    012import org.cpsolver.ifs.model.Constraint;
    013
    014
    015/**
    016 * Class limit constraint.
    017 *
    018 * @author  Tomáš Müller
    019 * @version CourseTT 1.3 (University Course Timetabling)<br>
    020 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    021 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    022 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    023 * <br>
    024 *          This library is free software; you can redistribute it and/or modify
    025 *          it under the terms of the GNU Lesser General Public License as
    026 *          published by the Free Software Foundation; either version 3 of the
    027 *          License, or (at your option) any later version. <br>
    028 * <br>
    029 *          This library is distributed in the hope that it will be useful, but
    030 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    031 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    032 *          Lesser General Public License for more details. <br>
    033 * <br>
    034 *          You should have received a copy of the GNU Lesser General Public
    035 *          License along with this library; if not see
    036 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    037 */
    038
    039public class ClassLimitConstraint extends Constraint<Lecture, Placement> {
    040    private int iClassLimit = 0;
    041    private Lecture iParent = null;
    042    private String iName = null;
    043    boolean iEnabled = true;
    044
    045    private int iClassLimitDelta = 0;
    046
    047    public ClassLimitConstraint(int classLimit, String name) {
    048        iClassLimit = classLimit;
    049        iName = name;
    050    }
    051
    052    public ClassLimitConstraint(Lecture parent, String name) {
    053        iParent = parent;
    054        iName = name;
    055    }
    056
    057    public int getClassLimitDelta() {
    058        return iClassLimitDelta;
    059    }
    060
    061    public void setClassLimitDelta(int classLimitDelta) {
    062        iClassLimitDelta = classLimitDelta;
    063    }
    064
    065    public int classLimit() {
    066        return (iParent == null ? iClassLimit + iClassLimitDelta : iParent.minClassLimit() + iClassLimitDelta);
    067    }
    068
    069    public Lecture getParentLecture() {
    070        return iParent;
    071    }
    072
    073    public int currentClassLimit(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    074        int limit = 0;
    075        for (Lecture lecture : variables()) {
    076            limit += lecture.classLimit(assignment, value, conflicts);
    077        }
    078        return limit;
    079    }
    080
    081    @Override
    082    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    083        if (!iEnabled)
    084            return;
    085        int currentLimit = currentClassLimit(assignment, value, conflicts);
    086        int classLimit = classLimit();
    087        if (currentLimit < classLimit) {
    088            // System.out.println(getName()+"> "+currentLimit+"<"+classLimit+" ("+value+")");
    089            TreeSet<Placement> adepts = new TreeSet<Placement>(new ClassLimitComparator());
    090            computeAdepts(assignment, adepts, variables(), value, conflicts);
    091            addParentAdepts(assignment, adepts, iParent, value, conflicts);
    092            // System.out.println(" -- found "+adepts.size()+" adepts");
    093            for (Placement adept : adepts) {
    094                // System.out.println("   -- selected "+adept);
    095                conflicts.add(adept);
    096                currentLimit = currentClassLimit(assignment, value, conflicts);
    097                // System.out.println("   -- new current limit "+currentLimit);
    098                if (currentLimit >= classLimit)
    099                    break;
    100            }
    101            // System.out.println(" -- done (currentLimit="+currentLimit+", classLimit="+classLimit+")");
    102        }
    103
    104        if (currentLimit < classLimit)
    105            conflicts.add(value);
    106
    107        if (iParent != null && iParent.getClassLimitConstraint() != null)
    108            iParent.getClassLimitConstraint().computeConflicts(assignment, value, conflicts);
    109    }
    110
    111    public void computeAdepts(Assignment<Lecture, Placement> assignment, Collection<Placement> adepts, List<Lecture> variables, Placement value,
    112            Set<Placement> conflicts) {
    113        for (Lecture lecture : variables) {
    114            if (lecture.isCommitted()) continue;
    115            Placement placement = assignment.getValue(lecture);
    116            if (placement != null && !placement.equals(value) && !conflicts.contains(placement)) {
    117                adepts.add(placement);
    118            }
    119            if (lecture.hasAnyChildren()) {
    120                for (Long subpartId: lecture.getChildrenSubpartIds()) {
    121                    computeAdepts(assignment, adepts, lecture.getChildren(subpartId), value, conflicts);
    122                }
    123            }
    124
    125        }
    126    }
    127
    128    public void addParentAdepts(Assignment<Lecture, Placement> assignment, Collection<Placement> adepts, Lecture parent, Placement value, Set<Placement> conflicts) {
    129        if (parent == null || parent.isCommitted() || parent.minClassLimit() == parent.maxClassLimit())
    130            return;
    131        Placement placement = assignment.getValue(parent);
    132        if (placement != null && !placement.equals(value) && !conflicts.contains(placement)) {
    133            adepts.add(placement);
    134        }
    135        addParentAdepts(assignment, adepts, parent.getParent(), value, conflicts);
    136    }
    137
    138    @Override
    139    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    140        if (!iEnabled)
    141            return false;
    142        int currentLimit = currentClassLimit(assignment, value, null);
    143        int classLimit = classLimit();
    144        if (currentLimit < classLimit)
    145            return true;
    146
    147        if (iParent != null && iParent.getClassLimitConstraint() != null)
    148            return iParent.getClassLimitConstraint().inConflict(assignment, value);
    149
    150        return false;
    151    }
    152
    153    @Override
    154    public String getName() {
    155        return iName;
    156    }
    157
    158    private static class ClassLimitComparator implements Comparator<Placement> {
    159        @Override
    160        public int compare(Placement p1, Placement p2) {
    161            Lecture l1 = p1.variable();
    162            Lecture l2 = p2.variable();
    163            int cl1 = Math.min(l1.maxClassLimit(), (int) Math.floor(p1.getRoomSize() / l1.roomToLimitRatio()));
    164            int cl2 = Math.min(l2.maxClassLimit(), (int) Math.floor(p2.getRoomSize() / l2.roomToLimitRatio()));
    165            int cmp = -Double.compare(l1.maxAchievableClassLimit() - cl1, l2.maxAchievableClassLimit() - cl2);
    166            if (cmp != 0)
    167                return cmp;
    168            return l1.getClassId().compareTo(l2.getClassId());
    169        }
    170    }
    171
    172    public void setEnabled(boolean enabled) {
    173        iEnabled = enabled;
    174    }
    175
    176    public boolean isEnabled() {
    177        return iEnabled;
    178    }
    179
    180    @Override
    181    public String toString() {
    182        return "Class-limit " + getName();
    183    }
    184
    185}