src/kitemviews/kfileitemmodel.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2011 by Peter Penz <peter.penz19@gmail.com>             *
   3  *                                                                         *
   4  *   This program is free software; you can redistribute it and/or modify  *
   5  *   it under the terms of the GNU General Public License as published by  *
   6  *   the Free Software Foundation; either version 2 of the License, or     *
   7  *   (at your option) any later version.                                   *
   8  *                                                                         *
   9  *   This program is distributed in the hope that it will be useful,       *
  10  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  12  *   GNU General Public License for more details.                          *
  13  *                                                                         *
  14  *   You should have received a copy of the GNU General Public License     *
  15  *   along with this program; if not, write to the                         *
  16  *   Free Software Foundation, Inc.,                                       *
  17  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
  18  ***************************************************************************/
  19
  20 #include "kfileitemmodel.h"
  21
  22 #include <KDirLister>
  23 #include <KDirModel>
  24 #include <KLocale>
  25 #include <KStringHandler>
  26 #include <KDebug>
  27
  28 #include <QMimeData>
  29 #include <QTimer>
  30
  31 #define KFILEITEMMODEL_DEBUG
  32
  33 KFileItemModel::KFileItemModel(KDirLister* dirLister, QObject* parent) :
  34     KItemModelBase("name", parent),
  35     m_dirLister(dirLister),
  36     m_naturalSorting(true),
  37     m_sortFoldersFirst(true),
  38     m_sortRole(NameRole),
  39     m_caseSensitivity(Qt::CaseInsensitive),
  40     m_sortedItems(),
  41     m_items(),
  42     m_data(),
  43     m_requestRole(),
  44     m_minimumUpdateIntervalTimer(0),
  45     m_maximumUpdateIntervalTimer(0),
  46     m_pendingItemsToInsert(),
  47     m_pendingEmitLoadingCompleted(false),
  48     m_groups(),
  49     m_rootExpansionLevel(-1),
  50     m_expandedUrls(),
  51     m_restoredExpandedUrls()
  52 {
  53     resetRoles();
  54     m_requestRole[NameRole] = true;
  55     m_requestRole[IsDirRole] = true;
  56
  57     Q_ASSERT(dirLister);
  58
  59     connect(dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  60     connect(dirLister, SIGNAL(completed()), this, SLOT(slotCompleted()));
  61     connect(dirLister, SIGNAL(newItems(KFileItemList)), this, SLOT(slotNewItems(KFileItemList)));
  62     connect(dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  63     connect(dirLister, SIGNAL(refreshItems(QList<QPair<KFileItem,KFileItem> >)), this, SLOT(slotRefreshItems(QList<QPair<KFileItem,KFileItem> >)));
  64     connect(dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  65     connect(dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  66
  67     // Although the layout engine of KItemListView is fast it is very inefficient to e.g.
  68     // emit 50 itemsInserted()-signals each 100 ms. m_minimumUpdateIntervalTimer assures that updates
  69     // are done in 1 second intervals for equal operations.
  70     m_minimumUpdateIntervalTimer = new QTimer(this);
  71     m_minimumUpdateIntervalTimer->setInterval(1000);
  72     m_minimumUpdateIntervalTimer->setSingleShot(true);
  73     connect(m_minimumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  74
  75     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  76     // before the completed() or canceled() signal has been emitted.
  77     m_maximumUpdateIntervalTimer = new QTimer(this);
  78     m_maximumUpdateIntervalTimer->setInterval(2000);
  79     m_maximumUpdateIntervalTimer->setSingleShot(true);
  80     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  81
  82     Q_ASSERT(m_minimumUpdateIntervalTimer->interval() <= m_maximumUpdateIntervalTimer->interval());
  83 }
  84
  85 KFileItemModel::~KFileItemModel()
  86 {
  87 }
  88
  89 int KFileItemModel::count() const
  90 {
  91     return m_data.count();
  92 }
  93
  94 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
  95 {
  96     if (index >= 0 && index < count()) {
  97         return m_data.at(index);
  98     }
  99     return QHash<QByteArray, QVariant>();
 100 }
 101
 102 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
 103 {
 104     if (index >= 0 && index < count()) {
 105         QHash<QByteArray, QVariant> currentValue = m_data.at(index);
 106
 107         QSet<QByteArray> changedRoles;
 108         QHashIterator<QByteArray, QVariant> it(values);
 109         while (it.hasNext()) {
 110             it.next();
 111             const QByteArray role = it.key();
 112             const QVariant value = it.value();
 113
 114             if (currentValue[role] != value) {
 115                 currentValue[role] = value;
 116                 changedRoles.insert(role);
 117             }
 118         }
 119
 120         if (!changedRoles.isEmpty()) {
 121             m_data[index] = currentValue;
 122             emit itemsChanged(KItemRangeList() << KItemRange(index, 1), changedRoles);
 123         }
 124
 125         return true;
 126     }
 127     return false;
 128 }
 129
 130 void KFileItemModel::setSortFoldersFirst(bool foldersFirst)
 131 {
 132     if (foldersFirst != m_sortFoldersFirst) {
 133         m_sortFoldersFirst = foldersFirst;
 134         resortAllItems();
 135     }
 136 }
 137
 138 bool KFileItemModel::sortFoldersFirst() const
 139 {
 140     return m_sortFoldersFirst;
 141 }
 142
 143 QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
 144 {
 145     QMimeData* data = new QMimeData();
 146
 147     // The following code has been taken from KDirModel::mimeData()
 148     // (kdelibs/kio/kio/kdirmodel.cpp)
 149     // Copyright (C) 2006 David Faure <faure@kde.org>
 150     KUrl::List urls;
 151     KUrl::List mostLocalUrls;
 152     bool canUseMostLocalUrls = true;
 153
 154     QSetIterator<int> it(indexes);
 155     while (it.hasNext()) {
 156         const int index = it.next();
 157         const KFileItem item = fileItem(index);
 158         if (!item.isNull()) {
 159             urls << item.url();
 160
 161             bool isLocal;
 162             mostLocalUrls << item.mostLocalUrl(isLocal);
 163             if (!isLocal) {
 164                 canUseMostLocalUrls = false;
 165             }
 166         }
 167     }
 168
 169     const bool different = canUseMostLocalUrls && mostLocalUrls != urls;
 170     urls = KDirModel::simplifiedUrlList(urls); // TODO: Check if we still need KDirModel for this in KDE 5.0
 171     if (different) {
 172         mostLocalUrls = KDirModel::simplifiedUrlList(mostLocalUrls);
 173         urls.populateMimeData(mostLocalUrls, data);
 174     } else {
 175         urls.populateMimeData(data);
 176     }
 177
 178     return data;
 179 }
 180
 181 int KFileItemModel::indexForKeyboardSearch(const QString& text, int startFromIndex) const
 182 {
 183     startFromIndex = qMax(0, startFromIndex);
 184     for (int i = startFromIndex; i < count(); ++i) {
 185         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 186             return i;
 187         }
 188     }
 189     for (int i = 0; i < startFromIndex; ++i) {
 190         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 191             return i;
 192         }
 193     }
 194     return -1;
 195 }
 196
 197 bool KFileItemModel::supportsDropping(int index) const
 198 {
 199     const KFileItem item = fileItem(index);
 200     return item.isNull() ? false : item.isDir();
 201 }
 202
 203 QString KFileItemModel::roleDescription(const QByteArray& role) const
 204 {
 205     QString descr;
 206
 207     switch (roleIndex(role)) {
 208     case NameRole:           descr = i18nc("@item:intable", "Name"); break;
 209     case SizeRole:           descr = i18nc("@item:intable", "Size"); break;
 210     case DateRole:           descr = i18nc("@item:intable", "Date"); break;
 211     case PermissionsRole:    descr = i18nc("@item:intable", "Permissions"); break;
 212     case OwnerRole:          descr = i18nc("@item:intable", "Owner"); break;
 213     case GroupRole:          descr = i18nc("@item:intable", "Group"); break;
 214     case TypeRole:           descr = i18nc("@item:intable", "Type"); break;
 215     case DestinationRole:    descr = i18nc("@item:intable", "Destination"); break;
 216     case PathRole:           descr = i18nc("@item:intable", "Path"); break;
 217     case NoRole:             break;
 218     case IsDirRole:          break;
 219     case IsExpandedRole:     break;
 220     case ExpansionLevelRole: break;
 221     default:                 Q_ASSERT(false); break;
 222     }
 223
 224     return descr;
 225 }
 226
 227 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 228 {
 229     if (!m_data.isEmpty() && m_groups.isEmpty()) {
 230 #ifdef KFILEITEMMODEL_DEBUG
 231         QElapsedTimer timer;
 232         timer.start();
 233 #endif
 234         switch (roleIndex(sortRole())) {
 235         case NameRole:           m_groups = nameRoleGroups(); break;
 236         case SizeRole:           m_groups = sizeRoleGroups(); break;
 237         case DateRole:           m_groups = dateRoleGroups(); break;
 238         case PermissionsRole:    m_groups = permissionRoleGroups(); break;
 239         case OwnerRole:          m_groups = ownerRoleGroups(); break;
 240         case GroupRole:          m_groups = groupRoleGroups(); break;
 241         case TypeRole:           m_groups = typeRoleGroups(); break;
 242         case DestinationRole:    m_groups = destinationRoleGroups(); break;
 243         case PathRole:           m_groups = pathRoleGroups(); break;
 244         case NoRole:             break;
 245         case IsDirRole:          break;
 246         case IsExpandedRole:     break;
 247         case ExpansionLevelRole: break;
 248         default:                 Q_ASSERT(false); break;
 249         }
 250
 251 #ifdef KFILEITEMMODEL_DEBUG
 252         kDebug() << "[TIME] Calculating groups for" << count() << "items:" << timer.elapsed();
 253 #endif
 254     }
 255
 256     return m_groups;
 257 }
 258
 259 KFileItem KFileItemModel::fileItem(int index) const
 260 {
 261     if (index >= 0 && index < count()) {
 262         return m_sortedItems.at(index);
 263     }
 264
 265     return KFileItem();
 266 }
 267
 268 KFileItem KFileItemModel::fileItem(const KUrl& url) const
 269 {
 270     const int index = m_items.value(url, -1);
 271     if (index >= 0) {
 272         return m_sortedItems.at(index);
 273     }
 274     return KFileItem();
 275 }
 276
 277 int KFileItemModel::index(const KFileItem& item) const
 278 {
 279     if (item.isNull()) {
 280         return -1;
 281     }
 282
 283     return m_items.value(item.url(), -1);
 284 }
 285
 286 int KFileItemModel::index(const KUrl& url) const
 287 {
 288     KUrl urlToFind = url;
 289     urlToFind.adjustPath(KUrl::RemoveTrailingSlash);
 290     return m_items.value(urlToFind, -1);
 291 }
 292
 293 KFileItem KFileItemModel::rootItem() const
 294 {
 295     const KDirLister* dirLister = m_dirLister.data();
 296     if (dirLister) {
 297         return dirLister->rootItem();
 298     }
 299     return KFileItem();
 300 }
 301
 302 void KFileItemModel::clear()
 303 {
 304     slotClear();
 305 }
 306
 307 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 308 {
 309     if (count() > 0) {
 310         const bool supportedExpanding = m_requestRole[IsExpandedRole] && m_requestRole[ExpansionLevelRole];
 311         const bool willSupportExpanding = roles.contains("isExpanded") && roles.contains("expansionLevel");
 312         if (supportedExpanding && !willSupportExpanding) {
 313             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 314             // that is not 0 (and hence are part of an expanded item).
 315             removeExpandedItems();
 316         }
 317     }
 318
 319     resetRoles();
 320     QSetIterator<QByteArray> it(roles);
 321     while (it.hasNext()) {
 322         const QByteArray& role = it.next();
 323         m_requestRole[roleIndex(role)] = true;
 324     }
 325
 326     if (count() > 0) {
 327         // Update m_data with the changed requested roles
 328         const int maxIndex = count() - 1;
 329         for (int i = 0; i <= maxIndex; ++i) {
 330             m_data[i] = retrieveData(m_sortedItems.at(i));
 331         }
 332
 333         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 334         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 335     }
 336 }
 337
 338 QSet<QByteArray> KFileItemModel::roles() const
 339 {
 340     QSet<QByteArray> roles;
 341     for (int i = 0; i < RolesCount; ++i) {
 342         if (m_requestRole[i]) {
 343             switch (i) {
 344             case NoRole:             break;
 345             case NameRole:           roles.insert("name"); break;
 346             case SizeRole:           roles.insert("size"); break;
 347             case DateRole:           roles.insert("date"); break;
 348             case PermissionsRole:    roles.insert("permissions"); break;
 349             case OwnerRole:          roles.insert("owner"); break;
 350             case GroupRole:          roles.insert("group"); break;
 351             case TypeRole:           roles.insert("type"); break;
 352             case DestinationRole:    roles.insert("destination"); break;
 353             case PathRole:           roles.insert("path"); break;
 354             case IsDirRole:          roles.insert("isDir"); break;
 355             case IsExpandedRole:     roles.insert("isExpanded"); break;
 356             case ExpansionLevelRole: roles.insert("expansionLevel"); break;
 357             default:                 Q_ASSERT(false); break;
 358             }
 359         }
 360     }
 361     return roles;
 362 }
 363
 364 bool KFileItemModel::setExpanded(int index, bool expanded)
 365 {
 366     if (isExpanded(index) == expanded || index < 0 || index >= count()) {
 367         return false;
 368     }
 369
 370     QHash<QByteArray, QVariant> values;
 371     values.insert("isExpanded", expanded);
 372     if (!setData(index, values)) {
 373         return false;
 374     }
 375
 376     const KUrl url = m_sortedItems.at(index).url();
 377     if (expanded) {
 378         m_expandedUrls.insert(url);
 379
 380         KDirLister* dirLister = m_dirLister.data();
 381         if (dirLister) {
 382             dirLister->openUrl(url, KDirLister::Keep);
 383             return true;
 384         }
 385     } else {
 386         m_expandedUrls.remove(url);
 387
 388         KFileItemList itemsToRemove;
 389         const int expansionLevel = data(index)["expansionLevel"].toInt();
 390         ++index;
 391         while (index < count() && data(index)["expansionLevel"].toInt() > expansionLevel) {
 392             itemsToRemove.append(m_sortedItems.at(index));
 393             ++index;
 394         }
 395         removeItems(itemsToRemove);
 396         return true;
 397     }
 398
 399     return false;
 400 }
 401
 402 bool KFileItemModel::isExpanded(int index) const
 403 {
 404     if (index >= 0 && index < count()) {
 405         return m_data.at(index).value("isExpanded").toBool();
 406     }
 407     return false;
 408 }
 409
 410 bool KFileItemModel::isExpandable(int index) const
 411 {
 412     if (index >= 0 && index < count()) {
 413         return m_sortedItems.at(index).isDir();
 414     }
 415     return false;
 416 }
 417
 418 QSet<KUrl> KFileItemModel::expandedUrls() const
 419 {
 420     return m_expandedUrls;
 421 }
 422
 423 void KFileItemModel::restoreExpandedUrls(const QSet<KUrl>& urls)
 424 {
 425     m_restoredExpandedUrls = urls;
 426 }
 427
 428 void KFileItemModel::onGroupedSortingChanged(bool current)
 429 {
 430     Q_UNUSED(current);
 431     m_groups.clear();
 432 }
 433
 434 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 435 {
 436     Q_UNUSED(previous);
 437     m_sortRole = roleIndex(current);
 438     resortAllItems();
 439 }
 440
 441 void KFileItemModel::onSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous)
 442 {
 443     Q_UNUSED(current);
 444     Q_UNUSED(previous);
 445     resortAllItems();
 446 }
 447
 448 void KFileItemModel::slotCompleted()
 449 {
 450     if (m_restoredExpandedUrls.isEmpty() && m_minimumUpdateIntervalTimer->isActive()) {
 451         // dispatchPendingItems() will be called when the timer
 452         // has been expired.
 453         m_pendingEmitLoadingCompleted = true;
 454         return;
 455     }
 456
 457     m_pendingEmitLoadingCompleted = false;
 458     dispatchPendingItemsToInsert();
 459
 460     if (!m_restoredExpandedUrls.isEmpty()) {
 461         // Try to find a URL that can be expanded.
 462         // Note that the parent folder must be expanded before any of its subfolders become visible.
 463         // Therefore, some URLs in m_restoredExpandedUrls might not be visible yet
 464         // -> we expand the first visible URL we find in m_restoredExpandedUrls.
 465         foreach(const KUrl& url, m_restoredExpandedUrls) {
 466             const int index = m_items.value(url, -1);
 467             if (index >= 0) {
 468                 // We have found an expandable URL. Expand it and return - when
 469                 // the dir lister has finished, this slot will be called again.
 470                 m_restoredExpandedUrls.remove(url);
 471                 setExpanded(index, true);
 472                 return;
 473             }
 474         }
 475
 476         // None of the URLs in m_restoredExpandedUrls could be found in the model. This can happen
 477         // if these URLs have been deleted in the meantime.
 478         m_restoredExpandedUrls.clear();
 479     }
 480
 481     emit loadingCompleted();
 482     m_minimumUpdateIntervalTimer->start();
 483 }
 484
 485 void KFileItemModel::slotCanceled()
 486 {
 487     m_minimumUpdateIntervalTimer->stop();
 488     m_maximumUpdateIntervalTimer->stop();
 489     dispatchPendingItemsToInsert();
 490 }
 491
 492 void KFileItemModel::slotNewItems(const KFileItemList& items)
 493 {
 494     m_pendingItemsToInsert.append(items);
 495
 496     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 497         // Assure that items get dispatched if no completed() or canceled() signal is
 498         // emitted during the maximum update interval.
 499         m_maximumUpdateIntervalTimer->start();
 500     }
 501 }
 502
 503 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 504 {
 505     if (!m_pendingItemsToInsert.isEmpty()) {
 506         insertItems(m_pendingItemsToInsert);
 507         m_pendingItemsToInsert.clear();
 508     }
 509     removeItems(items);
 510 }
 511
 512 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 513 {
 514     Q_ASSERT(!items.isEmpty());
 515 #ifdef KFILEITEMMODEL_DEBUG
 516     kDebug() << "Refreshing" << items.count() << "items";
 517 #endif
 518
 519     m_groups.clear();
 520
 521     // Get the indexes of all items that have been refreshed
 522     QList<int> indexes;
 523     indexes.reserve(items.count());
 524
 525     QListIterator<QPair<KFileItem, KFileItem> > it(items);
 526     while (it.hasNext()) {
 527         const QPair<KFileItem, KFileItem>& itemPair = it.next();
 528         const int index = m_items.value(itemPair.second.url(), -1);
 529         if (index >= 0) {
 530             indexes.append(index);
 531         }
 532     }
 533
 534     // If the changed items have been created recently, they might not be in m_items yet.
 535     // In that case, the list 'indexes' might be empty.
 536     if (indexes.isEmpty()) {
 537         return;
 538     }
 539
 540     // Extract the item-ranges out of the changed indexes
 541     qSort(indexes);
 542
 543     KItemRangeList itemRangeList;
 544     int rangeIndex = 0;
 545     int rangeCount = 1;
 546     int previousIndex = indexes.at(0);
 547
 548     const int maxIndex = indexes.count() - 1;
 549     for (int i = 1; i <= maxIndex; ++i) {
 550         const int currentIndex = indexes.at(i);
 551         if (currentIndex == previousIndex + 1) {
 552             ++rangeCount;
 553         } else {
 554             itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 555
 556             rangeIndex = currentIndex;
 557             rangeCount = 1;
 558         }
 559         previousIndex = currentIndex;
 560     }
 561
 562     if (rangeCount > 0) {
 563         itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 564     }
 565
 566     emit itemsChanged(itemRangeList, QSet<QByteArray>());
 567 }
 568
 569 void KFileItemModel::slotClear()
 570 {
 571 #ifdef KFILEITEMMODEL_DEBUG
 572     kDebug() << "Clearing all items";
 573 #endif
 574
 575     m_groups.clear();
 576
 577     m_minimumUpdateIntervalTimer->stop();
 578     m_maximumUpdateIntervalTimer->stop();
 579     m_pendingItemsToInsert.clear();
 580
 581     m_rootExpansionLevel = -1;
 582
 583     const int removedCount = m_data.count();
 584     if (removedCount > 0) {
 585         m_sortedItems.clear();
 586         m_items.clear();
 587         m_data.clear();
 588         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
 589     }
 590
 591     m_expandedUrls.clear();
 592 }
 593
 594 void KFileItemModel::slotClear(const KUrl& url)
 595 {
 596     Q_UNUSED(url);
 597 }
 598
 599 void KFileItemModel::dispatchPendingItemsToInsert()
 600 {
 601     if (!m_pendingItemsToInsert.isEmpty()) {
 602         insertItems(m_pendingItemsToInsert);
 603         m_pendingItemsToInsert.clear();
 604     }
 605
 606     if (m_pendingEmitLoadingCompleted) {
 607         emit loadingCompleted();
 608     }
 609 }
 610
 611 void KFileItemModel::insertItems(const KFileItemList& items)
 612 {
 613     if (items.isEmpty()) {
 614         return;
 615     }
 616
 617 #ifdef KFILEITEMMODEL_DEBUG
 618     QElapsedTimer timer;
 619     timer.start();
 620     kDebug() << "===========================================================";
 621     kDebug() << "Inserting" << items.count() << "items";
 622 #endif
 623
 624     m_groups.clear();
 625
 626     KFileItemList sortedItems = items;
 627     sort(sortedItems.begin(), sortedItems.end());
 628
 629 #ifdef KFILEITEMMODEL_DEBUG
 630     kDebug() << "[TIME] Sorting:" << timer.elapsed();
 631 #endif
 632
 633     KItemRangeList itemRanges;
 634     int targetIndex = 0;
 635     int sourceIndex = 0;
 636     int insertedAtIndex = -1;         // Index for the current item-range
 637     int insertedCount = 0;            // Count for the current item-range
 638     int previouslyInsertedCount = 0;  // Sum of previously inserted items for all ranges
 639     while (sourceIndex < sortedItems.count()) {
 640         // Find target index from m_items to insert the current item
 641         // in a sorted order
 642         const int previousTargetIndex = targetIndex;
 643         while (targetIndex < m_sortedItems.count()) {
 644             if (!lessThan(m_sortedItems.at(targetIndex), sortedItems.at(sourceIndex))) {
 645                 break;
 646             }
 647             ++targetIndex;
 648         }
 649
 650         if (targetIndex - previousTargetIndex > 0 && insertedAtIndex >= 0) {
 651             itemRanges << KItemRange(insertedAtIndex, insertedCount);
 652             previouslyInsertedCount += insertedCount;
 653             insertedAtIndex = targetIndex - previouslyInsertedCount;
 654             insertedCount = 0;
 655         }
 656
 657         // Insert item at the position targetIndex
 658         const KFileItem item = sortedItems.at(sourceIndex);
 659         m_sortedItems.insert(targetIndex, item);
 660         m_data.insert(targetIndex, retrieveData(item));
 661         // m_items will be inserted after the loop (see comment below)
 662         ++insertedCount;
 663
 664         if (insertedAtIndex < 0) {
 665             insertedAtIndex = targetIndex;
 666             Q_ASSERT(previouslyInsertedCount == 0);
 667         }
 668         ++targetIndex;
 669         ++sourceIndex;
 670     }
 671
 672     // The indexes of all m_items must be adjusted, not only the index
 673     // of the new items
 674     for (int i = 0; i < m_sortedItems.count(); ++i) {
 675         m_items.insert(m_sortedItems.at(i).url(), i);
 676     }
 677
 678     itemRanges << KItemRange(insertedAtIndex, insertedCount);
 679     emit itemsInserted(itemRanges);
 680
 681 #ifdef KFILEITEMMODEL_DEBUG
 682     kDebug() << "[TIME] Inserting of" << items.count() << "items:" << timer.elapsed();
 683 #endif
 684 }
 685
 686 void KFileItemModel::removeItems(const KFileItemList& items)
 687 {
 688     if (items.isEmpty()) {
 689         return;
 690     }
 691
 692 #ifdef KFILEITEMMODEL_DEBUG
 693     kDebug() << "Removing " << items.count() << "items";
 694 #endif
 695
 696     m_groups.clear();
 697
 698     KFileItemList sortedItems = items;
 699     sort(sortedItems.begin(), sortedItems.end());
 700
 701     QList<int> indexesToRemove;
 702     indexesToRemove.reserve(items.count());
 703
 704     // Calculate the item ranges that will get deleted
 705     KItemRangeList itemRanges;
 706     int removedAtIndex = -1;
 707     int removedCount = 0;
 708     int targetIndex = 0;
 709     foreach (const KFileItem& itemToRemove, sortedItems) {
 710         const int previousTargetIndex = targetIndex;
 711         while (targetIndex < m_sortedItems.count()) {
 712             if (m_sortedItems.at(targetIndex).url() == itemToRemove.url()) {
 713                 break;
 714             }
 715             ++targetIndex;
 716         }
 717         if (targetIndex >= m_sortedItems.count()) {
 718             kWarning() << "Item that should be deleted has not been found!";
 719             return;
 720         }
 721
 722         if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
 723             itemRanges << KItemRange(removedAtIndex, removedCount);
 724             removedAtIndex = targetIndex;
 725             removedCount = 0;
 726         }
 727
 728         indexesToRemove.append(targetIndex);
 729         if (removedAtIndex < 0) {
 730             removedAtIndex = targetIndex;
 731         }
 732         ++removedCount;
 733         ++targetIndex;
 734     }
 735
 736     // Delete the items
 737     for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
 738         const int indexToRemove = indexesToRemove.at(i);
 739         m_items.remove(m_sortedItems.at(indexToRemove).url());
 740         m_sortedItems.removeAt(indexToRemove);
 741         m_data.removeAt(indexToRemove);
 742     }
 743
 744     // The indexes of all m_items must be adjusted, not only the index
 745     // of the removed items
 746     for (int i = 0; i < m_sortedItems.count(); ++i) {
 747         m_items.insert(m_sortedItems.at(i).url(), i);
 748     }
 749
 750     if (count() <= 0) {
 751         m_rootExpansionLevel = -1;
 752     }
 753
 754     itemRanges << KItemRange(removedAtIndex, removedCount);
 755     emit itemsRemoved(itemRanges);
 756 }
 757
 758 void KFileItemModel::resortAllItems()
 759 {
 760     const int itemCount = count();
 761     if (itemCount <= 0) {
 762         return;
 763     }
 764
 765     m_groups.clear();
 766
 767     const KFileItemList oldSortedItems = m_sortedItems;
 768     const QHash<KUrl, int> oldItems = m_items;
 769     const QList<QHash<QByteArray, QVariant> > oldData = m_data;
 770
 771     m_items.clear();
 772     m_data.clear();
 773
 774     sort(m_sortedItems.begin(), m_sortedItems.end());
 775     int index = 0;
 776     foreach (const KFileItem& item, m_sortedItems) {
 777         m_items.insert(item.url(), index);
 778
 779         const int oldItemIndex = oldItems.value(item.url());
 780         m_data.append(oldData.at(oldItemIndex));
 781
 782         ++index;
 783     }
 784
 785     bool emitItemsMoved = false;
 786     QList<int> movedToIndexes;
 787     movedToIndexes.reserve(m_sortedItems.count());
 788     for (int i = 0; i < itemCount; i++) {
 789         const int newIndex = m_items.value(oldSortedItems.at(i).url());
 790         movedToIndexes.append(newIndex);
 791         if (!emitItemsMoved && newIndex != i) {
 792             emitItemsMoved = true;
 793         }
 794     }
 795
 796     if (emitItemsMoved) {
 797         emit itemsMoved(KItemRange(0, itemCount), movedToIndexes);
 798     }
 799 }
 800
 801 void KFileItemModel::removeExpandedItems()
 802 {
 803     KFileItemList expandedItems;
 804
 805     const int maxIndex = m_data.count() - 1;
 806     for (int i = 0; i <= maxIndex; ++i) {
 807         if (m_data.at(i).value("expansionLevel").toInt() > 0) {
 808             const KFileItem fileItem = m_sortedItems.at(i);
 809             expandedItems.append(fileItem);
 810         }
 811     }
 812
 813     // The m_rootExpansionLevel may not get reset before all items with
 814     // a bigger expansionLevel have been removed.
 815     Q_ASSERT(m_rootExpansionLevel >= 0);
 816     removeItems(expandedItems);
 817
 818     m_rootExpansionLevel = -1;
 819     m_expandedUrls.clear();
 820 }
 821
 822 void KFileItemModel::resetRoles()
 823 {
 824     for (int i = 0; i < RolesCount; ++i) {
 825         m_requestRole[i] = false;
 826     }
 827 }
 828
 829 KFileItemModel::Role KFileItemModel::roleIndex(const QByteArray& role) const
 830 {
 831     static QHash<QByteArray, Role> rolesHash;
 832     if (rolesHash.isEmpty()) {
 833         rolesHash.insert("name", NameRole);
 834         rolesHash.insert("size", SizeRole);
 835         rolesHash.insert("date", DateRole);
 836         rolesHash.insert("permissions", PermissionsRole);
 837         rolesHash.insert("owner", OwnerRole);
 838         rolesHash.insert("group", GroupRole);
 839         rolesHash.insert("type", TypeRole);
 840         rolesHash.insert("destination", DestinationRole);
 841         rolesHash.insert("path", PathRole);
 842         rolesHash.insert("isDir", IsDirRole);
 843         rolesHash.insert("isExpanded", IsExpandedRole);
 844         rolesHash.insert("expansionLevel", ExpansionLevelRole);
 845     }
 846     return rolesHash.value(role, NoRole);
 847 }
 848
 849 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item) const
 850 {
 851     // It is important to insert only roles that are fast to retrieve. E.g.
 852     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
 853     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
 854     QHash<QByteArray, QVariant> data;
 855     data.insert("iconPixmap", QPixmap());
 856
 857     const bool isDir = item.isDir();
 858     if (m_requestRole[IsDirRole]) {
 859         data.insert("isDir", isDir);
 860     }
 861
 862     if (m_requestRole[NameRole]) {
 863         data.insert("name", item.name());
 864     }
 865
 866     if (m_requestRole[SizeRole]) {
 867         if (isDir) {
 868             data.insert("size", QVariant());
 869         } else {
 870             data.insert("size", item.size());
 871         }
 872     }
 873
 874     if (m_requestRole[DateRole]) {
 875         // Don't use KFileItem::timeString() as this is too expensive when
 876         // having several thousands of items. Instead the formatting of the
 877         // date-time will be done on-demand by the view when the date will be shown.
 878         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
 879         data.insert("date", dateTime.dateTime());
 880     }
 881
 882     if (m_requestRole[PermissionsRole]) {
 883         data.insert("permissions", item.permissionsString());
 884     }
 885
 886     if (m_requestRole[OwnerRole]) {
 887         data.insert("owner", item.user());
 888     }
 889
 890     if (m_requestRole[GroupRole]) {
 891         data.insert("group", item.group());
 892     }
 893
 894     if (m_requestRole[DestinationRole]) {
 895         QString destination = item.linkDest();
 896         if (destination.isEmpty()) {
 897             destination = i18nc("@item:intable", "No destination");
 898         }
 899         data.insert("destination", destination);
 900     }
 901
 902     if (m_requestRole[PathRole]) {
 903         data.insert("path", item.localPath());
 904     }
 905
 906     if (m_requestRole[IsExpandedRole]) {
 907         data.insert("isExpanded", false);
 908     }
 909
 910     if (m_requestRole[ExpansionLevelRole]) {
 911         if (m_rootExpansionLevel < 0) {
 912             KDirLister* dirLister = m_dirLister.data();
 913             if (dirLister) {
 914                 const QString rootDir = dirLister->url().directory(KUrl::AppendTrailingSlash);
 915                 m_rootExpansionLevel = rootDir.count('/');
 916             }
 917         }
 918         const QString dir = item.url().directory(KUrl::AppendTrailingSlash);
 919         const int level = dir.count('/') - m_rootExpansionLevel - 1;
 920         data.insert("expansionLevel", level);
 921     }
 922
 923     if (item.isMimeTypeKnown()) {
 924         data.insert("iconName", item.iconName());
 925
 926         if (m_requestRole[TypeRole]) {
 927             data.insert("type", item.mimeComment());
 928         }
 929     }
 930
 931     return data;
 932 }
 933
 934 bool KFileItemModel::lessThan(const KFileItem& a, const KFileItem& b) const
 935 {
 936     int result = 0;
 937
 938     if (m_rootExpansionLevel >= 0) {
 939         result = expansionLevelsCompare(a, b);
 940         if (result != 0) {
 941             // The items have parents with different expansion levels
 942             return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
 943         }
 944     }
 945
 946     if (m_sortFoldersFirst || m_sortRole == SizeRole) {
 947         const bool isDirA = a.isDir();
 948         const bool isDirB = b.isDir();
 949         if (isDirA && !isDirB) {
 950             return true;
 951         } else if (!isDirA && isDirB) {
 952             return false;
 953         }
 954     }
 955
 956     switch (m_sortRole) {
 957     case NameRole: {
 958         result = stringCompare(a.text(), b.text());
 959         if (result == 0) {
 960             // KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
 961             result = stringCompare(a.name(m_caseSensitivity == Qt::CaseInsensitive),
 962                                    b.name(m_caseSensitivity == Qt::CaseInsensitive));
 963         }
 964         break;
 965     }
 966
 967     case DateRole: {
 968         const KDateTime dateTimeA = a.time(KFileItem::ModificationTime);
 969         const KDateTime dateTimeB = b.time(KFileItem::ModificationTime);
 970         if (dateTimeA < dateTimeB) {
 971             result = -1;
 972         } else if (dateTimeA > dateTimeB) {
 973             result = +1;
 974         }
 975         break;
 976     }
 977
 978     case SizeRole: {
 979         // TODO: Implement sorting folders by the number of items inside.
 980         // This is more tricky to get right because this number is retrieved
 981         // asynchronously by KFileItemModelRolesUpdater.
 982         const KIO::filesize_t sizeA = a.size();
 983         const KIO::filesize_t sizeB = b.size();
 984         if (sizeA < sizeB) {
 985             result = -1;
 986         } else if (sizeA > sizeB) {
 987             result = +1;
 988         }
 989         break;
 990     }
 991
 992     default:
 993         break;
 994     }
 995
 996     if (result == 0) {
 997         // It must be assured that the sort order is always unique even if two values have been
 998         // equal. In this case a comparison of the URL is done which is unique in all cases
 999         // within KDirLister.
1000         result = QString::compare(a.url().url(), b.url().url(), Qt::CaseSensitive);
1001     }
1002
1003     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
1004 }
1005
1006 void KFileItemModel::sort(const KFileItemList::iterator& startIterator, const KFileItemList::iterator& endIterator)
1007 {
1008     KFileItemList::iterator start = startIterator;
1009     KFileItemList::iterator end = endIterator;
1010
1011     // The implementation is based on qSortHelper() from qalgorithms.h
1012     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1013     // In opposite to qSort() it allows to use a member-function for the comparison of elements.
1014     while (1) {
1015         int span = int(end - start);
1016         if (span < 2) {
1017             return;
1018         }
1019
1020         --end;
1021         KFileItemList::iterator low = start, high = end - 1;
1022         KFileItemList::iterator pivot = start + span / 2;
1023
1024         if (lessThan(*end, *start)) {
1025             qSwap(*end, *start);
1026         }
1027         if (span == 2) {
1028             return;
1029         }
1030
1031         if (lessThan(*pivot, *start)) {
1032             qSwap(*pivot, *start);
1033         }
1034         if (lessThan(*end, *pivot)) {
1035             qSwap(*end, *pivot);
1036         }
1037         if (span == 3) {
1038             return;
1039         }
1040
1041         qSwap(*pivot, *end);
1042
1043         while (low < high) {
1044             while (low < high && lessThan(*low, *end)) {
1045                 ++low;
1046             }
1047
1048             while (high > low && lessThan(*end, *high)) {
1049                 --high;
1050             }
1051             if (low < high) {
1052                 qSwap(*low, *high);
1053                 ++low;
1054                 --high;
1055             } else {
1056                 break;
1057             }
1058         }
1059
1060         if (lessThan(*low, *end)) {
1061             ++low;
1062         }
1063
1064         qSwap(*end, *low);
1065         sort(start, low);
1066
1067         start = low + 1;
1068         ++end;
1069     }
1070 }
1071
1072 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
1073 {
1074     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
1075     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
1076     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
1077     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
1078
1079     if (m_caseSensitivity == Qt::CaseInsensitive) {
1080         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
1081                                             : QString::compare(a, b, Qt::CaseInsensitive);
1082         if (result != 0) {
1083             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
1084             // comparison, still a deterministic sort order is required. A case sensitive
1085             // comparison is done as fallback.
1086             return result;
1087         }
1088     }
1089
1090     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
1091                             : QString::compare(a, b, Qt::CaseSensitive);
1092 }
1093
1094 int KFileItemModel::expansionLevelsCompare(const KFileItem& a, const KFileItem& b) const
1095 {
1096     const KUrl urlA = a.url();
1097     const KUrl urlB = b.url();
1098     if (urlA.directory() == urlB.directory()) {
1099         // Both items have the same directory as parent
1100         return 0;
1101     }
1102
1103     // Check whether one item is the parent of the other item
1104     if (urlA.isParentOf(urlB)) {
1105         return -1;
1106     } else if (urlB.isParentOf(urlA)) {
1107         return +1;
1108     }
1109
1110     // Determine the maximum common path of both items and
1111     // remember the index in 'index'
1112     const QString pathA = urlA.path();
1113     const QString pathB = urlB.path();
1114
1115     const int maxIndex = qMin(pathA.length(), pathB.length()) - 1;
1116     int index = 0;
1117     while (index <= maxIndex && pathA.at(index) == pathB.at(index)) {
1118         ++index;
1119     }
1120     if (index > maxIndex) {
1121         index = maxIndex;
1122     }
1123     while ((pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/')) && index > 0) {
1124         --index;
1125     }
1126
1127     // Determine the first sub-path after the common path and
1128     // check whether it represents a directory or already a file
1129     bool isDirA = true;
1130     const QString subPathA = subPath(a, pathA, index, &isDirA);
1131     bool isDirB = true;
1132     const QString subPathB = subPath(b, pathB, index, &isDirB);
1133
1134     if (isDirA && !isDirB) {
1135         return -1;
1136     } else if (!isDirA && isDirB) {
1137         return +1;
1138     }
1139
1140     return stringCompare(subPathA, subPathB);
1141 }
1142
1143 QString KFileItemModel::subPath(const KFileItem& item,
1144                                 const QString& itemPath,
1145                                 int start,
1146                                 bool* isDir) const
1147 {
1148     Q_ASSERT(isDir);
1149     const int pathIndex = itemPath.indexOf('/', start + 1);
1150     *isDir = (pathIndex > 0) || item.isDir();
1151     return itemPath.mid(start, pathIndex - start);
1152 }
1153
1154 bool KFileItemModel::useMaximumUpdateInterval() const
1155 {
1156     const KDirLister* dirLister = m_dirLister.data();
1157     return dirLister && !dirLister->url().isLocalFile();
1158 }
1159
1160 QList<QPair<int, QVariant> > KFileItemModel::nameRoleGroups() const
1161 {
1162     Q_ASSERT(!m_data.isEmpty());
1163
1164     const int maxIndex = count() - 1;
1165     QList<QPair<int, QVariant> > groups;
1166
1167     QString groupValue;
1168     QChar firstChar;
1169     bool isLetter = false;
1170     for (int i = 0; i <= maxIndex; ++i) {
1171         if (m_requestRole[ExpansionLevelRole] && m_data.at(i).value("expansionLevel").toInt() > 0) {
1172             // KItemListView would be capable to show sub-groups in groups but
1173             // in typical usecases this results in visual clutter, hence we
1174             // just ignore sub-groups.
1175             continue;
1176         }
1177
1178         const QString name = m_data.at(i).value("name").toString();
1179
1180         // Use the first character of the name as group indication
1181         QChar newFirstChar = name.at(0).toUpper();
1182         if (newFirstChar == QLatin1Char('~') && name.length() > 1) {
1183             newFirstChar = name.at(1);
1184         }
1185
1186         if (firstChar != newFirstChar) {
1187             QString newGroupValue;
1188             if (newFirstChar >= QLatin1Char('A') && newFirstChar <= QLatin1Char('Z')) {
1189                 // Apply group 'A' - 'Z'
1190                 newGroupValue = newFirstChar;
1191                 isLetter = true;
1192             } else if (newFirstChar >= QLatin1Char('0') && newFirstChar <= QLatin1Char('9')) {
1193                 // Apply group '0 - 9' for any name that starts with a digit
1194                 newGroupValue = i18nc("@title:group Groups that start with a digit", "0 - 9");
1195                 isLetter = false;
1196             } else {
1197                 if (isLetter) {
1198                     // If the current group is 'A' - 'Z' check whether a locale character
1199                     // fits into the existing group.
1200                     // TODO: This does not work in the case if e.g. the group 'O' starts with
1201                     // an umlaut 'O' -> provide unit-test to document this known issue
1202                     const QChar prevChar(firstChar.unicode() - ushort(1));
1203                     const QChar nextChar(firstChar.unicode() + ushort(1));
1204                     const QString currChar(newFirstChar);
1205                     const bool partOfCurrentGroup = currChar.localeAwareCompare(prevChar) > 0 &&
1206                                                     currChar.localeAwareCompare(nextChar) < 0;
1207                     if (partOfCurrentGroup) {
1208                         continue;
1209                     }
1210                 }
1211                 newGroupValue = i18nc("@title:group", "Others");
1212                 isLetter = false;
1213             }
1214
1215             if (newGroupValue != groupValue) {
1216                 groupValue = newGroupValue;
1217                 groups.append(QPair<int, QVariant>(i, newGroupValue));
1218             }
1219
1220             firstChar = newFirstChar;
1221         }
1222     }
1223     return groups;
1224 }
1225
1226 QList<QPair<int, QVariant> > KFileItemModel::sizeRoleGroups() const
1227 {
1228     Q_ASSERT(!m_data.isEmpty());
1229
1230     return QList<QPair<int, QVariant> >();
1231 }
1232
1233 QList<QPair<int, QVariant> > KFileItemModel::dateRoleGroups() const
1234 {
1235     Q_ASSERT(!m_data.isEmpty());
1236     return QList<QPair<int, QVariant> >();
1237 }
1238
1239 QList<QPair<int, QVariant> > KFileItemModel::permissionRoleGroups() const
1240 {
1241     Q_ASSERT(!m_data.isEmpty());
1242     return QList<QPair<int, QVariant> >();
1243 }
1244
1245 QList<QPair<int, QVariant> > KFileItemModel::ownerRoleGroups() const
1246 {
1247     Q_ASSERT(!m_data.isEmpty());
1248     return QList<QPair<int, QVariant> >();
1249 }
1250
1251 QList<QPair<int, QVariant> > KFileItemModel::groupRoleGroups() const
1252 {
1253     Q_ASSERT(!m_data.isEmpty());
1254     return QList<QPair<int, QVariant> >();
1255 }
1256
1257 QList<QPair<int, QVariant> > KFileItemModel::typeRoleGroups() const
1258 {
1259     Q_ASSERT(!m_data.isEmpty());
1260     return QList<QPair<int, QVariant> >();
1261 }
1262
1263 QList<QPair<int, QVariant> > KFileItemModel::destinationRoleGroups() const
1264 {
1265     Q_ASSERT(!m_data.isEmpty());
1266     return QList<QPair<int, QVariant> >();
1267 }
1268
1269 QList<QPair<int, QVariant> > KFileItemModel::pathRoleGroups() const
1270 {
1271     Q_ASSERT(!m_data.isEmpty());
1272     return QList<QPair<int, QVariant> >();
1273 }
1274
1275 #include "kfileitemmodel.moc"