model.cpp

Go to the documentation of this file.

/******************************************************************************
 *
 *  Copyright 2008 Szymon Tomasz Stefanek <pragma@kvirc.net>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program 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 General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 *******************************************************************************/

//
// This class is a rather huge monster. It's something that resembles a QAbstractItemModel
// (because it has to provide the interface for a QTreeView) but isn't entirely one
// (for optimization reasons). It basically manages a tree of items of two types:
// GroupHeaderItem and MessageItem. Be sure to read the docs for ViewItemJob.
//
// A huge credit here goes to Till Adam which seems to have written most
// (if not all) of the original KMail threading code. The KMHeaders implementation,
// the documentation and his clever ideas were my starting points and essential tools.
// This is why I'm adding his copyright entry (copied from headeritem.cpp) here even if
// he didn't write a byte in this file until now :)
//
//                                       Szymon Tomasz Stefanek, 03 Aug 2008 04:50 (am)
//
// This class contains ideas from:
//
//   kmheaders.cpp / kmheaders.h, headeritem.cpp / headeritem.h
//   Copyright: (c) 2004 Till Adam < adam at kde dot org >
//
#include <config-messagelist.h>
#include "core/model.h"
#include "core/model_p.h"
#include "core/view.h"
#include "core/filter.h"
#include "core/groupheaderitem.h"
#include "core/item_p.h"
#include "core/messageitem.h"
#include "core/modelinvariantrowmapper.h"
#include "core/storagemodelbase.h"
#include "core/theme.h"
#include "core/delegate.h"
#include "core/manager.h"
#include "core/messageitemsetmanager.h"
#include "core/messageitem.h"

#include <akonadi/item.h>
#include <akonadi/kmime/messagestatus.h>
#include "messagecore/utils/stringutil.h"

#include <QApplication>
#include <QTimer>
#include <QDateTime>
#include <QScrollBar>

#include <KLocalizedString>
#include <KCalendarSystem>
#include <KGlobal>
#include <KIcon>
#include <KDebug>

namespace MessageList
{

namespace Core
{

K_GLOBAL_STATIC( QTimer, _k_heartBeatTimer )


class ViewItemJob
{
    public:
    enum Pass
    {
        Pass1Fill    = 0,     
        Pass1Cleanup = 1,     
        Pass1Update  = 2,     
        Pass2        = 3,     
        Pass3        = 4,     
        Pass4        = 5,     
        Pass5        = 6,     
        LastIndex    = 7      
    };
    private:
    // Data for "View Fill" jobs
    int mStartIndex;        
    int mCurrentIndex;      
    int mEndIndex;          

    // Data for "View Cleanup" jobs
    QList< ModelInvariantIndex * > * mInvariantIndexList; 

    // Common data

    // The maximum time that we can spend "at once" inside viewItemJobStep() (milliseconds)
    // The bigger this value, the larger chunks of work we do at once and less the time
    // we loose in "breaking and resuming" the job. On the other side large values tend
    // to make the view less responsive up to a "freeze" perception if this value is larger
    // than 2000.
    int mChunkTimeout;

    // The interval between two fillView steps. The larger the interval, the more interactivity
    // we have. The shorter the interval the more work we get done per second.
    int mIdleInterval;

    // The minimum number of messages we process in every viewItemJobStep() call
    // The larger this value the less time we loose in checking the timeout every N messages.
    // On the other side, making this very large may make the view less responsive
    // if we're processing very few messages at a time and very high values (say > 10000) may
    // eventually make our job unbreakable until the end.
    int mMessageCheckCount;
    Pass mCurrentPass;

    // If this parameter is true then this job uses a "disconnected" UI.
    // It's FAR faster since we don't need to call beginInsertRows()/endInsertRows()
    // and we simply emit a layoutChanged() at the end. It can be done only as the first
    // job though: subsequent jobs can't use layoutChanged() as it looses the expanded
    // state of items.
    bool mDisconnectUI;
    public:
    ViewItemJob( int startIndex, int endIndex, int chunkTimeout, int idleInterval, int messageCheckCount, bool disconnectUI = false )
        : mStartIndex( startIndex ), mCurrentIndex( startIndex ), mEndIndex( endIndex ),
          mInvariantIndexList( 0 ),
          mChunkTimeout( chunkTimeout ), mIdleInterval( idleInterval ),
          mMessageCheckCount( messageCheckCount ), mCurrentPass( Pass1Fill ),
          mDisconnectUI( disconnectUI ) {}

    ViewItemJob( Pass pass, QList< ModelInvariantIndex * > * invariantIndexList, int chunkTimeout, int idleInterval, int messageCheckCount )
        : mStartIndex( 0 ), mCurrentIndex( 0 ), mEndIndex( invariantIndexList->count() - 1 ),
          mInvariantIndexList( invariantIndexList ),
          mChunkTimeout( chunkTimeout ), mIdleInterval( idleInterval ),
          mMessageCheckCount( messageCheckCount ), mCurrentPass( pass ),
          mDisconnectUI( false ) {}

    ~ViewItemJob()
    {
        delete mInvariantIndexList;
    }
    public:
    int startIndex() const
    { return mStartIndex; }
    void setStartIndex( int startIndex )
    { mStartIndex = startIndex; mCurrentIndex = startIndex; }
    int currentIndex() const
    { return mCurrentIndex; }
    void setCurrentIndex( int currentIndex )
    { mCurrentIndex = currentIndex; }
    int endIndex() const
    { return mEndIndex; }
    void setEndIndex( int endIndex )
    { mEndIndex = endIndex; }
    Pass currentPass() const
    { return mCurrentPass; }
    void setCurrentPass( Pass pass )
    { mCurrentPass = pass; }
    int idleInterval() const
    { return mIdleInterval; }
    int chunkTimeout() const
    { return mChunkTimeout; }
    int messageCheckCount() const
    { return mMessageCheckCount; }
    QList< ModelInvariantIndex * > * invariantIndexList() const
    { return mInvariantIndexList; }
    bool disconnectUI() const
    { return mDisconnectUI; }
};

} // namespace Core

} // namespace MessageList

using namespace MessageList::Core;

Model::Model( View *pParent )
    : QAbstractItemModel( pParent ), d( new ModelPrivate( this ) )
{
    d->mRecursionCounterForReset = 0;
    d->mStorageModel = 0;
    d->mView = pParent;
    d->mAggregation = 0;
    d->mTheme = 0;
    d->mSortOrder = 0;
    d->mFilter = 0;
    d->mPersistentSetManager = 0;
    d->mInLengthyJobBatch = false;
    d->mLastSelectedMessageInFolder = 0;
    d->mLoading = false;

    d->mRootItem = new Item( Item::InvisibleRoot );
    d->mRootItem->setViewable( 0, true );

    d->mFillStepTimer.setSingleShot( true );
    d->mInvariantRowMapper = new ModelInvariantRowMapper();
    d->mModelForItemFunctions= this;
    connect( &d->mFillStepTimer, SIGNAL(timeout()),
             SLOT(viewItemJobStep()) );

    d->mCachedTodayLabel = i18n( "Today" );
    d->mCachedYesterdayLabel = i18n( "Yesterday" );
    d->mCachedUnknownLabel = i18nc( "Unknown date",
                                    "Unknown" );
    d->mCachedLastWeekLabel = i18n( "Last Week" );
    d->mCachedTwoWeeksAgoLabel = i18n( "Two Weeks Ago" );
    d->mCachedThreeWeeksAgoLabel = i18n( "Three Weeks Ago" );
    d->mCachedFourWeeksAgoLabel = i18n( "Four Weeks Ago" );
    d->mCachedFiveWeeksAgoLabel = i18n( "Five Weeks Ago" );

    d->mCachedWatchedOrIgnoredStatusBits = Akonadi::MessageStatus::statusIgnored().toQInt32() | Akonadi::MessageStatus::statusWatched().toQInt32();


    connect( _k_heartBeatTimer, SIGNAL(timeout()),
             this, SLOT(checkIfDateChanged()) );

    if ( !_k_heartBeatTimer->isActive() ) { // First model starts it
        _k_heartBeatTimer->start( 60000 ); // 1 minute
    }
}

Model::~Model()
{
    setStorageModel( 0 );

    d->clearJobList();
    d->mOldestItem = 0;
    d->mNewestItem = 0;
    d->clearUnassignedMessageLists();
    d->clearOrphanChildrenHash();
    d->clearThreadingCacheMessageSubjectMD5ToMessageItem();
    delete d->mPersistentSetManager;
    // Delete the invariant row mapper before removing the items.
    // It's faster since the items will not need to call the invariant
    delete d->mInvariantRowMapper;
    delete d->mRootItem;

    delete d;
}

void Model::setAggregation( const Aggregation * aggregation )
{
    d->mAggregation = aggregation;
    d->mView->setRootIsDecorated( ( d->mAggregation->grouping() == Aggregation::NoGrouping ) &&
                                  ( d->mAggregation->threading() != Aggregation::NoThreading ) );
}

void Model::setTheme( const Theme * theme )
{
    d->mTheme = theme;
}

void Model::setSortOrder( const SortOrder * sortOrder )
{
    d->mSortOrder = sortOrder;
}

const SortOrder * Model::sortOrder() const
{
    return d->mSortOrder;
}

void Model::setFilter( const Filter *filter )
{
    d->mFilter = filter;

    if (d->mFilter)
        connect( d->mFilter, SIGNAL(finished()), this, SLOT(slotApplyFilter()) );

    d->slotApplyFilter();
}

void ModelPrivate::slotApplyFilter()
{
    QList< Item * > * childList = mRootItem->childItems();
    if ( !childList )
        return;

    QModelIndex idx; // invalid

    QApplication::setOverrideCursor( Qt::WaitCursor );
    QList< Item * >::ConstIterator end = childList->constEnd();
    for ( QList< Item * >::ConstIterator it = childList->constBegin(); it != end; ++it )
        applyFilterToSubtree( *it, idx );

    QApplication::restoreOverrideCursor();
}

bool ModelPrivate::applyFilterToSubtree( Item * item, const QModelIndex &parentIndex )
{
    // This function applies the current filter (eventually empty)
    // to a message tree starting at "item".

    if ( !mModelForItemFunctions ) {
        kWarning() << "Cannot apply filter, the UI must be not disconnected.";
        return true;
    }
    Q_ASSERT( item );                    // the item must obviously be valid
    Q_ASSERT( item->isViewable() );      // the item must be viewable

    // Apply to children first

    QList< Item * > * childList = item->childItems();

    bool childrenMatch = false;

    QModelIndex thisIndex = q->index( item, 0 );

    if ( childList )
    {
        QList< Item * >::ConstIterator end( childList->constEnd() );
        for ( QList< Item * >::ConstIterator it = childList->constBegin(); it != end; ++it )
        {
            if ( applyFilterToSubtree( *it, thisIndex ) )
                childrenMatch = true;
        }
    }

    if ( !mFilter ) // empty filter always matches (but does not expand items)
    {
        mView->setRowHidden( thisIndex.row(), parentIndex, false );
        return true;
    }

    if ( childrenMatch )
    {
        mView->setRowHidden( thisIndex.row(), parentIndex, false );

        if ( !mView->isExpanded( thisIndex ) )
            mView->expand( thisIndex );
        return true;
    }

    if ( item->type() == Item::Message )
    {
        if ( mFilter->match( ( MessageItem * )item ) )
        {
            mView->setRowHidden( thisIndex.row(), parentIndex, false );
            return true;
        }
    } // else this is a group header and it never explicitly matches

    // filter doesn't match, hide the item
    mView->setRowHidden( thisIndex.row(), parentIndex, true );

    return false;
}

int Model::columnCount( const QModelIndex & parent ) const
{
    if ( !d->mTheme )
        return 0;
    if ( parent.column() > 0 )
        return 0;
    return d->mTheme->columns().count();
}

QVariant Model::data( const QModelIndex & index, int role ) const
{

    Item* item = static_cast< Item* >( index.internalPointer() );

    switch( role ) {
    case Qt::UserRole + 1: //EntityTreeModel::ItemIdRole
        if( item->type() == MessageList::Core::Item::Message ) {
            MessageItem* mItem = static_cast<MessageItem*>( item );
            return QVariant::fromValue( mItem->akonadiItem().id() );
        } else
            return QVariant();
        break;
    case Qt::UserRole + 2: //EntityTreeModel::ItemRole
        if( item->type() == MessageList::Core::Item::Message ) {
            MessageItem* mItem = static_cast<MessageItem*>( item );
            return QVariant::fromValue( mItem->akonadiItem() );
        } else
            return QVariant();
        break;
    case Qt::UserRole + 3: //EntityTreeModel::MimeTypeRole
        if( item->type() == MessageList::Core::Item::Message )
            return QLatin1String( "message/rfc822" );
        else
            return QVariant();
        break;
    case Qt::AccessibleTextRole:
        if( item->type() == MessageList::Core::Item::Message ) {
            MessageItem* mItem = static_cast<MessageItem*>( item );
            return mItem->accessibleText( d->mTheme , index.column() );
        } else if ( item->type() == MessageList::Core::Item::GroupHeader ) {
            if ( index.column() > 0)
                return QString();
            GroupHeaderItem* hItem = static_cast<GroupHeaderItem*>( item );
            return hItem->label();
        }
        return QString();
        break;
    default:
        return QVariant();
    }
}

QVariant Model::headerData(int section, Qt::Orientation, int role) const
{
    if ( !d->mTheme )
        return QVariant();

    Theme::Column * column = d->mTheme->column( section );
    if ( !column )
        return QVariant();

    if ( d->mStorageModel && column->isSenderOrReceiver() &&
         ( role == Qt::DisplayRole ) )
    {
        if ( d->mStorageModelContainsOutboundMessages )
            return QVariant( i18n( "Receiver" ) );
        return QVariant( i18n( "Sender" ) );
    }

    const bool columnPixmapEmpty(column->pixmapName().isEmpty());
    if ( ( role == Qt::DisplayRole ) && columnPixmapEmpty )
        return QVariant( column->label() );
    else if ( ( role == Qt::ToolTipRole ) && !columnPixmapEmpty )
        return QVariant( column->label() );
    else if ( ( role == Qt::DecorationRole ) && !columnPixmapEmpty )
        return QVariant( KIcon( column->pixmapName() ) );

    return QVariant();
}

QModelIndex Model::index( Item *item, int column ) const
{
    if ( !d->mModelForItemFunctions )
        return QModelIndex(); // called with disconnected UI: the item isn't known on the Qt side, yet

    if ( !item ) {
        return QModelIndex();
    }
    // FIXME: This function is a bottleneck (the caching in indexOfChildItem only works 30% of the time)
    Item * par = item->parent();
    if ( !par )
    {
        if ( item != d->mRootItem )
            item->dump(QString());
        return QModelIndex();
    }

    const int index = par->indexOfChildItem(item);
    if ( index < 0 )
        return QModelIndex(); // BUG
    return createIndex(index, column, item);
}

QModelIndex Model::index( int row, int column, const QModelIndex &parent ) const
{
    if ( !d->mModelForItemFunctions )
        return QModelIndex(); // called with disconnected UI: the item isn't known on the Qt side, yet

#ifdef READD_THIS_IF_YOU_WANT_TO_PASS_MODEL_TEST
    if ( column < 0 )
        return QModelIndex(); // senseless column (we could optimize by skipping this check but ModelTest from trolltech is pedantic)
#endif

    const Item *item;
    if ( parent.isValid() )
    {
        item = static_cast< const Item * >( parent.internalPointer() );
        if ( !item )
            return QModelIndex(); // should never happen
    } else {
        item = d->mRootItem;
    }

    if ( parent.column() > 0 )
        return QModelIndex(); // parent column is not 0: shouldn't have children (as per Qt documentation)

    Item * child = item->childItem( row );
    if ( !child )
        return QModelIndex(); // no such row in parent
    return createIndex( row, column, child );
}

QModelIndex Model::parent( const QModelIndex &modelIndex ) const
{
    Q_ASSERT( d->mModelForItemFunctions ); // should be never called with disconnected UI

    if ( !modelIndex.isValid() )
        return QModelIndex(); // should never happen
    Item *item = static_cast< Item * >( modelIndex.internalPointer() );
    if ( !item )
        return QModelIndex();
    Item *par = item->parent();
    if ( !par )
        return QModelIndex(); // should never happen
    //return index( par, modelIndex.column() );
    return index( par, 0 ); // parents are always in column 0 (as per Qt documentation)
}

int Model::rowCount( const QModelIndex &parent ) const
{
    if ( !d->mModelForItemFunctions )
        return 0; // called with disconnected UI

    const Item *item;
    if ( parent.isValid() )
    {
        item = static_cast< const Item * >( parent.internalPointer() );
        if ( !item )
            return 0; // should never happen
    } else {
        item = d->mRootItem;
    }

    if ( !item->isViewable() )
        return 0;

    return item->childItemCount();
}

class RecursionPreventer
{
public:
    RecursionPreventer( int &counter )
        : mCounter( counter ) { mCounter++; }
    ~RecursionPreventer() { mCounter--; }
    bool isRecursive() const { return mCounter > 1; }

private:
    int &mCounter;
};

StorageModel *Model::storageModel() const
{
    return d->mStorageModel;
}

void ModelPrivate::clear()
{
    if( mFillStepTimer.isActive() )
        mFillStepTimer.stop();

    // Kill pre-selection at this stage
    mPreSelectionMode = PreSelectNone;
    mLastSelectedMessageInFolder = 0;
    mOldestItem = 0;
    mNewestItem = 0;

    // Reset the row mapper before removing items
    // This is faster since the items don't need to access the mapper.
    mInvariantRowMapper->modelReset();

    clearJobList();
    clearUnassignedMessageLists();
    clearOrphanChildrenHash();
    mGroupHeaderItemHash.clear();
    mGroupHeadersThatNeedUpdate.clear();
    mThreadingCacheMessageIdMD5ToMessageItem.clear();
    mThreadingCacheMessageInReplyToIdMD5ToMessageItem.clear();
    clearThreadingCacheMessageSubjectMD5ToMessageItem();
    mViewItemJobStepChunkTimeout = 100;
    mViewItemJobStepIdleInterval = 10;
    mViewItemJobStepMessageCheckCount = 10;
    delete mPersistentSetManager;
    mPersistentSetManager = 0;
    mCurrentItemToRestoreAfterViewItemJobStep = 0;

    mTodayDate = QDate::currentDate();

    // FIXME: CLEAR THE FILTER HERE AS WE CAN'T APPLY IT WITH UI DISCONNECTED!


    mRootItem->killAllChildItems();

    q->reset();
    //emit headerDataChanged();

    mView->modelHasBeenReset();
    mView->selectionModel()->clearSelection();
}

