    001package org.cpsolver.coursett.model;
    002
    003import java.util.BitSet;
    004import java.util.Enumeration;
    005
    006import org.cpsolver.coursett.Constants;
    007import org.cpsolver.ifs.util.ToolBox;
    008
    009
    010/**
    011 * Time part of placement.
    012 *
    013 * @author  Tomáš Müller
    014 * @version CourseTT 1.3 (University Course Timetabling)<br>
    015 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    016 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    017 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    018 * <br>
    019 *          This library is free software; you can redistribute it and/or modify
    020 *          it under the terms of the GNU Lesser General Public License as
    021 *          published by the Free Software Foundation; either version 3 of the
    022 *          License, or (at your option) any later version. <br>
    023 * <br>
    024 *          This library is distributed in the hope that it will be useful, but
    025 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    026 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    027 *          Lesser General Public License for more details. <br>
    028 * <br>
    029 *          You should have received a copy of the GNU Lesser General Public
    030 *          License along with this library; if not see
    031 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    032 */
    033
    034public class TimeLocation {
    035    private int iStartSlot;
    036
    037    private int iPreference;
    038    private double iNormalizedPreference;
    039
    040    private Long iTimePatternId = null;
    041    private int iHashCode;
    042
    043    private int iDayCode;
    044    private int iLength;
    045    private int iNrMeetings;
    046    private int iBreakTime;
    047
    048    private BitSet iWeekCode;
    049    private Long iDatePatternId = null;
    050    private String iDatePatternName = null;
    051    private int iDatePreference;
    052
    053    /**
    054     * Constructor
    055     *
    056     * @param dayCode
    057     *            days (combination of 1 for Monday, 2 for Tuesday, ...)
    058     * @param startTime
    059     *            start slot
    060     * @param length
    061     *            number of slots
    062     * @param pref
    063     *            time preference
    064     * @param normPref normalized preference
    065     * @param datePatternPreference date pattern preference
    066     * @param datePatternId date pattern unique id
    067     * @param datePatternName date pattern name
    068     * @param weekCode date pattern (binary string with 1 for each day when classes take place)
    069     * @param breakTime break time in minutes
    070     */
    071    public TimeLocation(int dayCode, int startTime, int length, int pref, double normPref, int datePatternPreference,
    072            Long datePatternId, String datePatternName, BitSet weekCode, int breakTime) {
    073        iPreference = pref;
    074        iNormalizedPreference = normPref;
    075        iStartSlot = startTime;
    076        iDayCode = dayCode;
    077        iLength = length;
    078        iBreakTime = breakTime;
    079        iNrMeetings = 0;
    080        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    081            if ((iDayCode & Constants.DAY_CODES[i]) == 0)
    082                continue;
    083            iNrMeetings++;
    084        }
    085        iHashCode = combine(combine(iDayCode, iStartSlot), iLength);
    086        iDatePatternName = datePatternName;
    087        iWeekCode = weekCode;
    088        iDatePatternId = datePatternId;
    089        if (iDatePatternName == null)
    090            iDatePatternName = "not set";
    091        iDatePreference = datePatternPreference;
    092        if (iWeekCode == null) {
    093            iWeekCode = new BitSet(366);
    094            for (int i = 0; i <= 365; i++)
    095                iWeekCode.set(i);
    096        }
    097    }
    098
    099    public TimeLocation(int dayCode, int startTime, int length, int pref, double normPref, Long datePatternId,
    100            String datePatternName, BitSet weekCode, int breakTime) {
    101        this(dayCode, startTime, length, pref, normPref, 0, datePatternId, datePatternName, weekCode, breakTime);
    102    }
    103
    104    /** Number of meetings
    105     * @return number of meetings
    106     **/
    107    public int getNrMeetings() {
    108        return iNrMeetings;
    109    }
    110
    111    public int getBreakTime() {
    112        return iBreakTime;
    113    }
    114
    115    public void setBreakTime(int breakTime) {
    116        iBreakTime = breakTime;
    117    }
    118
    119    private static int combine(int a, int b) {
    120        int ret = 0;
    121        for (int i = 0; i < 15; i++)
    122            ret = ret | ((a & (1 << i)) << i) | ((b & (1 << i)) << (i + 1));
    123        return ret;
    124    }
    125
    126    /** Days (combination of 1 for Monday, 2 for Tuesday, ...)
    127     * @return days of the week of this time
    128     **/
    129    public int getDayCode() {
    130        return iDayCode;
    131    }
    132
    133    /** Days for printing purposes
    134     * @return day header (e.g., MWF for Monday - Wednesday - Friday time)
    135     **/
    136    public String getDayHeader() {
    137        StringBuffer sb = new StringBuffer();
    138        for (int i = 0; i < Constants.DAY_CODES.length; i++)
    139            if ((iDayCode & Constants.DAY_CODES[i]) != 0)
    140                sb.append(Constants.DAY_NAMES_SHORT[i]);
    141        return sb.toString();
    142    }
    143
    144    /** Start time for printing purposes
    145     * @param useAmPm use 12-hour format
    146     * @return time header (e.g., 7:30a)
    147     **/
    148    public String getStartTimeHeader(boolean useAmPm) {
    149        int min = iStartSlot * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN;
    150        int h = min / 60;
    151        int m = min % 60;
    152        if (useAmPm)
    153            return (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a");
    154        else
    155            return h + ":" + (m < 10 ? "0" : "") + m;
    156    }
    157
    158    /** Start time for printing purposes
    159     * @return time header (e.g., 7:30a)
    160     **/
    161    @Deprecated
    162    public String getStartTimeHeader() {
    163        return getStartTimeHeader(true);
    164    }
    165
    166    /** End time for printing purposes
    167     * @param useAmPm use 12-hour format
    168     * @return end time (e.g., 8:20a)
    169     **/
    170    public String getEndTimeHeader(boolean useAmPm) {
    171        int min = (iStartSlot + iLength) * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN - getBreakTime();
    172        int m = min % 60;
    173        int h = min / 60;
    174        if (useAmPm)
    175            return (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a");
    176        else
    177            return h + ":" + (m < 10 ? "0" : "") + m;
    178    }
    179
    180    /** End time for printing purposes
    181     * @return end time (e.g., 8:20a)
    182     **/
    183    @Deprecated
    184    public String getEndTimeHeader() {
    185        return getEndTimeHeader(true);
    186    }
    187
    188
    189    /** End time for printing purposes
    190     * @param useAmPm use 12-hour format
    191     * @return end time not counting break time (e.g., 8:30a)
    192     **/
    193    public String getEndTimeHeaderNoAdj(boolean useAmPm) {
    194        int min = (iStartSlot + iLength) * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN;
    195        int m = min % 60;
    196        int h = min / 60;
    197        if (useAmPm)
    198            return (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a");
    199        else
    200            return h + ":" + (m < 10 ? "0" : "") + m;
    201    }
    202
    203    /** End time for printing purposes
    204     * @return end time not counting break time (e.g., 8:30a)
    205     **/
    206    @Deprecated
    207    public String getEndTimeHeaderNoAdj() {
    208        return getEndTimeHeaderNoAdj(true);
    209    }
    210
    211    /** Start slot
    212     * @return start slot
    213     **/
    214    public int getStartSlot() {
    215        return iStartSlot;
    216    }
    217
    218    /** Used slots in a day (combination of 1..first, 2..second,...) */
    219
    220    /** true if days overlap
    221     * @param anotherLocation another time
    222     * @return true if days of the week overlaps
    223     **/
    224    public boolean shareDays(TimeLocation anotherLocation) {
    225        return ((iDayCode & anotherLocation.iDayCode) != 0);
    226    }
    227
    228    /** number of overlapping days
    229     * @param anotherLocation another time
    230     * @return number of days of the week that the two times share
    231     **/
    232    public int nrSharedDays(TimeLocation anotherLocation) {
    233        int ret = 0;
    234        for (int i = 0; i < Constants.NR_DAYS; i++) {
    235            if ((iDayCode & Constants.DAY_CODES[i]) == 0)
    236                continue;
    237            if ((anotherLocation.iDayCode & Constants.DAY_CODES[i]) == 0)
    238                continue;
    239            ret++;
    240        }
    241        return ret;
    242    }
    243
    244    /** true if hours overlap
    245     * @param anotherLocation another time
    246     * @return true if the two times overlap in time (just the time of the day is considered)
    247     **/
    248    public boolean shareHours(TimeLocation anotherLocation) {
    249        return (iStartSlot + iLength > anotherLocation.iStartSlot)
    250                && (anotherLocation.iStartSlot + anotherLocation.iLength > iStartSlot);
    251    }
    252
    253    /** number of overlapping time slots (ignoring days)
    254     * @param anotherLocation another time
    255     * @return number of time slots the two location overlap
    256     **/
    257    public int nrSharedHours(TimeLocation anotherLocation) {
    258        int end = Math.min(iStartSlot + iLength, anotherLocation.iStartSlot + anotherLocation.iLength);
    259        int start = Math.max(iStartSlot, anotherLocation.iStartSlot);
    260        return (end < start ? 0 : end - start);
    261    }
    262
    263    /** true if weeks overlap
    264     * @param anotherLocation another time
    265     * @return true if the date patterns overlap
    266     */
    267    public boolean shareWeeks(TimeLocation anotherLocation) {
    268        return iWeekCode.intersects(anotherLocation.iWeekCode);
    269    }
    270
    271    /** true if weeks overlap
    272     * @param weekCode another date pattern
    273     * @return true if the date patterns overlap
    274     */
    275    public boolean shareWeeks(BitSet weekCode) {
    276        return iWeekCode.intersects(weekCode);
    277    }
    278
    279    public boolean hasDay(int day) {
    280        return iWeekCode.get(day);
    281    }
    282
    283    /** true if overlap
    284     * @param anotherLocation another time
    285     * @return true if the two times overlap, this means that all three checks {@link TimeLocation#shareDays(TimeLocation)}, {@link TimeLocation#shareHours(TimeLocation)} and {@link TimeLocation#shareWeeks(TimeLocation)} are true.
    286     **/
    287    public boolean hasIntersection(TimeLocation anotherLocation) {
    288        return shareDays(anotherLocation) && shareHours(anotherLocation) && shareWeeks(anotherLocation);
    289    }
    290
    291    /** Used slots
    292     * @return enumeration of used slots
    293     **/
    294    public IntEnumeration getSlots() {
    295        return new SlotsEnum();
    296    }
    297
    298    /** Used start slots (for each meeting)
    299     * @return enumeration of start slots for each meeting of the time
    300     **/
    301    public IntEnumeration getStartSlots() {
    302        return new StartSlotsEnum();
    303    }
    304
    305    /** Days
    306     * @return enumeration of days of week of the time
    307     **/
    308    public IntEnumeration getDays() {
    309        return new DaysEnum();
    310    }
    311
    312    private int[] iDaysCache = null;
    313    public int[] getDaysArray() {
    314        if (iDaysCache == null) {
    315            iDaysCache = new int[getNrMeetings()];
    316            int i = 0;
    317            for (Enumeration<Integer> e = getDays(); e.hasMoreElements();)
    318                iDaysCache[i++] = e.nextElement();
    319        }
    320        return iDaysCache;
    321    }
    322
    323    /** Text representation
    324     * @param useAmPm 12-hour format
    325     * @return time name (e.g., MWF 7:30a)
    326     **/
    327    public String getName(boolean useAmPm) {
    328        return getDayHeader() + " " + getStartTimeHeader(useAmPm);
    329    }
    330
    331    @Deprecated
    332    public String getName() {
    333        return getName(true);
    334    }
    335
    336    public String getLongName(boolean useAmPm) {
    337        return getDayHeader() + " " + getStartTimeHeader(useAmPm) + " - " + getEndTimeHeader(useAmPm) + " " + getDatePatternName();
    338    }
    339
    340    @Deprecated
    341    public String getLongName() {
    342        return getLongName(true);
    343    }
    344
    345    public String getLongNameNoAdj(boolean useAmPm) {
    346        return getDayHeader() + " " + getStartTimeHeader(useAmPm) + " - " + getEndTimeHeaderNoAdj(useAmPm) + " " + getDatePatternName();
    347    }
    348
    349    public String getLongNameNoAdj() {
    350        return getLongNameNoAdj(true);
    351    }
    352
    353    /** Preference
    354     * @return time preference
    355     **/
    356    public int getPreference() {
    357        return iPreference;
    358    }
    359
    360    public void setPreference(int preference) {
    361        iPreference = preference;
    362    }
    363
    364    /** Length
    365     * @return time length (in the number of slots)
    366     **/
    367    public int getLength() {
    368        return iLength;
    369    }
    370
    371    /** Length
    372     * @return time length (in the number of slots)
    373     **/
    374    public int getNrSlotsPerMeeting() {
    375        return iLength;
    376    }
    377
    378    /** Normalized preference
    379     * @return normalized preference
    380     **/
    381    public double getNormalizedPreference() {
    382        return iNormalizedPreference;
    383    }
    384
    385    public void setNormalizedPreference(double normalizedPreference) {
    386        iNormalizedPreference = normalizedPreference;
    387    }
    388
    389    /** Time pattern model (can be null)
    390     * @return time pattern unique id
    391     **/
    392    public Long getTimePatternId() {
    393        return iTimePatternId;
    394    }
    395
    396    public Long getDatePatternId() {
    397        return iDatePatternId;
    398    }
    399
    400    public void setTimePatternId(Long timePatternId) {
    401        iTimePatternId = timePatternId;
    402    }
    403
    404    public BitSet getWeekCode() {
    405        return iWeekCode;
    406    }
    407
    408    public String getDatePatternName() {
    409        return iDatePatternName;
    410    }
    411
    412    public void setDatePattern(Long datePatternId, String datePatternName, BitSet weekCode) {
    413        iDatePatternId = datePatternId;
    414        iDatePatternName = datePatternName;
    415        iWeekCode = weekCode;
    416    }
    417
    418    public int getDatePatternPreference() {
    419        return iDatePreference;
    420    }
    421
    422    @Override
    423    public String toString() {
    424        return getName() + " (" + iNormalizedPreference + ")";
    425    }
    426
    427    @Override
    428    public int hashCode() {
    429        return iHashCode;
    430    }
    431
    432    private class StartSlotsEnum implements IntEnumeration {
    433        int day = -1;
    434        boolean hasNext = false;
    435
    436        private StartSlotsEnum() {
    437            hasNext = nextDay();
    438        }
    439
    440        boolean nextDay() {
    441            do {
    442                day++;
    443                if (day >= Constants.DAY_CODES.length)
    444                    return false;
    445            } while ((Constants.DAY_CODES[day] & iDayCode) == 0);
    446            return true;
    447        }
    448
    449        @Override
    450        public boolean hasMoreElements() {
    451            return hasNext;
    452        }
    453
    454        @Override
    455        public Integer nextElement() {
    456            int slot = (day * Constants.SLOTS_PER_DAY) + iStartSlot;
    457            hasNext = nextDay();
    458            return slot;
    459        }
    460
    461        @Deprecated
    462        @Override
    463        public Integer nextInt() {
    464            return nextElement();
    465        }
    466    }
    467
    468    private class DaysEnum extends StartSlotsEnum {
    469        private DaysEnum() {
    470            super();
    471        }
    472
    473        @Override
    474        public Integer nextElement() {
    475            int ret = day;
    476            hasNext = nextDay();
    477            return ret;
    478        }
    479    }
    480
    481    private class SlotsEnum extends StartSlotsEnum {
    482        int pos = 0;
    483
    484        private SlotsEnum() {
    485            super();
    486        }
    487
    488        private boolean nextSlot() {
    489            if (pos + 1 < iLength) {
    490                pos++;
    491                return true;
    492            }
    493            if (nextDay()) {
    494                pos = 0;
    495                return true;
    496            }
    497            return false;
    498        }
    499
    500        @Override
    501        public Integer nextElement() {
    502            int slot = (day * Constants.SLOTS_PER_DAY) + iStartSlot + pos;
    503            hasNext = nextSlot();
    504            return slot;
    505        }
    506    }
    507
    508    @Override
    509    public boolean equals(Object o) {
    510        if (o == null || !(o instanceof TimeLocation))
    511            return false;
    512        TimeLocation t = (TimeLocation) o;
    513        if (getStartSlot() != t.getStartSlot())
    514            return false;
    515        if (getLength() != t.getLength())
    516            return false;
    517        if (getDayCode() != t.getDayCode())
    518            return false;
    519        return ToolBox.equals(getTimePatternId(), t.getTimePatternId())
    520                && ToolBox.equals(getDatePatternId(), t.getDatePatternId());
    521    }
    522
    523    public int getNrWeeks() {
    524        return getNrWeeks(0, iWeekCode.size() - 1);
    525    }
    526
    527    public int getNrWeeks(int startDay, int endDay) {
    528        /*
    529         * BitSet x = new BitSet(1+(endDay-startDay)/Constants.NR_DAYS); for
    530         * (int i=iWeekCode.nextSetBit(startDay); i<=endDay && i>=0;
    531         * i=iWeekCode.nextSetBit(i+1)) x.set((i-startDay)/Constants.NR_DAYS);
    532         * return x.cardinality();
    533         */
    534        int card = iWeekCode.get(startDay, endDay).cardinality();
    535        if (card == 0)
    536            return 0;
    537        if (card <= 7)
    538            return 1;
    539        return (5 + card) / 6;
    540    }
    541
    542    public interface IntEnumeration extends Enumeration<Integer> {
    543        @Deprecated
    544        public Integer nextInt();
    545    }
    546
    547    private Integer iFirstMeeting = null;
    548    public int getFirstMeeting(int dayOfWeekOffset) {
    549        if (iFirstMeeting == null) {
    550            int idx = -1;
    551            while ((idx = getWeekCode().nextSetBit(1 + idx)) >= 0) {
    552                int dow = (idx + dayOfWeekOffset) % 7;
    553                if ((getDayCode() & Constants.DAY_CODES[dow]) != 0) break;
    554            }
    555            iFirstMeeting = idx;
    556        }
    557        return iFirstMeeting;
    558    }
    559
    560    private Integer iLastMeeting = null;
    561    public int getLastMeeting(int dayOfWeekOffset) {
    562        if (iLastMeeting == null) {
    563            int idx = -1;
    564            while ((idx = getWeekCode().nextSetBit(1 + idx)) >= 0) {
    565                int dow = (idx + dayOfWeekOffset) % 7;
    566                if ((getDayCode() & Constants.DAY_CODES[dow]) != 0)
    567                    iLastMeeting = idx;
    568            }
    569        }
    570        return iLastMeeting;
    571    }
    572
    573    /** List dates when this time location meets.
    574     * @return enumeration of dates of this time (indexes to the {@link TimeLocation#getWeekCode()} for matching days of the week)
    575     **/
    576    public IntEnumeration getDates(int dayOfWeekOffset) {
    577        return new DateEnum(dayOfWeekOffset);
    578    }
    579
    580    /**
    581     * Check if the given time location has a particular date
    582     * @param date a date, expressed as an index to the {@link TimeLocation#getWeekCode()}
    583     * @param dayOfWeekOffset day of the week offset for the weeks pattern
    584     * @return true if this time location is meeting on the given date
    585     */
    586    public boolean hasDate(int date, int dayOfWeekOffset) {
    587        if (date < 0) return false;
    588        if (getWeekCode().get(date)) {
    589            int dow = (date + dayOfWeekOffset) % 7;
    590            if ((getDayCode() & Constants.DAY_CODES[dow]) != 0) return true;
    591        }
    592        return false;
    593    }
    594
    595    /**
    596     * Check if the time location has the given date, identified by a day of the week and a week pattern
    597     * @param dayOfWeek day of the week
    598     * @param week week pattern, or null when only days of the week are to be checked
    599     * @param dayOfWeekOffset day of the week offset for the weeks pattern
    600     * @return true if this time location is meeting on the given date
    601     */
    602    public boolean hasDate(int dayOfWeek, BitSet week, int dayOfWeekOffset) {
    603        // check the day of the week
    604        if ((getDayCode() & Constants.DAY_CODES[dayOfWeek]) == 0) return false;
    605        if (week == null) {
    606            // no week -> just day code check is sufficient
    607            return true;
    608        } else {
    609            // has week -> check the week code
    610            // first date in the week
    611            int firstDate = week.nextSetBit(0);
    612            int dow = (firstDate + dayOfWeekOffset) % 7; // 5
    613            // adjustments the given day of the week
    614            int adj = (7 - dow + dayOfWeek) % 7;
    615            return week.get(firstDate + adj) && getWeekCode().get(firstDate + adj);
    616        }
    617    }
    618
    619    /**
    620     * Check if the time location has at least one date from a set identified by a day code and a bit set.
    621     * Precise computation of individual dates are used instead of just checking whether the day codes and week codes are overlapping.
    622     * @param dayCode day codes
    623     * @param weekCode week code
    624     * @param dayOfWeekOffset day of the week offset for the weeks pattern
    625     * @return true if there is at least one overlapping date
    626     */
    627    public boolean overlaps(int dayCode, BitSet weekCode, int dayOfWeekOffset) {
    628        // check day code
    629        if ((getDayCode() & dayCode) == 0) return false;
    630        if (weekCode == null) {
    631            // no week -> just day code check is sufficient
    632            return true;
    633        } else {
    634            // has week -> check the week code
    635            int idx = -1;
    636            while ((idx = weekCode.nextSetBit(1 + idx)) >= 0) {
    637                // iterate over all dates of the date pattern
    638                int dow = (idx + dayOfWeekOffset) % 7;
    639                if ((dayCode & Constants.DAY_CODES[dow]) == 0) continue;
    640                // check if this date is in the current time location
    641                if ((getDayCode() & Constants.DAY_CODES[dow]) != 0 && getWeekCode().get(idx))
    642                    return true;
    643            }
    644            return false;
    645        }
    646    }
    647
    648    /**
    649     * Count how many times this time location is meeting
    650     * @param dayOfWeekOffset day of the week offset for the weeks pattern
    651     * @return number of dates during which this time location is meeting
    652     */
    653    public int countDates(int dayOfWeekOffset) {
    654        int idx = -1;
    655        int count = 0;
    656        while ((idx = getWeekCode().nextSetBit(1 + idx)) >= 0) {
    657            int dow = (idx + dayOfWeekOffset) % 7;
    658            if ((getDayCode() & Constants.DAY_CODES[dow]) != 0) count++;
    659        }
    660        return count;
    661    }
    662
    663    private class DateEnum implements IntEnumeration {
    664        int dayOfWeekOffset = 0;
    665        int nextDate = -1;
    666        boolean hasNext = false;
    667
    668        private DateEnum(int dayOfWeekOffset) {
    669            this.dayOfWeekOffset = dayOfWeekOffset;
    670            hasNext = nextDate();
    671        }
    672
    673        boolean nextDate() {
    674            while (true) {
    675                nextDate = getWeekCode().nextSetBit(1 + nextDate);
    676                if (nextDate < 0) return false;
    677                int dow = (nextDate + dayOfWeekOffset) % 7;
    678                if ((getDayCode() & Constants.DAY_CODES[dow]) != 0) return true;
    679            }
    680        }
    681
    682        @Override
    683        public boolean hasMoreElements() {
    684            return hasNext;
    685        }
    686
    687        @Override
    688        public Integer nextElement() {
    689            int ret = nextDate;
    690            hasNext = nextDate();
    691            return ret;
    692        }
    693
    694        @Deprecated
    695        @Override
    696        public Integer nextInt() {
    697            return nextElement();
    698        }
    699    }
    700}