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         * 
084         */
085        MAX_DAYS("_(MaxDays):([0-9]+)_", MaxDaysFlexibleConstraint.class, "MaxDays"),
086        ;
087        
088        private String iPattern;
089        private Class<? extends FlexibleConstraint> iImplementation;
090        private String iName;
091        FlexibleConstraintType(String pattern, Class<? extends FlexibleConstraint> implementation, String name) {
092            iPattern = pattern; iImplementation = implementation; iName = name;
093        }
094        
095        public String getPattern() { return iPattern; }
096        
097        public String getName() { return iName; }
098
099        public FlexibleConstraint create(Long id, String owner, String preference, String reference) throws IllegalArgumentException {
100            try {
101                return iImplementation.getConstructor(Long.class, String.class, String.class, String.class).newInstance(id, owner, preference, reference);
102            } catch (IllegalArgumentException e) {
103                throw e;
104            } catch (Exception e) {
105                throw new IllegalArgumentException(e.getMessage(), e);
106            }
107        }
108    }
109    
110    /**
111     * Constructor
112     * @param id unique id
113     * @param owner identifier of distribution preference the constraint was created for
114     * @param preference time preference ("R" for required, "P" for prohibited, "-2",
115     *            "-1", "1", "2" for soft preference)   
116     * @param reference parameters of the constraint in String form            
117     */
118    public FlexibleConstraint(Long id, String owner, String preference, String reference){
119        super();                
120        iId = id;
121        iReference = reference;
122        iPreference = Constants.preference2preferenceLevel(preference);
123        iIsRequired = preference.equals(Constants.sPreferenceRequired);        
124        iOwner = owner;                
125    }
126    
127
128    /** 
129     * Return current number of violations.
130     * @param assignment current assignment
131     * @param conflicts conflicting placements to be unassigned
132     * @param assignments assigned placements 
133     * @return the number of violations of the constraint during days and all weeks of the semester
134     */
135    public abstract double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments);
136
137    
138    /**
139     * Return weeks of the term.
140     * @return a list of bitsets (one for each week of the term) representing datePatterns or null if semester is whole semester is considered
141     */
142    public List<BitSet> getWeeks(){
143        if (iWeeks == null){
144            TimetableModel model = (TimetableModel) getModel();
145            iWeeks = new ArrayList<BitSet>();
146
147            boolean checkWeeks = model.getProperties().getPropertyBoolean("FlexibleConstraint.CheckWeeks", false);
148            
149            if (checkWeeks) {
150                // get weeks method returns bitsets representing weeks during semester
151                iWeeks = model.getWeeks();
152            } else {
153                // weeks are not considered, all placements are taken into consideration
154                iWeeks.add(null);
155            } 
156        }  
157          
158        return iWeeks;
159    }
160    
161    @Override
162    public boolean isConsistent(Placement value1, Placement value2) {
163        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
164        if (value1 != null)
165            assignments.put(value1.variable(), value1);
166        if (value2 != null)
167            assignments.put(value2.variable(), value2);
168        
169        if (getNrViolations(null, null, assignments) != 0) return false;
170
171        return super.isConsistent(value1, value2);
172    }
173    
174    /**
175     * Returns placements of variables assigned to this constraint with assignment which satisfy following conditions:
176     * They must be taught in the day included in dayCode.
177     * They cannot be included in conflicts
178     * Their date pattern intersects with week
179     * 
180     * @param assignment current assignment
181     * @param dayCode representation of days in week combination
182     * @param conflicts placements to be unassigned
183     * @param value placement to be assigned
184     * @param assignments placements of variables
185     * @param week bitset representing a date pattern
186     * @return placements of variables assigned to this constraint with assignment which satisfy conditions above
187     */
188    protected Set<Placement> getRelevantPlacements(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value,
189            HashMap<Lecture, Placement> assignments, BitSet week) {
190        Set<Placement> placements = new HashSet<Placement>();
191        
192        for (Lecture lecture : variables()) {
193            // lecture of the value is already assigned
194            if(value != null && lecture.equals(value.variable()))continue;
195
196            // lecture might not have assignment if it is present in assignments
197            if (assignments != null && assignments.containsKey(lecture)) {
198                Placement placement = assignments.get(lecture);
199                if (placement != null && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode))
200                    placements.add(placement);
201            } else if (assignment != null) {
202                Placement placement = assignment.getValue(lecture);
203                if (placement != null && (conflicts == null || !conflicts.contains(placement)) && shareWeeksAndDay(placement.getTimeLocation(), week, dayCode))
204                    placements.add(placement);
205            }
206        }
207
208        if (value == null || (conflicts != null && conflicts.contains(value))) {
209            return placements;
210        } 
211        
212        if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value); 
213
214        return placements;
215    }
216    
217    /**
218     * Used to determine the daycode and week of a timelocation
219     * 
220     * @param t timelocation 
221     * @param week date pattern compared to timelocation
222     * @param dayCode days compared to timelocation
223     * @return true if TimeLocation matches the date pattern and days
224     */
225    private boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){
226        boolean matchDay = (t.getDayCode() & dayCode) != 0;
227        boolean matchWeek = (week == null || t.shareWeeks(week));                
228        
229        return matchDay && matchWeek;
230    }
231    
232    /**
233     * Creates a list of blocks from a placements sorted by startSlot
234     * 
235     * @param sorted list of placements sorted by startSlot
236     * @param maxBreakBetweenBTB maximum number of free slots between BTB placements
237     * @return groups of BTB placements as a list of blocks
238     */
239    protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){
240        List<Block> blocks = new ArrayList<Block>();
241        // add placements to blocks
242        for (int i = 0; i < sorted.size(); i++) {
243            Placement placement = sorted.get(i);
244            boolean added = false;
245            // add placement to a suitable block
246            for (int j = 0; j < blocks.size(); j++) {
247                if (blocks.get(j).addPlacement(placement)) {
248                    added = true;
249                }
250            }
251            // create a new block if a lecture does not fit into any block
252            if (!added) {
253                Block block = new Block(maxBreakBetweenBTB);
254                block.addPlacement(placement);
255                blocks.add(block);
256            }
257        }   
258        return blocks;
259    }
260    
261    @Override
262    public boolean isHard() {
263        return iIsRequired;
264    }    
265    
266    @Override
267    public String getName() {
268        return iOwner + ": " + iConstraintType.getName();
269    }
270    
271    public FlexibleConstraintType getType(){
272        return iConstraintType;
273    }
274    
275    public String getReference() {        
276        return iReference;
277    }
278    
279    public String getOwner() {        
280        return iOwner;
281    }   
282    
283    /**
284     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
285     * preference
286     * @return prolog preference
287     */
288    public String getPrologPreference() {
289        return Constants.preferenceLevel2preference(iPreference);
290    }
291
292    /**
293     * Return the current preference of the flexible constraint, considering conflicts and new assignments.
294     * Used to compute value for flexible constraint criterion.
295     * @param assignment current assignment
296     * @param conflicts conflicting assignment
297     * @param assignments proposed assignments
298     * @return the current preference of the flexible constraint
299     */
300    public double getCurrentPreference(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
301        if (isHard()) return 0;
302        double pref = getNrViolations(assignment, conflicts, assignments);
303        if(pref == 0){
304            return - Math.abs(iPreference);
305        }
306        return Math.abs(iPreference) * pref;
307    }
308
309    /**
310     * A block is a list of placements sorted by startSlot, which are BTB.
311     * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements
312     *
313     */
314    public class Block {
315        
316        // start slot of the block
317        private int startSlotCurrentBlock = -1;        
318        // end slot of the block
319        private int endSlotCurrentBlock = -1;        
320        // max number of slots between classes to be considered Back-To-Back; 4 slots default      
321        private int maxSlotsBetweenBackToBack = 4;
322        // the list of placements of this block
323        private List<Placement> placements = new ArrayList<Placement>();
324        
325        public Block(int maxSlotsBetweenBTB){
326            this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB;            
327        }              
328        
329        /**
330         * Adds placement to the block and updates block's attributes.
331         * 
332         * @param placement placement to be added to the block
333         * @return true if the placement was successfully added to the block
334         */
335        public boolean addPlacement(Placement placement){   
336            if (placement == null){
337                return false;
338            }
339            
340            TimeLocation t = placement.getTimeLocation();
341            
342            if (t == null){
343                return false;
344            }
345            
346            // if placements is empty, the block only contains currently added placement -> set start and end
347            if (placements.isEmpty()){
348                placements.add(placement);
349                startSlotCurrentBlock = t.getStartSlot();
350                endSlotCurrentBlock = t.getStartSlot() + t.getLength();
351                return true;
352            }
353            
354            // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock
355            if (t.getStartSlot() == startSlotCurrentBlock){
356                placements.add(placement);
357                int tEnd = t.getStartSlot() + t.getLength();
358                if (tEnd > endSlotCurrentBlock){
359                    endSlotCurrentBlock = tEnd;
360                }
361                return true;
362            }      
363            
364            // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement
365            if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){
366                placements.add(placement);
367                int tEnd = t.getStartSlot() + t.getLength();
368                if (tEnd > endSlotCurrentBlock){
369                    endSlotCurrentBlock = tEnd;
370                }
371                return true;
372            }
373            
374            return false;
375        }
376
377        public boolean haveSameStartTime() {
378            if (!placements.isEmpty()) {
379                int startSlot = placements.get(0).getTimeLocation().getStartSlot();
380                for (Placement p : getPlacements()) {
381                    if (p.getTimeLocation().getStartSlot() != startSlot)
382                        return false;
383                }
384            }
385            return true;
386        }
387        
388        public int getStartSlotCurrentBlock(){
389            return startSlotCurrentBlock;
390        }
391        
392        public int getEndSlotCurrentBlock(){
393            return endSlotCurrentBlock;
394        }
395        
396        public int getNbrPlacements(){
397            return placements.size();
398        }        
399       
400        public List<Placement> getPlacements(){
401            return placements;
402        }
403        
404        public int getLengthInSlots(){
405            return endSlotCurrentBlock - startSlotCurrentBlock;
406        }
407        
408        @Override
409        public String toString(){
410            return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements();
411        }          
412    }
413    
414    /**
415     * Placement comparator: earlier placement first, shorter placement first if both start at the same time.
416     */
417    protected static class PlacementTimeComparator implements Comparator<Placement> {
418        @Override
419        public int compare(Placement p1, Placement p2) {
420            TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
421            // compare by start time (earlier first)
422            if (t1.getStartSlot() < t2.getStartSlot())
423                return -1;
424            if (t1.getStartSlot() > t2.getStartSlot())
425                return 1;
426            // same start -> compare by length (shorter first)
427            if (t1.getLength() < t2.getLength())
428                return -1;
429            if (t1.getLength() > t2.getLength())
430                return 1;
431            // fallback
432            return 0;
433        }
434    }
435    
436    @Override
437    public String toString() {
438        return getName();
439    }
440    
441    @Override
442    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
443        return new FlexibleConstraintContext(assignment);
444    }
445    
446    public class FlexibleConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
447        protected double iLastPreference = 0;
448        
449        FlexibleConstraintContext() {}
450        
451        FlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
452            updateCriterion(assignment);
453        }
454
455        @Override
456        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
457            updateCriterion(assignment);
458        }
459
460        @Override
461        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
462            updateCriterion(assignment);
463        }
464
465        /**
466         * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints
467         */
468        protected void updateCriterion(Assignment<Lecture, Placement> assignment) {
469            if (!isHard()) {
470                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
471                if (criterion != null) {
472                    criterion.inc(assignment, -iLastPreference);                
473                    iLastPreference = getCurrentPreference(assignment, null, null);
474                    criterion.inc(assignment, iLastPreference);  
475                }
476            }
477        }
478        
479        public double getPreference() {
480            return iLastPreference;
481        }
482    }
483}