recurrencerule.cpp

/*
  This file is part of libkcal.

  Copyright (c) 2005 Reinhold Kainhofer <reinhold@kainhofe.com>
  Copyright (c) 2006-2008 David Jarvie <djarvie@kde.org>

  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 "recurrencerule.h"

#include <kdebug.h>
#include <kglobal.h>

#include <QtCore/QDateTime>
#include <QtCore/QList>
#include <QtCore/QStringList>

#include <limits.h>
#include <math.h>

using namespace KCal;

// Maximum number of intervals to process
const int LOOP_LIMIT = 10000;

static QString dumpTime( const KDateTime &dt );   // for debugging

/*=========================================================================
=                                                                         =
= IMPORTANT CODING NOTE:                                                  =
=                                                                         =
= Recurrence handling code is time critical, especially for sub-daily     =
= recurrences. For example, if getNextDate() is called repeatedly to      =
= check all consecutive occurrences over a few years, on a slow machine   =
= this could take many seconds to complete in the worst case. Simple      =
= sub-daily recurrences are optimised by use of mTimedRepetition.         =
=                                                                         =
==========================================================================*/

/**************************************************************************
 *                               DateHelper                               *
 **************************************************************************/
//@cond PRIVATE
class DateHelper
{
  public:
#ifndef NDEBUG
    static QString dayName( short day );
#endif
    static QDate getNthWeek( int year, int weeknumber, short weekstart = 1 );
    static int weekNumbersInYear( int year, short weekstart = 1 );
    static int getWeekNumber( const QDate &date, short weekstart, int *year = 0 );
    static int getWeekNumberNeg( const QDate &date, short weekstart, int *year = 0 );
    // Convert to QDate, allowing for day < 0.
    // month and day must be non-zero.
    static QDate getDate( int year, int month, int day )
    {
      if ( day >= 0 ) {
        return QDate( year, month, day );
      } else {
        if ( ++month > 12 ) {
          month = 1;
          ++year;
        }
        return QDate( year, month, 1 ).addDays( day );
      }
    }
};

#ifndef NDEBUG
// TODO: Move to a general library / class, as we need the same in the iCal
//       generator and in the xcal format
QString DateHelper::dayName( short day )
{
  switch ( day ) {
  case 1:
    return "MO";
  case 2:
    return "TU";
  case 3:
    return "WE";
  case 4:
    return "TH";
  case 5:
    return "FR";
  case 6:
    return "SA";
  case 7:
    return "SU";
  default:
    return "??";
  }
}
#endif

QDate DateHelper::getNthWeek( int year, int weeknumber, short weekstart )
{
  if ( weeknumber == 0 ) {
    return QDate();
  }

  // Adjust this to the first day of week #1 of the year and add 7*weekno days.
  QDate dt( year, 1, 4 ); // Week #1 is the week that contains Jan 4
  int adjust = -( 7 + dt.dayOfWeek() - weekstart ) % 7;
  if ( weeknumber > 0 ) {
    dt = dt.addDays( 7 * (weeknumber-1) + adjust );
  } else if ( weeknumber < 0 ) {
    dt = dt.addYears( 1 );
    dt = dt.addDays( 7 * weeknumber + adjust );
  }
  return dt;
}

int DateHelper::getWeekNumber( const QDate &date, short weekstart, int *year )
{
  int y = date.year();
  QDate dt( y, 1, 4 ); // <= definitely in week #1
  dt = dt.addDays( -( 7 + dt.dayOfWeek() - weekstart ) % 7 ); // begin of week #1

  int daysto = dt.daysTo( date );
  if ( daysto < 0 ) {
    // in first week of year
    --y;
    dt = QDate( y, 1, 4 );
    dt = dt.addDays( -( 7 + dt.dayOfWeek() - weekstart ) % 7 ); // begin of week #1
    daysto = dt.daysTo( date );
  } else if ( daysto > 355 ) {
    // near the end of the year - check if it's next year
    QDate dtn( y+1, 1, 4 ); // <= definitely first week of next year
    dtn = dtn.addDays( -( 7 + dtn.dayOfWeek() - weekstart ) % 7 );
    int dayston = dtn.daysTo( date );
    if ( dayston >= 0 ) {
      // in first week of next year;
      ++y;
      daysto = dayston;
    }
  }
  if ( year ) {
    *year = y;
  }
  return daysto / 7 + 1;
}

int DateHelper::weekNumbersInYear( int year, short weekstart )
{
  QDate dt( year, 1, weekstart );
  QDate dt1( year + 1, 1, weekstart );
  return dt.daysTo( dt1 ) / 7;
}

// Week number from the end of the year
int DateHelper::getWeekNumberNeg( const QDate &date, short weekstart, int *year )
{
  int weekpos = getWeekNumber( date, weekstart, year );
  return weekNumbersInYear( *year, weekstart ) - weekpos - 1;
}
//@endcond

/**************************************************************************
 *                               Constraint                               *
 **************************************************************************/
//@cond PRIVATE
class Constraint
{
  public:
    typedef QList<Constraint> List;

    explicit Constraint( KDateTime::Spec, int wkst = 1 );
    Constraint( const KDateTime &dt, RecurrenceRule::PeriodType type, int wkst );
    void clear();
    void setYear( int n )
    {
      year = n;
      useCachedDt = false;
    }
    void setMonth( int n )
    {
      month = n;
      useCachedDt = false;
    }
    void setDay( int n )
    {
      day = n;
      useCachedDt = false;
    }
    void setHour( int n )
    {
      hour = n;
      useCachedDt = false;
    }
    void setMinute( int n )
    {
      minute = n;
      useCachedDt = false;
    }
    void setSecond( int n )
    {
      second = n;
      useCachedDt = false;
    }
    void setWeekday( int n )
    {
      weekday = n;
      useCachedDt = false;
    }
    void setWeekdaynr( int n )
    {
      weekdaynr = n;
      useCachedDt = false;
    }
    void setWeeknumber( int n )
    {
      weeknumber = n;
      useCachedDt = false;
    }
    void setYearday( int n )
    {
      yearday = n;
      useCachedDt = false;
    }
    void setWeekstart( int n )
    {
      weekstart = n;
      useCachedDt = false;
    }
    void setSecondOccurrence( int n )
    {
      secondOccurrence = n;
      useCachedDt = false;
    }

    int year;       // 0 means unspecified
    int month;      // 0 means unspecified
    int day;        // 0 means unspecified
    int hour;       // -1 means unspecified
    int minute;     // -1 means unspecified
    int second;     // -1 means unspecified
    int weekday;    //  0 means unspecified
    int weekdaynr;  // index of weekday in month/year (0=unspecified)
    int weeknumber; //  0 means unspecified
    int yearday;    //  0 means unspecified
    int weekstart;  //  first day of week (1=monday, 7=sunday, 0=unspec.)
    KDateTime::Spec timespec;   // time zone etc. to use
    bool secondOccurrence;  // the time is the second occurrence during daylight savings shift

    bool readDateTime( const KDateTime &dt, RecurrenceRule::PeriodType type );
    bool matches( const QDate &dt, RecurrenceRule::PeriodType type ) const;
    bool matches( const KDateTime &dt, RecurrenceRule::PeriodType type ) const;
    bool merge( const Constraint &interval );
    bool isConsistent() const;
    bool isConsistent( RecurrenceRule::PeriodType period ) const;
    bool increase( RecurrenceRule::PeriodType type, int freq );
    KDateTime intervalDateTime( RecurrenceRule::PeriodType type ) const;
    QList<KDateTime> dateTimes( RecurrenceRule::PeriodType type ) const;
    void appendDateTime( const QDate &date, const QTime &time, QList<KDateTime> &list ) const;
    void dump() const;

  private:
    mutable bool useCachedDt;
    mutable KDateTime cachedDt;
};

Constraint::Constraint( KDateTime::Spec spec, int wkst )
  : weekstart( wkst ),
    timespec( spec )
{
  clear();
}

Constraint::Constraint( const KDateTime &dt, RecurrenceRule::PeriodType type, int wkst )
  : weekstart( wkst ),
    timespec( dt.timeSpec() )
{
  clear();
  readDateTime( dt, type );
}

void Constraint::clear()
{
  year = 0;
  month = 0;
  day = 0;
  hour = -1;
  minute = -1;
  second = -1;
  weekday = 0;
  weekdaynr = 0;
  weeknumber = 0;
  yearday = 0;
  secondOccurrence = false;
  useCachedDt = false;
}