void Model::setStorageModel( StorageModel *storageModel, PreSelectionMode preSelectionMode )
{
    // Prevent a case of recursion when opening a folder that has a message and the folder was
    // never opened before.
    RecursionPreventer preventer( d->mRecursionCounterForReset );
    if ( preventer.isRecursive() )
        return;

    d->clear();

    if ( d->mStorageModel ) {
        disconnect( d->mStorageModel, SIGNAL(rowsInserted(QModelIndex,int,int)),
                    this, SLOT(slotStorageModelRowsInserted(QModelIndex,int,int)) );
        disconnect( d->mStorageModel, SIGNAL(rowsRemoved(QModelIndex,int,int)),
                    this, SLOT(slotStorageModelRowsRemoved(QModelIndex,int,int)) );

        disconnect( d->mStorageModel, SIGNAL(layoutChanged()),
                    this, SLOT(slotStorageModelLayoutChanged()) );
        disconnect( d->mStorageModel, SIGNAL(modelReset()),
                    this, SLOT(slotStorageModelLayoutChanged()) );

        disconnect( d->mStorageModel, SIGNAL(dataChanged(QModelIndex,QModelIndex)),
                    this, SLOT(slotStorageModelDataChanged(QModelIndex,QModelIndex)) );
        disconnect( d->mStorageModel, SIGNAL(headerDataChanged(Qt::Orientation,int,int)),
                    this, SLOT(slotStorageModelHeaderDataChanged(Qt::Orientation,int,int)) );
    }

    d->mStorageModel = storageModel;

    if ( !d->mStorageModel )
        return; // no folder: nothing to fill

    // Sometimes the folders need to be resurrected...
    d->mStorageModel->prepareForScan();

    d->mPreSelectionMode = preSelectionMode;
    d->mStorageModelContainsOutboundMessages = d->mStorageModel->containsOutboundMessages();

    connect( d->mStorageModel, SIGNAL(rowsInserted(QModelIndex,int,int)),
             this, SLOT(slotStorageModelRowsInserted(QModelIndex,int,int)) );
    connect( d->mStorageModel, SIGNAL(rowsRemoved(QModelIndex,int,int)),
             this, SLOT(slotStorageModelRowsRemoved(QModelIndex,int,int)) );

    connect( d->mStorageModel, SIGNAL(layoutChanged()),
             this, SLOT(slotStorageModelLayoutChanged()) );
    connect( d->mStorageModel, SIGNAL(modelReset()),
             this, SLOT(slotStorageModelLayoutChanged()) );

    connect( d->mStorageModel, SIGNAL(dataChanged(QModelIndex,QModelIndex)),
             this, SLOT(slotStorageModelDataChanged(QModelIndex,QModelIndex)) );
    connect( d->mStorageModel, SIGNAL(headerDataChanged(Qt::Orientation,int,int)),
             this, SLOT(slotStorageModelHeaderDataChanged(Qt::Orientation,int,int)) );

    if ( d->mStorageModel->rowCount() == 0 )
        return; // folder empty: nothing to fill

    // Here we use different strategies based on user preference and the folder size.
    // The knobs we can tune are:
    //
    // - The number of jobs used to scan the whole folder and their order
    //
    //   There are basically two approaches to this. One is the "single big job"
    //   approach. It scans the folder from the beginning to the end in a single job
    //   entry. The job passes are done only once. It's advantage is that it's simplier
    //   and it's less likely to generate imperfect parent threadings. The bad
    //   side is that since the folders are "sort of" date ordered then the most interesting
    //   messages show up at the end of the work. Not nice for large folders.
    //   The other approach uses two jobs. This is a bit slower but smarter strategy.
    //   First we scan the latest 1000 messages and *then* take care of the older ones.
    //   This will show up the most interesting messages almost immediately. (Well...
    //   All this assuming that the underlying storage always appends the newly arrived messages)
    //   The strategy is slower since it  generates some imperfect parent threadings which must be
    //   adjusted by the second job. For instance, in my kernel mailing list folder this "smart" approach
    //   generates about 150 additional imperfectly threaded children... but the "today"
    //   messages show up almost immediately. The two-chunk job also makes computing
    //   the percentage user feedback a little harder and might break some optimization
    //   in the insertions (we're able to optimize appends and prepends but a chunked
    //   job is likely to split our work at a boundary where messages are always inserted
    //   in the middle of the list).
    //
    // - The maximum time to spend inside a single job step
    //
    //   The larger this time, the greater the number of messages per second that this
    //   engine can process but also greater time with frozen UI -> less interactivity.
    //   Reasonable values start at 50 msecs. Values larger than 300 msecs are very likely
    //   to be percieved by the user as UI non-reactivity.
    //
    // - The number of messages processed in each job step subchunk.
    //
    //   A job subchunk is processed without checking the maximum time above. This means
    //   that each job step will process at least the number of messages specified by this value.
    //   Very low values mean that we respect the maximum time very carefully but we also
    //   waste time to check if we ran out of time :)
    //   Very high values are likely to cause the engine to not respect the maximum step time.
    //   Reasonable values go from 5 to 100.
    //
    // - The "idle" time between two steps
    //
    //   The lower this time, the greater the number of messages per second that this
    //   engine can process but also lower time for the UI to process events -> less interactivity.
    //   A value of 0 here means that Qt will trigger the timer as soon as it has some
    //   idle time to spend. UI events will be still processed but slowdowns are possible.
    //   0 is reasonable though. Values larger than 200 will tend to make the total job
    //   completion times high.
    //

    // If we have no filter it seems that we can apply a huge optimization.
    // We disconnect the UI for the first huge filling job. This allows us
    // to save the extremely expensive beginInsertRows()/endInsertRows() calls
    // and call a single layoutChanged() at the end. This slows down a lot item
    // expansion. But on the other side if only few items need to be expanded
    // then this strategy is better. If filtering is enabled then this strategy
    // isn't applicable (because filtering requires interaction with the UI
    // while the data is loading).

    // So...

    // For the very first small chunk it's ok to work with disconnected UI as long
    // as we have no filter. The first small chunk is always 1000 messages, so
    // even if all of them are expanded, it's still somewhat acceptable.
    bool canDoFirstSmallChunkWithDisconnectedUI = !d->mFilter;

    // Larger works need a bigger condition: few messages must be expanded in the end.
    bool canDoJobWithDisconnectedUI =
            // we have no filter
            !d->mFilter &&
            (
                // we do no threading at all
                ( d->mAggregation->threading() == Aggregation::NoThreading ) ||
                // or we never expand threads
                ( d->mAggregation->threadExpandPolicy() == Aggregation::NeverExpandThreads ) ||
                // or we expand threads but we'll be going to expand really only a few
                (
                    // so we don't expand them all
                    ( d->mAggregation->threadExpandPolicy() != Aggregation::AlwaysExpandThreads ) &&
                    // and we'd expand only a few in fact
                    ( d->mStorageModel->initialUnreadRowCountGuess() < 1000 )
                    )
                );

    switch ( d->mAggregation->fillViewStrategy() )
    {
    case Aggregation::FavorInteractivity:
        // favor interactivity
        if ( ( !canDoJobWithDisconnectedUI ) && ( d->mStorageModel->rowCount() > 3000 ) ) // empiric value
        {
            // First a small job with the most recent messages. Large chunk, small (but non zero) idle interval
            // and a larger number of messages to process at once.
            ViewItemJob * job1 = new ViewItemJob( d->mStorageModel->rowCount() - 1000, d->mStorageModel->rowCount() - 1, 200, 20, 100, canDoFirstSmallChunkWithDisconnectedUI );
            d->mViewItemJobs.append( job1 );
            // Then a larger job with older messages. Small chunk, bigger idle interval, small number of messages to
            // process at once.
            ViewItemJob * job2 = new ViewItemJob( 0, d->mStorageModel->rowCount() - 1001, 100, 50, 10, false );
            d->mViewItemJobs.append( job2 );

            // We could even extremize this by splitting the folder in several
            // chunks and scanning them from the newest to the oldest... but the overhead
            // due to imperfectly threaded children would be probably too big.
        } else {
            // small folder or can be done with disconnected UI: single chunk work.
            // Lag the CPU a bit more but not too much to destroy even the earliest interactivity.
            ViewItemJob * job = new ViewItemJob( 0, d->mStorageModel->rowCount() - 1, 150, 30, 30, canDoJobWithDisconnectedUI );
            d->mViewItemJobs.append( job );
        }
        break;
    case Aggregation::FavorSpeed:
        // More batchy jobs, still interactive to a certain degree
        if ( ( !canDoJobWithDisconnectedUI ) && ( d->mStorageModel->rowCount() > 3000 ) ) // empiric value
        {
            // large folder, but favor speed
            ViewItemJob * job1 = new ViewItemJob( d->mStorageModel->rowCount() - 1000, d->mStorageModel->rowCount() - 1, 250, 0, 100, canDoFirstSmallChunkWithDisconnectedUI );
            d->mViewItemJobs.append( job1 );
            ViewItemJob * job2 = new ViewItemJob( 0, d->mStorageModel->rowCount() - 1001, 200, 0, 10, false );
            d->mViewItemJobs.append( job2 );
        } else {
            // small folder or can be done with disconnected UI and favor speed: single chunk work.
            // Lag the CPU more, get more work done
            ViewItemJob * job = new ViewItemJob( 0, d->mStorageModel->rowCount() - 1, 250, 0, 100, canDoJobWithDisconnectedUI );
            d->mViewItemJobs.append( job );
        }
        break;
    case Aggregation::BatchNoInteractivity:
    {
        // one large job, never interrupt, block UI
        ViewItemJob * job = new ViewItemJob( 0, d->mStorageModel->rowCount() - 1, 60000, 0, 100000, canDoJobWithDisconnectedUI );
        d->mViewItemJobs.append( job );
    }
        break;
    default:
        kWarning() << "Unrecognized fill view strategy";
        Q_ASSERT( false );
        break;
    }

    d->mLoading = true;

    d->viewItemJobStep();
}

void ModelPrivate::checkIfDateChanged()
{
    // This function is called by MessageList::Core::Manager once in a while (every 1 minute or sth).
    // It is used to check if the current date has changed (with respect to mTodayDate).
    //
    // Our message items cache the formatted dates (as formatting them
    // on the fly would be too expensive). We also cache the labels of the groups which often display dates.
    // When the date changes we would need to fix all these strings.
    //
    // A dedicated algorithm to refresh the labels of the items would be either too complex
    // or would block on large trees. Fixing the labels of the groups is also quite hard...
    //
    // So to keep the things simple we just reload the view.

    if ( !mStorageModel )
        return; // nothing to do

    if ( mLoading )
        return; // not now

    if ( !mViewItemJobs.isEmpty() )
        return; // not now

    if ( mTodayDate == QDate::currentDate() )
        return; // date not changed

    // date changed, reload the view (and try to preserve the current selection)
    q->setStorageModel( mStorageModel, PreSelectLastSelected );
}


void Model::setPreSelectionMode( PreSelectionMode preSelect )
{
    d->mPreSelectionMode = preSelect;
    d->mLastSelectedMessageInFolder = 0;
}

//
// The "view fill" algorithm implemented in the functions below is quite smart but also quite complex.
// It's governed by the following goals:
//
// - Be flexible: allow different configurations from "unsorted flat list" to a "grouped and threaded
//     list with different sorting algorightms applied to each aggregation level"
// - Be reasonably fast
// - Be non blocking: UI shouldn't freeze while the algorithm is running
// - Be interruptible: user must be able to abort the execution and just switch to another folder in the middle
//

void ModelPrivate::clearUnassignedMessageLists()
{
    // This is a bit tricky...
    // The three unassigned message lists contain messages that have been created
    // but not yet attached to the view. There may be two major cases for a message:
    // - it has no parent -> it must be deleted and it will delete its children too
    // - it has a parent -> it must NOT be deleted since it will be deleted by its parent.

    // Sometimes the things get a little complicated since in Pass2 and Pass3
    // we have transitional states in that the MessageItem object can be in two of these lists.

    // WARNING: This function does NOT fixup mNewestItem and mOldestItem. If one of these
    // two messages is in the lists below, it's deleted and the member becomes a dangling pointer.
    // The caller must ensure that both mNewestItem and mOldestItem are set to 0
    // and this is enforced in the assert below to avoid errors. This basically means
    // that this function should be called only when the storage model changes or
    // when the model is destroyed.
    Q_ASSERT( ( mOldestItem == 0 ) && ( mNewestItem == 0 ) );

    QList< MessageItem * >::ConstIterator it;

    if ( !mUnassignedMessageListForPass2.isEmpty() )
    {
        // We're actually in Pass1* or Pass2: everything is mUnassignedMessageListForPass2
        // Something may *also* be in mUnassignedMessageListForPass3 and mUnassignedMessageListForPass4
        // but that are duplicates for sure.

        // We can't just sweep the list and delete parentless items since each delete
        // could kill children which are somewhere AFTER in the list: accessing the children
        // would then lead to a SIGSEGV. We first sweep the list gathering parentless
        // items and *then* delete them without accessing the parented ones.

        QList< MessageItem * > parentless;
        QList< MessageItem * >::ConstIterator end( mUnassignedMessageListForPass2.constEnd() );

        for ( it = mUnassignedMessageListForPass2.constBegin();
              it != end; ++it )
        {
            if( !( *it )->parent() )
                parentless.append( *it );
        }

        end = parentless.constEnd();
        for ( it = parentless.constBegin(); it != end; ++it )
            delete *it;

        mUnassignedMessageListForPass2.clear();
        // Any message these list contain was also in mUnassignedMessageListForPass2
        mUnassignedMessageListForPass3.clear();
        mUnassignedMessageListForPass4.clear();
        return;
    }

    // mUnassignedMessageListForPass2 is empty

    if ( !mUnassignedMessageListForPass3.isEmpty() )
    {
        // We're actually at the very end of Pass2 or inside Pass3
        // Pass2 pushes stuff in mUnassignedMessageListForPass3 *or* mUnassignedMessageListForPass4
        // Pass3 pushes stuff from mUnassignedMessageListForPass3 to mUnassignedMessageListForPass4
        // So if we're in Pass2 then the two lists contain distinct messages but if we're in Pass3
        // then the two lists may contain the same messages.

        if ( !mUnassignedMessageListForPass4.isEmpty() )
        {
            // We're actually in Pass3: the messiest one.

            QHash< MessageItem *, MessageItem * > itemsToDelete;
            QList< MessageItem * >::ConstIterator end( mUnassignedMessageListForPass3.constEnd() );

            for ( it = mUnassignedMessageListForPass3.constBegin(); it != end; ++it )
            {
                if( !( *it )->parent() )
                    itemsToDelete.insert( *it, *it );
            }
            end = mUnassignedMessageListForPass4.constEnd();
            for ( it = mUnassignedMessageListForPass4.constBegin(); it != end; ++it )
            {
                if( !( *it )->parent() )
                    itemsToDelete.insert( *it, *it );
            }
            QHash< MessageItem *, MessageItem * >::ConstIterator end3 = itemsToDelete.constEnd();
            for ( QHash< MessageItem *, MessageItem * >::ConstIterator it3 = itemsToDelete.constBegin(); it3 != end3; ++it3 )
                delete ( *it3 );

            mUnassignedMessageListForPass3.clear();
            mUnassignedMessageListForPass4.clear();
            return;
        }

        // mUnassignedMessageListForPass4 is empty so we must be at the end of a very special kind of Pass2
        // We have the same problem as in mUnassignedMessageListForPass2.
        QList< MessageItem * > parentless;
        QList< MessageItem * >::ConstIterator end = mUnassignedMessageListForPass3.constEnd();
        for ( it = mUnassignedMessageListForPass3.constBegin(); it != end; ++it )
        {
            if( !( *it )->parent() )
                parentless.append( *it );
        }
        end = parentless.constEnd();
        for ( it = parentless.constBegin(); it != end; ++it )
            delete *it;

        mUnassignedMessageListForPass3.clear();
        return;
    }

    // mUnassignedMessageListForPass3 is empty
    if ( !mUnassignedMessageListForPass4.isEmpty() )
    {
        // we're in Pass4.. this is easy.

        // We have the same problem as in mUnassignedMessageListForPass2.
        QList< MessageItem * > parentless;
        QList< MessageItem * >::ConstIterator end = mUnassignedMessageListForPass4.constEnd();
        for (  it = mUnassignedMessageListForPass4.constBegin(); it != end; ++it )
        {
            if( !( *it )->parent() )
                parentless.append( *it );
        }
        end = parentless.constEnd();
        for ( it = parentless.constBegin(); it != end; ++it )
            delete *it;

        mUnassignedMessageListForPass4.clear();
        return;
    }
}

void ModelPrivate::clearThreadingCacheMessageSubjectMD5ToMessageItem()
{
    qDeleteAll( mThreadingCacheMessageSubjectMD5ToMessageItem );
    mThreadingCacheMessageSubjectMD5ToMessageItem.clear();
}

void ModelPrivate::clearOrphanChildrenHash()
{
    QHash< MessageItem *, MessageItem * >::ConstIterator end( mOrphanChildrenHash.constEnd() );
    for ( QHash< MessageItem *, MessageItem * >::ConstIterator it = mOrphanChildrenHash.constBegin();
          it != end; ++it )
    {
        //Q_ASSERT( !( *it )->parent() ); <-- this assert can actually fail for items that get a temporary parent assigned (to preserve the selection).
        delete ( *it );
    }
    mOrphanChildrenHash.clear();
}

void ModelPrivate::clearJobList()
{
    if ( mViewItemJobs.isEmpty() )
        return;

    if ( mInLengthyJobBatch )
    {
        mInLengthyJobBatch = false;
        mView->modelJobBatchTerminated();
    }

    QList< ViewItemJob * >::ConstIterator end = mViewItemJobs.constEnd();
    for( QList< ViewItemJob * >::ConstIterator it = mViewItemJobs.constBegin();
         it != end; ++it )
        delete ( *it );
    mViewItemJobs.clear();

    mModelForItemFunctions = q; // make sure it's true, as there remains no job with disconnected UI
}


void ModelPrivate::attachGroup( GroupHeaderItem *ghi )
{
    if ( ghi->parent() )
    {
        if (
                ( ( ghi )->childItemCount() > 0 ) && // has children
                ( ghi )->isViewable() && // is actually attached to the viewable root
                mModelForItemFunctions && // the UI is not disconnected
                mView->isExpanded( q->index( ghi, 0 ) ) // is actually expanded
                )
            saveExpandedStateOfSubtree( ghi );

        // FIXME: This *WILL* break selection and current index... :/

        ghi->parent()->takeChildItem( mModelForItemFunctions, ghi );
    }

    ghi->setParent( mRootItem );

    // I'm using a macro since it does really improve readability.
    // I'm NOT using a helper function since gcc will refuse to inline some of
    // the calls because they make this function grow too much.
#define INSERT_GROUP_WITH_COMPARATOR( _ItemComparator ) \
    switch( mSortOrder->groupSortDirection() ) \
    { \
    case SortOrder::Ascending: \
    mRootItem->d_ptr->insertChildItem< _ItemComparator, true >( mModelForItemFunctions, ghi ); \
    break; \
    case SortOrder::Descending: \
    mRootItem->d_ptr->insertChildItem< _ItemComparator, false >( mModelForItemFunctions, ghi ); \
    break; \
    default: /* should never happen... */ \
    mRootItem->appendChildItem( mModelForItemFunctions, ghi ); \
    break; \
}

    switch( mSortOrder->groupSorting() )
    {
    case SortOrder::SortGroupsByDateTime:
        INSERT_GROUP_WITH_COMPARATOR( ItemDateComparator )
                break;
    case SortOrder::SortGroupsByDateTimeOfMostRecent:
        INSERT_GROUP_WITH_COMPARATOR( ItemMaxDateComparator )
                break;
    case SortOrder::SortGroupsBySenderOrReceiver:
        INSERT_GROUP_WITH_COMPARATOR( ItemSenderOrReceiverComparator )
                break;
    case SortOrder::SortGroupsBySender:
        INSERT_GROUP_WITH_COMPARATOR( ItemSenderComparator )
                break;
    case SortOrder::SortGroupsByReceiver:
        INSERT_GROUP_WITH_COMPARATOR( ItemReceiverComparator )
                break;
    case SortOrder::NoGroupSorting:
        mRootItem->appendChildItem( mModelForItemFunctions, ghi );
        break;
    default: // should never happen
        mRootItem->appendChildItem( mModelForItemFunctions, ghi );
        break;
    }

    if ( ghi->initialExpandStatus() == Item::ExpandNeeded ) // this actually is a "non viewable expanded state"
        if ( ghi->childItemCount() > 0 )
            if ( mModelForItemFunctions ) // the UI is not disconnected
                syncExpandedStateOfSubtree( ghi );

    // A group header is always viewable, when attached: apply the filter, if we have it.
    if ( mFilter )
    {
        Q_ASSERT( mModelForItemFunctions ); // UI must be NOT disconnected
        // apply the filter to subtree
        applyFilterToSubtree( ghi, QModelIndex() );
    }
}

