diff --git a/incidenceeditor-ng/conflictresolver.cpp b/incidenceeditor-ng/conflictresolver.cpp index 7b54247268..20a0990543 100644 --- a/incidenceeditor-ng/conflictresolver.cpp +++ b/incidenceeditor-ng/conflictresolver.cpp @@ -1,547 +1,545 @@ /* Copyright (c) 2000,2001,2004 Cornelius Schumacher Copyright (c) 2010 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com Copyright (c) 2010 Andras Mantia Copyright (C) 2010 Casey Link This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "conflictresolver.h" #include "freebusymodel/freebusyitemmodel.h" #include #include #include 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 FreeBusyItemModel( this ) ), mParentWidget( parentWidget ), mWeekdays( 7 ), mSlotResolutionSeconds( DEFAULT_RESOLUTION_SECONDS ), mWorkingHoursOnly(false), mDuration(0) { // 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 << KCalCore::Attendee::ReqParticipant << KCalCore::Attendee::OptParticipant << KCalCore::Attendee::NonParticipant << KCalCore::Attendee::Chair; connect( mFBModel, SIGNAL(dataChanged(QModelIndex,QModelIndex)), SLOT(freebusyDataChanged()) ); connect( &mCalculateTimer, SIGNAL(timeout()), SLOT(findAllFreeSlots()) ); mCalculateTimer.setSingleShot( true ); } void ConflictResolver::insertAttendee( const KCalCore::Attendee::Ptr &attendee ) { if ( !mFBModel->containsAttendee( attendee ) ) { mFBModel->addItem( FreeBusyItem::Ptr( new FreeBusyItem( attendee, mParentWidget ) ) ); } } void ConflictResolver::insertAttendee( const FreeBusyItem::Ptr &freebusy ) { if ( !mFBModel->containsAttendee( freebusy->attendee() ) ) { mFBModel->addItem( freebusy ); } } void ConflictResolver::removeAttendee( const KCalCore::Attendee::Ptr &attendee ) { mFBModel->removeAttendee( attendee ); calculateConflicts(); } void ConflictResolver::clearAttendees() { mFBModel->clear(); } bool ConflictResolver::containsAttendee( const KCalCore::Attendee::Ptr &attendee ) { return mFBModel->containsAttendee( attendee ); } void ConflictResolver::setEarliestDate( const QDate &newDate ) { KDateTime newStart = mTimeframeConstraint.start(); newStart.setDate( newDate ); mTimeframeConstraint = KCalCore::Period( newStart, mTimeframeConstraint.end() ); calculateConflicts(); } void ConflictResolver::setEarliestTime( const QTime &newTime ) { KDateTime newStart = mTimeframeConstraint.start(); newStart.setTime( newTime ); mTimeframeConstraint = KCalCore::Period( newStart, mTimeframeConstraint.end() ); calculateConflicts(); } void ConflictResolver::setLatestDate( const QDate &newDate ) { KDateTime newEnd = mTimeframeConstraint.end(); newEnd.setDate( newDate ); mTimeframeConstraint = KCalCore::Period( mTimeframeConstraint.start(), newEnd ); calculateConflicts(); } void ConflictResolver::setLatestTime( const QTime &newTime ) { KDateTime newEnd = mTimeframeConstraint.end(); newEnd.setTime( newTime ); mTimeframeConstraint = KCalCore::Period( mTimeframeConstraint.start(), newEnd ); calculateConflicts(); } void ConflictResolver::setEarliestDateTime( const KDateTime &newDateTime ) { mTimeframeConstraint = KCalCore::Period( newDateTime, mTimeframeConstraint.end() ); calculateConflicts(); } void ConflictResolver::setLatestDateTime( const KDateTime &newDateTime ) { mTimeframeConstraint = KCalCore::Period( mTimeframeConstraint.start(), newDateTime ); calculateConflicts(); } void ConflictResolver::freebusyDataChanged() { calculateConflicts(); } void ConflictResolver::setWorkingHoursOnly(bool workingTime) { mWorkingHoursOnly = workingTime; calculateConflicts(); } bool ConflictResolver::workingHoursOnly() const { return mWorkingHoursOnly; } void ConflictResolver::setWorkingHours(QTime start, QTime end) { mWorkingHoursStart = start; mWorkingHoursEnd = end; calculateConflicts(); } void ConflictResolver::setDuration(int duration) { mDuration = duration; calculateConflicts(); } int ConflictResolver::tryDate( KDateTime &tryFrom, KDateTime &tryTo ) { int conflicts_count = 0; for ( int i = 0; i < mFBModel->rowCount(); ++i ) { QModelIndex index = mFBModel->index( i ); KCalCore::Attendee::Ptr attendee = mFBModel->data( index, FreeBusyItemModel::AttendeeRole ).value(); if ( !matchesRoleConstraint( attendee ) ) { continue; } KCalCore::FreeBusy::Ptr freebusy = mFBModel->data( index, FreeBusyItemModel::FreeBusyRole ).value(); if ( !tryDate( freebusy, tryFrom, tryTo ) ) { ++conflicts_count; } } return conflicts_count; } bool ConflictResolver::tryDate( const KCalCore::FreeBusy::Ptr &fb, KDateTime &tryFrom, KDateTime &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; } KCalCore::Period::List busyPeriods = fb->busyPeriods(); for ( KCalCore::Period::List::Iterator 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 int 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 KCalCore::Period &dateTimeRange ) { KDateTime dtFrom = dateTimeRange.start(); KDateTime dtTo = dateTimeRange.end(); if ( tryDate( dtFrom, dtTo ) ) { // Current time is acceptable return true; } KDateTime tryFrom = dtFrom; KDateTime 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. KDateTime now = KDateTime::currentUtcDateTime(); if ( tryFrom < now ) { // The slot to look for is at least partially in the past. const int 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 indcates # 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 KDateTime begin = mTimeframeConstraint.start(); const KDateTime end = mTimeframeConstraint.end(); const int duration = mDuration / mSlotResolutionSeconds; bool workingHoursOnly = mWorkingHoursOnly; if (workingHoursOnly && (!mWorkingHoursStart.isValid() || !mWorkingHoursStart.isValid() )) { workingHoursOnly = false; } // 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 ) { kWarning() << "free slot calculation: invalid range. range( " << begin.secsTo( end ) << ") / mSlotResolutionSeconds(" << mSlotResolutionSeconds << ") = " << range; return; } kDebug() << "from " << begin << " to " << end << "; mSlotResolutionSeconds = " << mSlotResolutionSeconds << "; range = " << range << "; workingtime =" << workingHoursOnly; // filter out attendees for which we don't have FB data // and which don't match the mandatory role contrstaint QList filteredFBItems; for ( int i = 0; i < mFBModel->rowCount(); ++i ) { QModelIndex index = mFBModel->index( i ); KCalCore::Attendee::Ptr attendee = mFBModel->data( index, FreeBusyItemModel::AttendeeRole ).value(); if ( !matchesRoleConstraint( attendee ) ) { continue; } KCalCore::FreeBusy::Ptr freebusy = mFBModel->data( index, FreeBusyItemModel::FreeBusyRole ).value(); if( freebusy ) { filteredFBItems << freebusy; } } // now we know the number of attendees we are calculating for const int number_attendees = filteredFBItems.size(); kDebug() << "num attendees: " << number_attendees; // this is a 2 dimensional array where the rows are attendees // and the columns are 0 or 1 denoting freee or busy respectively. QVector< QVector > fbTable; if ( number_attendees > 0 ) { // Explanation of the following loop: // iterate: through each attendee // allocate: an array of length 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 // etareti foreach ( KCalCore::FreeBusy::Ptr currentFB, filteredFBItems ) { Q_ASSERT( currentFB ); // sanity check KCalCore::Period::List busyPeriods = currentFB->busyPeriods(); QVector fbArray( range ); fbArray.fill( 0 ); // initialize to zero for ( KCalCore::Period::List::Iterator it = busyPeriods.begin(); it != busyPeriods.end(); ++it ) { if ( it->end() >= begin && it->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( it->end() <= end && it->start() >= begin ) { start_index = begin.secsTo( it->start() ) / mSlotResolutionSeconds; duration = it->start().secsTo( it->end() ) / mSlotResolutionSeconds; duration -= 1; // vector starts at 0 // case2: the period begins before our timeframe begins } else if( it->start() <= begin && it->end() <= end ) { start_index = 0; duration = ( begin.secsTo( it->end() ) / mSlotResolutionSeconds ) - 1; // case3: the period ends after our timeframe ends } else if( it->end() >= end && it->start() >= begin ) { start_index = begin.secsTo( it->start() ) / mSlotResolutionSeconds; duration = range - start_index - 1; // case4: case2+case3: our timeframe is inside the period } else if( it->start() <= begin && it->end() >= end ) { start_index = 0; duration = range - 1; } else { kFatal() << "impossible condition reached" << it->start() << it->end(); } // kDebug() << 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 ); } else { //If we have no information about freebusytime of participants, everything is free QVector fbArray( range ); fbArray.fill( 0 ); fbTable.append( fbArray ); } // Now, create another array to represent the allowed weekdays constraints // All days which are not allowed, will be marked as busy const KCalendarSystem *calSys = KGlobal::locale()->calendar(); QVector fbArray( range ); fbArray.fill( 0 ); // initialize to zero for ( int slot = 0; slot < fbArray.size(); ++slot ) { const KDateTime dateTime = begin.addSecs( slot * mSlotResolutionSeconds ); const int dayOfWeek = calSys->dayOfWeek( dateTime.date() ) - 1; // bitarray is 0 indexed if ( !mWeekdays[dayOfWeek] ) { fbArray[slot] = 1; } else if (workingHoursOnly && !(dateTime.time() >= mWorkingHoursStart && dateTime.time() < mWorkingHoursEnd)) { fbArray[slot] = 1; } } fbTable.append( fbArray ); // Create the composite array that will hold the sums for // each 15 minute timeslot QVector 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]; } } //if we know the event duration, skipall slotswith less time for the whole meeting if (duration > 0) { for (int i = 0; i < range - duration; ++i ) { if (summed[i] == 0) { for (int j = 1; j <= duration; j++) { if (summed[i+j] != 0) { summed[i] = 1; break; } } } } } // 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 optmize 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 KDateTime freeBegin = begin.addSecs( free_start_i * mSlotResolutionSeconds ); const KDateTime freeEnd = freeBegin.addSecs( ( free_end_i - free_start_i ) * mSlotResolutionSeconds ); // push the free block onto the list mAvailableSlots << KCalCore::Period( freeBegin, freeEnd ); free_count = 0; if ( !free_found ) { free_found = true; } } } } - if ( free_found ) { - emit freeSlotsAvailable( mAvailableSlots ); - } + 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() { KDateTime start = mTimeframeConstraint.start(); KDateTime end = mTimeframeConstraint.end(); const int count = tryDate( start, end ); emit conflictsDetected( count ); if ( !mCalculateTimer.isActive() ) { mCalculateTimer.start( 0 ); } } void ConflictResolver::setAllowedWeekdays( const QBitArray &weekdays ) { mWeekdays = weekdays; calculateConflicts(); } void ConflictResolver::setMandatoryRoles( const QSet< KCalCore::Attendee::Role > &roles ) { mMandatoryRoles = roles; calculateConflicts(); } bool ConflictResolver::matchesRoleConstraint( const KCalCore::Attendee::Ptr &attendee ) { return mMandatoryRoles.contains( attendee->role() ); } KCalCore::Period::List ConflictResolver::availableSlots() const { return mAvailableSlots; } void ConflictResolver::setResolution( int seconds ) { mSlotResolutionSeconds = seconds; } FreeBusyItemModel *ConflictResolver::model() const { return mFBModel; }