bool Constraint::matches( const QDate &dt, RecurrenceRule::PeriodType type ) const
{
  // If the event recurs in week 53 or 1, the day might not belong to the same
  // year as the week it is in. E.g. Jan 1, 2005 is in week 53 of year 2004.
  // So we can't simply check the year in that case!
  if ( weeknumber == 0 ) {
    if ( year > 0 && year != dt.year() ) {
      return false;
    }
  } else {
    int y;
    if ( weeknumber > 0 &&
         weeknumber != DateHelper::getWeekNumber( dt, weekstart, &y ) ) {
      return false;
    }
    if ( weeknumber < 0 &&
         weeknumber != DateHelper::getWeekNumberNeg( dt, weekstart, &y ) ) {
      return false;
    }
    if ( year > 0 && year != y ) {
      return false;
    }
  }

  if ( month > 0 && month != dt.month() ) {
    return false;
  }
  if ( day > 0 && day != dt.day() ) {
    return false;
  }
  if ( day < 0 && dt.day() != ( dt.daysInMonth() + day + 1 ) ) {
    return false;
  }
  if ( weekday > 0 ) {
    if ( weekday != dt.dayOfWeek() ) {
      return false;
    }
    if ( weekdaynr != 0 ) {
      // If it's a yearly recurrence and a month is given, the position is
      // still in the month, not in the year.
      if ( ( type == RecurrenceRule::rMonthly ) ||
           ( type == RecurrenceRule::rYearly && month > 0 ) ) {
        // Monthly
        if ( weekdaynr > 0 &&
             weekdaynr != ( dt.day() - 1 ) / 7 + 1 ) {
          return false;
        }
        if ( weekdaynr < 0 &&
             weekdaynr != -( ( dt.daysInMonth() - dt.day() ) / 7 + 1 ) ) {
          return false;
        }
      } else {
        // Yearly
        if ( weekdaynr > 0 &&
             weekdaynr != ( dt.dayOfYear() - 1 ) / 7 + 1 ) {
          return false;
        }
        if ( weekdaynr < 0 &&
             weekdaynr != -( ( dt.daysInYear() - dt.dayOfYear() ) / 7 + 1 ) ) {
          return false;
        }
      }
    }
  }
  if ( yearday > 0 && yearday != dt.dayOfYear() ) {
    return false;
  }
  if ( yearday < 0 && yearday != dt.daysInYear() - dt.dayOfYear() + 1 ) {
    return false;
  }
  return true;
}

/* Check for a match with the specified date/time.
 * The date/time's time specification must correspond with that of the start date/time.
 */
bool Constraint::matches( const KDateTime &dt, RecurrenceRule::PeriodType type ) const
{
  if ( ( hour >= 0 && ( hour != dt.time().hour() ||
                        secondOccurrence != dt.isSecondOccurrence() ) ) ||
       ( minute >= 0 && minute != dt.time().minute() ) ||
       ( second >= 0 && second != dt.time().second() ) ||
       !matches( dt.date(), type ) ) {
    return false;
  }
  return true;
}

bool Constraint::isConsistent( RecurrenceRule::PeriodType /*period*/) const
{
  // TODO: Check for consistency, e.g. byyearday=3 and bymonth=10
  return true;
}

// Return a date/time set to the constraint values, but with those parts less
// significant than the given period type set to 1 (for dates) or 0 (for times).
KDateTime Constraint::intervalDateTime( RecurrenceRule::PeriodType type ) const
{
  if ( useCachedDt ) {
    return cachedDt;
  }
  QDate d;
  QTime t( 0, 0, 0 );
  bool subdaily = true;
  switch ( type ) {
    case RecurrenceRule::rSecondly:
      t.setHMS( hour, minute, second );
      break;
    case RecurrenceRule::rMinutely:
      t.setHMS( hour, minute, 0 );
      break;
    case RecurrenceRule::rHourly:
      t.setHMS( hour, 0, 0 );
      break;
    case RecurrenceRule::rDaily:
      break;
    case RecurrenceRule::rWeekly:
      d = DateHelper::getNthWeek( year, weeknumber, weekstart );
      subdaily = false;
      break;
    case RecurrenceRule::rMonthly:
      d.setYMD( year, month, 1 );
      subdaily = false;
      break;
    case RecurrenceRule::rYearly:
      d.setYMD( year, 1, 1 );
      subdaily = false;
      break;
    default:
      break;
  }
  if ( subdaily ) {
    d = DateHelper::getDate( year, (month>0)?month:1, day?day:1 );
  }
  cachedDt = KDateTime( d, t, timespec );
  if ( secondOccurrence ) {
    cachedDt.setSecondOccurrence( true );
  }
  useCachedDt = true;
  return cachedDt;
}

bool Constraint::merge( const Constraint &interval )
{
#define mergeConstraint( name, cmparison ) \
  if ( interval.name cmparison ) { \
    if ( !( name cmparison ) ) { \
      name = interval.name; \
    } else if ( name != interval.name ) { \
      return false;\
    } \
  }

  useCachedDt = false;

  mergeConstraint( year, > 0 );
  mergeConstraint( month, > 0 );
  mergeConstraint( day, != 0 );
  mergeConstraint( hour, >= 0 );
  mergeConstraint( minute, >= 0 );
  mergeConstraint( second, >= 0 );

  mergeConstraint( weekday, != 0 );
  mergeConstraint( weekdaynr, != 0 );
  mergeConstraint( weeknumber, != 0 );
  mergeConstraint( yearday, != 0 );

#undef mergeConstraint
  return true;
}

//           Y  M  D | H  Mn S | WD #WD | WN | YD
// required:
//           x       | x  x  x |        |    |
// 0) Trivial: Exact date given, maybe other restrictions
//           x  x  x | x  x  x |        |    |
// 1) Easy case: no weekly restrictions -> at most a loop through possible dates
//           x  +  + | x  x  x |  -  -  |  - |  -
// 2) Year day is given -> date known
//           x       | x  x  x |        |    |  +
// 3) week number is given -> loop through all days of that week. Further
//    restrictions will be applied in the end, when we check all dates for
//    consistency with the constraints
//           x       | x  x  x |        |  + | (-)
// 4) week day is specified ->
//           x       | x  x  x |  x  ?  | (-)| (-)
// 5) All possiblecases have already been treated, so this must be an error!

QList<KDateTime> Constraint::dateTimes( RecurrenceRule::PeriodType type ) const
{
  QList<KDateTime> result;
  bool done = false;
  if ( !isConsistent( type ) ) {
    return result;
  }

  // TODO_Recurrence: Handle all-day
  QTime tm( hour, minute, second );

  if ( !done && day && month > 0 ) {
    appendDateTime( DateHelper::getDate( year, month, day ), tm, result );
    done = true;
  }

  if ( !done && weekday == 0 && weeknumber == 0 && yearday == 0 ) {
    // Easy case: date is given, not restrictions by week or yearday
    uint mstart = ( month > 0 ) ? month : 1;
    uint mend = ( month <= 0 ) ? 12 : month;
    for ( uint m = mstart; m <= mend; ++m ) {
      uint dstart, dend;
      if ( day > 0 ) {
        dstart = dend = day;
      } else if ( day < 0 ) {
        QDate date( year, month, 1 );
        dstart = dend = date.daysInMonth() + day + 1;
      } else {
        QDate date( year, month, 1 );
        dstart = 1;
        dend = date.daysInMonth();
      }
      uint d = dstart;
      for ( QDate dt( year, m, dstart ); ; dt = dt.addDays( 1 ) ) {
        appendDateTime( dt, tm, result );
        if ( ++d > dend ) {
          break;
        }
      }
    }
    done = true;
  }

  // Else: At least one of the week / yearday restrictions was given...
  // If we have a yearday (and of course a year), we know the exact date
  if ( !done && yearday != 0 ) {
    // yearday < 0 means from end of year, so we'll need Jan 1 of the next year
    QDate d( year + ( ( yearday > 0 ) ? 0 : 1 ), 1, 1 );
    d = d.addDays( yearday - ( ( yearday > 0 ) ? 1 : 0 ) );
    appendDateTime( d, tm, result );
    done = true;
  }

  // Else: If we have a weeknumber, we have at most 7 possible dates, loop through them
  if ( !done && weeknumber != 0 ) {
    QDate wst( DateHelper::getNthWeek( year, weeknumber, weekstart ) );
    if ( weekday != 0 ) {
      wst = wst.addDays( ( 7 + weekday - weekstart ) % 7 );
      appendDateTime( wst, tm, result );
    } else {
      for ( int i = 0; i < 7; ++i ) {
        appendDateTime( wst, tm, result );
        wst = wst.addDays( 1 );
      }
    }
    done = true;
  }

  // weekday is given
  if ( !done && weekday != 0 ) {
    QDate dt( year, 1, 1 );
    // If type == yearly and month is given, pos is still in month not year!
    // TODO_Recurrence: Correct handling of n-th  BYDAY...
    int maxloop = 53;
    bool inMonth = ( type == RecurrenceRule::rMonthly ) ||
                   ( type == RecurrenceRule::rYearly && month > 0 );
    if ( inMonth && month > 0 ) {
      dt = QDate( year, month, 1 );
      maxloop = 5;
    }
    if ( weekdaynr < 0 ) {
      // From end of period (month, year) => relative to begin of next period
      if ( inMonth ) {
        dt = dt.addMonths( 1 );
      } else {
        dt = dt.addYears( 1 );
      }
    }
    int adj = ( 7 + weekday - dt.dayOfWeek() ) % 7;
    dt = dt.addDays( adj ); // correct first weekday of the period

    if ( weekdaynr > 0 ) {
      dt = dt.addDays( ( weekdaynr - 1 ) * 7 );
      appendDateTime( dt, tm, result );
    } else if ( weekdaynr < 0 ) {
      dt = dt.addDays( weekdaynr * 7 );
      appendDateTime( dt, tm, result );
    } else {
      // loop through all possible weeks, non-matching will be filtered later
      for ( int i = 0; i < maxloop; ++i ) {
        appendDateTime( dt, tm, result );
        dt = dt.addDays( 7 );
      }
    }
  } // weekday != 0

  // Only use those times that really match all other constraints, too
  QList<KDateTime> valid;
  for ( int i = 0, iend = result.count();  i < iend;  ++i ) {
    if ( matches( result[i], type ) ) {
      valid.append( result[i] );
    }
  }
  // Don't sort it here, would be unnecessary work. The results from all
  // constraints will be merged to one big list of the interval. Sort that one!
  return valid;
}