void ModelPrivate::saveExpandedStateOfSubtree( Item *root )
{
    Q_ASSERT( mModelForItemFunctions ); // UI must be NOT disconnected here
    Q_ASSERT( root );

    root->setInitialExpandStatus( Item::ExpandNeeded );

    QList< Item * > * children = root->childItems();
    if ( !children )
        return;
    QList< Item * >::ConstIterator end( children->constEnd() );
    for( QList< Item * >::ConstIterator it = children->constBegin(); it != end; ++it )
    {
        if (
                ( ( *it )->childItemCount() > 0 ) && // has children
                ( *it )->isViewable() && // is actually attached to the viewable root
                mView->isExpanded( q->index( *it, 0 ) ) // is actually expanded
                )
            saveExpandedStateOfSubtree( *it );
    }
}

void ModelPrivate::syncExpandedStateOfSubtree( Item *root )
{
    Q_ASSERT( mModelForItemFunctions ); // UI must be NOT disconnected here

    // WE ASSUME that:
    // - the item is viewable
    // - its initialExpandStatus() is Item::ExpandNeeded
    // - it has at least one children (well.. this is not a strict requirement, but it's a waste of resources to expand items that don't have children)

    QModelIndex idx = q->index( root, 0 );

    //if ( !mView->isExpanded( idx ) ) // this is O(logN!) in Qt.... very ugly... but it should never happen here
    mView->expand( idx ); // sync the real state in the view
    root->setInitialExpandStatus( Item::ExpandExecuted );

    QList< Item * > * children = root->childItems();
    if ( !children )
        return;

    QList< Item * >::ConstIterator end( children->constEnd() );
    for( QList< Item * >::ConstIterator it = children->constBegin(); it != end; ++it )
    {
        if ( ( *it )->initialExpandStatus() == Item::ExpandNeeded )
        {
            if ( ( *it )->childItemCount() > 0 )
                syncExpandedStateOfSubtree( *it );
        }
    }
}

void ModelPrivate::attachMessageToGroupHeader( MessageItem *mi )
{
    QString groupLabel;
    time_t date;

    // compute the group header label and the date
    switch( mAggregation->grouping() )
    {
    case Aggregation::GroupByDate:
    case Aggregation::GroupByDateRange:
    {
        if ( mAggregation->threadLeader() == Aggregation::MostRecentMessage )
        {
            date = mi->maxDate();
        } else
        {
            date = mi->date();
        }

        QDateTime dt;
        dt.setTime_t( date );
        QDate dDate = dt.date();
        const KCalendarSystem *calendar = KGlobal::locale()->calendar();
        int daysAgo = -1;
        if ( calendar->isValid( dDate ) && calendar->isValid( mTodayDate ) ) {
            daysAgo = dDate.daysTo( mTodayDate );
        }

        if ( ( daysAgo < 0 ) || // In the future
             ( static_cast< uint >( date ) == static_cast< uint >( -1 ) ) ) // Invalid
        {
            groupLabel = mCachedUnknownLabel;
        } else if( daysAgo == 0 ) // Today
        {
            groupLabel = mCachedTodayLabel;
        } else if ( daysAgo == 1 ) // Yesterday
        {
            groupLabel = mCachedYesterdayLabel;
        } else if ( daysAgo > 1 && daysAgo < calendar->daysInWeek( mTodayDate ) ) // Within last seven days
        {
            groupLabel = KGlobal::locale()->calendar()->weekDayName( dDate );
        } else if ( mAggregation->grouping() == Aggregation::GroupByDate ) { // GroupByDate seven days or more ago
            groupLabel = KGlobal::locale()->formatDate( dDate, KLocale::ShortDate );
        } else if( ( calendar->month( dDate ) == calendar->month( mTodayDate ) ) && // GroupByDateRange within this month
                   ( calendar->year( dDate ) == calendar->year( mTodayDate ) ) )
        {
            int startOfWeekDaysAgo = ( calendar->daysInWeek( mTodayDate ) + calendar->dayOfWeek( mTodayDate ) -
                                       KGlobal::locale()->weekStartDay() ) % calendar->daysInWeek( mTodayDate );
            int weeksAgo = ( ( daysAgo - startOfWeekDaysAgo ) / calendar->daysInWeek( mTodayDate ) ) + 1;
            switch( weeksAgo )
            {
            case 0: // This week
                groupLabel = KGlobal::locale()->calendar()->weekDayName( dDate );
                break;
            case 1: // 1 week ago
                groupLabel = mCachedLastWeekLabel;
                break;
            case 2:
                groupLabel = mCachedTwoWeeksAgoLabel;
                break;
            case 3:
                groupLabel = mCachedThreeWeeksAgoLabel;
                break;
            case 4:
                groupLabel = mCachedFourWeeksAgoLabel;
                break;
            case 5:
                groupLabel = mCachedFiveWeeksAgoLabel;
                break;
            default: // should never happen
                groupLabel = mCachedUnknownLabel;
            }
        } else if ( calendar->year( dDate ) == calendar->year( mTodayDate ) ) { // GroupByDateRange within this year
            groupLabel = calendar->monthName( dDate );
        } else { // GroupByDateRange in previous years
            groupLabel = i18nc( "Message Aggregation Group Header: Month name and Year number", "%1 %2", calendar->monthName( dDate ),
                                calendar->formatDate( dDate, KLocale::Year, KLocale::LongNumber ) );
        }
        break;
    }

    case Aggregation::GroupBySenderOrReceiver:
        date = mi->date();
        groupLabel = MessageCore::StringUtil::stripEmailAddr( mi->senderOrReceiver() );
        break;

    case Aggregation::GroupBySender:
        date = mi->date();
        groupLabel = MessageCore::StringUtil::stripEmailAddr( mi->sender() );
        break;

    case Aggregation::GroupByReceiver:
        date = mi->date();
        groupLabel = MessageCore::StringUtil::stripEmailAddr( mi->receiver() );
        break;

    case Aggregation::NoGrouping:
        // append directly to root
        attachMessageToParent( mRootItem, mi );
        return;

    default:
        // should never happen
        attachMessageToParent( mRootItem, mi );
        return;
    }

    GroupHeaderItem * ghi;

    ghi = mGroupHeaderItemHash.value( groupLabel, 0 );
    if( !ghi )
    {
        // not found

        ghi = new GroupHeaderItem( groupLabel );
        ghi->initialSetup( date, mi->size(), mi->sender(), mi->receiver(), mi->useReceiver() );

        switch( mAggregation->groupExpandPolicy() )
        {
        case Aggregation::NeverExpandGroups:
            // nothing to do
            break;
        case Aggregation::AlwaysExpandGroups:
            // expand always
            ghi->setInitialExpandStatus( Item::ExpandNeeded );
            break;
        case Aggregation::ExpandRecentGroups:
            // expand only if "close" to today
            if ( mViewItemJobStepStartTime > ghi->date() )
            {
                if ( ( mViewItemJobStepStartTime - ghi->date() ) < ( 3600 * 72 ) )
                    ghi->setInitialExpandStatus( Item::ExpandNeeded );
            } else {
                if ( ( ghi->date() - mViewItemJobStepStartTime ) < ( 3600 * 72 ) )
                    ghi->setInitialExpandStatus( Item::ExpandNeeded );
            }
            break;
        default:
            // b0rken
            break;
        }

        attachMessageToParent( ghi, mi );

        attachGroup( ghi ); // this will expand the group if required

        mGroupHeaderItemHash.insert( groupLabel, ghi );
    } else {
        // the group was already there (certainly viewable)

        // This function may be also called to re-group a message.
        // That is, to eventually find a new group for a message that has changed
        // its properties (but was already attacched to a group).
        // So it may happen that we find out that in fact re-grouping wasn't really
        // needed because the message is already in the correct group.
        if ( mi->parent() == ghi )
            return; // nothing to be done

        attachMessageToParent( ghi, mi );
    }
}

MessageItem * ModelPrivate::findMessageParent( MessageItem * mi )
{
    Q_ASSERT( mAggregation->threading() != Aggregation::NoThreading ); // caller must take care of this

    // This function attempts to find a thread parent for the item "mi"
    // which actually may already have a children subtree.

    // Forged or plain broken message trees are dangerous here.
    // For example, a message tree with circular references like
    //
    //        Message mi, Id=1, In-Reply-To=2
    //          Message childOfMi, Id=2, In-Reply-To=1
    //
    // is perfectly possible and will cause us to find childOfMi
    // as parent of mi. This will then create a loop in the message tree
    // (which will then no longer be a tree in fact) and cause us to freeze
    // once we attempt to climb the parents. We need to take care of that.

    bool bMessageWasThreadable = false;
    MessageItem * pParent;

    // First of all try to find a "perfect parent", that is the message for that
    // we have the ID in the "In-Reply-To" field. This is actually done by using
    // MD5 caches of the message ids because of speed. Collisions are very unlikely.

    QByteArray md5 = mi->inReplyToIdMD5();
    if ( !md5.isEmpty() )
    {
        // have an In-Reply-To field MD5
        pParent = mThreadingCacheMessageIdMD5ToMessageItem.value( md5, 0 );
        if(pParent)
        {
            // Take care of circular references
            if (
                    ( mi == pParent ) ||              // self referencing message
                    (
                        ( mi->childItemCount() > 0 ) && // mi already has children, this is fast to determine
                        pParent->hasAncestor( mi )      // pParent is in the mi's children tree
                        )
                    )
            {
                kWarning() << "Circular In-Reply-To reference loop detected in the message tree";
                mi->setThreadingStatus( MessageItem::NonThreadable );
                return 0; // broken message: throw it away
            }
            mi->setThreadingStatus( MessageItem::PerfectParentFound );
            return pParent; // got a perfect parent for this message
        }

        // got no perfect parent
        bMessageWasThreadable = true; // but the message was threadable
    }

    if ( mAggregation->threading() == Aggregation::PerfectOnly )
    {
        mi->setThreadingStatus( bMessageWasThreadable ? MessageItem::ParentMissing : MessageItem::NonThreadable );
        return 0; // we're doing only perfect parent matches
    }

    // Try to use the "References" field. In fact we have the MD5 of the
    // (n-1)th entry in References.
    //
    // Original rationale from KMHeaders:
    //
    // If we don't have a replyToId, or if we have one and the
    // corresponding message is not in this folder, as happens
    // if you keep your outgoing messages in an OUTBOX, for
    // example, try the list of references, because the second
    // to last will likely be in this folder. replyToAuxIdMD5
    // contains the second to last one.

    md5 = mi->referencesIdMD5();
    if ( !md5.isEmpty() )
    {
        pParent = mThreadingCacheMessageIdMD5ToMessageItem.value( md5, 0 );
        if(pParent)
        {
            // Take care of circular references
            if (
                    ( mi == pParent ) ||              // self referencing message
                    (
                        ( mi->childItemCount() > 0 ) && // mi already has children, this is fast to determine
                        pParent->hasAncestor( mi )      // pParent is in the mi's children tree
                        )
                    )
            {
                kWarning() << "Circular reference loop detected in the message tree";
                mi->setThreadingStatus( MessageItem::NonThreadable );
                return 0; // broken message: throw it away
            }
            mi->setThreadingStatus( MessageItem::ImperfectParentFound );
            return pParent; // got an imperfect parent for this message
        }

        // got no imperfect parent
        bMessageWasThreadable = true; // but the message was threadable
    }

    if ( mAggregation->threading() == Aggregation::PerfectAndReferences )
    {
        mi->setThreadingStatus( bMessageWasThreadable ? MessageItem::ParentMissing : MessageItem::NonThreadable );
        return 0; // we're doing only perfect parent matches
    }

    Q_ASSERT( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject );

    // We are supposed to do subject based threading but we can't do it now.
    // This is because the subject based threading *may* be wrong and waste
    // time by creating circular references (that we'd need to detect and fix).
    // We first try the perfect and references based threading on all the messages
    // and then run subject based threading only on the remaining ones.

    mi->setThreadingStatus( ( bMessageWasThreadable || mi->subjectIsPrefixed() ) ? MessageItem::ParentMissing : MessageItem::NonThreadable );
    return 0;
}

// Subject threading cache stuff

#if 0
// Debug helpers
void dump_iterator_and_list( QList< MessageItem * >::Iterator &iter, QList< MessageItem * > *list )
{
    kDebug() << "Threading cache part dump" << endl;
    if ( iter == list->end() )
        kDebug() << "Iterator pointing to end of the list" << endl;
    else
        kDebug() << "Iterator pointing to " << *iter << " subject [" << (*iter)->subject() << "] date [" << (*iter)->date() << "]" << endl;

    for ( QList< MessageItem * >::Iterator it = list->begin(); it != list->end(); ++it )
    {
        kDebug() << "List element " << *it << " subject [" << (*it)->subject() << "] date [" << (*it)->date() << "]" << endl;
    }

    kDebug() << "End of threading cache part dump" << endl;
}

void dump_list( QList< MessageItem * > *list )
{
    kDebug() << "Threading cache part dump" << endl;

    for ( QList< MessageItem * >::Iterator it = list->begin(); it != list->end(); ++it )
    {
        kDebug() << "List element " << *it << " subject [" << (*it)->subject() << "] date [" << (*it)->date() << "]" << endl;
    }

    kDebug() << "End of threading cache part dump" << endl;
}
#endif // debug helpers

// a helper class used in a qLowerBound() call below
class MessageLessThanByDate
{
public:
    inline bool operator()( const MessageItem * mi1, const MessageItem * mi2 ) const
    {
        if ( mi1->date() < mi2->date() ) // likely
            return true;
        if ( mi1->date() > mi2->date() ) // likely
            return false;
        // dates are equal, compare by pointer
        return mi1 < mi2;
    }
};

void ModelPrivate::addMessageToSubjectBasedThreadingCache( MessageItem * mi )
{
    // Messages in this cache are sorted by date, and if dates are equal then they are sorted by pointer value.
    // Sorting by date is used to optimize the parent lookup in guessMessageParent() below.

    // WARNING: If the message date changes for some reason (like in the "update" step)
    //          then the cache may become unsorted. For this reason the message about to
    //          be changed must be first removed from the cache and then reinserted.

    // Lookup the list of messages with the same stripped subject
    QList< MessageItem * > * messagesWithTheSameStrippedSubject =
            mThreadingCacheMessageSubjectMD5ToMessageItem.value( mi->strippedSubjectMD5(), 0 );

    if ( !messagesWithTheSameStrippedSubject )
    {
        // Not there yet: create it and append.
        messagesWithTheSameStrippedSubject = new QList< MessageItem * >();
        mThreadingCacheMessageSubjectMD5ToMessageItem.insert( mi->strippedSubjectMD5(), messagesWithTheSameStrippedSubject );
        messagesWithTheSameStrippedSubject->append( mi );
        return;
    }

    // Found: assert that we have no duplicates in the cache.
    Q_ASSERT( !messagesWithTheSameStrippedSubject->contains( mi ) );

    // Ordered insert: first by date then by pointer value.
    QList< MessageItem * >::Iterator it = qLowerBound( messagesWithTheSameStrippedSubject->begin(), messagesWithTheSameStrippedSubject->end(), mi, MessageLessThanByDate() );
    messagesWithTheSameStrippedSubject->insert( it, mi );
}

void ModelPrivate::removeMessageFromSubjectBasedThreadingCache( MessageItem * mi )
{
    // We assume that the caller knows what he is doing and the message is actually in the cache.
    // If the message isn't in the cache then we should be called at all.
    //
    // The game is called "performance"

    // Grab the list of all the messages with the same stripped subject (all potential parents)
    QList< MessageItem * > * messagesWithTheSameStrippedSubject = mThreadingCacheMessageSubjectMD5ToMessageItem.value( mi->strippedSubjectMD5(), 0 );

    // We assume that the message is there so the list must be non null.
    Q_ASSERT( messagesWithTheSameStrippedSubject );

    // The cache *MUST* be ordered first by date then by pointer value
    QList< MessageItem * >::Iterator it = qLowerBound( messagesWithTheSameStrippedSubject->begin(), messagesWithTheSameStrippedSubject->end(), mi, MessageLessThanByDate() );

    // The binary based search must have found a message
    Q_ASSERT( it != messagesWithTheSameStrippedSubject->end() );

    // and it must have found exactly the message requested
    Q_ASSERT( *it == mi );

    // Kill it
    messagesWithTheSameStrippedSubject->erase( it );

    // And kill the list if it was the last one
    if ( messagesWithTheSameStrippedSubject->isEmpty() )
    {
        mThreadingCacheMessageSubjectMD5ToMessageItem.remove( mi->strippedSubjectMD5() );
        delete messagesWithTheSameStrippedSubject;
    }
}

MessageItem * ModelPrivate::guessMessageParent( MessageItem * mi )
{
    // This function implements subject based threading
    // It attempts to guess a thread parent for the item "mi"
    // which actually may already have a children subtree.

    // We have all the problems of findMessageParent() plus the fact that
    // we're actually guessing (and often we may be *wrong*).

    Q_ASSERT( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject ); // caller must take care of this
    Q_ASSERT( mi->subjectIsPrefixed() ); // caller must take care of this
    Q_ASSERT( mi->threadingStatus() == MessageItem::ParentMissing );


    // Do subject based threading
    const QByteArray md5 = mi->strippedSubjectMD5();
    if ( !md5.isEmpty() )
    {
        QList< MessageItem * > * messagesWithTheSameStrippedSubject =
                mThreadingCacheMessageSubjectMD5ToMessageItem.value( md5, 0 );

        if ( messagesWithTheSameStrippedSubject )
        {
            Q_ASSERT( messagesWithTheSameStrippedSubject->count() > 0 );

            // Need to find the message with the maximum date lower than the one of this message

            time_t maxTime = (time_t)0;
            MessageItem * pParent = 0;

            // Here'we re really guessing so circular references are possible
            // even on perfectly valid trees. This is why we don't consider it
            // an error but just continue searching.

            // FIXME: This might be speed up with an initial binary search (?)
            // ANSWER: No. We can't rely on date order (as it can be updated on the fly...)
            QList< MessageItem * >::ConstIterator end( messagesWithTheSameStrippedSubject->constEnd() );

            for ( QList< MessageItem * >::ConstIterator it = messagesWithTheSameStrippedSubject->constBegin(); it != end; ++it )
            {
                int delta = mi->date() - ( *it )->date();

                // We don't take into account messages with a delta smaller than 120.
                // Assuming that our date() values are correct (that is, they take into
                // account timezones etc..) then one usually needs more than 120 seconds
                // to answer to a message. Better safe than sorry.

                // This check also includes negative deltas so messages later than mi aren't considered

                if ( delta < 120 )
                    break; // The list is ordered by date (ascending) so we can stop searching here

                // About the "magic" 3628899 value here comes a Till's comment from the original KMHeaders:
                //
                //   "Parents more than six weeks older than the message are not accepted. The reasoning being
                //   that if a new message with the same subject turns up after such a long time, the chances
                //   that it is still part of the same thread are slim. The value of six weeks is chosen as a
                //   result of a poll conducted on kde-devel, so it's probably bogus. :)"

                if ( delta < 3628899 )
                {
                    // Compute the closest.
                    if ( ( maxTime < ( *it )->date() ) )
                    {
                        // This algorithm *can* be (and often is) wrong.
                        // Take care of circular threading which is really possible at this level.
                        // If mi contains (*it) inside its children subtree then we have
                        // found such a circular threading problem.

                        // Note that here we can't have *it == mi because of the delta >= 120 check above.

                        if ( ( mi->childItemCount() == 0 ) || !( *it )->hasAncestor( mi ) )
                        {
                            maxTime = ( *it )->date();
                            pParent = ( *it );
                        }
                    }
                }
            }

            if ( pParent )
            {
                mi->setThreadingStatus( MessageItem::ImperfectParentFound );
                return pParent; // got an imperfect parent for this message
            }
        }
    }

    return 0;
}

