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