void Constraint::appendDateTime( const QDate &date, const QTime &time,
                                 QList<KDateTime> &list ) const
{
  KDateTime dt( date, time, timespec );
  if ( dt.isValid() ) {
    if ( secondOccurrence ) {
      dt.setSecondOccurrence( true );
    }
    list.append( dt );
  }
}

bool Constraint::increase( RecurrenceRule::PeriodType type, int freq )
{
  // convert the first day of the interval to KDateTime
  intervalDateTime( type );

  // Now add the intervals
  switch ( type ) {
    case RecurrenceRule::rSecondly:
      cachedDt = cachedDt.addSecs( freq );
      break;
    case RecurrenceRule::rMinutely:
      cachedDt = cachedDt.addSecs( 60 * freq );
      break;
    case RecurrenceRule::rHourly:
      cachedDt = cachedDt.addSecs( 3600 * freq );
      break;
    case RecurrenceRule::rDaily:
      cachedDt = cachedDt.addDays( freq );
      break;
    case RecurrenceRule::rWeekly:
      cachedDt = cachedDt.addDays( 7 * freq );
      break;
    case RecurrenceRule::rMonthly:
      cachedDt = cachedDt.addMonths( freq );
      break;
    case RecurrenceRule::rYearly:
      cachedDt = cachedDt.addYears( freq );
      break;
    default:
      break;
  }
  // Convert back from KDateTime to the Constraint class
  readDateTime( cachedDt, type );
  useCachedDt = true;   // readDateTime() resets this

  return true;
}

// Set the constraint's value appropriate to 'type', to the value contained in a date/time.
bool Constraint::readDateTime( const KDateTime &dt, RecurrenceRule::PeriodType type )
{
  switch ( type ) {
    // Really fall through! Only weekly needs to be treated differently!
  case RecurrenceRule::rSecondly:
    second = dt.time().second();
  case RecurrenceRule::rMinutely:
    minute = dt.time().minute();
  case RecurrenceRule::rHourly:
    hour = dt.time().hour();
    secondOccurrence = dt.isSecondOccurrence();
  case RecurrenceRule::rDaily:
    day = dt.date().day();
  case RecurrenceRule::rMonthly:
    month = dt.date().month();
  case RecurrenceRule::rYearly:
    year = dt.date().year();
    break;
  case RecurrenceRule::rWeekly:
    // Determine start day of the current week, calculate the week number from that
    weeknumber = DateHelper::getWeekNumber( dt.date(), weekstart, &year );
    break;
  default:
    break;
  }
  useCachedDt = false;
  return true;
}
//@endcond

/**************************************************************************
 *                        RecurrenceRule::Private                         *
 **************************************************************************/

//@cond PRIVATE
class KCal::RecurrenceRule::Private
{
  public:
    Private( RecurrenceRule *parent )
      : mParent( parent ),
        mPeriod( rNone ),
        mFrequency( 0 ),
        mWeekStart( 1 ),
        mIsReadOnly( false ),
        mAllDay( false )
    {}

    Private( RecurrenceRule *parent, const Private &p );

    Private &operator=( const Private &other );
    bool operator==( const Private &other ) const;
    void clear();
    void setDirty();
    void buildConstraints();
    bool buildCache() const;
    Constraint getNextValidDateInterval( const KDateTime &preDate, PeriodType type ) const;
    Constraint getPreviousValidDateInterval( const KDateTime &afterDate, PeriodType type ) const;
    DateTimeList datesForInterval( const Constraint &interval, PeriodType type ) const;

    RecurrenceRule *mParent;
    QString mRRule;            // RRULE string
    PeriodType mPeriod;
    KDateTime mDateStart;      // start of recurrence (but mDateStart is not an occurrence
                               // unless it matches the rule)
    uint mFrequency;
    int mDuration;
    KDateTime mDateEnd;

    QList<int> mBySeconds;     // values: second 0-59
    QList<int> mByMinutes;     // values: minute 0-59
    QList<int> mByHours;       // values: hour 0-23

    QList<WDayPos> mByDays;   // n-th weekday of the month or year
    QList<int> mByMonthDays;   // values: day -31 to -1 and 1-31
    QList<int> mByYearDays;    // values: day -366 to -1 and 1-366
    QList<int> mByWeekNumbers; // values: week -53 to -1 and 1-53
    QList<int> mByMonths;      // values: month 1-12
    QList<int> mBySetPos;      // values: position -366 to -1 and 1-366
    short mWeekStart;               // first day of the week (1=Monday, 7=Sunday)

    Constraint::List mConstraints;
    QList<RuleObserver*> mObservers;

    // Cache for duration
    mutable DateTimeList mCachedDates;
    mutable KDateTime mCachedDateEnd;
    mutable KDateTime mCachedLastDate;   // when mCachedDateEnd invalid, last date checked
    mutable bool mCached;

    bool mIsReadOnly;
    bool mAllDay;
    bool mNoByRules;        // no BySeconds, ByMinutes, ... rules exist
    uint mTimedRepetition;  // repeats at a regular number of seconds interval, or 0
};

RecurrenceRule::Private::Private( RecurrenceRule *parent, const Private &p )
  : mParent( parent ),
    mRRule( p.mRRule ),
    mPeriod( p.mPeriod ),
    mDateStart( p.mDateStart ),
    mFrequency( p.mFrequency ),
    mDuration( p.mDuration ),
    mDateEnd( p.mDateEnd ),

    mBySeconds( p.mBySeconds ),
    mByMinutes( p.mByMinutes ),
    mByHours( p.mByHours ),
    mByDays( p.mByDays ),
    mByMonthDays( p.mByMonthDays ),
    mByYearDays( p.mByYearDays ),
    mByWeekNumbers( p.mByWeekNumbers ),
    mByMonths( p.mByMonths ),
    mBySetPos( p.mBySetPos ),
    mWeekStart( p.mWeekStart ),

    mIsReadOnly( p.mIsReadOnly ),
    mAllDay( p.mAllDay )
{
    setDirty();
}

RecurrenceRule::Private &RecurrenceRule::Private::operator=( const Private &p )
{
  // check for self assignment
  if ( &p == this ) {
    return *this;
  }

  mRRule = p.mRRule;
  mPeriod = p.mPeriod;
  mDateStart = p.mDateStart;
  mFrequency = p.mFrequency;
  mDuration = p.mDuration;
  mDateEnd = p.mDateEnd;

  mBySeconds = p.mBySeconds;
  mByMinutes = p.mByMinutes;
  mByHours = p.mByHours;
  mByDays = p.mByDays;
  mByMonthDays = p.mByMonthDays;
  mByYearDays = p.mByYearDays;
  mByWeekNumbers = p.mByWeekNumbers;
  mByMonths = p.mByMonths;
  mBySetPos = p.mBySetPos;
  mWeekStart = p.mWeekStart;

  mIsReadOnly = p.mIsReadOnly;
  mAllDay = p.mAllDay;

  setDirty();

  return *this;
}