//
// A little template helper, hopefully inlineable.
//
// Return true if the specified message item is in the wrong position
// inside the specified parent and needs re-sorting. Return false otherwise.
// Both parent and messageItem must not be null.
//
// Checking if a message needs re-sorting instead of just re-sorting it
// is very useful since re-sorting is an expensive operation.
//
template< class ItemComparator > static bool messageItemNeedsReSorting( SortOrder::SortDirection messageSortDirection,
                                                                        ItemPrivate *parent, MessageItem *messageItem )
{
    if ( ( messageSortDirection == SortOrder::Ascending )
         || ( parent->mType == Item::Message ) )
    {
        return parent->childItemNeedsReSorting< ItemComparator, true >( messageItem );
    }
    return parent->childItemNeedsReSorting< ItemComparator, false >( messageItem );
}

bool ModelPrivate::handleItemPropertyChanges( int propertyChangeMask, Item * parent, Item * item )
{
    // The facts:
    //
    // - If dates changed:
    //   - If we're sorting messages by min/max date then at each level the messages might need resorting.
    //   - If the thread leader is the most recent message of a thread then the uppermost
    //     message of the thread might need re-grouping.
    //   - If the groups are sorted by min/max date then the group might need re-sorting too.
    //
    // This function explicitly doesn't re-apply the filter when ActionItemStatus changes.
    // This is because filters must be re-applied due to a broader range of status variations:
    // this is done in viewItemJobStepInternalForJobPass1Update() instead (which is the only
    // place in that ActionItemStatus may be set).

    if( parent->type() == Item::InvisibleRoot )
    {
        // item is either a message or a group attacched to the root.
        // It might need resorting.
        if ( item->type() == Item::GroupHeader )
        {
            // item is a group header attacched to the root.
            if (
                    (
                        // max date changed
                        ( propertyChangeMask & MaxDateChanged ) &&
                        // groups sorted by max date
                        ( mSortOrder->groupSorting() == SortOrder::SortGroupsByDateTimeOfMostRecent )
                        ) || (
                        // date changed
                        ( propertyChangeMask & DateChanged ) &&
                        // groups sorted by date
                        ( mSortOrder->groupSorting() == SortOrder::SortGroupsByDateTime )
                        )
                    )
            {
                // This group might need re-sorting.

                // Groups are large container of messages so it's likely that
                // another message inserted will cause this group to be marked again.
                // So we wait until the end to do the grand final re-sorting: it will be done in Pass4.
                mGroupHeadersThatNeedUpdate.insert( static_cast< GroupHeaderItem * >( item ), static_cast< GroupHeaderItem * >( item ) );
            }
        } else {
            // item is a message. It might need re-sorting.

            // Since sorting is an expensive operation, we first check if it's *really* needed.
            // Re-sorting will actually not change min/max dates at all and
            // will not climb up the parent's ancestor tree.

            switch ( mSortOrder->messageSorting() )
            {
            case SortOrder::SortMessagesByDateTime:
                if ( propertyChangeMask & DateChanged ) // date changed
                {
                    if ( messageItemNeedsReSorting< ItemDateComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else date changed, but it doesn't match sorting order: no need to re-sort
                break;
            case SortOrder::SortMessagesByDateTimeOfMostRecent:
                if ( propertyChangeMask & MaxDateChanged ) // max date changed
                {
                    if ( messageItemNeedsReSorting< ItemMaxDateComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else max date changed, but it doesn't match sorting order: no need to re-sort
                break;
            case SortOrder::SortMessagesByActionItemStatus:
                if ( propertyChangeMask & ActionItemStatusChanged ) // todo status changed
                {
                    if ( messageItemNeedsReSorting< ItemActionItemStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else to do status changed, but it doesn't match sorting order: no need to re-sort
                break;
            case SortOrder::SortMessagesByUnreadStatus:
                if ( propertyChangeMask & UnreadStatusChanged ) // new / unread status changed
                {
                    if ( messageItemNeedsReSorting< ItemUnreadStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else new/unread status changed, but it doesn't match sorting order: no need to re-sort
                break;
            case SortOrder::SortMessagesByImportantStatus:
                if ( propertyChangeMask & ImportantStatusChanged ) // important status changed
                {
                    if ( messageItemNeedsReSorting< ItemImportantStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else new/unread status changed, but it doesn't match sorting order: no need to re-sort
                break;
            case SortOrder::SortMessagesByAttachmentStatus:
                if ( propertyChangeMask & AttachmentStatusChanged ) // attachment status changed
                {
                    if ( messageItemNeedsReSorting< ItemAttachmentStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                        attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
                } // else new/unread status changed, but it doesn't match sorting order: no need to re-sort
                break;
            default:
                // this kind of message sorting isn't affected by the property changes: nothing to do.
                break;
            }
        }

        return false; // the invisible root isn't affected by any change.
    }

    if ( parent->type() == Item::GroupHeader )
    {
        // item is a message attacched to a GroupHeader.
        // It might need re-grouping or re-sorting (within the same group)

        // Check re-grouping here.
        if (
                (
                    // max date changed
                    ( propertyChangeMask & MaxDateChanged ) &&
                    // thread leader is most recent message
                    ( mAggregation->threadLeader() == Aggregation::MostRecentMessage )
                    ) || (
                    // date changed
                    ( propertyChangeMask & DateChanged ) &&
                    // thread leader the topmost message
                    ( mAggregation->threadLeader() == Aggregation::TopmostMessage )
                    )
                )
        {
            // Might really need re-grouping.
            // attachMessageToGroupHeader() will find the right group for this message
            // and if it's different than the current it will move it.
            attachMessageToGroupHeader( static_cast< MessageItem * >( item ) );
            // Re-grouping fixes the properties of the involved group headers
            // so at exit of attachMessageToGroupHeader() the parent can't be affected
            // by the change anymore.
            return false;
        }

        // Re-grouping wasn't needed. Re-sorting might be.

    } // else item is a message attacched to another message and might need re-sorting only.

    // Check if message needs re-sorting.

    switch ( mSortOrder->messageSorting() )
    {
    case SortOrder::SortMessagesByDateTime:
        if ( propertyChangeMask & DateChanged ) // date changed
        {
            if ( messageItemNeedsReSorting< ItemDateComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else date changed, but it doesn't match sorting order: no need to re-sort
        break;
    case SortOrder::SortMessagesByDateTimeOfMostRecent:
        if ( propertyChangeMask & MaxDateChanged ) // max date changed
        {
            if ( messageItemNeedsReSorting< ItemMaxDateComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else max date changed, but it doesn't match sorting order: no need to re-sort
        break;
    case SortOrder::SortMessagesByActionItemStatus:
        if ( propertyChangeMask & ActionItemStatusChanged ) // todo status changed
        {
            if ( messageItemNeedsReSorting< ItemActionItemStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else to do status changed, but it doesn't match sorting order: no need to re-sort
        break;
    case SortOrder::SortMessagesByUnreadStatus:
        if ( propertyChangeMask & UnreadStatusChanged ) // new / unread status changed
        {
            if ( messageItemNeedsReSorting< ItemUnreadStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else new/unread status changed, but it doesn't match sorting order: no need to re-sort
        break;
    case SortOrder::SortMessagesByImportantStatus:
        if ( propertyChangeMask & ImportantStatusChanged ) // important status changed
        {
            if ( messageItemNeedsReSorting< ItemImportantStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else important status changed, but it doesn't match sorting order: no need to re-sort
        break;
    case SortOrder::SortMessagesByAttachmentStatus:
        if ( propertyChangeMask & AttachmentStatusChanged ) // attachment status changed
        {
            if ( messageItemNeedsReSorting< ItemAttachmentStatusComparator >( mSortOrder->messageSortDirection(), parent->d_ptr, static_cast< MessageItem * >( item ) ) )
                attachMessageToParent( parent, static_cast< MessageItem * >( item ) );
        } // else important status changed, but it doesn't match sorting order: no need to re-sort
        break;
    default:
        // this kind of message sorting isn't affected by property changes: nothing to do.
        break;
    }

    return true; // parent might be affected too.
}

void ModelPrivate::messageDetachedUpdateParentProperties( Item *oldParent, MessageItem *mi )
{
    Q_ASSERT( oldParent );
    Q_ASSERT( mi );
    Q_ASSERT( oldParent != mRootItem );


    // oldParent might have its properties changed because of the child removal.
    // propagate the changes up.
    for(;;)
    {
        // pParent is not the root item now. This is assured by how we enter this loop
        // and by the fact that handleItemPropertyChanges returns false when grandParent
        // is Item::InvisibleRoot. We could actually assert it here...

        // Check if its dates need an update.
        int propertyChangeMask;

        if ( ( mi->maxDate() == oldParent->maxDate() ) && oldParent->recomputeMaxDate() )
            propertyChangeMask = MaxDateChanged;
        else
            break; // from the for(;;) loop

        // One of the oldParent properties has changed for sure

        Item * grandParent = oldParent->parent();

        // If there is no grandParent then oldParent isn't attacched to the view.
        // Re-sorting / re-grouping isn't needed for sure.
        if ( !grandParent )
            break; // from the for(;;) loop

        // The following function will return true if grandParent may be affected by the change.
        // If the grandParent isn't affected, we stop climbing.
        if ( !handleItemPropertyChanges( propertyChangeMask, grandParent, oldParent ) )
            break; // from the for(;;) loop

        // Now we need to climb up one level and check again.
        oldParent = grandParent;
    } // for(;;) loop

    // If the last message was removed from a group header then this group will need an update
    // for sure. We will need to remove it (unless a message is attacched back to it)
    if ( oldParent->type() == Item::GroupHeader )
    {
        if ( oldParent->childItemCount() == 0 )
            mGroupHeadersThatNeedUpdate.insert( static_cast< GroupHeaderItem * >( oldParent ), static_cast< GroupHeaderItem * >( oldParent ) );
    }
}

void ModelPrivate::propagateItemPropertiesToParent( Item * item )
{
    Item * pParent = item->parent();
    Q_ASSERT( pParent );
    Q_ASSERT( pParent != mRootItem );

    for(;;)
    {
        // pParent is not the root item now. This is assured by how we enter this loop
        // and by the fact that handleItemPropertyChanges returns false when grandParent
        // is Item::InvisibleRoot. We could actually assert it here...

        // Check if its dates need an update.
        int propertyChangeMask;

        if ( item->maxDate() > pParent->maxDate() )
        {
            pParent->setMaxDate( item->maxDate() );
            propertyChangeMask = MaxDateChanged;
        } else {
            // No parent dates have changed: no further work is needed. Stop climbing here.
            break; // from the for(;;) loop
        }

        // One of the pParent properties has changed.

        Item * grandParent = pParent->parent();

        // If there is no grandParent then pParent isn't attacched to the view.
        // Re-sorting / re-grouping isn't needed for sure.
        if ( !grandParent )
            break; // from the for(;;) loop

        // The following function will return true if grandParent may be affected by the change.
        // If the grandParent isn't affected, we stop climbing.
        if ( !handleItemPropertyChanges( propertyChangeMask, grandParent, pParent ) )
            break; // from the for(;;) loop

        // Now we need to climb up one level and check again.
        pParent = grandParent;

    } // for(;;)
}


void ModelPrivate::attachMessageToParent( Item *pParent, MessageItem *mi )
{
    Q_ASSERT( pParent );
    Q_ASSERT( mi );

    // This function may be called to do a simple "re-sort" of the item inside the parent.
    // In that case mi->parent() is equal to pParent.
    bool oldParentWasTheSame;

    if ( mi->parent() )
    {
        Item * oldParent = mi->parent();

        // The item already had a parent and this means that we're moving it.
        oldParentWasTheSame = oldParent == pParent; // just re-sorting ?

        if ( mi->isViewable() ) // is actually
        {
            // The message is actually attached to the viewable root

            // Unfortunately we need to hack the model/view architecture
            // since it's somewhat flawed in this. At the moment of writing
            // there is simply no way to atomically move a subtree.
            // We must detach, call beginRemoveRows()/endRemoveRows(),
            // save the expanded state, save the selection, save the current item,
            // save the view position (YES! As we are removing items the view
            // will hopelessly jump around so we're just FORCED to break
            // the isolation from the view)...
            // ...*then* reattach, restore the expanded state, restore the selection,
            // restore the current item, restore the view position and pray
            // that nothing will fail in the (rather complicated) process....

            // Yet more unfortunately, while saving the expanded state might stop
            // at a certain (unexpanded) point in the tree, saving the selection
            // is hopelessly recursive down to the bare leafs.

            // Furthermore the expansion of items is a common case while selection
            // in the subtree is rare, so saving it would be a huge cost with
            // a low revenue.

            // This is why we just let the selection screw up. I hereby refuse to call
            // yet another expensive recursive function here :D

            // The current item saving can be somewhat optimized doing it once for
            // a single job step...

            if (
                    ( ( mi )->childItemCount() > 0 ) && // has children
                    mModelForItemFunctions && // the UI is not actually disconnected
                    mView->isExpanded( q->index( mi, 0 ) ) // is actually expanded
                    )
                saveExpandedStateOfSubtree( mi );
        }

        // If the parent is viewable (so mi was viewable too) then the beginRemoveRows()
        // and endRemoveRows() functions of this model will be called too.
        oldParent->takeChildItem( mModelForItemFunctions, mi );

        if ( ( !oldParentWasTheSame ) && ( oldParent != mRootItem ) )
            messageDetachedUpdateParentProperties( oldParent, mi );

    } else {
        // The item had no parent yet.
        oldParentWasTheSame = false;
    }

    // Take care of perfect / imperfect threading.
    // Items that are now perfectly threaded, but already have a different parent
    // might have been imperfectly threaded before. Remove them from the caches.
    // Items that are now imperfectly threaded must be added to the caches.
    //
    // If we're just re-sorting the item inside the same parent then the threading
    // caches don't need to be updated (since they actually depend on the parent).

    if ( !oldParentWasTheSame )
    {
        switch( mi->threadingStatus() )
        {
        case MessageItem::PerfectParentFound:
            if ( !mi->inReplyToIdMD5().isEmpty() )
                mThreadingCacheMessageInReplyToIdMD5ToMessageItem.remove( mi->inReplyToIdMD5(), mi );
            break;
        case MessageItem::ImperfectParentFound:
        case MessageItem::ParentMissing: // may be: temporary or just fallback assignment
            if ( !mi->inReplyToIdMD5().isEmpty() )
            {
                if ( !mThreadingCacheMessageInReplyToIdMD5ToMessageItem.contains( mi->inReplyToIdMD5(), mi ) )
                    mThreadingCacheMessageInReplyToIdMD5ToMessageItem.insert( mi->inReplyToIdMD5(), mi );
            }
            break;
        case MessageItem::NonThreadable: // this also happens when we do no threading at all
            // make gcc happy
            Q_ASSERT( !mThreadingCacheMessageInReplyToIdMD5ToMessageItem.contains( mi->inReplyToIdMD5(), mi ) );
            break;
        }
    }

    // Set the new parent
    mi->setParent( pParent );

    // Propagate watched and ignored status
    if (
            ( pParent->status().toQInt32() & mCachedWatchedOrIgnoredStatusBits ) && // unlikely
            ( pParent->type() == Item::Message ) // likely
            )
    {
        // the parent is either watched or ignored: propagate to the child
        if ( pParent->status().isWatched() )
        {
            int row = mInvariantRowMapper->modelInvariantIndexToModelIndexRow( mi );
            mi->setStatus( Akonadi::MessageStatus::statusWatched() );
            mStorageModel->setMessageItemStatus( mi, row, Akonadi::MessageStatus::statusWatched() );
        } else if ( pParent->status().isIgnored() )
        {
            int row = mInvariantRowMapper->modelInvariantIndexToModelIndexRow( mi );
            mi->setStatus( Akonadi::MessageStatus::statusIgnored() );
            mStorageModel->setMessageItemStatus( mi, row, Akonadi::MessageStatus::statusIgnored() );
        }
    }

    // And insert into its child list

    // If pParent is viewable then the insert/append functions will call this model's
    // beginInsertRows() and endInsertRows() functions. This is EXTREMELY
    // expensive and ugly but it's the only way with the Qt4 imposed Model/View method.
    // Dude... (citation from Lost, if it wasn't clear).

    // I'm using a macro since it does really improve readability.
    // I'm NOT using a helper function since gcc will refuse to inline some of
    // the calls because they make this function grow too much.
#define INSERT_MESSAGE_WITH_COMPARATOR( _ItemComparator ) \
    if ( ( mSortOrder->messageSortDirection() == SortOrder::Ascending ) \
    || ( pParent->type() == Item::Message ) ) \
    { \
    pParent->d_ptr->insertChildItem< _ItemComparator, true >( mModelForItemFunctions, mi ); \
} \
    else \
    { \
    pParent->d_ptr->insertChildItem< _ItemComparator, false >( mModelForItemFunctions, mi ); \
}

    // If pParent is viewable then the insertion call will also set the child state to viewable.
    // Since mi MAY have children, then this call may make them viewable.
    switch( mSortOrder->messageSorting() )
    {
    case SortOrder::SortMessagesByDateTime:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemDateComparator )
                break;
    case SortOrder::SortMessagesByDateTimeOfMostRecent:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemMaxDateComparator )
                break;
    case SortOrder::SortMessagesBySize:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemSizeComparator )
                break;
    case SortOrder::SortMessagesBySenderOrReceiver:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemSenderOrReceiverComparator )
                break;
    case SortOrder::SortMessagesBySender:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemSenderComparator )
                break;
    case SortOrder::SortMessagesByReceiver:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemReceiverComparator )
                break;
    case SortOrder::SortMessagesBySubject:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemSubjectComparator )
                break;
    case SortOrder::SortMessagesByActionItemStatus:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemActionItemStatusComparator )
                break;
    case SortOrder::SortMessagesByUnreadStatus:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemUnreadStatusComparator )
                break;
    case SortOrder::SortMessagesByImportantStatus:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemImportantStatusComparator )
                break;
    case SortOrder::SortMessagesByAttachmentStatus:
        INSERT_MESSAGE_WITH_COMPARATOR( ItemAttachmentStatusComparator )
                break;
    case SortOrder::NoMessageSorting:
        pParent->appendChildItem( mModelForItemFunctions, mi );
        break;
    default: // should never happen
        pParent->appendChildItem( mModelForItemFunctions, mi );
        break;
    }

    // Decide if we need to expand parents
    bool childNeedsExpanding = ( mi->initialExpandStatus() == Item::ExpandNeeded );

    if ( pParent->initialExpandStatus() == Item::NoExpandNeeded )
    {
        switch( mAggregation->threadExpandPolicy() )
        {
        case Aggregation::NeverExpandThreads:
            // just do nothing unless this child has children and is already marked for expansion
            if ( childNeedsExpanding )
                pParent->setInitialExpandStatus( Item::ExpandNeeded );
            break;
        case Aggregation::ExpandThreadsWithNewMessages: // No more new status. fall through to unread if it exists in config
        case Aggregation::ExpandThreadsWithUnreadMessages:
            // expand only if unread (or it has children marked for expansion)
            if ( childNeedsExpanding || !mi->status().isRead() )
                pParent->setInitialExpandStatus( Item::ExpandNeeded );
            break;
        case Aggregation::ExpandThreadsWithUnreadOrImportantMessages:
            // expand only if unread, important or todo (or it has children marked for expansion)
            // FIXME: Wouldn't it be nice to be able to test for bitmasks in MessageStatus ?
            if ( childNeedsExpanding || !mi->status().isRead() || mi->status().isImportant() || mi->status().isToAct() )
                pParent->setInitialExpandStatus( Item::ExpandNeeded );
            break;
        case Aggregation::AlwaysExpandThreads:
            // expand everything
            pParent->setInitialExpandStatus( Item::ExpandNeeded );
            break;
        default:
            // BUG
            break;
        }
    } // else it's already marked for expansion or expansion has been already executed

    // expand parent first, if possible
    if ( pParent->initialExpandStatus() == Item::ExpandNeeded )
    {
        // If UI is not disconnected and parent is viewable, go up and expand
        if ( mModelForItemFunctions && pParent->isViewable() )
        {
            // Now expand parents as needed
            Item * parentToExpand = pParent;
            while ( parentToExpand )
            {
                if ( parentToExpand == mRootItem )
                    break; // no need to set it expanded
                // parentToExpand is surely viewable (because this item is)
                if ( parentToExpand->initialExpandStatus() == Item::ExpandExecuted )
                    break;

                mView->expand( q->index( parentToExpand, 0 ) );

                parentToExpand->setInitialExpandStatus( Item::ExpandExecuted );
                parentToExpand = parentToExpand->parent();
            }
        } else {
            // It isn't viewable or UI is disconnected: climb up marking only
            Item * parentToExpand = pParent->parent();
            while ( parentToExpand )
            {
                if ( parentToExpand == mRootItem )
                    break; // no need to set it expanded
                parentToExpand->setInitialExpandStatus( Item::ExpandNeeded );
                parentToExpand = parentToExpand->parent();
            }
        }
    }

    if ( mi->isViewable() )
    {
        // mi is now viewable

        // sync subtree expanded status
        if ( childNeedsExpanding )
        {
            if ( mi->childItemCount() > 0 )
                if ( mModelForItemFunctions ) // the UI is not disconnected
                    syncExpandedStateOfSubtree( mi ); // sync the real state in the view
        }

        // apply the filter, if needed
        if ( mFilter )
        {
            Q_ASSERT( mModelForItemFunctions ); // the UI must be NOT disconnected here

            // apply the filter to subtree
            if ( applyFilterToSubtree( mi, q->index( pParent, 0 ) ) )
            {
                // mi matched, expand parents (unconditionally)
                mView->ensureDisplayedWithParentsExpanded( mi );
            }
        }
    }

    // Now we need to propagate the property changes the upper levels.

    // If we have just inserted a message inside the root then no work needs to be done:
    // no grouping is in effect and the message is already in the right place.
    if ( pParent == mRootItem )
        return;

    // If we have just removed the item from this parent and re-inserted it
    // then this operation was a simple re-sort. The code above didn't update
    // the properties when removing the item so we don't actually need
    // to make the updates back.
    if ( oldParentWasTheSame )
        return;

    // FIXME: OPTIMIZE THIS: First propagate changes THEN syncExpandedStateOfSubtree()
    //        and applyFilterToSubtree... (needs some thinking though).

    // Time to propagate up.
    propagateItemPropertiesToParent( mi );

    // Aaah.. we're done. Time for a thea ? :)
}

// FIXME: ThreadItem ?
//
// Foo Bar, Joe Thommason, Martin Rox ... Eddie Maiden                    <date of the thread>
// Title                                      <number of messages>, Last by xxx <inner status>
//
// When messages are added, mark it as dirty only (?)

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass5( ViewItemJob *job, const QTime &tStart )
{
    // In this pass we scan the group headers that are in mGroupHeadersThatNeedUpdate.
    // Empty groups get deleted while the other ones are re-sorted.
    int elapsed;

    int curIndex = job->currentIndex();

    QHash< GroupHeaderItem *, GroupHeaderItem * >::Iterator it = mGroupHeadersThatNeedUpdate.begin();
    QHash< GroupHeaderItem *, GroupHeaderItem * >::Iterator end = mGroupHeadersThatNeedUpdate.end();

    while ( it != end )
    {
        if ( ( *it )->childItemCount() == 0 )
        {
            // group with no children, kill it
            ( *it )->parent()->takeChildItem( mModelForItemFunctions, *it );
            mGroupHeaderItemHash.remove( ( *it )->label() );

            // If we were going to restore its position after the job step, well.. we can't do it anymore.
            if ( mCurrentItemToRestoreAfterViewItemJobStep == ( *it ) )
                mCurrentItemToRestoreAfterViewItemJobStep = 0;

            // bye bye
            delete *it;
        } else {
            // Group with children: probably needs re-sorting.

            // Re-sorting here is an expensive operation.
            // In fact groups have been put in the QHash above on the assumption
            // that re-sorting *might* be needed but no real (expensive) check
            // has been done yet. Also by sorting a single group we might actually
            // put the others in the right place.
            // So finally check if re-sorting is *really* needed.
            bool needsReSorting;

            // A macro really improves readability here.
#define CHECK_IF_GROUP_NEEDS_RESORTING( _ItemDateComparator ) \
    switch ( mSortOrder->groupSortDirection() ) \
            { \
    case SortOrder::Ascending: \
    needsReSorting = ( *it )->parent()->d_ptr->childItemNeedsReSorting< _ItemDateComparator, true >( *it ); \
    break; \
    case SortOrder::Descending: \
    needsReSorting = ( *it )->parent()->d_ptr->childItemNeedsReSorting< _ItemDateComparator, false >( *it ); \
    break; \
    default: /* should never happen */ \
    needsReSorting = false; \
    break; \
        }

            switch ( mSortOrder->groupSorting() )
            {
            case SortOrder::SortGroupsByDateTime:
                CHECK_IF_GROUP_NEEDS_RESORTING( ItemDateComparator )
                        break;
            case SortOrder::SortGroupsByDateTimeOfMostRecent:
                CHECK_IF_GROUP_NEEDS_RESORTING( ItemMaxDateComparator )
                        break;
            case SortOrder::SortGroupsBySenderOrReceiver:
                CHECK_IF_GROUP_NEEDS_RESORTING( ItemSenderOrReceiverComparator )
                        break;
            case SortOrder::SortGroupsBySender:
                CHECK_IF_GROUP_NEEDS_RESORTING( ItemSenderComparator )
                        break;
            case SortOrder::SortGroupsByReceiver:
                CHECK_IF_GROUP_NEEDS_RESORTING( ItemReceiverComparator )
                        break;
            case SortOrder::NoGroupSorting:
                needsReSorting = false;
                break;
            default:
                // Should never happen... just assume re-sorting is not needed
                needsReSorting = false;
                break;
            }

            if ( needsReSorting )
                attachGroup( *it ); // it will first detach and then re-attach in the proper place
        }

        it = mGroupHeadersThatNeedUpdate.erase( it );

        curIndex++;

        // FIXME: In fact a single update is likely to manipulate
        //        a subtree with a LOT of messages inside. If interactivity is favored
        //        we should check the time really more often.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( it != mGroupHeadersThatNeedUpdate.end() )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }

    }

    return ViewItemJobCompleted;
}



ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass4( ViewItemJob *job, const QTime &tStart )
{
    // In this pass we scan mUnassignedMessageListForPass4 which now
    // contains both items with parents and items without parents.
    // We scan mUnassignedMessageList for messages without parent (the ones that haven't been
    // attacched to the viewable tree yet) and find a suitable group for them. Then we simply
    // clear mUnassignedMessageList.

    // We call this pass "Grouping"

    int elapsed;

    int curIndex = job->currentIndex();
    int endIndex = job->endIndex();

    while ( curIndex <= endIndex )
    {
        MessageItem * mi = mUnassignedMessageListForPass4[curIndex];
        if ( !mi->parent() )
        {
            // Unassigned item: thread leader, insert into the proper group.
            // Locate the group (or root if no grouping requested)
            attachMessageToGroupHeader( mi );
        } else {
            // A parent was already assigned in Pass3: we have nothing to do here
        }
        curIndex++;

        // FIXME: In fact a single call to attachMessageToGroupHeader() is likely to manipulate
        //        a subtree with a LOT of messages inside. If interactivity is favored
        //        we should check the time really more often.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    mUnassignedMessageListForPass4.clear();
    return ViewItemJobCompleted;
}

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass3( ViewItemJob *job, const QTime &tStart )
{
    // In this pass we scan the mUnassignedMessageListForPass3 and try to do construct the threads
    // by using subject based threading. If subject based threading is not in effect then
    // this pass turns to a nearly-no-op: at the end of Pass2 we have swapped the lists
    // and mUnassignedMessageListForPass3 is actually empty.

    // We don't shrink the mUnassignedMessageListForPass3 for two reasons:
    // - It would mess up this chunked algorithm by shifting indexes
    // - mUnassignedMessageList is a QList which is basically an array. It's faster
    //   to traverse an array of N entries than to remove K>0 entries one by one and
    //   to traverse the remaining N-K entries.

    int elapsed;

    int curIndex = job->currentIndex();
    int endIndex = job->endIndex();

    while ( curIndex <= endIndex )
    {
        // If we're here, then threading is requested for sure.
        MessageItem * mi = mUnassignedMessageListForPass3[curIndex];
        if ( ( !mi->parent() ) || ( mi->threadingStatus() == MessageItem::ParentMissing ) )
        {
            // Parent is missing (either "physically" with the item being not attacched or "logically"
            // with the item being attacched to a group or directly to the root.
            if ( mi->subjectIsPrefixed() )
            {
                // We can try to guess it
                MessageItem * mparent = guessMessageParent( mi );

                if ( mparent )
                {
                    // imperfect parent found
                    if ( mi->isViewable() )
                    {
                        // mi was already viewable, we're just trying to re-parent it better...
                        attachMessageToParent( mparent, mi );
                        if ( !mparent->isViewable() )
                        {
                            // re-attach it immediately (so current item is not lost)
                            MessageItem * topmost = mparent->topmostMessage();
                            Q_ASSERT( !topmost->parent() ); // groups are always viewable!
                            topmost->setThreadingStatus( MessageItem::ParentMissing );
                            attachMessageToGroupHeader( topmost );
                        }
                    } else {
                        // mi wasn't viewable yet.. no need to attach parent
                        attachMessageToParent( mparent, mi );
                    }
                    // and we're done for now
                } else {
                    // so parent not found, (threadingStatus() is either MessageItem::ParentMissing or MessageItem::NonThreadable)
                    Q_ASSERT( ( mi->threadingStatus() == MessageItem::ParentMissing ) || ( mi->threadingStatus() == MessageItem::NonThreadable ) );
                    mUnassignedMessageListForPass4.append( mi ); // this is ~O(1)
                    // and wait for Pass4
                }
            } else {
                // can't guess the parent as the subject isn't prefixed
                Q_ASSERT( ( mi->threadingStatus() == MessageItem::ParentMissing ) || ( mi->threadingStatus() == MessageItem::NonThreadable ) );
                mUnassignedMessageListForPass4.append( mi ); // this is ~O(1)
                // and wait for Pass4
            }
        } else {
            // Has a parent: either perfect parent already found or non threadable.
            // Since we don't end here if mi has status of parent missing then mi must not have imperfect parent.
            Q_ASSERT( mi->threadingStatus() != MessageItem::ImperfectParentFound );
            Q_ASSERT( mi->isViewable() );
        }

        curIndex++;

        // FIXME: In fact a single call to attachMessageToGroupHeader() is likely to manipulate
        //        a subtree with a LOT of messages inside. If interactivity is favored
        //        we should check the time really more often.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    mUnassignedMessageListForPass3.clear();
    return ViewItemJobCompleted;
}

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass2( ViewItemJob *job, const QTime &tStart )
{
    // In this pass we scan the mUnassignedMessageList and try to do construct the threads.
    // If some thread leader message got attacched to the viewable tree in Pass1Fill then
    // we'll also attach all of its children too. The thread leaders we were unable
    // to attach in Pass1Fill and their children (which we find here) will make it to the small Pass3

    // We don't shrink the mUnassignedMessageList for two reasons:
    // - It would mess up this chunked algorithm by shifting indexes
    // - mUnassignedMessageList is a QList which is basically an array. It's faster
    //   to traverse an array of N entries than to remove K>0 entries one by one and
    //   to traverse the remaining N-K entries.

    // We call this pass "Threading"

    int elapsed;

    int curIndex = job->currentIndex();
    int endIndex = job->endIndex();

    while ( curIndex <= endIndex )
    {
        // If we're here, then threading is requested for sure.
        MessageItem * mi = mUnassignedMessageListForPass2[curIndex];
        // The item may or may not have a parent.
        // If it has no parent or it has a temporary one (mi->parent() && mi->threadingStatus() == MessageItem::ParentMissing)
        // then we attempt to (re-)thread it. Otherwise we just do nothing (the job has already been done by the previous steps).
        if ( ( !mi->parent() ) || ( mi->threadingStatus() == MessageItem::ParentMissing ) )
        {
            MessageItem * mparent = findMessageParent( mi );

            if ( mparent )
            {
                // parent found, either perfect or imperfect
                if ( mi->isViewable() )
                {
                    // mi was already viewable, we're just trying to re-parent it better...
                    attachMessageToParent( mparent, mi );
                    if ( !mparent->isViewable() )
                    {
                        // re-attach it immediately (so current item is not lost)
                        MessageItem * topmost = mparent->topmostMessage();
                        Q_ASSERT( !topmost->parent() ); // groups are always viewable!
                        topmost->setThreadingStatus( MessageItem::ParentMissing );
                        attachMessageToGroupHeader( topmost );
                    }
                } else {
                    // mi wasn't viewable yet.. no need to attach parent
                    attachMessageToParent( mparent, mi );
                }
                // and we're done for now
            } else {
                // so parent not found, (threadingStatus() is either MessageItem::ParentMissing or MessageItem::NonThreadable)
                switch( mi->threadingStatus() )
                {
                case MessageItem::ParentMissing:
                    if ( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject )
                    {
                        // parent missing but still can be found in Pass3
                        mUnassignedMessageListForPass3.append( mi ); // this is ~O(1)
                    } else {
                        // We're not doing subject based threading: will never be threaded, go straight to Pass4
                        mUnassignedMessageListForPass4.append( mi ); // this is ~O(1)
                    }
                    break;
                case MessageItem::NonThreadable:
                    // will never be threaded, go straight to Pass4
                    mUnassignedMessageListForPass4.append( mi ); // this is ~O(1)
                    break;
                default:
                    // a bug for sure
                    kWarning() << "ERROR: Invalid message threading status returned by findMessageParent()!";
                    Q_ASSERT( false );
                    break;
                }
            }
        } else {
            // Has a parent: either perfect parent already found or non threadable.
            // Since we don't end here if mi has status of parent missing then mi must not have imperfect parent.
            Q_ASSERT( mi->threadingStatus() != MessageItem::ImperfectParentFound );
            if ( !mi->isViewable() )
            {
                kWarning() << "Non viewable message " << mi << " subject " << mi->subject().toUtf8().data();
                Q_ASSERT( mi->isViewable() );
            }
        }

        curIndex++;

        // FIXME: In fact a single call to attachMessageToGroupHeader() is likely to manipulate
        //        a subtree with a LOT of messages inside. If interactivity is favored
        //        we should check the time really more often.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    mUnassignedMessageListForPass2.clear();
    return ViewItemJobCompleted;
}

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass1Fill( ViewItemJob *job, const QTime &tStart )
{
    // In this pass we scan the a contiguous region of the underlying storage (that is
    // assumed to be FLAT) and create the corresponding MessageItem objects.
    // The deal is to show items to the user as soon as possible so in this pass we
    // *TRY* to attach them to the viewable tree (which is rooted on mRootItem).
    // Messages we're unable to attach for some reason (mainly due to threading) get appended
    // to mUnassignedMessageList and wait for Pass2.

    // We call this pass "Processing"

    int elapsed;

    // Should we use the receiver or the sender field for sorting ?
    bool bUseReceiver = mStorageModelContainsOutboundMessages;

    // The begin storage index of our work
    int curIndex = job->currentIndex();
    // The end storage index of our work.
    int endIndex = job->endIndex();

    unsigned long msgToSelect = mPreSelectionMode == PreSelectLastSelected ? mStorageModel->preSelectedMessage() : 0;

    MessageItem * mi = 0;

    while( curIndex <= endIndex )
    {
        // Create the message item with no parent: we'll set it later
        if ( !mi )
        {
            mi = new MessageItem();
        } else {
            // a MessageItem discarded by a previous iteration: reuse it.
            Q_ASSERT( mi->parent() == 0 );
        }

        if ( !mStorageModel->initializeMessageItem( mi, curIndex, bUseReceiver ) )
        {
            // ugh
            kWarning() << "Fill of the MessageItem at storage row index " << curIndex << " failed";
            curIndex++;
            continue;
        }

        // If we're supposed to pre-select a specific message, check if it's this one.
        if ( msgToSelect != 0 && msgToSelect == mi->uniqueId() ) {
            // Found, it's this one.
            // But actually it's not viewable (so not selectable). We must wait
            // until the end of the job to be 100% sure. So here we just translate
            // the unique id to a MessageItem pointer and wait.
            mLastSelectedMessageInFolder = mi;
            msgToSelect = 0; // already found, don't bother checking anymore
        }

        // Update the newest/oldest message, since we might be supposed to select those later
        if ( !mOldestItem || mOldestItem->date() > mi->date() ) {
            mOldestItem = mi;
        }
        if ( !mNewestItem || mNewestItem->date() < mi->date() ) {
            mNewestItem = mi;
        }

        // Ok.. it passed the initial checks: we will not be discarding it.
        // Make this message item an invariant index to the underlying model storage.
        mInvariantRowMapper->createModelInvariantIndex( curIndex, mi );


        // Attempt to do threading as soon as possible (to display items to the user)
        if ( mAggregation->threading() != Aggregation::NoThreading )
        {
            // Threading is requested

            // Fetch the data needed for proper threading
            // Add the item to the threading caches

            switch( mAggregation->threading() )
            {
            case Aggregation::PerfectReferencesAndSubject:
                mStorageModel->fillMessageItemThreadingData( mi, curIndex, StorageModel::PerfectThreadingReferencesAndSubject );

                // We also need to build the subject-based threading cache
                addMessageToSubjectBasedThreadingCache( mi );
                break;
            case Aggregation::PerfectAndReferences:
                mStorageModel->fillMessageItemThreadingData( mi, curIndex, StorageModel::PerfectThreadingPlusReferences );
                break;
            default:
                mStorageModel->fillMessageItemThreadingData( mi, curIndex, StorageModel::PerfectThreadingOnly );
                break;
            }

            // Perfect/References threading cache
            mThreadingCacheMessageIdMD5ToMessageItem.insert( mi->messageIdMD5(), mi );

            // Check if this item is a perfect parent for some imperfectly threaded
            // message (that is actually attacched to it, but not necessairly to the
            // viewable root). If it is, then remove the imperfect child from its
            // current parent rebuild the hierarchy on the fly.

            bool needsImmediateReAttach = false;

            if ( mThreadingCacheMessageInReplyToIdMD5ToMessageItem.count() > 0 ) // unlikely
            {
                QList< MessageItem * > lImperfectlyThreaded = mThreadingCacheMessageInReplyToIdMD5ToMessageItem.values( mi->messageIdMD5() );
                if ( !lImperfectlyThreaded.isEmpty() )
                {
                    // must move all of the items in the perfect parent
                    QList< MessageItem * >::ConstIterator end( lImperfectlyThreaded.constEnd() );
                    for ( QList< MessageItem * >::ConstIterator it = lImperfectlyThreaded.constBegin(); it != end; ++it )
                    {
                        Q_ASSERT( ( *it )->parent() );
                        Q_ASSERT( ( *it )->parent() != mi );

                        if ( !( ( (*it)->threadingStatus() == MessageItem::ImperfectParentFound ) ||
                                ( (*it)->threadingStatus() == MessageItem::ParentMissing ) ) ) {
                            kError() << "Got message " << (*it) << " with threading status" << (*it)->threadingStatus();
                            Q_ASSERT_X( false, "ModelPrivate::viewItemJobStepInternalForJobPass1Fill", "Wrong threading status" );
                        }

                        // If the item was already attached to the view then
                        // re-attach it immediately. This will avoid a message
                        // being displayed for a short while in the view and then
                        // disappear until a perfect parent isn't found.
                        if ( ( *it )->isViewable() )
                            needsImmediateReAttach = true;

                        ( *it )->setThreadingStatus( MessageItem::PerfectParentFound );
                        attachMessageToParent( mi, *it );
                    }
                }
            }

            // FIXME: Might look by "References" too, here... (?)

            // Attempt to do threading with anything we already have in caches until now
            // Note that this is likely to work since thread-parent messages tend
            // to come before thread-children messages in the folders (simply because of
            // date of arrival).

            Item * pParent;

            // First of all try to find a "perfect parent", that is the message for that
            // we have the ID in the "In-Reply-To" field. This is actually done by using
            // MD5 caches of the message ids because of speed. Collisions are very unlikely.

            const QByteArray md5 = mi->inReplyToIdMD5();

            if ( !md5.isEmpty() )
            {
                // Have an In-Reply-To field MD5.
                // In well behaved mailing lists 70% of the threadable messages get a parent here :)
                pParent = mThreadingCacheMessageIdMD5ToMessageItem.value( md5, 0 );

                if( pParent ) // very likely
                {
                    // Take care of self-referencing (which is always possible)
                    // and circular In-Reply-To reference loops which are possible
                    // in case this item was found to be a perfect parent for some
                    // imperfectly threaded message just above.
                    if (
                            ( mi == pParent ) ||              // self referencing message
                            (
                                ( mi->childItemCount() > 0 ) && // mi already has children, this is fast to determine
                                pParent->hasAncestor( mi )      // pParent is in the mi's children tree
                                )
                            )
                    {
                        // Bad, bad message.. it has In-Reply-To equal to Message-Id
                        // or it's in a circular In-Reply-To reference loop.
                        // Will wait for Pass2 with References-Id only
                        kWarning() << "Circular In-Reply-To reference loop detected in the message tree";
                        mUnassignedMessageListForPass2.append( mi );
                    } else {
                        // wow, got a perfect parent for this message!
                        mi->setThreadingStatus( MessageItem::PerfectParentFound );
                        attachMessageToParent( pParent, mi );
                        // we're done with this message (also for Pass2)
                    }
                } else {
                    // got no parent
                    // will have to wait Pass2
                    mUnassignedMessageListForPass2.append( mi );
                }
            } else {
                // No In-Reply-To header.

                bool mightHaveOtherMeansForThreading;

                switch( mAggregation->threading() )
                {
                case Aggregation::PerfectReferencesAndSubject:
                    mightHaveOtherMeansForThreading = mi->subjectIsPrefixed() || !mi->referencesIdMD5().isEmpty();
                    break;
                case Aggregation::PerfectAndReferences:
                    mightHaveOtherMeansForThreading = !mi->referencesIdMD5().isEmpty();
                    break;
                case Aggregation::PerfectOnly:
                    mightHaveOtherMeansForThreading = false;
                    break;
                default:
                    // BUG: there shouldn't be other values (NoThreading is excluded in an upper branch)
                    Q_ASSERT( false );
                    mightHaveOtherMeansForThreading = false; // make gcc happy
                    break;
                }

                if ( mightHaveOtherMeansForThreading )
                {
                    // We might have other means for threading this message, wait until Pass2
                    mUnassignedMessageListForPass2.append( mi );
                } else {
                    // No other means for threading this message. This is either
                    // a standalone message or a thread leader.
                    // If there is no grouping in effect or thread leaders are just the "topmost"
                    // messages then we might be done with this one.
                    if (
                            ( mAggregation->grouping() == Aggregation::NoGrouping ) ||
                            ( mAggregation->threadLeader() == Aggregation::TopmostMessage )
                            )
                    {
                        // We're done with this message: it will be surely either toplevel (no grouping in effect)
                        // or a thread leader with a well defined group. Do it :)
                        //kDebug() << "Setting message status from " << mi->threadingStatus() << " to non threadable (1) " << mi;
                        mi->setThreadingStatus( MessageItem::NonThreadable );
                        // Locate the parent group for this item
                        attachMessageToGroupHeader( mi );
                        // we're done with this message (also for Pass2)
                    } else {
                        // Threads belong to the most recent message in the thread. This means
                        // that we have to wait until Pass2 or Pass3 to assign a group.
                        mUnassignedMessageListForPass2.append( mi );
                    }
                }
            }

            if ( needsImmediateReAttach && !mi->isViewable() )
            {
                // The item gathered previously viewable children. They must be immediately
                // re-shown. So this item must currently be attached to the view.
                // This is a temporary measure: it will be probably still moved.
                MessageItem * topmost = mi->topmostMessage();
                Q_ASSERT( topmost->threadingStatus() == MessageItem::ParentMissing );
                attachMessageToGroupHeader( topmost );
            }

        } else {
            // else no threading requested: we don't even need Pass2
            // set not threadable status (even if it might be not true, but in this mode we don't care)
            //kDebug() << "Setting message status from " << mi->threadingStatus() << " to non threadable (2) " << mi;
            mi->setThreadingStatus( MessageItem::NonThreadable );
            // locate the parent group for this item
            if ( mAggregation->grouping() == Aggregation::NoGrouping )
                attachMessageToParent( mRootItem, mi ); // no groups requested, attach directly to root
            else
                attachMessageToGroupHeader( mi );
            // we're done with this message (also for Pass2)
        }

        mi = 0; // this item was pushed somewhere, create a new one at next iteration
        curIndex++;

        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    if ( mi )
        delete mi;
    return ViewItemJobCompleted;
}

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass1Cleanup( ViewItemJob *job, const QTime &tStart )
{
    Q_ASSERT( mModelForItemFunctions ); // UI must be not disconnected here
    // In this pass we remove the MessageItem objects that are present in the job
    // and put their children in the unassigned message list.

    // Note that this list in fact contains MessageItem objects (we need dynamic_cast<>).
    QList< ModelInvariantIndex * > * invalidatedMessages = job->invariantIndexList();

    // We don't shrink the invalidatedMessages because it's basically an array.
    // It's faster to traverse an array of N entries than to remove K>0 entries
    // one by one and to traverse the remaining N-K entries.

    int elapsed;

    // The begin index of our work
    int curIndex = job->currentIndex();
    // The end index of our work.
    int endIndex = job->endIndex();

    if ( curIndex == job->startIndex() )
        Q_ASSERT( mOrphanChildrenHash.isEmpty() );

    while( curIndex <= endIndex )
    {
        // Get the underlying storage message data...
        MessageItem * dyingMessage = dynamic_cast< MessageItem * >( invalidatedMessages->at( curIndex ) );
        // This MUST NOT be null (otherwise we have a bug somewhere in this file).
        Q_ASSERT( dyingMessage );

        // If we were going to pre-select this message but we were interrupted
        // *before* it was actually made viewable, we just clear the pre-selection pointer
        // and unique id (abort pre-selection).
        if ( dyingMessage == mLastSelectedMessageInFolder )
        {
            mLastSelectedMessageInFolder = 0;
            mPreSelectionMode = PreSelectNone;
        }

        // remove the message from any pending user job
        if ( mPersistentSetManager )
        {
            mPersistentSetManager->removeMessageItemFromAllSets( dyingMessage );
            if ( mPersistentSetManager->setCount() < 1 )
            {
                delete mPersistentSetManager;
                mPersistentSetManager = 0;
            }
        }

        if ( dyingMessage->parent() )
        {
            // Handle saving the current selection: if this item was the current before the step
            // then zero it out. We have killed it and it's OK for the current item to change.

            if ( dyingMessage == mCurrentItemToRestoreAfterViewItemJobStep )
            {
                Q_ASSERT( dyingMessage->isViewable() );
                // Try to select the item below the removed one as it helps in doing a "readon" of emails:
                // you read a message, decide to delete it and then go to the next.
                // Qt tends to select the message above the removed one instead (this is a hardcoded logic in
                // QItemSelectionModelPrivate::_q_rowsAboutToBeRemoved()).
                mCurrentItemToRestoreAfterViewItemJobStep = mView->messageItemAfter( dyingMessage, MessageTypeAny, false );

                if ( !mCurrentItemToRestoreAfterViewItemJobStep )
                {
                    // There is no item below. Try the item above.
                    // We still do it better than qt which tends to find the *thread* above
                    // instead of the item above.
                    mCurrentItemToRestoreAfterViewItemJobStep = mView->messageItemBefore( dyingMessage, MessageTypeAny, false );
                }

                Q_ASSERT( (!mCurrentItemToRestoreAfterViewItemJobStep) || mCurrentItemToRestoreAfterViewItemJobStep->isViewable() );
            }

            if (
                    dyingMessage->isViewable() &&
                    ( ( dyingMessage )->childItemCount() > 0 ) && // has children
                    mView->isExpanded( q->index( dyingMessage, 0 ) ) // is actually expanded
                    )
                saveExpandedStateOfSubtree( dyingMessage );

            Item * oldParent = dyingMessage->parent();
            oldParent->takeChildItem( q, dyingMessage );

            // FIXME: This can generate many message movements.. it would be nicer
            //        to start from messages that are higher in the hierarchy so
            //        we would need to move less stuff above.

            if ( oldParent != mRootItem )
                messageDetachedUpdateParentProperties( oldParent, dyingMessage );

            // We might have already removed its parent from the view, so it
            // might already be in the orphan child hash...
            if ( dyingMessage->threadingStatus() == MessageItem::ParentMissing )
                mOrphanChildrenHash.remove( dyingMessage ); // this can turn to a no-op (dyingMessage not present in fact)

        } else {
            // The dying message had no parent: this should happen only if it's already an orphan

            Q_ASSERT( dyingMessage->threadingStatus() == MessageItem::ParentMissing );
            Q_ASSERT( mOrphanChildrenHash.contains( dyingMessage ) );
            Q_ASSERT( dyingMessage != mCurrentItemToRestoreAfterViewItemJobStep );

            mOrphanChildrenHash.remove( dyingMessage );
        }

        if ( mAggregation->threading() != Aggregation::NoThreading )
        {
            // Threading is requested: remove the message from threading caches.

            // Remove from the cache of potential parent items
            mThreadingCacheMessageIdMD5ToMessageItem.remove( dyingMessage->messageIdMD5() );

            // If we also have a cache for subject-based threading then remove the message from there too
            if( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject )
                removeMessageFromSubjectBasedThreadingCache( dyingMessage );

            // If this message wasn't perfectly parented then it might still be in another cache.
            switch( dyingMessage->threadingStatus() )
            {
            case MessageItem::ImperfectParentFound:
            case MessageItem::ParentMissing:
                if ( !dyingMessage->inReplyToIdMD5().isEmpty() )
                    mThreadingCacheMessageInReplyToIdMD5ToMessageItem.remove( dyingMessage->inReplyToIdMD5() );
                break;
            default:
                Q_ASSERT( !mThreadingCacheMessageInReplyToIdMD5ToMessageItem.contains( dyingMessage->inReplyToIdMD5(), dyingMessage ) );
                // make gcc happy
                break;
            }
        }

        while ( Item * childItem = dyingMessage->firstChildItem() )
        {
            MessageItem * childMessage = dynamic_cast< MessageItem * >( childItem );
            Q_ASSERT( childMessage );

            dyingMessage->takeChildItem( q, childMessage );

            if ( mAggregation->threading() != Aggregation::NoThreading )
            {
                if ( childMessage->threadingStatus() == MessageItem::PerfectParentFound )
                {
                    // If the child message was perfectly parented then now it had
                    // lost its perfect parent. Add to the cache of imperfectly parented.
                    if ( !childMessage->inReplyToIdMD5().isEmpty() )
                    {
                        Q_ASSERT( !mThreadingCacheMessageInReplyToIdMD5ToMessageItem.contains( childMessage->inReplyToIdMD5(), childMessage ) );
                        mThreadingCacheMessageInReplyToIdMD5ToMessageItem.insert( childMessage->inReplyToIdMD5(), childMessage );
                    }
                }
            }

            // Parent is gone
            childMessage->setThreadingStatus( MessageItem::ParentMissing );

            // If the child (or any message in its subtree) is going to be selected,
            // then we must immediately reattach it to a temporary group in order for the
            // selection to be preserved across multiple steps. Otherwise we could end
            // with the child-to-be-selected being non viewable at the end
            // of the view job step. Attach to a temporary group.
            if (
                    // child is going to be re-selected
                    ( childMessage == mCurrentItemToRestoreAfterViewItemJobStep ) ||
                    (
                        // there is a message that is going to be re-selected
                        mCurrentItemToRestoreAfterViewItemJobStep &&
                        // that message is in the childMessage subtree
                        mCurrentItemToRestoreAfterViewItemJobStep->hasAncestor( childMessage )
                        )
                    )
            {
                attachMessageToGroupHeader( childMessage );

                Q_ASSERT( childMessage->isViewable() );
            }

            mOrphanChildrenHash.insert( childMessage, childMessage );
        }

        if ( mNewestItem == dyingMessage ) {
            mNewestItem = 0;
        }
        if ( mOldestItem == dyingMessage ) {
            mOldestItem = 0;
        }

        delete dyingMessage;

        curIndex++;

        // FIXME: Maybe we should check smaller steps here since the
        //        code above can generate large message tree movements
        //        for each single item we sweep in the invalidatedMessages list.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    // We looped over the entire deleted message list.

    job->setCurrentIndex( endIndex + 1 );

    // A quick last cleaning pass: this is usually very fast so we don't have a real
    // Pass enumeration for it. We just include it as trailer of Pass1Cleanup to be executed
    // when job->currentIndex() > job->endIndex();

    // We move all the messages from the orphan child hash to the unassigned message
    // list and get them ready for the standard Pass2.

    QHash< MessageItem *, MessageItem * >::Iterator it = mOrphanChildrenHash.begin();
    QHash< MessageItem *, MessageItem * >::Iterator end = mOrphanChildrenHash.end();

    curIndex = 0;

    while ( it != end )
    {
        mUnassignedMessageListForPass2.append( *it );

        it = mOrphanChildrenHash.erase( it );

        // This is still interruptible

        curIndex++;

        // FIXME: We could take "larger" steps here
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( it != mOrphanChildrenHash.end() )
                    return ViewItemJobInterrupted;
            }
        }
    }

    return ViewItemJobCompleted;
}


ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJobPass1Update( ViewItemJob *job, const QTime &tStart )
{
    Q_ASSERT( mModelForItemFunctions ); // UI must be not disconnected here

    // In this pass we simply update the MessageItem objects that are present in the job.

    // Note that this list in fact contains MessageItem objects (we need dynamic_cast<>).
    QList< ModelInvariantIndex * > * messagesThatNeedUpdate = job->invariantIndexList();

    // We don't shrink the messagesThatNeedUpdate because it's basically an array.
    // It's faster to traverse an array of N entries than to remove K>0 entries
    // one by one and to traverse the remaining N-K entries.

    int elapsed;

    // The begin index of our work
    int curIndex = job->currentIndex();
    // The end index of our work.
    int endIndex = job->endIndex();

    while( curIndex <= endIndex )
    {
        // Get the underlying storage message data...
        MessageItem * message = dynamic_cast< MessageItem * >( messagesThatNeedUpdate->at( curIndex ) );
        // This MUST NOT be null (otherwise we have a bug somewhere in this file).
        Q_ASSERT( message );

        int row = mInvariantRowMapper->modelInvariantIndexToModelIndexRow( message );

        if ( row < 0 )
        {
            // Must have been invalidated (so it's basically about to be deleted)
            Q_ASSERT( !message->isValid() );
            // Skip it here.
            curIndex++;
            continue;
        }

        time_t prevDate = message->date();
        time_t prevMaxDate = message->maxDate();
        bool toDoStatus = message->status().isToAct();
        bool prevUnreadStatus = !message->status().isRead();
        bool prevImportantStatus = message->status().isImportant();

        // The subject based threading cache is sorted by date: we must remove
        // the item and re-insert it since updateMessageItemData() may change the date too.
        if( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject )
            removeMessageFromSubjectBasedThreadingCache( message );

        // Do update
        mStorageModel->updateMessageItemData( message, row );
        QModelIndex idx = q->index( message, 0 );
        emit q->dataChanged( idx, idx );

        // Reinsert the item to the cache, if needed
        if( mAggregation->threading() == Aggregation::PerfectReferencesAndSubject )
            addMessageToSubjectBasedThreadingCache( message );


        int propertyChangeMask = 0;

        if ( prevDate != message->date() )
            propertyChangeMask |= DateChanged;
        if ( prevMaxDate != message->maxDate() )
            propertyChangeMask |= MaxDateChanged;
        if ( toDoStatus != message->status().isToAct() )
            propertyChangeMask |= ActionItemStatusChanged;
        if ( prevUnreadStatus != ( !message->status().isRead() ) )
            propertyChangeMask |= UnreadStatusChanged;
        if ( prevImportantStatus != ( !message->status().isImportant() ) )
            propertyChangeMask |= ImportantStatusChanged;

        if ( propertyChangeMask )
        {
            // Some message data has changed
            // now we need to handle the changes that might cause re-grouping/re-sorting
            // and propagate them to the parents.

            Item * pParent = message->parent();

            if ( pParent && ( pParent != mRootItem ) )
            {
                // The following function will return true if itemParent may be affected by the change.
                // If the itemParent isn't affected, we stop climbing.
                if ( handleItemPropertyChanges( propertyChangeMask, pParent, message ) )
                {
                    Q_ASSERT( message->parent() ); // handleItemPropertyChanges() must never leave an item detached

                    // Note that actually message->parent() may be different than pParent since
                    // handleItemPropertyChanges() may have re-grouped it.

                    // Time to propagate up.
                    propagateItemPropertiesToParent( message );
                }
            } // else there is no parent so the item isn't attached to the view: re-grouping/re-sorting not needed.
        } // else message data didn't change an there is nothing interesting to do

        // (re-)apply the filter, if needed
        if ( mFilter && message->isViewable() )
        {
            // In all the other cases we (re-)apply the filter to the topmost subtree that this message is in.
            Item * pTopMostNonRoot = message->topmostNonRoot();

            Q_ASSERT( pTopMostNonRoot );
            Q_ASSERT( pTopMostNonRoot != mRootItem );
            Q_ASSERT( pTopMostNonRoot->parent() == mRootItem );

            // FIXME: The call below works, but it's expensive when we are updating
            //        a lot of items with filtering enabled. This is because the updated
            //        items are likely to be in the same subtree which we then filter multiple times.
            //        A point for us is that when filtering there shouldn't be really many
            //        items in the view so the user isn't going to update a lot of them at once...
            //        Well... anyway, the alternative would be to write yet another
            //        specialized routine that would update only the "message" item
            //        above and climb up eventually hiding parents (without descending the sibling subtrees again).
            //        If people complain about performance in this particular case I'll consider that solution.

            applyFilterToSubtree( pTopMostNonRoot, QModelIndex() );

        } // otherwise there is no filter or the item isn't viewable: very likely
        // left detached while propagating property changes. Will filter it
        // on reattach.

        // Done updating this message

        curIndex++;

        // FIXME: Maybe we should check smaller steps here since the
        //        code above can generate large message tree movements
        //        for each single item we sweep in the messagesThatNeedUpdate list.
        if ( ( curIndex % mViewItemJobStepMessageCheckCount ) == 0 )
        {
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( curIndex <= endIndex )
                {
                    job->setCurrentIndex( curIndex );
                    return ViewItemJobInterrupted;
                }
            }
        }
    }

    return ViewItemJobCompleted;
}


ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternalForJob( ViewItemJob *job, const QTime &tStart )
{
    // This function does a timed chunk of work for a single Fill View job.
    // It attempts to process messages until a timeout forces it to return to the caller.

    // A macro would improve readability here but since this is a good point
    // to place debugger breakpoints then we need it explicited.
    // A (template) helper would need to pass many parameters and would not be inlined...

    int elapsed;

    if ( job->currentPass() == ViewItemJob::Pass1Fill )
    {
        // We're in Pass1Fill of the job.
        switch ( viewItemJobStepInternalForJobPass1Fill( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 1 has been completed
            // # TODO: Refactor this, make it virtual or whatever, but switch == bad, code duplication etc
            job->setCurrentPass( ViewItemJob::Pass2 );
            job->setStartIndex( 0 );
            job->setEndIndex( mUnassignedMessageListForPass2.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                return ViewItemJobInterrupted;
            } // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    } else if ( job->currentPass() == ViewItemJob::Pass1Cleanup )
    {
        // We're in Pass1Cleanup of the job.
        switch ( viewItemJobStepInternalForJobPass1Cleanup( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 1 has been completed
            job->setCurrentPass( ViewItemJob::Pass2 );
            job->setStartIndex( 0 );
            job->setEndIndex( mUnassignedMessageListForPass2.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                return ViewItemJobInterrupted;
            } // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    } else if ( job->currentPass() == ViewItemJob::Pass1Update )
    {
        // We're in Pass1Update of the job.
        switch ( viewItemJobStepInternalForJobPass1Update( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 1 has been completed
            // Since Pass2, Pass3 and Pass4 are empty for an Update operation
            // we simply skip them. (TODO: Triple-verify this assertion...).
            job->setCurrentPass( ViewItemJob::Pass5 );
            job->setStartIndex( 0 );
            job->setEndIndex( mGroupHeadersThatNeedUpdate.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                return ViewItemJobInterrupted;
            } // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    }

    // Pass1Fill/Pass1Cleanup/Pass1Update has been already completed.

    if ( job->currentPass() == ViewItemJob::Pass2 )
    {
        // We're in Pass2 of the job.
        switch ( viewItemJobStepInternalForJobPass2( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 2 has been completed
            job->setCurrentPass( ViewItemJob::Pass3 );
            job->setStartIndex( 0 );
            job->setEndIndex( mUnassignedMessageListForPass3.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
                return ViewItemJobInterrupted;
            // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    }

    if ( job->currentPass() == ViewItemJob::Pass3 )
    {
        // We're in Pass3 of the job.
        switch ( viewItemJobStepInternalForJobPass3( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 3 has been completed
            job->setCurrentPass( ViewItemJob::Pass4 );
            job->setStartIndex( 0 );
            job->setEndIndex( mUnassignedMessageListForPass4.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
                return ViewItemJobInterrupted;
            // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    }

    if ( job->currentPass() == ViewItemJob::Pass4 )
    {
        // We're in Pass4 of the job.
        switch ( viewItemJobStepInternalForJobPass4( job, tStart ) )
        {
        case ViewItemJobInterrupted:
            // current job interrupted by timeout: propagate status to caller
            return ViewItemJobInterrupted;
            break;
        case ViewItemJobCompleted:
            // pass 4 has been completed
            job->setCurrentPass( ViewItemJob::Pass5 );
            job->setStartIndex( 0 );
            job->setEndIndex( mGroupHeadersThatNeedUpdate.count() - 1 );
            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
                return ViewItemJobInterrupted;
            // else proceed with the next pass
            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";;
            Q_ASSERT( false );
            break;
        }
    }

    // Pass4 has been already completed. Proceed to Pass5.
    return viewItemJobStepInternalForJobPass5( job, tStart );
}

#ifdef KDEPIM_FOLDEROPEN_PROFILE

// Namespace to collect all the vars and functions for KDEPIM_FOLDEROPEN_PROFILE
namespace Stats {

// Number of existing jobs/passes
static const int numberOfPasses = ViewItemJob::LastIndex;

// The pass in the last call of viewItemJobStepInternal(), used to detect when
// a new pass starts
static int lastPass = -1;

// Total number of messages in the folder
static int totalMessages;

// Per-Job data
static int numElements[numberOfPasses];
static int totalTime[numberOfPasses];
static int chunks[numberOfPasses];

// Time, in msecs for some special operations
static int expandingTreeTime;
static int layoutChangeTime;

// Descriptions of the job, for nicer debug output
static const char *jobDescription[numberOfPasses] = {
    "Creating items from messages and simple threading",
    "Removing messages",
    "Updating messages",
    "Additional Threading",
    "Subject-Based threading",
    "Grouping",
    "Group resorting + cleanup"
};

// Timer to track time between start of first job and end of last job
static QTime firstStartTime;

// Timer to track time the current job takes
static QTime currentJobStartTime;

// Zeros the stats, to be called when the first job starts
static void resetStats()
{
    totalMessages = 0;
    layoutChangeTime = 0;
    expandingTreeTime = 0;
    lastPass = -1;
    for ( int i = 0; i < numberOfPasses; ++i ) {
        numElements[i] = 0;
        totalTime[i] = 0;
        chunks[i] = 0;
    }
}

} // namespace Stats

void ModelPrivate::printStatistics()
{
    using namespace Stats;
    int totalTotalTime = 0;
    int completeTime = firstStartTime.elapsed();
    for ( int i = 0; i < numberOfPasses; ++i )
        totalTotalTime += totalTime[i];

    float msgPerSecond = totalMessages / ( totalTotalTime / 1000.0f );
    float msgPerSecondComplete = totalMessages / ( completeTime / 1000.0f );

    int messagesWithSameSubjectAvg = 0;
    int messagesWithSameSubjectMax = 0;
    foreach( const QList< MessageItem * > *messages, mThreadingCacheMessageSubjectMD5ToMessageItem ) {
        if ( messages->size() > messagesWithSameSubjectMax )
            messagesWithSameSubjectMax = messages->size();
        messagesWithSameSubjectAvg += messages->size();
    }
    messagesWithSameSubjectAvg = messagesWithSameSubjectAvg / (float)mThreadingCacheMessageSubjectMD5ToMessageItem.size();

    int totalThreads = 0;
    if ( !mGroupHeaderItemHash.isEmpty() ) {
        foreach( const GroupHeaderItem *groupHeader, mGroupHeaderItemHash ) {
            totalThreads += groupHeader->childItemCount();
        }
    }
    else
        totalThreads = mRootItem->childItemCount();

    kDebug() << "Finished filling the view with" << totalMessages << "messages";
    kDebug() << "That took" << totalTotalTime << "msecs inside the model and"
             << completeTime << "in total.";
    kDebug() << ( totalTotalTime / (float) completeTime ) * 100.0f
             << "percent of the time was spent in the model.";
    kDebug() << "Time for layoutChanged(), in msecs:" << layoutChangeTime
             << "(" << (layoutChangeTime / (float)totalTotalTime) * 100.0f << "percent )";
    kDebug() << "Time to expand tree, in msecs:" << expandingTreeTime
             << "(" << (expandingTreeTime / (float)totalTotalTime) * 100.0f << "percent )";
    kDebug() << "Number of messages per second in the model:" << msgPerSecond;
    kDebug() << "Number of messages per second in total:" << msgPerSecondComplete;
    kDebug() << "Number of threads:" << totalThreads;
    kDebug() << "Number of groups:" << mGroupHeaderItemHash.size();
    kDebug() << "Messages per thread:" << totalMessages / (float)totalThreads;
    kDebug() << "Threads per group:" << totalThreads / (float)mGroupHeaderItemHash.size();
    kDebug() << "Messages with the same subject:"
             << "Max:" << messagesWithSameSubjectMax
             << "Avg:" << messagesWithSameSubjectAvg;
    kDebug();
    kDebug() << "Now follows a breakdown of the jobs.";
    kDebug();
    for ( int i = 0; i < numberOfPasses; ++i ) {
        if ( totalTime[i] == 0 )
            continue;
        float elementsPerSecond = numElements[i] / ( totalTime[i] / 1000.0f );
        float percent = totalTime[i] / (float)totalTotalTime * 100.0f;
        kDebug() << "----------------------------------------------";
        kDebug() << "Job" << i + 1 << "(" << jobDescription[i] << ")";
        kDebug() << "Share of complete time:" << percent << "percent";
        kDebug() << "Time in msecs:" << totalTime[i];
        kDebug() << "Number of elements:" << numElements[i]; // TODO: map of element string
        kDebug() << "Elements per second:" << elementsPerSecond;
        kDebug() << "Number of chunks:" << chunks[i];
        kDebug();
    }

    kDebug() << "==========================================================";
    resetStats();
}

#endif

ModelPrivate::ViewItemJobResult ModelPrivate::viewItemJobStepInternal()
{
    // This function does a timed chunk of work in our View Fill operation.
    // It attempts to do processing until it either runs out of jobs
    // to be done or a timeout forces it to interrupt and jump back to the caller.

    QTime tStart = QTime::currentTime();
    int elapsed;

    while( !mViewItemJobs.isEmpty() )
    {
        // Have a job to do.
        ViewItemJob * job = mViewItemJobs.first();

#ifdef KDEPIM_FOLDEROPEN_PROFILE

        // Here we check if an old job has just completed or if we are at the start of the
        // first job. We then initialize job data stuff and timers based on this.

        const int currentPass = job->currentPass();
        const bool firstChunk = currentPass != Stats::lastPass;
        if ( currentPass != Stats::lastPass && Stats::lastPass != -1 ) {
            Stats::totalTime[Stats::lastPass] = Stats::currentJobStartTime.elapsed();
        }
        const bool firstJob = job->currentPass() == ViewItemJob::Pass1Fill && firstChunk;
        const int elements = job->endIndex() - job->startIndex();
        if ( firstJob ) {
            Stats::resetStats();
            Stats::totalMessages = elements;
            Stats::firstStartTime.restart();
        }
        if ( firstChunk ) {
            Stats::numElements[currentPass] = elements;
            Stats::currentJobStartTime.restart();
        }
        Stats::chunks[currentPass]++;
        Stats::lastPass = currentPass;

#endif

        mViewItemJobStepIdleInterval = job->idleInterval();
        mViewItemJobStepChunkTimeout = job->chunkTimeout();
        mViewItemJobStepMessageCheckCount = job->messageCheckCount();

        if ( job->disconnectUI() )
        {
            mModelForItemFunctions = 0; // disconnect the UI for this job
            Q_ASSERT( mLoading ); // this must be true in the first job
            // FIXME: Should assert yet more that this is the very first job for this StorageModel
            //        Asserting only mLoading is not enough as we could be using a two-jobs loading strategy
            //        or this could be a job enqueued before the first job has completed.
        } else {
            // With a connected UI we need to avoid the view to update the scrollbars at EVERY insertion or expansion.
            // QTreeViewPrivate::updateScrollBars() is very expensive as it loops through ALL the items in the view every time.
            // We can't disable the function directly as it's hidden in the private data object of QTreeView
            // but we can disable the parent QTreeView::updateGeometries() instead.
            // We will trigger it "manually" at the end of the step.
            mView->ignoreUpdateGeometries( true );

            // Ok.. I know that this seems unbelieveable but disabling updates actually
            // causes a (significant) performance loss in most cases. This is probably because QTreeView
            // uses delayed layouts when updates are disabled which should be delayed but in
            // fact are "forced" by next item insertions. The delayed layout algorithm, then
            // is probably slower than the non-delayed one.
            // Disabling the paintEvent() doesn't seem to work either.
            //mView->setUpdatesEnabled( false );
        }

        switch( viewItemJobStepInternalForJob( job, tStart ) )
        {
        case ViewItemJobInterrupted:
        {
            // current job interrupted by timeout: will propagate status to caller
            // but before this, give some feedback to the user

            // FIXME: This is now inaccurate, think of something else
            switch( job->currentPass() )
            {
            case ViewItemJob::Pass1Fill:
            case ViewItemJob::Pass1Cleanup:
            case ViewItemJob::Pass1Update:
                emit q->statusMessage( i18np( "Processed 1 Message of %2",
                                              "Processed %1 Messages of %2",
                                              job->currentIndex() - job->startIndex(),
                                              job->endIndex() - job->startIndex() + 1 ) );
                break;
            case ViewItemJob::Pass2:
                emit q->statusMessage( i18np( "Threaded 1 Message of %2",
                                              "Threaded %1 Messages of %2",
                                              job->currentIndex() - job->startIndex(),
                                              job->endIndex() - job->startIndex() + 1 ) );
                break;
            case ViewItemJob::Pass3:
                emit q->statusMessage( i18np( "Threaded 1 Message of %2",
                                              "Threaded %1 Messages of %2",
                                              job->currentIndex() - job->startIndex(),
                                              job->endIndex() - job->startIndex() + 1 ) );
                break;
            case ViewItemJob::Pass4:
                emit q->statusMessage( i18np( "Grouped 1 Thread of %2",
                                              "Grouped %1 Threads of %2",
                                              job->currentIndex() - job->startIndex(),
                                              job->endIndex() - job->startIndex() + 1 ) );
                break;
            case ViewItemJob::Pass5:
                emit q->statusMessage( i18np( "Updated 1 Group of %2",
                                              "Updated %1 Groups of %2",
                                              job->currentIndex() - job->startIndex(),
                                              job->endIndex() - job->startIndex() + 1 ) );
                break;
            default: break;
            }

            if( !job->disconnectUI() )
            {
                mView->ignoreUpdateGeometries( false );
                // explicit call to updateGeometries() here
                mView->updateGeometries();
            }

            return ViewItemJobInterrupted;
        }
            break;
        case ViewItemJobCompleted:

            // If this job worked with a disconnected UI, emit layoutChanged()
            // to reconnect it. We go back to normal operation now.
            if ( job->disconnectUI() )
            {
                mModelForItemFunctions = q;
                // This call would destroy the expanded state of items.
                // This is why when mModelForItemFunctions was 0 we didn't actually expand them
                // but we just set a "ExpandNeeded" mark...
#ifdef KDEPIM_FOLDEROPEN_PROFILE
                QTime layoutChangedTimer;
                layoutChangedTimer.start();
#endif
                mView->modelAboutToEmitLayoutChanged();
                emit q->layoutChanged();
                mView->modelEmittedLayoutChanged();

#ifdef KDEPIM_FOLDEROPEN_PROFILE
                Stats::layoutChangeTime = layoutChangedTimer.elapsed();
                QTime expandingTime;
                expandingTime.start();
#endif

                // expand all the items that need it in a single sweep

                // FIXME: This takes quite a lot of time, it could be made an interruptible job

                QList< Item * > * rootChildItems = mRootItem->childItems();
                if ( rootChildItems )
                {
                    QList< Item * >::ConstIterator end( rootChildItems->constEnd() );
                    for ( QList< Item * >::ConstIterator it = rootChildItems->constBegin(); it != end ;++it )
                    {
                        if ( ( *it )->initialExpandStatus() == Item::ExpandNeeded )
                            syncExpandedStateOfSubtree( *it );
                    }
                }
#ifdef KDEPIM_FOLDEROPEN_PROFILE
                Stats::expandingTreeTime = expandingTime.elapsed();
#endif
            } else {
                mView->ignoreUpdateGeometries( false );
                // explicit call to updateGeometries() here
                mView->updateGeometries();
            }

            // this job has been completed
            delete mViewItemJobs.takeFirst();

#ifdef KDEPIM_FOLDEROPEN_PROFILE
            // Last job finished!
            Stats::totalTime[currentPass] = Stats::currentJobStartTime.elapsed();
            printStatistics();
#endif

            // take care of small jobs which never timeout by themselves because
            // of a small number of messages. At the end of each job check
            // the time used and if we're timeoutting and there is another job
            // then interrupt.
            elapsed = tStart.msecsTo( QTime::currentTime() );
            if ( ( elapsed > mViewItemJobStepChunkTimeout ) || ( elapsed < 0 ) )
            {
                if ( !mViewItemJobs.isEmpty() )
                    return ViewItemJobInterrupted;
                // else it's completed in fact
            } // else proceed with the next job

            break;
        default:
            // This is *really* a BUG
            kWarning() << "ERROR: returned an invalid result";
            Q_ASSERT( false );
            break;
        }
    }

    // no more jobs

    emit q->statusMessage( i18nc( "@info:status Finished view fill", "Ready" ) );

    return ViewItemJobCompleted;
}


void ModelPrivate::viewItemJobStep()
{
    // A single step in the View Fill operation.
    // This function wraps viewItemJobStepInternal() which does the step job
    // and either completes it or stops because of a timeout.
    // If the job is stopped then we start a zero-msecs timer to call us
    // back and resume the job. Otherwise we're just done.

    mViewItemJobStepStartTime = ::time( 0 );

    if( mFillStepTimer.isActive() )
        mFillStepTimer.stop();

    if ( !mStorageModel )
        return; // nothing more to do


    // Save the current item in the view as our process may
    // cause items to be reparented (and QTreeView will forget the current item in the meantime).
    // This machinery is also needed when we're about to remove items from the view in
    // a cleanup job: we'll be trying to set as current the item after the one removed.

    QModelIndex currentIndexBeforeStep = mView->currentIndex();
    Item * currentItemBeforeStep = currentIndexBeforeStep.isValid() ?
                static_cast< Item * >( currentIndexBeforeStep.internalPointer() ) : 0;

    // mCurrentItemToRestoreAfterViewItemJobStep will be zeroed out if it's killed
    mCurrentItemToRestoreAfterViewItemJobStep = currentItemBeforeStep;

    // Save the current item position in the viewport as QTreeView fails to keep
    // the current item in the sample place when items are added or removed...
    QRect rectBeforeViewItemJobStep;

    const bool lockView = mView->isScrollingLocked();

    // This is generally SLOW AS HELL... (so we avoid it if we lock the view and thus don't need it)
    if ( mCurrentItemToRestoreAfterViewItemJobStep && ( !lockView ) )
        rectBeforeViewItemJobStep = mView->visualRect( currentIndexBeforeStep );

    // FIXME: If the current item is NOT in the view, preserve the position
    //        of the top visible item. This will make the view move yet less.

    // Insulate the View from (very likely spurious) "currentChanged()" signals.
    mView->ignoreCurrentChanges( true );

    // And go to real work.
    switch( viewItemJobStepInternal() )
    {
    case ViewItemJobInterrupted:
        // Operation timed out, need to resume in a while
        if ( !mInLengthyJobBatch )
        {
            mInLengthyJobBatch = true;
            mView->modelJobBatchStarted();
        }
        mFillStepTimer.start( mViewItemJobStepIdleInterval ); // this is a single shot timer connected to viewItemJobStep()
        // and go dealing with current/selection out of the switch.
        break;
    case ViewItemJobCompleted:
        // done :)

        Q_ASSERT( mModelForItemFunctions ); // UI must be no (longer) disconnected in this state

        // Ask the view to remove the eventual busy indications
        if ( mInLengthyJobBatch )
        {
            mInLengthyJobBatch = false;
            mView->modelJobBatchTerminated();
        }

        if ( mLoading )
        {
            mLoading = false;
            mView->modelFinishedLoading();
        }

        // Apply pre-selection, if any
        if ( mPreSelectionMode != PreSelectNone )
        {
            mView->ignoreCurrentChanges( false );

            bool bSelectionDone = false;

            switch( mPreSelectionMode )
            {
            case PreSelectLastSelected:
                // fall down
                break;
            case PreSelectFirstUnreadCentered:
                bSelectionDone = mView->selectFirstMessageItem( MessageTypeUnreadOnly, true ); // center
                break;
            case PreSelectOldestCentered:
                mView->setCurrentMessageItem( mOldestItem, true /* center */ );
                bSelectionDone = true;
                break;
            case PreSelectNewestCentered:
                mView->setCurrentMessageItem( mNewestItem, true /* center */ );
                bSelectionDone = true;
                break;
            case PreSelectNone:
                // deal with selection below
                break;
            default:
                kWarning() << "ERROR: Unrecognized pre-selection mode " << (int)mPreSelectionMode;
                break;
            }

            if ( ( !bSelectionDone ) && ( mPreSelectionMode != PreSelectNone ) )
            {
                // fallback to last selected, if possible
                if ( mLastSelectedMessageInFolder ) // we found it in the loading process: select and jump out
                {
                    mView->setCurrentMessageItem( mLastSelectedMessageInFolder );
                    bSelectionDone = true;
                }
            }

            if ( bSelectionDone ) {
                mLastSelectedMessageInFolder = 0;
                mPreSelectionMode = PreSelectNone;
                return; // already taken care of current / selection
            }
        }
        // deal with current/selection out of the switch

        break;
    default:
        // This is *really* a BUG
        kWarning() << "ERROR: returned an invalid result";
        Q_ASSERT( false );
        break;
    }

    // Everything else here deals with the selection

    // If UI is disconnected then we don't have anything else to do here
    if ( !mModelForItemFunctions )
    {
        mView->ignoreCurrentChanges( false );
        return;
    }

    // Restore current/selection and/or scrollbar position

    if ( mCurrentItemToRestoreAfterViewItemJobStep )
    {
        bool stillIgnoringCurrentChanges = true;

        // If the assert below fails then the previously current item got detached
        // and didn't get reattached in the step: this should never happen.
        Q_ASSERT( mCurrentItemToRestoreAfterViewItemJobStep->isViewable() );

        // Check if the current item changed
        QModelIndex currentIndexAfterStep = mView->currentIndex();
        Item * currentAfterStep = currentIndexAfterStep.isValid() ?
                    static_cast< Item * >( currentIndexAfterStep.internalPointer() ) : 0;

        if ( mCurrentItemToRestoreAfterViewItemJobStep != currentAfterStep )
        {
            // QTreeView lost the current item...
            if ( mCurrentItemToRestoreAfterViewItemJobStep != currentItemBeforeStep )
            {
                // Some view job code expects us to actually *change* the current item.
                // This is done by the cleanup step which removes items and tries
                // to set as current the item *after* the removed one, if possible.
                // We need the view to handle the change though.
                stillIgnoringCurrentChanges = false;
                mView->ignoreCurrentChanges( false );
            } else {
                // we just have to restore the old current item. The code
                // outside shouldn't have noticed that we lost it (e.g. the message viewer
                // still should have the old message opened). So we don't need to
                // actually notify the view of the restored setting.
            }
            // Restore it
            kDebug() << "Gonna restore current here" << mCurrentItemToRestoreAfterViewItemJobStep->subject();
            mView->setCurrentIndex( q->index( mCurrentItemToRestoreAfterViewItemJobStep, 0 ) );
        } else {
            // The item we're expected to set as current is already current
            if ( mCurrentItemToRestoreAfterViewItemJobStep != currentItemBeforeStep )
            {
                // But we have changed it in the job step.
                // This means that: we have deleted the current item and chosen a
                // new candidate as current but Qt also has chosen it as candidate
                // and already made it current. The problem is that (as of Qt 4.4)
                // it probably didn't select it.
                if ( !mView->selectionModel()->hasSelection() )
                {
                    stillIgnoringCurrentChanges = false;
                    mView->ignoreCurrentChanges( false );

                    kDebug() << "Gonna restore selection here" << mCurrentItemToRestoreAfterViewItemJobStep->subject();

                    QItemSelection selection;
                    selection.append( QItemSelectionRange( q->index( mCurrentItemToRestoreAfterViewItemJobStep, 0 ) ) );
                    mView->selectionModel()->select( selection, QItemSelectionModel::Select | QItemSelectionModel::Rows );
                }
            }
        }

        // FIXME: If it was selected before the change, then re-select it (it may happen that it's not)
        if ( !lockView )
        {
            // we prefer to keep the currently selected item steady in the view
            QRect rectAfterViewItemJobStep = mView->visualRect( q->index( mCurrentItemToRestoreAfterViewItemJobStep, 0 ) );
            if ( rectBeforeViewItemJobStep.y() != rectAfterViewItemJobStep.y() )
            {
                // QTreeView lost its position...
                mView->verticalScrollBar()->setValue( mView->verticalScrollBar()->value() + rectAfterViewItemJobStep.y() - rectBeforeViewItemJobStep.y() );
            }
        }

        // and kill the insulation, if not yet done
        if ( stillIgnoringCurrentChanges )
            mView->ignoreCurrentChanges( false );

        return;
    }

    // Either there was no current item before, or it was lost in a cleanup step and another candidate for
    // current item couldn't be found (possibly empty view)
    mView->ignoreCurrentChanges( false );

    if ( currentItemBeforeStep )
    {
        // lost in a cleanup..
        // tell the view that we have a new current, this time with no insulation
        mView->slotSelectionChanged( QItemSelection(), QItemSelection() );
    }
}

void ModelPrivate::slotStorageModelRowsInserted( const QModelIndex &parent, int from, int to )
{
    if ( parent.isValid() )
        return; // ugh... should never happen

    Q_ASSERT( from <= to );

    int count = ( to - from ) + 1;

    mInvariantRowMapper->modelRowsInserted( from, count );

    // look if no current job is in the middle

    int jobCount = mViewItemJobs.count();

    for ( int idx = 0; idx < jobCount; idx++ )
    {
        ViewItemJob * job = mViewItemJobs.at( idx );

        if ( job->currentPass() != ViewItemJob::Pass1Fill )
        {
            // The job is a cleanup or in a later pass: the storage has been already accessed
            // and the messages created... no need to care anymore: the invariant row mapper will do the job.
            continue;
        }

        if ( job->currentIndex() > job->endIndex() )
        {
            // The job finished the Pass1Fill but still waits for the pass indicator to be
            // changed. This is unlikely but still may happen if the job has been interrupted
            // and then a call to slotStorageModelRowsRemoved() caused it to be forcibly completed.
            continue;
        }

        //
        // The following cases are possible:
        //
        //               from  to
        //                 |    |                              -> shift up job
        //               from             to
        //                 |              |                    -> shift up job
        //               from                            to
        //                 |                             |     -> shift up job
        //                           from   to
        //                             |     |                 -> split job
        //                           from                to
        //                             |                 |     -> split job
        //                                     from      to
        //                                       |       |     -> job unaffected
        //
        //
        // FOLDER
        // |-------------------------|---------|--------------|
        // 0                   currentIndex endIndex         count
        //                           +-- job --+
        //

        if ( from > job->endIndex() )
        {
            // The change is completely above the job, the job is not affected
            continue;
        }

        if( from > job->currentIndex() ) // and from <= job->endIndex()
        {
            // The change starts in the middle of the job in a way that it must be split in two.
            // The first part is unaffected by the shift and ranges from job->currentIndex() to from - 1.
            // The second part ranges from "from" to job->endIndex() that are now shifted up by count steps.

            // First add a new job for the second part.
            ViewItemJob * newJob = new ViewItemJob( from + count, job->endIndex() + count, job->chunkTimeout(), job->idleInterval(), job->messageCheckCount() );

            Q_ASSERT( newJob->currentIndex() <= newJob->endIndex() );

            idx++; // we can skip this job in the loop, it's already ok
            jobCount++; // and our range increases by one.
            mViewItemJobs.insert( idx, newJob );

            // Then limit the original job to the first part
            job->setEndIndex( from - 1 );

            Q_ASSERT( job->currentIndex() <= job->endIndex() );

            continue;
        }

        // The change starts below (or exactly on the beginning of) the job.
        // The job must be shifted up.
        job->setCurrentIndex( job->currentIndex() + count );
        job->setEndIndex( job->endIndex() + count );

        Q_ASSERT( job->currentIndex() <= job->endIndex() );
    }

    bool newJobNeeded = true;

    // Try to attach to an existing fill job, if any.
    // To enforce consistency we can attach only if the Fill job
    // is the last one in the list (might be eventually *also* the first,
    // and even being already processed but we must make sure that there
    // aren't jobs _after_ it).
    if ( jobCount > 0 )
    {
        ViewItemJob * job = mViewItemJobs.at( jobCount - 1 );
        if ( job->currentPass() == ViewItemJob::Pass1Fill )
        {
            if (
                    // The job ends just before the added rows
                    ( from == ( job->endIndex() + 1 ) ) &&
                    // The job didn't reach the end of Pass1Fill yet
                    ( job->currentIndex() <= job->endIndex() )
                    )
            {
                // We can still attach this :)
                job->setEndIndex( to );
                Q_ASSERT( job->currentIndex() <= job->endIndex() );
                newJobNeeded = false;
            }
        }
    }

    if ( newJobNeeded )
    {
        // FIXME: Should take timing options from aggregation here ?
        ViewItemJob * job = new ViewItemJob( from, to, 100, 50, 10 );
        mViewItemJobs.append( job );
    }

    if ( !mFillStepTimer.isActive() )
        mFillStepTimer.start( mViewItemJobStepIdleInterval );
}

void ModelPrivate::slotStorageModelRowsRemoved( const QModelIndex &parent, int from, int to )
{
    // This is called when the underlying StorageModel emits the rowsRemoved signal.

    if ( parent.isValid() )
        return; // ugh... should never happen

    // look if no current job is in the middle

    Q_ASSERT( from <= to );

    const int count = ( to - from ) + 1;

    int jobCount = mViewItemJobs.count();

    if (mRootItem && from == 0 && count == mRootItem->childItemCount() && jobCount == 0) {
        clear();
        return;
    }

    for ( int idx = 0; idx < jobCount; idx++ )
    {
        ViewItemJob * job = mViewItemJobs.at( idx );

        if ( job->currentPass() != ViewItemJob::Pass1Fill )
        {
            // The job is a cleanup or in a later pass: the storage has been already accessed
            // and the messages created... no need to care: we will invalidate the messages in a while.
            continue;
        }

        if ( job->currentIndex() > job->endIndex() )
        {
            // The job finished the Pass1Fill but still waits for the pass indicator to be
            // changed. This is unlikely but still may happen if the job has been interrupted
            // and then a call to slotStorageModelRowsRemoved() caused it to be forcibly completed.
            continue;
        }

        //
        // The following cases are possible:
        //
        //               from  to
        //                 |    |                              -> shift down job
        //               from             to
        //                 |              |                    -> shift down and crop job
        //               from                            to
        //                 |                             |     -> kill job
        //                           from   to
        //                             |     |                 -> split job, crop and shift
        //                           from                to
        //                             |                 |     -> crop job
        //                                     from      to
        //                                       |       |     -> job unaffected
        //
        //
        // FOLDER
        // |-------------------------|---------|--------------|
        // 0                   currentIndex endIndex         count
        //                           +-- job --+
        //

        if ( from > job->endIndex() )
        {
            // The change is completely above the job, the job is not affected
            continue;
        }

        if( from > job->currentIndex() ) // and from <= job->endIndex()
        {
            // The change starts in the middle of the job and ends in the middle or after the job.
            // The first part is unaffected by the shift and ranges from job->currentIndex() to from - 1
            // We use the existing job for this.
            job->setEndIndex( from - 1 ); // stop before the first removed row

            Q_ASSERT( job->currentIndex() <= job->endIndex() );

            if ( to < job->endIndex() )
            {
                // The change ends inside the job and a part of it can be completed.

                // We create a new job for the shifted remaining part. It would actually
                // range from to + 1 up to job->endIndex(), but we need to shift it down by count.
                // since count = ( to - from ) + 1 so from = to + 1 - count

                ViewItemJob * newJob = new ViewItemJob( from, job->endIndex() - count, job->chunkTimeout(), job->idleInterval(), job->messageCheckCount() );

                Q_ASSERT( newJob->currentIndex() < newJob->endIndex() );

                idx++; // we can skip this job in the loop, it's already ok
                jobCount++; // and our range increases by one.
                mViewItemJobs.insert( idx, newJob );
            } // else the change includes completely the end of the job and no other part of it can be completed.

            continue;
        }

        // The change starts below (or exactly on the beginning of) the job. ( from <= job->currentIndex() )
        if ( to >= job->endIndex() )
        {
            // The change completely covers the job: kill it

            // We don't delete the job since we want the other passes to be completed
            // This is because the Pass1Fill may have already filled mUnassignedMessageListForPass2
            // and may have set mOldestItem and mNewestItem. We *COULD* clear the unassigned
            // message list with clearUnassignedMessageLists() but mOldestItem and mNewestItem
            // could be still dangling pointers. So we just move the current index of the job
            // after the end (so storage model scan terminates) and let it complete spontaneously.
            job->setCurrentIndex( job->endIndex() + 1 );

            continue;
        }

        if ( to >= job->currentIndex() )
        {
            // The change partially covers the job. Only a part of it can be completed
            // and it must be shifted down. It would actually
            // range from to + 1 up to job->endIndex(), but we need to shift it down by count.
            // since count = ( to - from ) + 1 so from = to + 1 - count
            job->setCurrentIndex( from );
            job->setEndIndex( job->endIndex() - count );

            Q_ASSERT( job->currentIndex() <= job->endIndex() );

            continue;
        }

        // The change is completely below the job: it must be shifted down.
        job->setCurrentIndex( job->currentIndex() - count );
        job->setEndIndex( job->endIndex() - count );
    }

    // This will invalidate the ModelInvariantIndex-es that have been removed and return
    // them all in a nice list that we can feed to a view removal job.
    QList< ModelInvariantIndex * > * invalidatedIndexes = mInvariantRowMapper->modelRowsRemoved( from, count );

    if ( invalidatedIndexes )
    {
        // Try to attach to an existing cleanup job, if any.
        // To enforce consistency we can attach only if the Cleanup job
        // is the last one in the list (might be eventually *also* the first,
        // and even being already processed but we must make sure that there
        // aren't jobs _after_ it).
        if ( jobCount > 0 )
        {
            ViewItemJob * job = mViewItemJobs.at( jobCount - 1 );
            if ( job->currentPass() == ViewItemJob::Pass1Cleanup )
            {
                if ( ( job->currentIndex() <= job->endIndex() ) && job->invariantIndexList() )
                {
                    //kDebug() << "Appending " << invalidatedIndexes->count() << " invalidated indexes to existing cleanup job" << endl;
                    // We can still attach this :)
                    *( job->invariantIndexList() ) += *invalidatedIndexes;
                    job->setEndIndex( job->endIndex() + invalidatedIndexes->count() );
                    delete invalidatedIndexes;
                    invalidatedIndexes = 0;
                }
            }
        }

        if ( invalidatedIndexes )
        {
            // Didn't append to any existing cleanup job.. create a new one

            //kDebug() << "Creating new cleanup job for " << invalidatedIndexes->count() << " invalidated indexes" << endl;
            // FIXME: Should take timing options from aggregation here ?
            ViewItemJob * job = new ViewItemJob( ViewItemJob::Pass1Cleanup, invalidatedIndexes, 100, 50, 10 );
            mViewItemJobs.append( job );
        }

        if ( !mFillStepTimer.isActive() )
            mFillStepTimer.start( mViewItemJobStepIdleInterval );
    }
}

void ModelPrivate::slotStorageModelLayoutChanged()
{
    kDebug() << "Storage model layout changed";
    // need to reset everything...
    q->setStorageModel( mStorageModel );
    kDebug() << "Storage model layout changed done";
}

void ModelPrivate::slotStorageModelDataChanged( const QModelIndex &fromIndex, const QModelIndex &toIndex )
{
    Q_ASSERT( mStorageModel ); // must exist (and be the sender of the signal connected to this slot)

    int from = fromIndex.row();
    int to = toIndex.row();

    Q_ASSERT( from <= to );

    int count = ( to - from ) + 1;

    int jobCount = mViewItemJobs.count();

    // This will find out the ModelInvariantIndex-es that need an update and will return
    // them all in a nice list that we can feed to a view removal job.
    QList< ModelInvariantIndex * > * indexesThatNeedUpdate = mInvariantRowMapper->modelIndexRowRangeToModelInvariantIndexList( from, count );

    if ( indexesThatNeedUpdate )
    {
        // Try to attach to an existing update job, if any.
        // To enforce consistency we can attach only if the Update job
        // is the last one in the list (might be eventually *also* the first,
        // and even being already processed but we must make sure that there
        // aren't jobs _after_ it).
        if ( jobCount > 0 )
        {
            ViewItemJob * job = mViewItemJobs.at( jobCount - 1 );
            if ( job->currentPass() == ViewItemJob::Pass1Update )
            {
                if ( ( job->currentIndex() <= job->endIndex() ) && job->invariantIndexList() )
                {
                    // We can still attach this :)
                    *( job->invariantIndexList() ) += *indexesThatNeedUpdate;
                    job->setEndIndex( job->endIndex() + indexesThatNeedUpdate->count() );
                    delete indexesThatNeedUpdate;
                    indexesThatNeedUpdate = 0;
                }
            }
        }

        if ( indexesThatNeedUpdate )
        {
            // Didn't append to any existing update job.. create a new one
            // FIXME: Should take timing options from aggregation here ?
            ViewItemJob * job = new ViewItemJob( ViewItemJob::Pass1Update, indexesThatNeedUpdate, 100, 50, 10 );
            mViewItemJobs.append( job );
        }

        if ( !mFillStepTimer.isActive() )
            mFillStepTimer.start( mViewItemJobStepIdleInterval );
    }

}

void ModelPrivate::slotStorageModelHeaderDataChanged( Qt::Orientation, int, int )
{
    if ( mStorageModelContainsOutboundMessages!=mStorageModel->containsOutboundMessages() ) {
        mStorageModelContainsOutboundMessages = mStorageModel->containsOutboundMessages();
        emit q->headerDataChanged( Qt::Horizontal, 0, q->columnCount() );
    }
}

Qt::ItemFlags Model::flags( const QModelIndex &index ) const
{
    if ( !index.isValid() )
        return Qt::NoItemFlags;

    Q_ASSERT( d->mModelForItemFunctions ); // UI must be connected if a valid index was queried

    Item * it = static_cast< Item * >( index.internalPointer() );

    Q_ASSERT( it );

    if ( it->type() == Item::GroupHeader )
        return Qt::ItemIsEnabled;

    Q_ASSERT( it->type() == Item::Message );

    if ( !static_cast< MessageItem * >( it )->isValid() )
        return Qt::NoItemFlags; // not enabled, not selectable

    if ( static_cast< MessageItem * >( it )->aboutToBeRemoved() )
        return Qt::NoItemFlags; // not enabled, not selectable

    if ( static_cast< MessageItem * >( it )->status().isDeleted() )
        return Qt::NoItemFlags; // not enabled, not selectable

    return Qt::ItemIsEnabled | Qt::ItemIsSelectable;
}

QMimeData* MessageList::Core::Model::mimeData( const QModelIndexList& indexes ) const
{
    QList< MessageItem* > msgs;
    foreach( const QModelIndex &idx, indexes ) {
        if( idx.isValid() ) {
            Item* item = static_cast< Item* >( idx.internalPointer() );
            if( item->type() == MessageList::Core::Item::Message ) {
                msgs << static_cast< MessageItem* >( idx.internalPointer() );
            }
        }
    }
    return storageModel()->mimeData( msgs );
}


Item *Model::rootItem() const
{
    return d->mRootItem;
}

bool Model::isLoading() const
{
    return d->mLoading;
}

MessageItem * Model::messageItemByStorageRow( int row ) const
{
    if ( !d->mStorageModel )
        return 0;
    ModelInvariantIndex * idx = d->mInvariantRowMapper->modelIndexRowToModelInvariantIndex( row );
    if ( !idx )
        return 0;

    return static_cast< MessageItem * >( idx );
}


MessageItemSetReference Model::createPersistentSet( const QList< MessageItem * > &items )
{
    if ( !d->mPersistentSetManager )
        d->mPersistentSetManager = new MessageItemSetManager();

    MessageItemSetReference ref = d->mPersistentSetManager->createSet();
    QList< MessageItem * >::ConstIterator end = items.constEnd();
    for ( QList< MessageItem * >::ConstIterator it = items.constBegin(); it != end; ++it )
        d->mPersistentSetManager->addMessageItem( ref, *it );

    return ref;
}

QList< MessageItem * > Model::persistentSetCurrentMessageItemList( MessageItemSetReference ref )
{
    if ( d->mPersistentSetManager )
        return d->mPersistentSetManager->messageItems( ref );
    return QList< MessageItem * >();

}

void Model::deletePersistentSet( MessageItemSetReference ref )
{
    if ( !d->mPersistentSetManager )
        return;

    d->mPersistentSetManager->removeSet( ref );

    if ( d->mPersistentSetManager->setCount() < 1 )
    {
        delete d->mPersistentSetManager;
        d->mPersistentSetManager = 0;
    }
}

#include "moc_model.cpp"