Incidenceeditor

conflictresolver.cpp
1/*
2 SPDX-FileCopyrightText: 2000, 2001, 2004 Cornelius Schumacher <schumacher@kde.org>
3 SPDX-FileCopyrightText: 2010 Klarälvdalens Datakonsult AB, a KDAB Group company <info@kdab.com>
4 SPDX-FileCopyrightText: 2010 Andras Mantia <andras@kdab.com>
5 SPDX-FileCopyrightText: 2010 Casey Link <casey@kdab.com>
6
7 SPDX-License-Identifier: LGPL-2.0-or-later
8*/
9
10#include "conflictresolver.h"
11#include "incidenceeditor_debug.h"
12#include <CalendarSupport/FreeBusyItemModel>
13
14#include <QDate>
15
16static const int DEFAULT_RESOLUTION_SECONDS = 15 * 60; // 15 minutes, 1 slot = 15 minutes
17
18using namespace IncidenceEditorNG;
19
21 : QObject(parent)
22 , mFBModel(new CalendarSupport::FreeBusyItemModel(this))
23 , mParentWidget(parentWidget)
24 , mWeekdays(7)
25 , mSlotResolutionSeconds(DEFAULT_RESOLUTION_SECONDS)
26{
27 const QDateTime currentLocalDateTime = QDateTime::currentDateTime();
28 mTimeframeConstraint = KCalendarCore::Period(currentLocalDateTime, currentLocalDateTime);
29
30 // trigger a reload in case any attendees were inserted before
31 // the connection was made
32 // triggerReload();
33
34 // set default values, all the days
35 mWeekdays.setBit(0); // Monday
36 mWeekdays.setBit(1);
37 mWeekdays.setBit(2);
38 mWeekdays.setBit(3);
39 mWeekdays.setBit(4);
40 mWeekdays.setBit(5);
41 mWeekdays.setBit(6); // Sunday
42
43 mMandatoryRoles.reserve(4);
46
47 connect(mFBModel, &CalendarSupport::FreeBusyItemModel::dataChanged, this, &ConflictResolver::freebusyDataChanged);
48
49 connect(&mCalculateTimer, &QTimer::timeout, this, &ConflictResolver::findAllFreeSlots);
50 mCalculateTimer.setSingleShot(true);
51}
52
54{
55 if (!mFBModel->containsAttendee(attendee)) {
56 mFBModel->addItem(CalendarSupport::FreeBusyItem::Ptr(new CalendarSupport::FreeBusyItem(attendee, mParentWidget)));
57 }
58}
59
60void ConflictResolver::insertAttendee(const CalendarSupport::FreeBusyItem::Ptr &freebusy)
61{
62 if (!mFBModel->containsAttendee(freebusy->attendee())) {
63 mFBModel->addItem(freebusy);
64 }
65}
66
68{
69 mFBModel->removeAttendee(attendee);
70 calculateConflicts();
71}
72
74{
75 mFBModel->clear();
76}
77
79{
80 return mFBModel->containsAttendee(attendee);
81}
82
84{
85 QDateTime newStart = mTimeframeConstraint.start();
86 newStart.setDate(newDate);
87 mTimeframeConstraint = KCalendarCore::Period(newStart, mTimeframeConstraint.end());
88 calculateConflicts();
89}
90
91void ConflictResolver::setEarliestTime(QTime newTime)
92{
93 QDateTime newStart = mTimeframeConstraint.start();
94 newStart.setTime(newTime);
95 mTimeframeConstraint = KCalendarCore::Period(newStart, mTimeframeConstraint.end());
96 calculateConflicts();
97}
98
99void ConflictResolver::setLatestDate(QDate newDate)
100{
101 QDateTime newEnd = mTimeframeConstraint.end();
102 newEnd.setDate(newDate);
103 mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newEnd);
104 calculateConflicts();
105}
106
107void ConflictResolver::setLatestTime(QTime newTime)
108{
109 QDateTime newEnd = mTimeframeConstraint.end();
110 newEnd.setTime(newTime);
111 mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newEnd);
112 calculateConflicts();
113}
114
115void ConflictResolver::setEarliestDateTime(const QDateTime &newDateTime)
116{
117 mTimeframeConstraint = KCalendarCore::Period(newDateTime, mTimeframeConstraint.end());
118 calculateConflicts();
119}
120
121void ConflictResolver::setLatestDateTime(const QDateTime &newDateTime)
122{
123 mTimeframeConstraint = KCalendarCore::Period(mTimeframeConstraint.start(), newDateTime);
124 calculateConflicts();
125}
126
127void ConflictResolver::freebusyDataChanged()
128{
129 calculateConflicts();
130}
131
132int ConflictResolver::tryDate(QDateTime &tryFrom, QDateTime &tryTo)
133{
134 int conflicts_count = 0;
135 for (int i = 0; i < mFBModel->rowCount(); ++i) {
136 QModelIndex index = mFBModel->index(i);
137 auto attendee = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::AttendeeRole).value<KCalendarCore::Attendee>();
138 if (!matchesRoleConstraint(attendee)) {
139 continue;
140 }
141 auto freebusy = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::FreeBusyRole).value<KCalendarCore::FreeBusy::Ptr>();
142 if (!tryDate(freebusy, tryFrom, tryTo)) {
143 ++conflicts_count;
144 }
145 }
146 return conflicts_count;
147}
148
149bool ConflictResolver::tryDate(const KCalendarCore::FreeBusy::Ptr &fb, QDateTime &tryFrom, QDateTime &tryTo)
150{
151 // If we don't have any free/busy information, assume the
152 // participant is free. Otherwise a participant without available
153 // information would block the whole allocation.
154 if (!fb) {
155 return true;
156 }
157
158 KCalendarCore::Period::List busyPeriods = fb->busyPeriods();
159 for (auto it = busyPeriods.begin(); it != busyPeriods.end(); ++it) {
160 if ((*it).end() <= tryFrom // busy period ends before try period
161 || (*it).start() >= tryTo) { // busy period starts after try period
162 continue;
163 } else {
164 // the current busy period blocks the try period, try
165 // after the end of the current busy period
166 const qint64 secsDuration = tryFrom.secsTo(tryTo);
167 tryFrom = (*it).end();
168 tryTo = tryFrom.addSecs(secsDuration);
169 // try again with the new try period
170 tryDate(fb, tryFrom, tryTo);
171 // we had to change the date at least once
172 return false;
173 }
174 }
175 return true;
176}
177
179{
180 QDateTime dtFrom = dateTimeRange.start();
181 QDateTime dtTo = dateTimeRange.end();
182 if (tryDate(dtFrom, dtTo)) {
183 // Current time is acceptable
184 return true;
185 }
186
187 QDateTime tryFrom = dtFrom;
188 QDateTime tryTo = dtTo;
189
190 // Make sure that we never suggest a date in the past, even if the
191 // user originally scheduled the meeting to be in the past.
193 if (tryFrom < now) {
194 // The slot to look for is at least partially in the past.
195 const qint64 secs = tryFrom.secsTo(tryTo);
196 tryFrom = now;
197 tryTo = tryFrom.addSecs(secs);
198 }
199
200 bool found = false;
201 while (!found) {
202 found = tryDate(tryFrom, tryTo);
203 // PENDING(kalle) Make the interval configurable
204 if (!found && dtFrom.daysTo(tryFrom) > 365) {
205 break; // don't look more than one year in the future
206 }
207 }
208
209 dtFrom = tryFrom;
210 dtTo = tryTo;
211
212 return found;
213}
214
215void ConflictResolver::findAllFreeSlots()
216{
217 // Uses an O(p*n) (n number of attendees, p timeframe range / timeslot resolution ) algorithm to
218 // locate all free blocks in a given timeframe that match the search constraints.
219 // Does so by:
220 // 1. convert each attendees schedule for the timeframe into a bitarray according to
221 // the time resolution, where each time slot has a value of 1 = busy, 0 = free.
222 // 2. align the arrays vertically, and sum the columns
223 // 3. the resulting summation indicates # of conflicts at each timeslot
224 // 4. locate contiguous timeslots with a values of 0. these are the free time blocks.
225
226 // define these locally for readability
227 const QDateTime begin = mTimeframeConstraint.start();
228 const QDateTime end = mTimeframeConstraint.end();
229
230 // calculate the time resolution
231 // each timeslot in the arrays represents a unit of time
232 // specified here.
233 if (mSlotResolutionSeconds < 1) {
234 // fallback to default, if the user's value is invalid
235 mSlotResolutionSeconds = DEFAULT_RESOLUTION_SECONDS;
236 }
237
238 // calculate the length of the timeframe in terms of the amount of timeslots.
239 // Example: 1 week timeframe, with resolution of 15 minutes
240 // 1 week = 10080 minutes / 15 = 672 15 min timeslots
241 // So, the array would have a length of 672
242 const int range = begin.secsTo(end) / mSlotResolutionSeconds;
243 if (range <= 0) {
244 qCWarning(INCIDENCEEDITOR_LOG) << "free slot calculation: invalid range. range( " << begin.secsTo(end) << ") / mSlotResolutionSeconds("
245 << mSlotResolutionSeconds << ") = " << range;
246 return;
247 }
248
249 qCDebug(INCIDENCEEDITOR_LOG) << "from " << begin << " to " << end << "; mSlotResolutionSeconds = " << mSlotResolutionSeconds << "; range = " << range;
250 // filter out attendees for which we don't have FB data
251 // and which don't match the mandatory role constraint
253 for (int i = 0; i < mFBModel->rowCount(); ++i) {
254 QModelIndex index = mFBModel->index(i);
255 auto attendee = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::AttendeeRole).value<KCalendarCore::Attendee>();
256 if (!matchesRoleConstraint(attendee)) {
257 continue;
258 }
259 auto freebusy = mFBModel->data(index, CalendarSupport::FreeBusyItemModel::FreeBusyRole).value<KCalendarCore::FreeBusy::Ptr>();
260 if (freebusy) {
261 filteredFBItems << freebusy;
262 }
263 }
264
265 // now we know the number of attendees we are calculating for
266 const int number_attendees = filteredFBItems.size();
267 if (number_attendees <= 0) {
268 qCDebug(INCIDENCEEDITOR_LOG) << "no attendees match search criteria";
269 return;
270 }
271 qCDebug(INCIDENCEEDITOR_LOG) << "num attendees: " << number_attendees;
272 // this is a 2 dimensional array where the rows are attendees
273 // and the columns are 0 or 1 denoting free or busy respectively.
274 QList<QList<int>> fbTable;
275
276 // Explanation of the following loop:
277 // iterate: through each attendee
278 // allocate: an array of length <range> and fill it with 0s
279 // iterate: through each attendee's busy period
280 // if: the period lies inside our timeframe
281 // then:
282 // calculate the array index within the timeframe range of the beginning of the busy period
283 // fill from that index until the period ends with a 1, representing busy
284 // fi
285 // etareti
286 // append the allocated array to <fbTable>
287 // etareti
288 for (const KCalendarCore::FreeBusy::Ptr &currentFB : std::as_const(filteredFBItems)) {
289 Q_ASSERT(currentFB); // sanity check
290 const KCalendarCore::Period::List busyPeriods = currentFB->busyPeriods();
291 QList<int> fbArray(range);
292 fbArray.fill(0); // initialize to zero
293 for (const auto &period : busyPeriods) {
294 if (period.end() >= begin && period.start() <= end) {
295 int start_index = -1; // Initialize it to an invalid value.
296 int duration = -1; // Initialize it to an invalid value.
297 // case1: the period is completely in our timeframe
298 if (period.end() <= end && period.start() >= begin) {
299 start_index = begin.secsTo(period.start()) / mSlotResolutionSeconds;
300 duration = period.start().secsTo(period.end()) / mSlotResolutionSeconds;
301 duration -= 1; // vector starts at 0
302 // case2: the period begins before our timeframe begins
303 } else if (period.start() <= begin && period.end() <= end) {
304 start_index = 0;
305 duration = (begin.secsTo(period.end()) / mSlotResolutionSeconds) - 1;
306 // case3: the period ends after our timeframe ends
307 } else if (period.end() >= end && period.start() >= begin) {
308 start_index = begin.secsTo(period.start()) / mSlotResolutionSeconds;
309 duration = range - start_index - 1;
310 // case4: case2+case3: our timeframe is inside the period
311 } else if (period.start() <= begin && period.end() >= end) {
312 start_index = 0;
313 duration = range - 1;
314 } else {
315 // QT5
316 // qCCritical(INCIDENCEEDITOR_LOG) << "impossible condition reached" << period.start() << period.end();
317 }
318 // qCDebug(INCIDENCEEDITOR_LOG) << start_index << "+" << duration << "="
319 // << start_index + duration << "<=" << range;
320 Q_ASSERT((start_index + duration) < range); // sanity check
321 for (int i = start_index; i <= start_index + duration; ++i) {
322 fbArray[i] = 1;
323 }
324 }
325 }
326 Q_ASSERT(fbArray.size() == range); // sanity check
327 fbTable.append(fbArray);
328 }
329
330 Q_ASSERT(fbTable.size() == number_attendees);
331
332 // Now, create another array to represent the allowed weekdays constraints
333 // All days which are not allowed, will be marked as busy
334 QList<int> fbArray(range);
335 fbArray.fill(0); // initialize to zero
336 for (int slot = 0; slot < fbArray.size(); ++slot) {
337 const QDateTime dateTime = begin.addSecs(slot * mSlotResolutionSeconds);
338 const int dayOfWeek = dateTime.date().dayOfWeek() - 1; // bitarray is 0 indexed
339 if (!mWeekdays[dayOfWeek]) {
340 fbArray[slot] = 1;
341 }
342 }
343 fbTable.append(fbArray);
344
345 // Create the composite array that will hold the sums for
346 // each 15 minute timeslot
347 QList<int> summed(range);
348 summed.fill(0); // initialize to zero
349
350 // Sum the columns of the table
351 for (int i = 0; i < fbTable.size(); ++i) {
352 for (int j = 0; j < range; ++j) {
353 summed[j] += fbTable[i][j];
354 }
355 }
356
357 // Finally, iterate through the composite array locating contiguous free timeslots
358 int free_count = 0;
359 bool free_found = false;
360 mAvailableSlots.clear();
361 for (int i = 0; i < range; ++i) {
362 // free timeslot encountered, increment counter
363 if (summed[i] == 0) {
364 ++free_count;
365 }
366 if (summed[i] != 0 || (i == (range - 1) && summed[i] == 0)) {
367 // current slot is not free, so push the previous free blocks
368 // OR we are in the last slot and it is free
369 if (free_count > 0) {
370 int free_start_i; // start index of the free block
371 int free_end_i; // end index of the free block
372 if (summed[i] == 0) {
373 // special case: we are on the last slot and it is free
374 // so we want to include this slot in the free block
375 free_start_i = i - free_count + 1; // add one, to set us back inside the array because
376 // free_count was incremented already this iteration
377 free_end_i = i + 1; // add one to compensate for the fact that the array is 0 indexed
378 } else {
379 free_start_i = i - free_count;
380 free_end_i = i - 1 + 1; // add one to compensate for the fact that the array is 0 indexed
381 // compiler will optimize out the -1+1, but I leave it here to make the reasoning apparent.
382 }
383 // convert from our timeslot interval back into to normal seconds
384 // then calculate the date times of the free block based on
385 // our initial timeframe
386 const QDateTime freeBegin = begin.addSecs(free_start_i * mSlotResolutionSeconds);
387 const QDateTime freeEnd = freeBegin.addSecs((free_end_i - free_start_i) * mSlotResolutionSeconds);
388 // push the free block onto the list
389 mAvailableSlots << KCalendarCore::Period(freeBegin, freeEnd);
390 free_count = 0;
391 if (!free_found) {
392 free_found = true;
393 }
394 }
395 }
396 }
397 if (free_found) {
398 Q_EMIT freeSlotsAvailable(mAvailableSlots);
399 }
400#if 0
401 //DEBUG, dump the arrays. very helpful for debugging
402 QTextStream dump(stdout);
403 dump << " ";
404 dump.setFieldWidth(3);
405 for (int i = 0; i < range; ++i) { // header
406 dump << i;
407 }
408 dump.setFieldWidth(1);
409 dump << "\n\n";
410 for (int i = 0; i < number_attendees; ++i) {
411 dump.setFieldWidth(1);
412 dump << i << ": ";
413 dump.setFieldWidth(3);
414 for (int j = 0; j < range; ++j) {
415 dump << fbTable[i][j];
416 }
417 dump << "\n\n";
418 }
419 dump.setFieldWidth(1);
420 dump << " ";
421 dump.setFieldWidth(3);
422 for (int i = 0; i < range; ++i) {
423 dump << summed[i];
424 }
425 dump << "\n";
426#endif
427}
428
429void ConflictResolver::calculateConflicts()
430{
431 QDateTime start = mTimeframeConstraint.start();
432 QDateTime end = mTimeframeConstraint.end();
433 const int count = tryDate(start, end);
435
436 if (!mCalculateTimer.isActive()) {
437 mCalculateTimer.start(0);
438 }
439}
440
442{
443 mWeekdays = weekdays;
444 calculateConflicts();
445}
446
448{
449 mMandatoryRoles = roles;
450 calculateConflicts();
451}
452
453bool ConflictResolver::matchesRoleConstraint(const KCalendarCore::Attendee &attendee)
454{
455 return mMandatoryRoles.contains(attendee.role());
456}
457
459{
460 return mAvailableSlots;
461}
462
463void ConflictResolver::setResolution(int seconds)
464{
465 mSlotResolutionSeconds = seconds;
466}
467
468CalendarSupport::FreeBusyItemModel *ConflictResolver::model() const
469{
470 return mFBModel;
471}
472
473#include "moc_conflictresolver.cpp"
void clearAttendees()
Clear all attendees.
ConflictResolver(QWidget *parentWidget, QObject *parent=nullptr)
void setEarliestDate(QDate newDate)
Set the timeframe constraints.
bool containsAttendee(const KCalendarCore::Attendee &attendee)
Returns whether the resolver contains the attendee.
void insertAttendee(const KCalendarCore::Attendee &attendee)
Add an attendee The attendees free busy info will be fetched and integrated into the resolver.
void removeAttendee(const KCalendarCore::Attendee &attendee)
Removes an attendee The attendee will no longer be considered when resolving conflicts.
void freeSlotsAvailable(const KCalendarCore::Period::List &)
Emitted when the resolver locates new free slots.
void setAllowedWeekdays(const QBitArray &weekdays)
Constrain the free time slot search to the weekdays identified by their KCalendarSystem integer repre...
bool findFreeSlot(const KCalendarCore::Period &dateTimeRange)
Finds a free slot in the future which has at least the same size as the initial slot.
void setMandatoryRoles(const QSet< KCalendarCore::Attendee::Role > &roles)
Constrain the free time slot search to the set participant roles.
void conflictsDetected(int number)
Emitted when there are conflicts.
KCalendarCore::Period::List availableSlots() const
Returns a list of date time ranges that conform to the search constraints.
QDateTime end() const
QDateTime start() const
Q_SCRIPTABLE Q_NOREPLY void start()
const QList< QKeySequence > & begin()
const QList< QKeySequence > & end()
void setBit(qsizetype i)
int dayOfWeek() const const
QDateTime addSecs(qint64 s) const const
QDateTime currentDateTime()
QDateTime currentDateTimeUtc()
QDate date() const const
qint64 daysTo(const QDateTime &other) const const
qint64 secsTo(const QDateTime &other) const const
void setDate(QDate date)
void setTime(QTime time)
void append(QList< T > &&value)
iterator begin()
void clear()
iterator end()
qsizetype size() const const
Q_EMITQ_EMIT
QMetaObject::Connection connect(const QObject *sender, PointerToMemberFunction signal, Functor functor)
bool contains(const QSet< T > &other) const const
void reserve(qsizetype size)
bool isActive() const const
void setSingleShot(bool singleShot)
void start()
void timeout()
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Sat Dec 21 2024 16:58:15 by doxygen 1.12.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.