bool RecurrenceRule::Private::operator==( const Private &r ) const
{
  return
    mPeriod == r.mPeriod &&
    mDateStart == r.mDateStart &&
    mDuration == r.mDuration &&
    mDateEnd == r.mDateEnd &&
    mFrequency == r.mFrequency &&
    mIsReadOnly == r.mIsReadOnly &&
    mAllDay == r.mAllDay &&
    mBySeconds == r.mBySeconds &&
    mByMinutes == r.mByMinutes &&
    mByHours == r.mByHours &&
    mByDays == r.mByDays &&
    mByMonthDays == r.mByMonthDays &&
    mByYearDays == r.mByYearDays &&
    mByWeekNumbers == r.mByWeekNumbers &&
    mByMonths == r.mByMonths &&
    mBySetPos == r.mBySetPos &&
    mWeekStart == r.mWeekStart;
}

void RecurrenceRule::Private::clear()
{
  if ( mIsReadOnly ) {
    return;
  }
  mPeriod = rNone;
  mBySeconds.clear();
  mByMinutes.clear();
  mByHours.clear();
  mByDays.clear();
  mByMonthDays.clear();
  mByYearDays.clear();
  mByWeekNumbers.clear();
  mByMonths.clear();
  mBySetPos.clear();
  mWeekStart = 1;

  setDirty();
}

void RecurrenceRule::Private::setDirty()
{
  buildConstraints();
  mCached = false;
  mCachedDates.clear();
  for ( int i = 0, iend = mObservers.count();  i < iend;  ++i ) {
    if ( mObservers[i] ) {
      mObservers[i]->recurrenceChanged( mParent );
    }
  }
}
//@endcond

/**************************************************************************
 *                              RecurrenceRule                            *
 **************************************************************************/

RecurrenceRule::RecurrenceRule()
  : d( new Private( this ) )
{
}

RecurrenceRule::RecurrenceRule( const RecurrenceRule &r )
  : d( new Private( this, *r.d ) )
{
}

RecurrenceRule::~RecurrenceRule()
{
  delete d;
}

bool RecurrenceRule::operator==( const RecurrenceRule &r ) const
{
  return *d == *r.d;
}

RecurrenceRule &RecurrenceRule::operator=( const RecurrenceRule &r )
{
  // check for self assignment
  if ( &r == this ) {
    return *this;
  }

  *d = *r.d;

  return *this;
}

void RecurrenceRule::addObserver( RuleObserver *observer )
{
  if ( !d->mObservers.contains( observer ) ) {
    d->mObservers.append( observer );
  }
}

void RecurrenceRule::removeObserver( RuleObserver *observer )
{
  if ( d->mObservers.contains( observer ) ) {
    d->mObservers.removeAll( observer );
  }
}

void RecurrenceRule::setRecurrenceType( PeriodType period )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mPeriod = period;
  d->setDirty();
}

KDateTime RecurrenceRule::endDt( bool *result ) const
{
  if ( result ) {
    *result = false;
  }
  if ( d->mPeriod == rNone ) {
    return KDateTime();
  }
  if ( d->mDuration < 0 ) {
    return KDateTime();
  }
  if ( d->mDuration == 0 ) {
    if ( result ) {
      *result = true;
    }
    return d->mDateEnd;
  }

  // N occurrences. Check if we have a full cache. If so, return the cached end date.
  if ( !d->mCached ) {
    // If not enough occurrences can be found (i.e. inconsistent constraints)
    if ( !d->buildCache() ) {
      return KDateTime();
    }
  }
  if ( result ) {
    *result = true;
  }
  return d->mCachedDateEnd;
}

void RecurrenceRule::setEndDt( const KDateTime &dateTime )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mDateEnd = dateTime;
  d->mDuration = 0; // set to 0 because there is an end date/time
  d->setDirty();
}

void RecurrenceRule::setDuration( int duration )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mDuration = duration;
  d->setDirty();
}

void RecurrenceRule::setAllDay( bool allDay )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mAllDay = allDay;
  d->setDirty();
}

void RecurrenceRule::clear()
{
  d->clear();
}

void RecurrenceRule::setDirty()
{
  d->setDirty();
}

void RecurrenceRule::setStartDt( const KDateTime &start )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mDateStart = start;
  d->setDirty();
}

void RecurrenceRule::setFrequency( int freq )
{
  if ( isReadOnly() || freq <= 0 ) {
    return;
  }
  d->mFrequency = freq;
  d->setDirty();
}

void RecurrenceRule::setBySeconds( const QList<int> bySeconds )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mBySeconds = bySeconds;
  d->setDirty();
}

void RecurrenceRule::setByMinutes( const QList<int> byMinutes )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByMinutes = byMinutes;
  d->setDirty();
}

void RecurrenceRule::setByHours( const QList<int> byHours )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByHours = byHours;
  d->setDirty();
}

void RecurrenceRule::setByDays( const QList<WDayPos> byDays )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByDays = byDays;
  d->setDirty();
}

void RecurrenceRule::setByMonthDays( const QList<int> byMonthDays )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByMonthDays = byMonthDays;
  d->setDirty();
}

void RecurrenceRule::setByYearDays( const QList<int> byYearDays )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByYearDays = byYearDays;
  d->setDirty();
}

void RecurrenceRule::setByWeekNumbers( const QList<int> byWeekNumbers )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByWeekNumbers = byWeekNumbers;
  d->setDirty();
}

void RecurrenceRule::setByMonths( const QList<int> byMonths )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mByMonths = byMonths;
  d->setDirty();
}

void RecurrenceRule::setBySetPos( const QList<int> bySetPos )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mBySetPos = bySetPos;
  d->setDirty();
}

void RecurrenceRule::setWeekStart( short weekStart )
{
  if ( isReadOnly() ) {
    return;
  }
  d->mWeekStart = weekStart;
  d->setDirty();
}

void RecurrenceRule::shiftTimes( const KDateTime::Spec &oldSpec, const KDateTime::Spec &newSpec )
{
  d->mDateStart = d->mDateStart.toTimeSpec( oldSpec );
  d->mDateStart.setTimeSpec( newSpec );
  if ( d->mDuration == 0 ) {
    d->mDateEnd = d->mDateEnd.toTimeSpec( oldSpec );
    d->mDateEnd.setTimeSpec( newSpec );
  }
  d->setDirty();
}

// Taken from recurrence.cpp
// int RecurrenceRule::maxIterations() const
// {
//   /* Find the maximum number of iterations which may be needed to reach the
//    * next actual occurrence of a monthly or yearly recurrence.
//    * More than one iteration may be needed if, for example, it's the 29th February,
//    * the 31st day of the month or the 5th Monday, and the month being checked is
//    * February or a 30-day month.
//    * The following recurrences may never occur:
//    * - For rMonthlyDay: if the frequency is a whole number of years.
//    * - For rMonthlyPos: if the frequency is an even whole number of years.
//    * - For rYearlyDay, rYearlyMonth: if the frequeny is a multiple of 4 years.
//    * - For rYearlyPos: if the frequency is an even number of years.
//    * The maximum number of iterations needed, assuming that it does actually occur,
//    * was found empirically.
//    */
//   switch (recurs) {
//     case rMonthlyDay:
//       return (rFreq % 12) ? 6 : 8;
//
//     case rMonthlyPos:
//       if (rFreq % 12 == 0) {
//         // Some of these frequencies may never occur
//         return (rFreq % 84 == 0) ? 364         // frequency = multiple of 7 years
//              : (rFreq % 48 == 0) ? 7           // frequency = multiple of 4 years
//              : (rFreq % 24 == 0) ? 14 : 28;    // frequency = multiple of 2 or 1 year
//       }
//       // All other frequencies will occur sometime
//       if (rFreq > 120)
//         return 364;    // frequencies of > 10 years will hit the date limit first
//       switch (rFreq) {
//         case 23:   return 50;
//         case 46:   return 38;
//         case 56:   return 138;
//         case 66:   return 36;
//         case 89:   return 54;
//         case 112:  return 253;
//         default:   return 25;       // most frequencies will need < 25 iterations
//       }
//
//     case rYearlyMonth:
//     case rYearlyDay:
//       return 8;          // only 29th Feb or day 366 will need more than one iteration
//
//     case rYearlyPos:
//       if (rFreq % 7 == 0)
//         return 364;    // frequencies of a multiple of 7 years will hit the date limit first
//       if (rFreq % 2 == 0) {
//         // Some of these frequencies may never occur
//         return (rFreq % 4 == 0) ? 7 : 14;    // frequency = even number of years
//       }
//       return 28;
//   }
//   return 1;
// }

