File indexing completed on 2024-04-28 05:11:31

 /*
   SPDX-FileCopyrightText: 2000, 2001, 2004 Cornelius Schumacher <schumacher@kde.org>
   SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.com>
   SPDX-FileCopyrightText: 2010 Andras Mantia <andras@kdab.com>
   SPDX-FileCopyrightText: 2010 Casey Link <casey@kdab.com>
 
   SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #include "conflictresolver.h"
 #include "incidenceeditor_debug.h"
 #include <CalendarSupport/FreeBusyItemModel>
 
 #include <QDate>
 
 static const int DEFAULT_RESOLUTION_SECONDS = 15 * 60; // 15 minutes, 1 slot = 15 minutes
 
 using namespace IncidenceEditorNG;
 
 ConflictResolver::ConflictResolver(QWidget *parentWidget, QObject *parent)
     : QObject(parent)
     , mFBModel(new CalendarSupport::FreeBusyItemModel(this))
     , mParentWidget(parentWidget)
     , mWeekdays(7)
     , mSlotResolutionSeconds(DEFAULT_RESOLUTION_SECONDS)
 {
     const QDateTime currentLocalDateTime = QDateTime::currentDateTime();
     mTimeframeConstraint = KCalendarCore::Period(currentLocalDateTime, currentLocalDateTime);
 
     // trigger a reload in case any attendees were inserted before
     // the connection was made
     // triggerReload();
 
     // set default values, all the days
     mWeekdays.setBit(0); // Monday
     mWeekdays.setBit(1);
     mWeekdays.setBit(2);
     mWeekdays.setBit(3);
     mWeekdays.setBit(4);
     mWeekdays.setBit(5);
     mWeekdays.setBit(6); // Sunday
 
     mMandatoryRoles.reserve(4);
     mMandatoryRoles << KCalendarCore::Attendee::ReqParticipant << KCalendarCore::Attendee::OptParticipant << KCalendarCore::Attendee::NonParticipant
                     << KCalendarCore::Attendee::Chair;
 
     connect(mFBModel, &CalendarSupport::FreeBusyItemModel::dataChanged, this, &ConflictResolver::freebusyDataChanged);
 
     connect(&mCalculateTimer, &QTimer::timeout, this, &ConflictResolver::findAllFreeSlots);
     mCalculateTimer.setSingleShot(true);
 }
 
 void ConflictResolver::insertAttendee(const KCalendarCore::Attendee &attendee)
 {
     if (!mFBModel->containsAttendee(attendee)) {
         mFBModel->addItem(CalendarSupport::FreeBusyItem::Ptr(new CalendarSupport::FreeBusyItem(attendee, mParentWidget)));
     }
 }
 
 void ConflictResolver::insertAttendee(const CalendarSupport::FreeBusyItem::Ptr &freebusy)
 {
     if (!mFBModel->containsAttendee(freebusy->attendee())) {
         mFBModel->addItem(freebusy);
     }
 }
 
 void ConflictResolver::removeAttendee(const KCalendarCore::Attendee &attendee)
 {
     mFBModel->removeAttendee(attendee);
     calculateConflicts();
 }
 
 void ConflictResolver::clearAttendees()
 {
     mFBModel->clear();
 }
 
 bool ConflictResolver::containsAttendee(const KCalendarCore::Attendee &attendee)
 {
     return mFBModel->containsAttendee(attendee);
 }
 
 void ConflictResolver::setEarliestDate(QDate newDate)
 {
     QDateTime newStart = mTimeframeConstraint.start();
     newStart.setDate(newDate);
     mTimeframeConstraint = KCalendarCore::Period(newStart, mTimeframeConstraint.end());
     calculateConflicts();
 }
 
 void ConflictResolver::setEarliestTime(QTime newTime)
 {
     QDateTime newStart = mTimeframeConstraint.start();
     newStart.setTime(newTime);
     mTimeframeConstraint = KCalendarCore::Period(newStart, mTimeframeConstraint.end());
     calculateConflicts();
 }
 
 void ConflictResolver::setLatestDate(QDate newDate)
 {
     QDateTime newEnd = mTimeframeConstraint.end();
     newEnd.setDate(newDate);
     mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newEnd);
     calculateConflicts();
 }
 
 void ConflictResolver::setLatestTime(QTime newTime)
 {
     QDateTime newEnd = mTimeframeConstraint.end();
     newEnd.setTime(newTime);
     mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newEnd);
     calculateConflicts();
 }
 
 void ConflictResolver::setEarliestDateTime(const QDateTime &newDateTime)
 {
     mTimeframeConstraint = KCalendarCore::Period(newDateTime, mTimeframeConstraint.end());
     calculateConflicts();
 }
 
 void ConflictResolver::setLatestDateTime(const QDateTime &newDateTime)
 {
     mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newDateTime);
     calculateConflicts();
 }
 
 void ConflictResolver::freebusyDataChanged()
 {
     calculateConflicts();
 }
 
 int ConflictResolver::tryDate(QDateTime &tryFrom, QDateTime &tryTo)
 {
     int conflicts_count = 0;
     for (int i = 0; i < mFBModel->rowCount(); ++i) {
         QModelIndex index = mFBModel->index(i);
         auto attendee = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::AttendeeRole).value<KCalendarCore::Attendee>();
         if (!matchesRoleConstraint(attendee)) {
             continue;
         }
         auto freebusy = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::FreeBusyRole).value<KCalendarCore::FreeBusy::Ptr>();
         if (!tryDate(freebusy, tryFrom, tryTo)) {
             ++conflicts_count;
         }
     }
     return conflicts_count;
 }
 
 bool ConflictResolver::tryDate(const KCalendarCore::FreeBusy::Ptr &fb, QDateTime &tryFrom, QDateTime &tryTo)
 {
     // If we don't have any free/busy information, assume the
     // participant is free. Otherwise a participant without available
     // information would block the whole allocation.
     if (!fb) {
         return true;
     }
 
     KCalendarCore::Period::List busyPeriods = fb->busyPeriods();
     for (auto it = busyPeriods.begin(); it != busyPeriods.end(); ++it) {
         if ((*it).end() <= tryFrom // busy period ends before try period
             || (*it).start() >= tryTo) { // busy period starts after try period
             continue;
         } else {
             // the current busy period blocks the try period, try
             // after the end of the current busy period
             const qint64 secsDuration = tryFrom.secsTo(tryTo);
             tryFrom = (*it).end();
             tryTo = tryFrom.addSecs(secsDuration);
             // try again with the new try period
             tryDate(fb, tryFrom, tryTo);
             // we had to change the date at least once
             return false;
         }
     }
     return true;
 }
 
 bool ConflictResolver::findFreeSlot(const KCalendarCore::Period &dateTimeRange)
 {
     QDateTime dtFrom = dateTimeRange.start();
     QDateTime dtTo = dateTimeRange.end();
     if (tryDate(dtFrom, dtTo)) {
         // Current time is acceptable
         return true;
     }
 
     QDateTime tryFrom = dtFrom;
     QDateTime tryTo = dtTo;
 
     // Make sure that we never suggest a date in the past, even if the
     // user originally scheduled the meeting to be in the past.
     QDateTime now = QDateTime::currentDateTimeUtc();
     if (tryFrom < now) {
         // The slot to look for is at least partially in the past.
         const qint64 secs = tryFrom.secsTo(tryTo);
         tryFrom = now;
         tryTo = tryFrom.addSecs(secs);
     }
 
     bool found = false;
     while (!found) {
         found = tryDate(tryFrom, tryTo);
         // PENDING(kalle) Make the interval configurable
         if (!found && dtFrom.daysTo(tryFrom) > 365) {
             break; // don't look more than one year in the future
         }
     }
 
     dtFrom = tryFrom;
     dtTo = tryTo;
 
     return found;
 }
 
 void ConflictResolver::findAllFreeSlots()
 {
     // Uses an O(p*n) (n number of attendees, p timeframe range / timeslot resolution ) algorithm to
     // locate all free blocks in a given timeframe that match the search constraints.
     // Does so by:
     // 1. convert each attendees schedule for the timeframe into a bitarray according to
     //    the time resolution, where each time slot has a value of 1 = busy, 0 = free.
     // 2. align the arrays vertically, and sum the columns
     // 3. the resulting summation indicates # of conflicts at each timeslot
     // 4. locate contiguous timeslots with a values of 0. these are the free time blocks.
 
     // define these locally for readability
     const QDateTime begin = mTimeframeConstraint.start();
     const QDateTime end = mTimeframeConstraint.end();
 
     // calculate the time resolution
     // each timeslot in the arrays represents a unit of time
     // specified here.
     if (mSlotResolutionSeconds < 1) {
         // fallback to default, if the user's value is invalid
         mSlotResolutionSeconds = DEFAULT_RESOLUTION_SECONDS;
     }
 
     // calculate the length of the timeframe in terms of the amount of timeslots.
     // Example: 1 week timeframe, with resolution of 15 minutes
     //          1 week = 10080 minutes / 15 = 672 15 min timeslots
     //          So, the array would have a length of 672
     const int range = begin.secsTo(end) / mSlotResolutionSeconds;
     if (range <= 0) {
         qCWarning(INCIDENCEEDITOR_LOG) << "free slot calculation: invalid range. range( " << begin.secsTo(end) << ") / mSlotResolutionSeconds("
                                        << mSlotResolutionSeconds << ") = " << range;
         return;
     }
 
     qCDebug(INCIDENCEEDITOR_LOG) << "from " << begin << " to " << end << "; mSlotResolutionSeconds = " << mSlotResolutionSeconds << "; range = " << range;
     // filter out attendees for which we don't have FB data
     // and which don't match the mandatory role constraint
     QList<KCalendarCore::FreeBusy::Ptr> filteredFBItems;
     for (int i = 0; i < mFBModel->rowCount(); ++i) {
         QModelIndex index = mFBModel->index(i);
         auto attendee = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::AttendeeRole).value<KCalendarCore::Attendee>();
         if (!matchesRoleConstraint(attendee)) {
             continue;
         }
         auto freebusy = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::FreeBusyRole).value<KCalendarCore::FreeBusy::Ptr>();
         if (freebusy) {
             filteredFBItems << freebusy;
         }
     }
 
     // now we know the number of attendees we are calculating for
     const int number_attendees = filteredFBItems.size();
     if (number_attendees <= 0) {
         qCDebug(INCIDENCEEDITOR_LOG) << "no attendees match search criteria";
         return;
     }
     qCDebug(INCIDENCEEDITOR_LOG) << "num attendees: " << number_attendees;
     // this is a 2 dimensional array where the rows are attendees
     // and the columns are 0 or 1 denoting free or busy respectively.
     QList<QList<int>> fbTable;
 
     // Explanation of the following loop:
     // iterate: through each attendee
     //   allocate: an array of length <range> and fill it with 0s
     //   iterate: through each attendee's busy period
     //     if: the period lies inside our timeframe
     //     then:
     //       calculate the array index within the timeframe range of the beginning of the busy period
     //       fill from that index until the period ends with a 1, representing busy
     //     fi
     //   etareti
     // append the allocated array to <fbTable>
     // etareti
     for (const KCalendarCore::FreeBusy::Ptr &currentFB : std::as_const(filteredFBItems)) {
         Q_ASSERT(currentFB); // sanity check
         const KCalendarCore::Period::List busyPeriods = currentFB->busyPeriods();
         QList<int> fbArray(range);
         fbArray.fill(0); // initialize to zero
         for (const auto &period : busyPeriods) {
             if (period.end() >= begin && period.start() <= end) {
                 int start_index = -1; // Initialize it to an invalid value.
                 int duration = -1; // Initialize it to an invalid value.
                 // case1: the period is completely in our timeframe
                 if (period.end() <= end && period.start() >= begin) {
                     start_index = begin.secsTo(period.start()) / mSlotResolutionSeconds;
                     duration = period.start().secsTo(period.end()) / mSlotResolutionSeconds;
                     duration -= 1; // vector starts at 0
                     // case2: the period begins before our timeframe begins
                 } else if (period.start() <= begin && period.end() <= end) {
                     start_index = 0;
                     duration = (begin.secsTo(period.end()) / mSlotResolutionSeconds) - 1;
                     // case3: the period ends after our timeframe ends
                 } else if (period.end() >= end && period.start() >= begin) {
                     start_index = begin.secsTo(period.start()) / mSlotResolutionSeconds;
                     duration = range - start_index - 1;
                     // case4: case2+case3: our timeframe is inside the period
                 } else if (period.start() <= begin && period.end() >= end) {
                     start_index = 0;
                     duration = range - 1;
                 } else {
                     // QT5
                     // qCCritical(INCIDENCEEDITOR_LOG) << "impossible condition reached" << period.start() << period.end();
                 }
                 //      qCDebug(INCIDENCEEDITOR_LOG) << start_index << "+" << duration << "="
                 //               << start_index + duration << "<=" << range;
                 Q_ASSERT((start_index + duration) < range); // sanity check
                 for (int i = start_index; i <= start_index + duration; ++i) {
                     fbArray[i] = 1;
                 }
             }
         }
         Q_ASSERT(fbArray.size() == range); // sanity check
         fbTable.append(fbArray);
     }
 
     Q_ASSERT(fbTable.size() == number_attendees);
 
     // Now, create another array to represent the allowed weekdays constraints
     // All days which are not allowed, will be marked as busy
     QList<int> fbArray(range);
     fbArray.fill(0); // initialize to zero
     for (int slot = 0; slot < fbArray.size(); ++slot) {
         const QDateTime dateTime = begin.addSecs(slot * mSlotResolutionSeconds);
         const int dayOfWeek = dateTime.date().dayOfWeek() - 1; // bitarray is 0 indexed
         if (!mWeekdays[dayOfWeek]) {
             fbArray[slot] = 1;
         }
     }
     fbTable.append(fbArray);
 
     // Create the composite array that will hold the sums for
     // each 15 minute timeslot
     QList<int> summed(range);
     summed.fill(0); // initialize to zero
 
     // Sum the columns of the table
     for (int i = 0; i < fbTable.size(); ++i) {
         for (int j = 0; j < range; ++j) {
             summed[j] += fbTable[i][j];
         }
     }
 
     // Finally, iterate through the composite array locating contiguous free timeslots
     int free_count = 0;
     bool free_found = false;
     mAvailableSlots.clear();
     for (int i = 0; i < range; ++i) {
         // free timeslot encountered, increment counter
         if (summed[i] == 0) {
             ++free_count;
         }
         if (summed[i] != 0 || (i == (range - 1) && summed[i] == 0)) {
             // current slot is not free, so push the previous free blocks
             // OR we are in the last slot and it is free
             if (free_count > 0) {
                 int free_start_i; // start index of the free block
                 int free_end_i; // end index of the free block
                 if (summed[i] == 0) {
                     // special case: we are on the last slot and it is free
                     //               so we want to include this slot in the free block
                     free_start_i = i - free_count + 1; // add one, to set us back inside the array because
                     // free_count was incremented already this iteration
                     free_end_i = i + 1; // add one to compensate for the fact that the array is 0 indexed
                 } else {
                     free_start_i = i - free_count;
                     free_end_i = i - 1 + 1; // add one to compensate for the fact that the array is 0 indexed
                     // compiler will optimize out the -1+1, but I leave it here to make the reasoning apparent.
                 }
                 // convert from our timeslot interval back into to normal seconds
                 // then calculate the date times of the free block based on
                 // our initial timeframe
                 const QDateTime freeBegin = begin.addSecs(free_start_i * mSlotResolutionSeconds);
                 const QDateTime freeEnd = freeBegin.addSecs((free_end_i - free_start_i) * mSlotResolutionSeconds);
                 // push the free block onto the list
                 mAvailableSlots << KCalendarCore::Period(freeBegin, freeEnd);
                 free_count = 0;
                 if (!free_found) {
                     free_found = true;
                 }
             }
         }
     }
     if (free_found) {
         Q_EMIT freeSlotsAvailable(mAvailableSlots);
     }
 #if 0
     //DEBUG, dump the arrays. very helpful for debugging
     QTextStream dump(stdout);
     dump << "    ";
     dump.setFieldWidth(3);
     for (int i = 0; i < range; ++i) {   // header
         dump << i;
     }
     dump.setFieldWidth(1);
     dump << "\n\n";
     for (int i = 0; i < number_attendees; ++i) {
         dump.setFieldWidth(1);
         dump << i << ":  ";
         dump.setFieldWidth(3);
         for (int j = 0; j < range; ++j) {
             dump << fbTable[i][j];
         }
         dump << "\n\n";
     }
     dump.setFieldWidth(1);
     dump << "    ";
     dump.setFieldWidth(3);
     for (int i = 0; i < range; ++i) {
         dump << summed[i];
     }
     dump << "\n";
 #endif
 }
 
 void ConflictResolver::calculateConflicts()
 {
     QDateTime start = mTimeframeConstraint.start();
     QDateTime end = mTimeframeConstraint.end();
     const int count = tryDate(start, end);
     Q_EMIT conflictsDetected(count);
 
     if (!mCalculateTimer.isActive()) {
         mCalculateTimer.start(0);
     }
 }
 
 void ConflictResolver::setAllowedWeekdays(const QBitArray &weekdays)
 {
     mWeekdays = weekdays;
     calculateConflicts();
 }
 
 void ConflictResolver::setMandatoryRoles(const QSet<KCalendarCore::Attendee::Role> &roles)
 {
     mMandatoryRoles = roles;
     calculateConflicts();
 }
 
 bool ConflictResolver::matchesRoleConstraint(const KCalendarCore::Attendee &attendee)
 {
     return mMandatoryRoles.contains(attendee.role());
 }
 
 KCalendarCore::Period::List ConflictResolver::availableSlots() const
 {
     return mAvailableSlots;
 }
 
 void ConflictResolver::setResolution(int seconds)
 {
     mSlotResolutionSeconds = seconds;
 }
 
 CalendarSupport::FreeBusyItemModel *ConflictResolver::model() const
 {
     return mFBModel;
 }
 
 #include "moc_conflictresolver.cpp"