    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Comparator;
    006import java.util.HashMap;
    007import java.util.HashSet;
    008import java.util.List;
    009import java.util.Set;
    010
    011import org.cpsolver.coursett.Constants;
    012import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
    013import org.cpsolver.coursett.model.Lecture;
    014import org.cpsolver.coursett.model.Placement;
    015import org.cpsolver.coursett.model.TimeLocation;
    016import org.cpsolver.coursett.model.TimetableModel;
    017import org.cpsolver.ifs.assignment.Assignment;
    018import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    019import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
    020import org.cpsolver.ifs.criteria.Criterion;
    021
    022
    023/**
    024 * Flexible constraint. <br>
    025 * This constraint expresses relations between several classes. Provides similar
    026 * functions as Group constraint. Unlike group constraint, Flexible constraint
    027 * is able to parse some of its parameters from its reference field<br>
    028 *
    029 * @version CourseTT 1.3 (University Course Timetabling)<br>
    030 *          Copyright (C) 2013 Matej Lukac<br>
    031 * <br>
    032 *          This library is free software; you can redistribute it and/or modify
    033 *          it under the terms of the GNU Lesser General Public License as
    034 *          published by the Free Software Foundation; either version 3 of the
    035 *          License, or (at your option) any later version. <br>
    036 * <br>
    037 *          This library is distributed in the hope that it will be useful, but
    038 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    039 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    040 *          Lesser General Public License for more details. <br>
    041 * <br>
    042 *          You should have received a copy of the GNU Lesser General Public
    043 *          License along with this library; if not see
    044 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    045 */
    046public abstract class FlexibleConstraint extends ConstraintWithContext<Lecture, Placement, FlexibleConstraint.FlexibleConstraintContext> {
    047
    048    protected int iPreference;
    049    private boolean iIsRequired;
    050    private String iOwner;
    051
    052    // Constraint type
    053    protected FlexibleConstraintType iConstraintType = null;
    054
    055    // A pattern the constraint was created from
    056    protected String iReference = "";
    057
    058    // Determines whether the constraint is checked for every week in the semester
    059    protected List<BitSet> iWeeks = null;
    060
    061    /**
    062     * Flexible constraint types
    063     *
    064     */
    065    public static enum FlexibleConstraintType {
    066        /**
    067         * Given classes must be taught in a way there is a break between two blocks of classes.
    068         */
    069        MAXBLOCK_BACKTOBACK("_(MaxBlock):([0-9]+):([0-9]+)_", MaxBlockFlexibleConstraint.class, "Block"),
    070        /**
    071         * There must be a break of a given length in a given time interval.
    072         */
    073        BREAK("_(Break):([0-9]+):([0-9]+):([0-9]+)_", BreakFlexibleConstraint.class, "Break"),
    074        /**
    075         * Limit number of breaks between adjacent classes on a day.
    076         */
    077        MAX_BREAKS("_(MaxBreaks):([0-9]+):([0-9]+)_", MaxBreaksFlexibleConstraint.class, "MaxBreaks"),
    078        /**
    079         * Limit number of weeks on which an a class can take place.
    080         */
    081        MAX_WEEKS("_(MaxWeeks):([0-9]+):([0-9]+)_", MaxWeeksFlexibleConstraint.class, "MaxWeeks"),
    082        /**
    083         * Limit number of days of a week.
    084         */
    085        MAX_DAYS("_(MaxDays):([0-9]+)_", MaxDaysFlexibleConstraint.class, "MaxDays"),
    086        /**
    087         * Minimize free time of an instructor during a day (between the first and the last class).
    088         */
    089        MAX_HOLES("_(MaxHoles):([0-9]+)_", MaxHolesFlexibleConstraint.class, "MaxHoles"),
    090        /**
    091         * Limit number of half-days of a week.
    092         */
    093        MAX_HALF_DAYS("_(MaxHalfDays):([0-9]+)_", MaxHalfDaysFlexibleConstraint.class, "MaxHalfDays"),
    094        ;
    095
    096        private String iPattern;
    097        private Class<? extends FlexibleConstraint> iImplementation;
    098        private String iName;
    099        FlexibleConstraintType(String pattern, Class<? extends FlexibleConstraint> implementation, String name) {
    100            iPattern = pattern; iImplementation = implementation; iName = name;
    101        }
    102
    103        public String getPattern() { return iPattern; }
    104
    105        public String getName() { return iName.replaceAll("(?<=[^A-Z])([A-Z])"," $1"); }
    106
    107        public FlexibleConstraint create(Long id, String owner, String preference, String reference) throws IllegalArgumentException {
    108            try {
    109                return iImplementation.getConstructor(Long.class, String.class, String.class, String.class).newInstance(id, owner, preference, reference);
    110            } catch (IllegalArgumentException e) {
    111                throw e;
    112            } catch (Exception e) {
    113                throw new IllegalArgumentException(e.getMessage(), e);
    114            }
    115        }
    116    }
    117
    118    /**
    119     * Constructor
    120     * @param id unique id
    121     * @param owner identifier of distribution preference the constraint was created for
    122     * @param preference time preference ("R" for required, "P" for prohibited, "-2",
    123     *            "-1", "1", "2" for soft preference)
    124     * @param reference parameters of the constraint in String form
    125     */
    126    public FlexibleConstraint(Long id, String owner, String preference, String reference){
    127        super();
    128        iId = id;
    129        iReference = reference;
    130        iPreference = Constants.preference2preferenceLevel(preference);
    131        iIsRequired = preference.equals(Constants.sPreferenceRequired);
    132        iOwner = owner;
    133    }
    134
    135
    136    /**
    137     * Return current number of violations.
    138     * @param assignment current assignment
    139     * @param conflicts conflicting placements to be unassigned
    140     * @param assignments assigned placements
    141     * @return the number of violations of the constraint during days and all weeks of the semester
    142     */
    143    public abstract double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments);
    144
    145
    146    /**
    147     * Return weeks of the term.
    148     * @return a list of bitsets (one for each week of the term) representing datePatterns or null if semester is whole semester is considered
    149     */
    150    public List<BitSet> getWeeks(){
    151        if (iWeeks == null){
    152            TimetableModel model = (TimetableModel) getModel();
    153            iWeeks = new ArrayList<BitSet>();
    154
    155            boolean checkWeeks = model.getProperties().getPropertyBoolean("FlexibleConstraint.CheckWeeks", false);
    156
    157            if (checkWeeks) {
    158                // get weeks method returns bitsets representing weeks during semester
    159                iWeeks = model.getWeeks();
    160            } else {
    161                // weeks are not considered, all placements are taken into consideration
    162                iWeeks.add(null);
    163            }
    164        }
    165
    166        return iWeeks;
    167    }
    168
    169    @Override
    170    public boolean isConsistent(Placement value1, Placement value2) {
    171        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    172        if (value1 != null)
    173            assignments.put(value1.variable(), value1);
    174        if (value2 != null)
    175            assignments.put(value2.variable(), value2);
    176
    177        if (getNrViolations(null, null, assignments) != 0) return false;
    178
    179        return super.isConsistent(value1, value2);
    180    }
    181
    182    /**
    183     * Returns placements of variables assigned to this constraint with assignment which satisfy following conditions:
    184     * They must be taught in the day included in dayCode.
    185     * They cannot be included in conflicts
    186     * Their date pattern intersects with week
    187     *
    188     * @param assignment current assignment
    189     * @param dayCode representation of days in week combination
    190     * @param conflicts placements to be unassigned
    191     * @param value placement to be assigned
    192     * @param assignments placements of variables
    193     * @param week bitset representing a date pattern
    194     * @return placements of variables assigned to this constraint with assignment which satisfy conditions above
    195     */
    196    protected Set<Placement> getRelevantPlacements(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value,
    197            HashMap<Lecture, Placement> assignments, BitSet week) {
    198        Set<Placement> placements = new HashSet<Placement>();
    199
    200        for (Lecture lecture : variables()) {
    201            // lecture of the value is already assigned
    202            if(value != null && lecture.equals(value.variable()))continue;
    203
    204            // lecture might not have assignment if it is present in assignments
    205            if (assignments != null && assignments.containsKey(lecture)) {
    206                Placement placement = assignments.get(lecture);
    207                if (placement != null && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode))
    208                    placements.add(placement);
    209            } else if (assignment != null) {
    210                Placement placement = assignment.getValue(lecture);
    211                if (placement != null && (conflicts == null || !conflicts.contains(placement)) && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode))
    212                    placements.add(placement);
    213            }
    214        }
    215
    216        if (value == null || (conflicts != null && conflicts.contains(value))) {
    217            return placements;
    218        }
    219
    220        if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value);
    221
    222        return placements;
    223    }
    224
    225    /**
    226     * Used to determine the daycode and week of a timelocation
    227     *
    228     * @param t timelocation
    229     * @param week date pattern compared to timelocation
    230     * @param dayCode days compared to timelocation
    231     * @return true if TimeLocation matches the date pattern and days
    232     */
    233    private boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){
    234        boolean matchDay = (t.getDayCode() & dayCode) != 0;
    235        boolean matchWeek = (week == null || t.shareWeeks(week));
    236
    237        return matchDay && matchWeek;
    238    }
    239
    240    /**
    241     * Creates a list of blocks from a placements sorted by startSlot
    242     *
    243     * @param sorted list of placements sorted by startSlot
    244     * @param maxBreakBetweenBTB maximum number of free slots between BTB placements
    245     * @return groups of BTB placements as a list of blocks
    246     */
    247    protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){
    248        List<Block> blocks = new ArrayList<Block>();
    249        // add placements to blocks
    250        for (int i = 0; i < sorted.size(); i++) {
    251            Placement placement = sorted.get(i);
    252            boolean added = false;
    253            // add placement to a suitable block
    254            for (int j = 0; j < blocks.size(); j++) {
    255                if (blocks.get(j).addPlacement(placement)) {
    256                    added = true;
    257                }
    258            }
    259            // create a new block if a lecture does not fit into any block
    260            if (!added) {
    261                Block block = new Block(maxBreakBetweenBTB);
    262                block.addPlacement(placement);
    263                blocks.add(block);
    264            }
    265        }
    266        return blocks;
    267    }
    268
    269    @Override
    270    public boolean isHard() {
    271        return iIsRequired;
    272    }
    273
    274    @Override
    275    public String getName() {
    276        return iOwner + ": " + iConstraintType.getName();
    277    }
    278
    279    public FlexibleConstraintType getType(){
    280        return iConstraintType;
    281    }
    282
    283    public String getReference() {
    284        return iReference;
    285    }
    286
    287    public String getOwner() {
    288        return iOwner;
    289    }
    290
    291    /**
    292     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
    293     * preference
    294     * @return prolog preference
    295     */
    296    public String getPrologPreference() {
    297        return Constants.preferenceLevel2preference(iPreference);
    298    }
    299
    300    /**
    301     * Return the current preference of the flexible constraint, considering conflicts and new assignments.
    302     * Used to compute value for flexible constraint criterion.
    303     * @param assignment current assignment
    304     * @param conflicts conflicting assignment
    305     * @param assignments proposed assignments
    306     * @return the current preference of the flexible constraint
    307     */
    308    public double getCurrentPreference(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
    309        if (isHard()) return 0;
    310        double pref = getNrViolations(assignment, conflicts, assignments);
    311        if(pref == 0){
    312            return - Math.abs(iPreference);
    313        }
    314        return Math.abs(iPreference) * pref;
    315    }
    316
    317    /**
    318     * A block is a list of placements sorted by startSlot, which are BTB.
    319     * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements
    320     *
    321     */
    322    public class Block {
    323
    324        // start slot of the block
    325        private int startSlotCurrentBlock = -1;
    326        // end slot of the block
    327        private int endSlotCurrentBlock = -1;
    328        // max number of slots between classes to be considered Back-To-Back; 4 slots default
    329        private int maxSlotsBetweenBackToBack = 4;
    330        // the list of placements of this block
    331        private List<Placement> placements = new ArrayList<Placement>();
    332
    333        public Block(int maxSlotsBetweenBTB){
    334            this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB;
    335        }
    336
    337        /**
    338         * Adds placement to the block and updates block's attributes.
    339         *
    340         * @param placement placement to be added to the block
    341         * @return true if the placement was successfully added to the block
    342         */
    343        public boolean addPlacement(Placement placement){
    344            if (placement == null){
    345                return false;
    346            }
    347
    348            TimeLocation t = placement.getTimeLocation();
    349
    350            if (t == null){
    351                return false;
    352            }
    353
    354            // if placements is empty, the block only contains currently added placement -> set start and end
    355            if (placements.isEmpty()){
    356                placements.add(placement);
    357                startSlotCurrentBlock = t.getStartSlot();
    358                endSlotCurrentBlock = t.getStartSlot() + t.getLength();
    359                return true;
    360            }
    361
    362            // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock
    363            if (t.getStartSlot() == startSlotCurrentBlock){
    364                placements.add(placement);
    365                int tEnd = t.getStartSlot() + t.getLength();
    366                if (tEnd > endSlotCurrentBlock){
    367                    endSlotCurrentBlock = tEnd;
    368                }
    369                return true;
    370            }
    371
    372            // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement
    373            if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){
    374                placements.add(placement);
    375                int tEnd = t.getStartSlot() + t.getLength();
    376                if (tEnd > endSlotCurrentBlock){
    377                    endSlotCurrentBlock = tEnd;
    378                }
    379                return true;
    380            }
    381
    382            return false;
    383        }
    384
    385        public boolean haveSameStartTime() {
    386            if (!placements.isEmpty()) {
    387                int startSlot = placements.get(0).getTimeLocation().getStartSlot();
    388                for (Placement p : getPlacements()) {
    389                    if (p.getTimeLocation().getStartSlot() != startSlot)
    390                        return false;
    391                }
    392            }
    393            return true;
    394        }
    395
    396        public int getStartSlotCurrentBlock(){
    397            return startSlotCurrentBlock;
    398        }
    399
    400        public int getEndSlotCurrentBlock(){
    401            return endSlotCurrentBlock;
    402        }
    403
    404        public int getNbrPlacements(){
    405            return placements.size();
    406        }
    407
    408        public List<Placement> getPlacements(){
    409            return placements;
    410        }
    411
    412        public int getLengthInSlots(){
    413            return endSlotCurrentBlock - startSlotCurrentBlock;
    414        }
    415
    416        @Override
    417        public String toString(){
    418            return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements();
    419        }
    420    }
    421
    422    /**
    423     * Placement comparator: earlier placement first, shorter placement first if both start at the same time.
    424     */
    425    protected static class PlacementTimeComparator implements Comparator<Placement> {
    426        @Override
    427        public int compare(Placement p1, Placement p2) {
    428            TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
    429            // compare by start time (earlier first)
    430            if (t1.getStartSlot() < t2.getStartSlot())
    431                return -1;
    432            if (t1.getStartSlot() > t2.getStartSlot())
    433                return 1;
    434            // same start -> compare by length (shorter first)
    435            if (t1.getLength() < t2.getLength())
    436                return -1;
    437            if (t1.getLength() > t2.getLength())
    438                return 1;
    439            // fallback
    440            return 0;
    441        }
    442    }
    443
    444    @Override
    445    public String toString() {
    446        return getName();
    447    }
    448
    449    @Override
    450    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    451        return new FlexibleConstraintContext(assignment);
    452    }
    453
    454    public class FlexibleConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
    455        protected double iLastPreference = 0;
    456
    457        FlexibleConstraintContext() {}
    458
    459        FlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    460            updateCriterion(assignment);
    461        }
    462
    463        @Override
    464        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    465            updateCriterion(assignment);
    466        }
    467
    468        @Override
    469        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    470            updateCriterion(assignment);
    471        }
    472
    473        /**
    474         * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints
    475         */
    476        protected void updateCriterion(Assignment<Lecture, Placement> assignment) {
    477            if (!isHard()) {
    478                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
    479                if (criterion != null) {
    480                    criterion.inc(assignment, -iLastPreference);
    481                    iLastPreference = getCurrentPreference(assignment, null, null);
    482                    criterion.inc(assignment, iLastPreference);
    483                }
    484            }
    485        }
    486
    487        public double getPreference() {
    488            return iLastPreference;
    489        }
    490    }
    491}