//@cond PRIVATE
void RecurrenceRule::Private::buildConstraints()
{
  mTimedRepetition = 0;
  mNoByRules = mBySetPos.isEmpty();
  mConstraints.clear();
  Constraint con( mDateStart.timeSpec() );
  if ( mWeekStart > 0 ) {
    con.setWeekstart( mWeekStart );
  }
  mConstraints.append( con );

  int c, cend;
  int i, iend;
  Constraint::List tmp;

  #define intConstraint( list, setElement ) \
  if ( !list.isEmpty() ) { \
    mNoByRules = false; \
    iend = list.count(); \
    if ( iend == 1 ) { \
      for ( c = 0, cend = mConstraints.count();  c < cend;  ++c ) { \
        mConstraints[c].setElement( list[0] ); \
      } \
    } else { \
      for ( c = 0, cend = mConstraints.count();  c < cend;  ++c ) { \
        for ( i = 0;  i < iend;  ++i ) { \
          con = mConstraints[c]; \
          con.setElement( list[i] ); \
          tmp.append( con ); \
        } \
      } \
      mConstraints = tmp; \
      tmp.clear(); \
    } \
  }

  intConstraint( mBySeconds, setSecond );
  intConstraint( mByMinutes, setMinute );
  intConstraint( mByHours, setHour );
  intConstraint( mByMonthDays, setDay );
  intConstraint( mByMonths, setMonth );
  intConstraint( mByYearDays, setYearday );
  intConstraint( mByWeekNumbers, setWeeknumber );
  #undef intConstraint

  if ( !mByDays.isEmpty() ) {
    mNoByRules = false;
    for ( c = 0, cend = mConstraints.count();  c < cend;  ++c ) {
      for ( i = 0, iend = mByDays.count();  i < iend;  ++i ) {
        con = mConstraints[c];
        con.setWeekday( mByDays[i].day() );
        con.setWeekdaynr( mByDays[i].pos() );
        tmp.append( con );
      }
    }
    mConstraints = tmp;
    tmp.clear();
  }

  #define fixConstraint( setElement, value ) \
  { \
    for ( c = 0, cend = mConstraints.count();  c < cend;  ++c ) { \
      mConstraints[c].setElement( value );                        \
    } \
  }
  // Now determine missing values from DTSTART. This can speed up things,
  // because we have more restrictions and save some loops.

  // TODO: Does RFC 2445 intend to restrict the weekday in all cases of weekly?
  if ( mPeriod == rWeekly && mByDays.isEmpty() ) {
    fixConstraint( setWeekday, mDateStart.date().dayOfWeek() );
  }

  // Really fall through in the cases, because all smaller time intervals are
  // constrained from dtstart
  switch ( mPeriod ) {
  case rYearly:
    if ( mByDays.isEmpty() && mByWeekNumbers.isEmpty() &&
         mByYearDays.isEmpty() && mByMonths.isEmpty() ) {
      fixConstraint( setMonth, mDateStart.date().month() );
    }
  case rMonthly:
    if ( mByDays.isEmpty() && mByWeekNumbers.isEmpty() &&
         mByYearDays.isEmpty() && mByMonthDays.isEmpty() ) {
      fixConstraint( setDay, mDateStart.date().day() );
    }
  case rWeekly:
  case rDaily:
    if ( mByHours.isEmpty() ) {
      fixConstraint( setHour, mDateStart.time().hour() );
    }
  case rHourly:
    if ( mByMinutes.isEmpty() ) {
      fixConstraint( setMinute, mDateStart.time().minute() );
    }
  case rMinutely:
    if ( mBySeconds.isEmpty() ) {
      fixConstraint( setSecond, mDateStart.time().second() );
    }
  case rSecondly:
  default:
    break;
  }
  #undef fixConstraint

  if ( mNoByRules ) {
    switch ( mPeriod ) {
      case rHourly:
        mTimedRepetition = mFrequency * 3600;
        break;
      case rMinutely:
        mTimedRepetition = mFrequency * 60;
        break;
      case rSecondly:
        mTimedRepetition = mFrequency;
        break;
      default:
        break;
    }
  } else {
    for ( c = 0, cend = mConstraints.count(); c < cend; ) {
      if ( mConstraints[c].isConsistent( mPeriod ) ) {
        ++c;
      } else {
        mConstraints.removeAt( c );
        --cend;
      }
    }
  }
}

// Build and cache a list of all occurrences.
// Only call buildCache() if mDuration > 0.
bool RecurrenceRule::Private::buildCache() const
{
  // Build the list of all occurrences of this event (we need that to determine
  // the end date!)
  Constraint interval( getNextValidDateInterval( mDateStart, mPeriod ) );
  QDateTime next;

  DateTimeList dts = datesForInterval( interval, mPeriod );
  // Only use dates after the event has started (start date is only included
  // if it matches)
  int i = dts.findLT( mDateStart );
  if ( i >= 0 ) {
    dts.erase( dts.begin(), dts.begin() + i + 1 );
  }

  int loopnr = 0;
  int dtnr = dts.count();
  // some validity checks to avoid infinite loops (i.e. if we have
  // done this loop already 10000 times, bail out )
  while ( loopnr < LOOP_LIMIT && dtnr < mDuration ) {
    interval.increase( mPeriod, mFrequency );
    // The returned date list is already sorted!
    dts += datesForInterval( interval, mPeriod );
    dtnr = dts.count();
    ++loopnr;
  }
  if ( dts.count() > mDuration ) {
    // we have picked up more occurrences than necessary, remove them
    dts.erase( dts.begin() + mDuration, dts.end() );
  }
  mCached = true;
  mCachedDates = dts;

// it = dts.begin();
// while ( it != dts.end() ) {
//   kDebug() << "            -=>" << dumpTime(*it);
//   ++it;
// }
  if ( int( dts.count() ) == mDuration ) {
    mCachedDateEnd = dts.last();
    return true;
  } else {
    // The cached date list is incomplete
    mCachedDateEnd = KDateTime();
    mCachedLastDate = interval.intervalDateTime( mPeriod );
    return false;
  }
}
//@endcond

bool RecurrenceRule::dateMatchesRules( const KDateTime &kdt ) const
{
  KDateTime dt = kdt.toTimeSpec( d->mDateStart.timeSpec() );
  for ( int i = 0, iend = d->mConstraints.count();  i < iend;  ++i ) {
    if ( d->mConstraints[i].matches( dt, recurrenceType() ) ) {
      return true;
    }
  }
  return false;
}

