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