001    package net.sf.cpsolver.coursett.constraint;
002    
003    import java.util.ArrayList;
004    import java.util.BitSet;
005    import java.util.Comparator;
006    import java.util.HashMap;
007    import java.util.HashSet;
008    import java.util.List;
009    import java.util.Set;
010    
011    import net.sf.cpsolver.coursett.Constants;
012    import net.sf.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
013    import net.sf.cpsolver.coursett.model.Lecture;
014    import net.sf.cpsolver.coursett.model.Placement;
015    import net.sf.cpsolver.coursett.model.TimeLocation;
016    import net.sf.cpsolver.coursett.model.TimetableModel;
017    import 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     */
042    public 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                    TimeLocation t = assignments.get(lecture).getTimeLocation();
186                    if (shareWeeksAndDay(t, week, dayCode))
187                        placements.add(assignments.get(lecture));
188                    continue;
189                }
190                if (lecture.getAssignment() == null || lecture.getAssignment().getTimeLocation() == null)
191                    continue;
192                if (conflicts != null && conflicts.contains(lecture.getAssignment()))
193                    continue;
194    
195                TimeLocation t = lecture.getAssignment().getTimeLocation();
196                if (t == null || !shareWeeksAndDay(t, week, dayCode))
197                    continue;
198    
199                placements.add(lecture.getAssignment());
200            }
201    
202            if (value == null || (conflicts != null && conflicts.contains(value))) {
203                return placements;
204            } 
205            
206            if (shareWeeksAndDay(value.getTimeLocation(), week, dayCode)) placements.add(value); 
207    
208            return placements;
209        }
210        
211        /**
212         * Used to determine the daycode and week of a timelocation
213         * 
214         * @param t timelocation 
215         * @param week date pattern compared to timelocation
216         * @param dayCode days compared to timelocation
217         * @return true if TimeLocation matches the date pattern and days
218         */
219        private boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){
220            boolean matchDay = (t.getDayCode() & dayCode) != 0;
221            boolean matchWeek = (week == null || t.shareWeeks(week));                
222            
223            return matchDay && matchWeek;
224        }
225        
226        /**
227         * Creates a list of blocks from a placements sorted by startSlot
228         * 
229         * @param sorted list of placements sorted by startSlot
230         * @param maxBreakBetweenBTB maximum number of free slots between BTB placements
231         * @return groups of BTB placements as a list of blocks
232         */
233        protected List<Block> mergeToBlocks(List<Placement> sorted, int maxBreakBetweenBTB){
234            List<Block> blocks = new ArrayList<Block>();
235            // add placements to blocks
236            for (int i = 0; i < sorted.size(); i++) {
237                Placement placement = sorted.get(i);
238                boolean added = false;
239                // add placement to a suitable block
240                for (int j = 0; j < blocks.size(); j++) {
241                    if (blocks.get(j).addPlacement(placement)) {
242                        added = true;
243                    }
244                }
245                // create a new block if a lecture does not fit into any block
246                if (!added) {
247                    Block block = new Block(maxBreakBetweenBTB);
248                    block.addPlacement(placement);
249                    blocks.add(block);
250                }
251            }   
252            return blocks;
253        }
254        
255        @Override
256        public boolean isHard() {
257            return iIsRequired;
258        }    
259        
260        @Override
261        public String getName() {
262            return iOwner + ": " + iConstraintType.getName();
263        }
264        
265        public FlexibleConstraintType getType(){
266            return iConstraintType;
267        }
268        
269        @Override
270        public void assigned(long iteration, Placement value) {        
271            super.assigned(iteration, value);
272            updateCriterion();        
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         */
287        public String getPrologPreference() {
288            return Constants.preferenceLevel2preference(iPreference);
289        }
290    
291        /**
292         * Update value of FlexibleConstraintCriterion and number of violated FlexibleConstraints
293         */
294        private void updateCriterion() {
295            FlexibleConstraintCriterion pc = (FlexibleConstraintCriterion)getModel().getCriterion(FlexibleConstraintCriterion.class);
296            if (pc != null) {            
297                if (!isHard()){                
298                    pc.inc(-iLastPreference);                
299                    iLastPreference = getCurrentPreference(null, null);
300                    pc.inc(iLastPreference);  
301                }   
302            }         
303        }
304        
305        /**
306         * Return the current preference of the flexible constraint, considering conflicts and new assignments.
307         * Used to compute value for flexible constraint criterion.
308         * 
309         * @param conflicts
310         * @param assignments
311         * @return the current preference of the flexible constraint
312         */
313        public double getCurrentPreference(Set<Placement> conflicts, HashMap<Lecture, Placement> assignments){
314            double pref = getNrViolations(conflicts, assignments);
315            if(pref == 0){
316                return - Math.abs(iPreference);
317            }
318            return Math.abs(iPreference) * pref;
319        }
320    
321        @Override
322        public void unassigned(long iteration, Placement value) {
323            super.unassigned(iteration, value);
324            updateCriterion();
325        }   
326        
327        /**
328         * A block is a list of placements sorted by startSlot, which are BTB.
329         * maxSlotsBetweenBackToBack determines the number of free slots between two BTB placements
330         *
331         */
332        public class Block {
333            
334            // start slot of the block
335            private int startSlotCurrentBlock = -1;        
336            // end slot of the block
337            private int endSlotCurrentBlock = -1;        
338            // max number of slots between classes to be considered Back-To-Back; 4 slots default      
339            private int maxSlotsBetweenBackToBack = 4;
340            // the list of placements of this block
341            private List<Placement> placements = new ArrayList<Placement>();
342            
343            public Block(int maxSlotsBetweenBTB){
344                this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB;            
345            }              
346            
347            /**
348             * Adds placement to the block and updates block's attributes.
349             * 
350             * @param placement placement to be added to the block
351             * @return true if the placement was successfully added to the block
352             */
353            public boolean addPlacement(Placement placement){   
354                if (placement == null){
355                    return false;
356                }
357                
358                TimeLocation t = placement.getTimeLocation();
359                
360                if (t == null){
361                    return false;
362                }
363                
364                // if placements is empty, the block only contains currently added placement -> set start and end
365                if (placements.isEmpty()){
366                    placements.add(placement);
367                    startSlotCurrentBlock = t.getStartSlot();
368                    endSlotCurrentBlock = t.getStartSlot() + t.getLength();
369                    return true;
370                }
371                
372                // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock
373                if (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                // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement
383                if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){
384                    placements.add(placement);
385                    int tEnd = t.getStartSlot() + t.getLength();
386                    if (tEnd > endSlotCurrentBlock){
387                        endSlotCurrentBlock = tEnd;
388                    }
389                    return true;
390                }
391                
392                return false;
393            }
394    
395            public boolean haveSameStartTime() {
396                if (!placements.isEmpty()) {
397                    int startSlot = placements.get(0).getTimeLocation().getStartSlot();
398                    for (Placement p : getPlacements()) {
399                        if (p.getTimeLocation().getStartSlot() != startSlot)
400                            return false;
401                    }
402                }
403                return true;
404            }
405            
406            public int getStartSlotCurrentBlock(){
407                return startSlotCurrentBlock;
408            }
409            
410            public int getEndSlotCurrentBlock(){
411                return endSlotCurrentBlock;
412            }
413            
414            public int getNbrPlacements(){
415                return placements.size();
416            }        
417           
418            public List<Placement> getPlacements(){
419                return placements;
420            }
421            
422            public int getLengthInSlots(){
423                return endSlotCurrentBlock - startSlotCurrentBlock;
424            }
425            
426            @Override
427            public String toString(){
428                return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements();
429            }          
430        }
431        
432        /**
433         * Placement comparator: earlier placement first, shorter placement first if both start at the same time.
434         */
435        protected static class PlacementTimeComparator implements Comparator<Placement> {
436            @Override
437            public int compare(Placement p1, Placement p2) {
438                TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
439                // compare by start time (earlier first)
440                if (t1.getStartSlot() < t2.getStartSlot())
441                    return -1;
442                if (t1.getStartSlot() > t2.getStartSlot())
443                    return 1;
444                // same start -> compare by length (shorter first)
445                if (t1.getLength() < t2.getLength())
446                    return -1;
447                if (t1.getLength() > t2.getLength())
448                    return 1;
449                // fallback
450                return 0;
451            }
452        }
453        
454        @Override
455        public String toString() {
456            return getName();
457        }
458    }