bool RecurrenceRule::recursOn( const QDate &qd, const KDateTime::Spec &timeSpec ) const
{
  int i, iend;
  if ( allDay() ) {
    // It's a date-only rule, so it has no time specification.
    // Therefore ignore 'timeSpec'.
    if ( qd < d->mDateStart.date() ) {
      return false;
    }
    // Start date is only included if it really matches
    QDate endDate;
    if ( d->mDuration >= 0 ) {
      endDate =  endDt().date();
      if ( qd > endDate ) {
        return false;
      }
    }

    // The date must be in an appropriate interval (getNextValidDateInterval),
    // Plus it must match at least one of the constraints
    bool match = false;
    for ( i = 0, iend = d->mConstraints.count();  i < iend && !match;  ++i ) {
      match = d->mConstraints[i].matches( qd, recurrenceType() );
    }
    if ( !match ) {
      return false;
    }

    KDateTime start( qd, QTime( 0, 0, 0 ), d->mDateStart.timeSpec() );
    Constraint interval( d->getNextValidDateInterval( start, recurrenceType() ) );
    // Constraint::matches is quite efficient, so first check if it can occur at
    // all before we calculate all actual dates.
    if ( !interval.matches( qd, recurrenceType() ) ) {
      return false;
    }
    // We really need to obtain the list of dates in this interval, since
    // otherwise BYSETPOS will not work (i.e. the date will match the interval,
    // but BYSETPOS selects only one of these matching dates!
    KDateTime end = start.addDays(1);
    do {
      DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
      for ( i = 0, iend = dts.count();  i < iend;  ++i ) {
        if ( dts[i].date() >= qd ) {
          return dts[i].date() == qd;
        }
      }
      interval.increase( recurrenceType(), frequency() );
    } while ( interval.intervalDateTime( recurrenceType() ) < end );
    return false;
  }

  // It's a date-time rule, so we need to take the time specification into account.
  KDateTime start( qd, QTime( 0, 0, 0 ), timeSpec );
  KDateTime end = start.addDays( 1 ).toTimeSpec( d->mDateStart.timeSpec() );
  start = start.toTimeSpec( d->mDateStart.timeSpec() );
  if ( end < d->mDateStart ) {
    return false;
  }
  if ( start < d->mDateStart ) {
    start = d->mDateStart;
  }

  // Start date is only included if it really matches
  if ( d->mDuration >= 0 ) {
    KDateTime endRecur = endDt();
    if ( endRecur.isValid() ) {
      if ( start > endRecur ) {
        return false;
      }
      if ( end > endRecur ) {
        end = endRecur;    // limit end-of-day time to end of recurrence rule
      }
    }
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    int n = static_cast<int>( ( d->mDateStart.secsTo_long( start ) - 1 ) % d->mTimedRepetition );
    return start.addSecs( d->mTimedRepetition - n ) < end;
  }

  // Find the start and end dates in the time spec for the rule
  QDate startDay = start.date();
  QDate endDay = end.addSecs( -1 ).date();
  int dayCount = startDay.daysTo( endDay ) + 1;

  // The date must be in an appropriate interval (getNextValidDateInterval),
  // Plus it must match at least one of the constraints
  bool match = false;
  for ( i = 0, iend = d->mConstraints.count();  i < iend && !match;  ++i ) {
    match = d->mConstraints[i].matches( startDay, recurrenceType() );
    for ( int day = 1;  day < dayCount && !match;  ++day ) {
      match = d->mConstraints[i].matches( startDay.addDays( day ), recurrenceType() );
    }
  }
  if ( !match ) {
    return false;
  }

  Constraint interval( d->getNextValidDateInterval( start, recurrenceType() ) );
  // Constraint::matches is quite efficient, so first check if it can occur at
  // all before we calculate all actual dates.
  match = false;
  Constraint intervalm = interval;
  do {
    match = intervalm.matches( startDay, recurrenceType() );
    for ( int day = 1;  day < dayCount && !match;  ++day ) {
      match = intervalm.matches( startDay.addDays( day ), recurrenceType() );
    }
    if ( match ) {
      break;
    }
    intervalm.increase( recurrenceType(), frequency() );
  } while ( intervalm.intervalDateTime( recurrenceType() ) < end );
  if ( !match ) {
    return false;
  }

  // We really need to obtain the list of dates in this interval, since
  // otherwise BYSETPOS will not work (i.e. the date will match the interval,
  // but BYSETPOS selects only one of these matching dates!
  do {
    DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
    int i = dts.findGE( start );
    if ( i >= 0 ) {
      return dts[i] <= end;
    }
    interval.increase( recurrenceType(), frequency() );
  } while ( interval.intervalDateTime( recurrenceType() ) < end );

  return false;
}

bool RecurrenceRule::recursAt( const KDateTime &kdt ) const
{
  // Convert to the time spec used by this recurrence rule
  KDateTime dt( kdt.toTimeSpec( d->mDateStart.timeSpec() ) );

  if ( allDay() ) {
    return recursOn( dt.date(), dt.timeSpec() );
  }
  if ( dt < d->mDateStart ) {
    return false;
  }
  // Start date is only included if it really matches
  if ( d->mDuration >= 0 && dt > endDt() ) {
    return false;
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    return !( d->mDateStart.secsTo_long( dt ) % d->mTimedRepetition );
  }

  // The date must be in an appropriate interval (getNextValidDateInterval),
  // Plus it must match at least one of the constraints
  if ( !dateMatchesRules( dt ) ) {
    return false;
  }
  // if it recurs every interval, speed things up...
//   if ( d->mFrequency == 1 && d->mBySetPos.isEmpty() && d->mByDays.isEmpty() ) return true;
  Constraint interval( d->getNextValidDateInterval( dt, recurrenceType() ) );
  // TODO_Recurrence: Does this work with BySetPos???
  if ( interval.matches( dt, recurrenceType() ) ) {
    return true;
  }
  return false;
}

TimeList RecurrenceRule::recurTimesOn( const QDate &date, const KDateTime::Spec &timeSpec ) const
{
  TimeList lst;
  if ( allDay() ) {
    return lst;
  }
  KDateTime start( date, QTime( 0, 0, 0 ), timeSpec );
  KDateTime end = start.addDays( 1 ).addSecs( -1 );
  DateTimeList dts = timesInInterval( start, end );   // returns between start and end inclusive
  for ( int i = 0, iend = dts.count();  i < iend;  ++i ) {
    lst += dts[i].toTimeSpec( timeSpec ).time();
  }
  return lst;
}

int RecurrenceRule::durationTo( const KDateTime &dt ) const
{
  // Convert to the time spec used by this recurrence rule
  KDateTime toDate( dt.toTimeSpec( d->mDateStart.timeSpec() ) );
  // Easy cases:
  // either before start, or after all recurrences and we know their number
  if ( toDate < d->mDateStart ) {
    return 0;
  }
  // Start date is only included if it really matches
  if ( d->mDuration > 0 && toDate >= endDt() ) {
    return d->mDuration;
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    return static_cast<int>( d->mDateStart.secsTo_long( toDate ) / d->mTimedRepetition );
  }

  return timesInInterval( d->mDateStart, toDate ).count();
}

int RecurrenceRule::durationTo( const QDate &date ) const
{
  return durationTo( KDateTime( date, QTime( 23, 59, 59 ), d->mDateStart.timeSpec() ) );
}

KDateTime RecurrenceRule::getPreviousDate( const KDateTime &afterDate ) const
{
  // Convert to the time spec used by this recurrence rule
  KDateTime toDate( afterDate.toTimeSpec( d->mDateStart.timeSpec() ) );

  // Invalid starting point, or beyond end of recurrence
  if ( !toDate.isValid() || toDate < d->mDateStart ) {
    return KDateTime();
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    KDateTime prev = toDate;
    if ( d->mDuration >= 0 && endDt().isValid() && toDate > endDt() ) {
      prev = endDt().addSecs( 1 ).toTimeSpec( d->mDateStart.timeSpec() );
    }
    int n = static_cast<int>( ( d->mDateStart.secsTo_long( prev ) - 1 ) % d->mTimedRepetition );
    if ( n < 0 ) {
      return KDateTime();  // before recurrence start
    }
    prev = prev.addSecs( -n - 1 );
    return prev >= d->mDateStart ? prev : KDateTime();
  }

  // If we have a cache (duration given), use that
  if ( d->mDuration > 0 ) {
    if ( !d->mCached ) {
      d->buildCache();
    }
    int i = d->mCachedDates.findLT( toDate );
    if ( i >= 0 ) {
      return d->mCachedDates[i];
    }
    return KDateTime();
  }

  KDateTime prev = toDate;
  if ( d->mDuration >= 0 && endDt().isValid() && toDate > endDt() ) {
    prev = endDt().addSecs( 1 ).toTimeSpec( d->mDateStart.timeSpec() );
  }

  Constraint interval( d->getPreviousValidDateInterval( prev, recurrenceType() ) );
  DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
  int i = dts.findLT( prev );
  if ( i >= 0 ) {
    return ( dts[i] >= d->mDateStart ) ? dts[i] : KDateTime();
  }

  // Previous interval. As soon as we find an occurrence, we're done.
  while ( interval.intervalDateTime( recurrenceType() ) > d->mDateStart ) {
    interval.increase( recurrenceType(), -int( frequency() ) );
    // The returned date list is sorted
    DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
    // The list is sorted, so take the last one.
    if ( !dts.isEmpty() ) {
      prev = dts.last();
      if ( prev.isValid() && prev >= d->mDateStart ) {
        return prev;
      } else {
        return KDateTime();
      }
    }
  }
  return KDateTime();
}

KDateTime RecurrenceRule::getNextDate( const KDateTime &preDate ) const
{
  // Convert to the time spec used by this recurrence rule
  KDateTime fromDate( preDate.toTimeSpec( d->mDateStart.timeSpec() ) );
  // Beyond end of recurrence
  if ( d->mDuration >= 0 && endDt().isValid() && fromDate >= endDt() ) {
    return KDateTime();
  }

  // Start date is only included if it really matches
  if ( fromDate < d->mDateStart ) {
    fromDate = d->mDateStart.addSecs( -1 );
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    int n = static_cast<int>( ( d->mDateStart.secsTo_long( fromDate ) + 1 ) % d->mTimedRepetition );
    KDateTime next = fromDate.addSecs( d->mTimedRepetition - n + 1 );
    return d->mDuration < 0 || !endDt().isValid() || next <= endDt() ? next : KDateTime();
  }

  if ( d->mDuration > 0 ) {
    if ( !d->mCached ) {
      d->buildCache();
    }
    int i = d->mCachedDates.findGT( fromDate );
    if ( i >= 0 ) {
      return d->mCachedDates[i];
    }
  }

  KDateTime end = endDt();
  Constraint interval( d->getNextValidDateInterval( fromDate, recurrenceType() ) );
  DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
  int i = dts.findGT( fromDate );
  if ( i >= 0 ) {
    return ( d->mDuration < 0 || dts[i] <= end ) ? dts[i] : KDateTime();
  }
  interval.increase( recurrenceType(), frequency() );
  if ( d->mDuration >= 0 && interval.intervalDateTime( recurrenceType() ) > end ) {
    return KDateTime();
  }

  // Increase the interval. The first occurrence that we find is the result (if
  // if's before the end date).
  // TODO: some validity checks to avoid infinite loops for contradictory constraints
  int loop = 0;
  do {
    DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
    if ( dts.count() > 0 ) {
      KDateTime ret( dts[0] );
      if ( d->mDuration >= 0 && ret > end ) {
        return KDateTime();
      } else {
        return ret;
      }
    }
    interval.increase( recurrenceType(), frequency() );
  } while ( ++loop < LOOP_LIMIT &&
            ( d->mDuration < 0 || interval.intervalDateTime( recurrenceType() ) < end ) );
  return KDateTime();
}

DateTimeList RecurrenceRule::timesInInterval( const KDateTime &dtStart,
                                              const KDateTime &dtEnd ) const
{
  KDateTime start = dtStart.toTimeSpec( d->mDateStart.timeSpec() );
  KDateTime end = dtEnd.toTimeSpec( d->mDateStart.timeSpec() );
  DateTimeList result;
  if ( end < d->mDateStart ) {
    return result;    // before start of recurrence
  }
  KDateTime enddt = end;
  if ( d->mDuration >= 0 ) {
    KDateTime endRecur = endDt();
    if ( endRecur.isValid() ) {
      if ( start > endRecur ) {
        return result;    // beyond end of recurrence
      }
      if ( end > endRecur ) {
        enddt = endRecur;    // limit end time to end of recurrence rule
      }
    }
  }

  if ( d->mTimedRepetition ) {
    // It's a simple sub-daily recurrence with no constraints
    int n = static_cast<int>( ( d->mDateStart.secsTo_long( start ) - 1 ) % d->mTimedRepetition );
    KDateTime dt = start.addSecs( d->mTimedRepetition - n );
    if ( dt < enddt ) {
      n = static_cast<int>( ( dt.secsTo_long( enddt ) - 1 ) / d->mTimedRepetition ) + 1;
      // limit n by a sane value else we can "explode".
      n = qMin( n, LOOP_LIMIT );
      for ( int i = 0;  i < n;  dt = dt.addSecs( d->mTimedRepetition ), ++i ) {
        result += dt;
      }
    }
    return result;
  }

  KDateTime st = start;
  bool done = false;
  if ( d->mDuration > 0 ) {
    if ( !d->mCached ) {
      d->buildCache();
    }
    if ( d->mCachedDateEnd.isValid() && start > d->mCachedDateEnd ) {
      return result;    // beyond end of recurrence
    }
    int i = d->mCachedDates.findGE( start );
    if ( i >= 0 ) {
      int iend = d->mCachedDates.findGT( enddt, i );
      if ( iend < 0 ) {
        iend = d->mCachedDates.count();
      } else {
        done = true;
      }
      while ( i < iend ) {
        result += d->mCachedDates[i++];
      }
    }
    if ( d->mCachedDateEnd.isValid() ) {
      done = true;
    } else if ( !result.isEmpty() ) {
      result += KDateTime();    // indicate that the returned list is incomplete
      done = true;
    }
    if ( done ) {
      return result;
    }
    // We don't have any result yet, but we reached the end of the incomplete cache
    st = d->mCachedLastDate.addSecs( 1 );
  }

  Constraint interval( d->getNextValidDateInterval( st, recurrenceType() ) );
  int loop = 0;
  do {
    DateTimeList dts = d->datesForInterval( interval, recurrenceType() );
    int i = 0;
    int iend = dts.count();
    if ( loop == 0 ) {
      i = dts.findGE( st );
      if ( i < 0 ) {
        i = iend;
      }
    }
    int j = dts.findGT( enddt, i );
    if ( j >= 0 ) {
      iend = j;
      loop = LOOP_LIMIT;
    }
    while ( i < iend ) {
      result += dts[i++];
    }
    // Increase the interval.
    interval.increase( recurrenceType(), frequency() );
  } while ( ++loop < LOOP_LIMIT &&
            interval.intervalDateTime( recurrenceType() ) < end );
  return result;
}

//@cond PRIVATE
// Find the date/time of the occurrence at or before a date/time,
// for a given period type.
// Return a constraint whose value appropriate to 'type', is set to
// the value contained in the date/time.
Constraint RecurrenceRule::Private::getPreviousValidDateInterval( const KDateTime &dt,
                                                                  PeriodType type ) const
{
  long periods = 0;
  KDateTime start = mDateStart;
  KDateTime nextValid( start );
  int modifier = 1;
  KDateTime toDate( dt.toTimeSpec( start.timeSpec() ) );
  // for super-daily recurrences, don't care about the time part

  // Find the #intervals since the dtstart and round to the next multiple of
  // the frequency
  switch ( type ) {
    // Really fall through for sub-daily, since the calculations only differ
    // by the factor 60 and 60*60! Same for weekly and daily (factor 7)
  case rHourly:
    modifier *= 60;
  case rMinutely:
    modifier *= 60;
  case rSecondly:
    periods = static_cast<int>( start.secsTo_long( toDate ) / modifier );
    // round it down to the next lower multiple of frequency:
    if ( mFrequency > 0 ) {
      periods = ( periods / mFrequency ) * mFrequency;
    }
    nextValid = start.addSecs( modifier * periods );
    break;
  case rWeekly:
    toDate = toDate.addDays( -( 7 + toDate.date().dayOfWeek() - mWeekStart ) % 7 );
    start = start.addDays( -( 7 + start.date().dayOfWeek() - mWeekStart ) % 7 );
    modifier *= 7;
  case rDaily:
    periods = start.daysTo( toDate ) / modifier;
    // round it down to the next lower multiple of frequency:
    if ( mFrequency > 0 ) {
      periods = ( periods / mFrequency ) * mFrequency;
    }
    nextValid = start.addDays( modifier * periods );
    break;
  case rMonthly:
  {
    periods = 12 * ( toDate.date().year() - start.date().year() ) +
              ( toDate.date().month() - start.date().month() );
    // round it down to the next lower multiple of frequency:
    if ( mFrequency > 0 ) {
      periods = ( periods / mFrequency ) * mFrequency;
    }
    // set the day to the first day of the month, so we don't have problems
    // with non-existent days like Feb 30 or April 31
    start.setDate( QDate( start.date().year(), start.date().month(), 1 ) );
    nextValid.setDate( start.date().addMonths( periods ) );
    break; }
  case rYearly:
    periods = ( toDate.date().year() - start.date().year() );
    // round it down to the next lower multiple of frequency:
    if ( mFrequency > 0 ) {
      periods = ( periods / mFrequency ) * mFrequency;
    }
    nextValid.setDate( start.date().addYears( periods ) );
    break;
  default:
    break;
  }

  return Constraint( nextValid, type, mWeekStart );
}

// Find the date/time of the next occurrence at or after a date/time,
// for a given period type.
// Return a constraint whose value appropriate to 'type', is set to the
// value contained in the date/time.
Constraint RecurrenceRule::Private::getNextValidDateInterval( const KDateTime &dt,
                                                              PeriodType type ) const
{
  // TODO: Simplify this!
  long periods = 0;
  KDateTime start = mDateStart;
  KDateTime nextValid( start );
  int modifier = 1;
  KDateTime toDate( dt.toTimeSpec( start.timeSpec() ) );
  // for super-daily recurrences, don't care about the time part

  // Find the #intervals since the dtstart and round to the next multiple of
  // the frequency
  switch ( type ) {
    // Really fall through for sub-daily, since the calculations only differ
    // by the factor 60 and 60*60! Same for weekly and daily (factor 7)
  case rHourly:
    modifier *= 60;
  case rMinutely:
    modifier *= 60;
  case rSecondly:
    periods = static_cast<int>( start.secsTo_long( toDate ) / modifier );
    periods = qMax( 0L, periods );
    if ( periods > 0 && mFrequency > 0 ) {
      periods += ( mFrequency - 1 - ( ( periods - 1 ) % mFrequency ) );
    }
    nextValid = start.addSecs( modifier * periods );
    break;
  case rWeekly:
    // correct both start date and current date to start of week
    toDate = toDate.addDays( -( 7 + toDate.date().dayOfWeek() - mWeekStart ) % 7 );
    start = start.addDays( -( 7 + start.date().dayOfWeek() - mWeekStart ) % 7 );
    modifier *= 7;
  case rDaily:
    periods = start.daysTo( toDate ) / modifier;
    periods = qMax( 0L, periods );
    if ( periods > 0 && mFrequency > 0 ) {
      periods += ( mFrequency - 1 - ( ( periods - 1 ) % mFrequency ) );
    }
    nextValid = start.addDays( modifier * periods );
    break;
  case rMonthly:
  {
    periods = 12 * ( toDate.date().year() - start.date().year() ) +
              ( toDate.date().month() - start.date().month() );
    periods = qMax( 0L, periods );
    if ( periods > 0 && mFrequency > 0 ) {
      periods += ( mFrequency - 1 - ( ( periods - 1 ) % mFrequency ) );
    }
    // set the day to the first day of the month, so we don't have problems
    // with non-existent days like Feb 30 or April 31
    start.setDate( QDate( start.date().year(), start.date().month(), 1 ) );
    nextValid.setDate( start.date().addMonths( periods ) );
    break;
  }
  case rYearly:
    periods = ( toDate.date().year() - start.date().year() );
    periods = qMax( 0L, periods );
    if ( periods > 0 && mFrequency > 0 ) {
      periods += ( mFrequency - 1 - ( ( periods - 1 ) % mFrequency ) );
    }
    nextValid.setDate( start.date().addYears( periods ) );
    break;
  default:
    break;
  }

  return Constraint( nextValid, type, mWeekStart );
}

DateTimeList RecurrenceRule::Private::datesForInterval( const Constraint &interval,
                                                        PeriodType type ) const
{
  /* -) Loop through constraints,
     -) merge interval with each constraint
     -) if merged constraint is not consistent => ignore that constraint
     -) if complete => add that one date to the date list
     -) Loop through all missing fields => For each add the resulting
  */
  DateTimeList lst;
  for ( int i = 0, iend = mConstraints.count();  i < iend;  ++i ) {
    Constraint merged( interval );
    if ( merged.merge( mConstraints[i] ) ) {
      // If the information is incomplete, we can't use this constraint
      if ( merged.year > 0 && merged.hour >= 0 && merged.minute >= 0 && merged.second >= 0 ) {
        // We have a valid constraint, so get all datetimes that match it andd
        // append it to all date/times of this interval
        QList<KDateTime> lstnew = merged.dateTimes( type );
        lst += lstnew;
      }
    }
  }
  // Sort it so we can apply the BySetPos. Also some logic relies on this being sorted
  lst.sortUnique();

/*if ( lst.isEmpty() ) {
  kDebug() << "         No Dates in Interval";
} else {
  kDebug() << "         Dates:";
  for ( int i = 0, iend = lst.count();  i < iend;  ++i ) {
    kDebug()<< "              -)" << dumpTime(lst[i]);
  }
  kDebug() << "       ---------------------";
}*/
  if ( !mBySetPos.isEmpty() ) {
    DateTimeList tmplst = lst;
    lst.clear();
    for ( int i = 0, iend = mBySetPos.count();  i < iend;  ++i ) {
      int pos = mBySetPos[i];
      if ( pos > 0 ) {
        --pos;
      }
      if ( pos < 0 ) {
        pos += tmplst.count();
      }
      if ( pos >= 0 && pos < tmplst.count() ) {
        lst.append( tmplst[pos] );
      }
    }
    lst.sortUnique();
  }

  return lst;
}
//@endcond

void RecurrenceRule::dump() const
{
#ifndef NDEBUG
  kDebug();
  if ( !d->mRRule.isEmpty() ) {
    kDebug() << "   RRULE=" << d->mRRule;
  }
  kDebug() << "   Read-Only:" << isReadOnly();

  kDebug() << "   Period type:" << recurrenceType()
           << ", frequency:" << frequency();
  kDebug() << "   #occurrences:" << duration();
  kDebug() << "   start date:" << dumpTime( startDt() )
           << ", end date:" << dumpTime( endDt() );

#define dumpByIntList(list,label) \
  if ( !list.isEmpty() ) {\
    QStringList lst;\
    for ( int i = 0, iend = list.count();  i < iend;  ++i ) {\
      lst.append( QString::number( list[i] ) );\
    }\
    kDebug() << "  " << label << lst.join( ", " );\
  }
  dumpByIntList( d->mBySeconds, "BySeconds:  " );
  dumpByIntList( d->mByMinutes, "ByMinutes:  " );
  dumpByIntList( d->mByHours, "ByHours:    " );
  if ( !d->mByDays.isEmpty() ) {
    QStringList lst;
    for ( int i = 0, iend = d->mByDays.count();  i < iend;  ++i ) {\
      lst.append( ( d->mByDays[i].pos() ? QString::number( d->mByDays[i].pos() ) : "" ) +
                   DateHelper::dayName( d->mByDays[i].day() ) );
    }
    kDebug() << "   ByDays:    " << lst.join( ", " );
  }
  dumpByIntList( d->mByMonthDays, "ByMonthDays:" );
  dumpByIntList( d->mByYearDays, "ByYearDays: " );
  dumpByIntList( d->mByWeekNumbers, "ByWeekNr:   " );
  dumpByIntList( d->mByMonths, "ByMonths:   " );
  dumpByIntList( d->mBySetPos, "BySetPos:   " );
  #undef dumpByIntList

  kDebug() << "   Week start:" << DateHelper::dayName( d->mWeekStart );

  kDebug() << "   Constraints:";
  // dump constraints
  for ( int i = 0, iend = d->mConstraints.count();  i < iend;  ++i ) {
    d->mConstraints[i].dump();
  }
#endif
}

//@cond PRIVATE
void Constraint::dump() const
{
  kDebug() << "     ~> Y=" << year
           << ", M=" << month
           << ", D=" << day
           << ", H=" << hour
           << ", m=" << minute
           << ", S=" << second
           << ", wd=" << weekday
           << ",#wd=" << weekdaynr
           << ", #w=" << weeknumber
           << ", yd=" << yearday;
}
//@endcond

QString dumpTime( const KDateTime &dt )
{
#ifndef NDEBUG
  if ( !dt.isValid() ) {
    return QString();
  }
  QString result;
  if ( dt.isDateOnly() ) {
    result = dt.toString( "%a %Y-%m-%d %:Z" );
  } else {
    result = dt.toString( "%a %Y-%m-%d %H:%M:%S %:Z" );
    if ( dt.isSecondOccurrence() ) {
      result += QLatin1String( " (2nd)" );
    }
  }
  if ( dt.timeSpec() == KDateTime::Spec::ClockTime() ) {
    result += QLatin1String( "Clock" );
  }
  return result;
#else
  Q_UNUSED( dt );
  return QString();
#endif
}

KDateTime RecurrenceRule::startDt() const
{
  return d->mDateStart;
}

RecurrenceRule::PeriodType RecurrenceRule::recurrenceType() const
{
  return d->mPeriod;
}

uint RecurrenceRule::frequency() const
{
  return d->mFrequency;
}

int RecurrenceRule::duration() const
{
  return d->mDuration;
}

QString RecurrenceRule::rrule() const
{
  return d->mRRule;
}

void RecurrenceRule::setRRule( const QString &rrule )
{
  d->mRRule = rrule;
}

bool RecurrenceRule::isReadOnly() const
{
  return d->mIsReadOnly;
}

void RecurrenceRule::setReadOnly( bool readOnly )
{
  d->mIsReadOnly = readOnly;
}

bool RecurrenceRule::recurs() const
{
  return d->mPeriod != rNone;
}

bool RecurrenceRule::allDay() const
{
  return d->mAllDay;
}

const QList<int> &RecurrenceRule::bySeconds() const
{
  return d->mBySeconds;
}

const QList<int> &RecurrenceRule::byMinutes() const
{
  return d->mByMinutes;
}

const QList<int> &RecurrenceRule::byHours() const
{
  return d->mByHours;
}

const QList<RecurrenceRule::WDayPos> &RecurrenceRule::byDays() const
{
  return d->mByDays;
}

const QList<int> &RecurrenceRule::byMonthDays() const
{
  return d->mByMonthDays;
}

const QList<int> &RecurrenceRule::byYearDays() const
{
  return d->mByYearDays;
}

const QList<int> &RecurrenceRule::byWeekNumbers() const
{
  return d->mByWeekNumbers;
}

const QList<int> &RecurrenceRule::byMonths() const
{
  return d->mByMonths;
}

const QList<int> &RecurrenceRule::bySetPos() const
{
  return d->mBySetPos;
}

short RecurrenceRule::weekStart() const
{
  return d->mWeekStart;
}