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 <KLocale>
  24 #include <KStringHandler>
  25 #include <KDebug>
  26
  27 #include <QTimer>
  28
  29 #define KFILEITEMMODEL_DEBUG
  30
  31 KFileItemModel::KFileItemModel(KDirLister* dirLister, QObject* parent) :
  32     KItemModelBase(QByteArray(), "name", parent),
  33     m_dirLister(dirLister),
  34     m_naturalSorting(true),
  35     m_sortFoldersFirst(true),
  36     m_groupRole(NoRole),
  37     m_sortRole(NameRole),
  38     m_caseSensitivity(Qt::CaseInsensitive),
  39     m_sortedItems(),
  40     m_items(),
  41     m_data(),
  42     m_requestRole(),
  43     m_minimumUpdateIntervalTimer(0),
  44     m_maximumUpdateIntervalTimer(0),
  45     m_pendingItemsToInsert(),
  46     m_pendingItemsToDelete(),
  47     m_rootExpansionLevel(-1)
  48 {
  49     resetRoles();
  50     m_requestRole[NameRole] = true;
  51     m_requestRole[IsDirRole] = true;
  52
  53     Q_ASSERT(dirLister);
  54
  55     connect(dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  56     connect(dirLister, SIGNAL(completed()), this, SLOT(slotCompleted()));
  57     connect(dirLister, SIGNAL(newItems(KFileItemList)), this, SLOT(slotNewItems(KFileItemList)));
  58     connect(dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  59     connect(dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  60     connect(dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  61
  62     // Although the layout engine of KItemListView is fast it is very inefficient to e.g.
  63     // emit 50 itemsInserted()-signals each 100 ms. m_minimumUpdateIntervalTimer assures that updates
  64     // are done in 1 second intervals for equal operations.
  65     m_minimumUpdateIntervalTimer = new QTimer(this);
  66     m_minimumUpdateIntervalTimer->setInterval(1000);
  67     m_minimumUpdateIntervalTimer->setSingleShot(true);
  68     connect(m_minimumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItems()));
  69
  70     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  71     // before the completed() or canceled() signal has been emitted.
  72     m_maximumUpdateIntervalTimer = new QTimer(this);
  73     m_maximumUpdateIntervalTimer->setInterval(2000);
  74     m_maximumUpdateIntervalTimer->setSingleShot(true);
  75     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItems()));
  76
  77     Q_ASSERT(m_minimumUpdateIntervalTimer->interval() <= m_maximumUpdateIntervalTimer->interval());
  78 }
  79
  80 KFileItemModel::~KFileItemModel()
  81 {
  82 }
  83
  84 int KFileItemModel::count() const
  85 {
  86     return m_data.count();
  87 }
  88
  89 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
  90 {
  91     if (index >= 0 && index < count()) {
  92         return m_data.at(index);
  93     }
  94     return QHash<QByteArray, QVariant>();
  95 }
  96
  97 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
  98 {
  99     if (index >= 0 && index < count()) {
 100         QHash<QByteArray, QVariant> currentValue = m_data.at(index);
 101
 102         QSet<QByteArray> changedRoles;
 103         QHashIterator<QByteArray, QVariant> it(values);
 104         while (it.hasNext()) {
 105             it.next();
 106             const QByteArray role = it.key();
 107             const QVariant value = it.value();
 108
 109             if (currentValue[role] != value) {
 110                 currentValue[role] = value;
 111                 changedRoles.insert(role);
 112             }
 113         }
 114
 115         if (!changedRoles.isEmpty()) {
 116             m_data[index] = currentValue;
 117             emit itemsChanged(KItemRangeList() << KItemRange(index, 1), changedRoles);
 118         }
 119
 120         return true;
 121     }
 122     return false;
 123 }
 124
 125 bool KFileItemModel::supportsGrouping() const
 126 {
 127     return true;
 128 }
 129
 130 bool KFileItemModel::supportsSorting() const
 131 {
 132     return true;
 133 }
 134
 135 KFileItem KFileItemModel::fileItem(int index) const
 136 {
 137     if (index >= 0 && index < count()) {
 138         return m_sortedItems.at(index);
 139     }
 140
 141     return KFileItem();
 142 }
 143
 144 int KFileItemModel::index(const KFileItem& item) const
 145 {
 146     if (item.isNull()) {
 147         return -1;
 148     }
 149
 150     return m_items.value(item, -1);
 151 }
 152
 153 void KFileItemModel::clear()
 154 {
 155     slotClear();
 156 }
 157
 158 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 159 {
 160     if (count() > 0) {
 161         const bool supportedExpanding = m_requestRole[IsExpandedRole] && m_requestRole[ExpansionLevelRole];
 162         const bool willSupportExpanding = roles.contains("isExpanded") && roles.contains("expansionLevel");
 163         if (supportedExpanding && !willSupportExpanding) {
 164             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 165             // that is not 0 (and hence are part of an expanded item).
 166             removeExpandedItems();
 167         }
 168     }
 169
 170     resetRoles();
 171     QSetIterator<QByteArray> it(roles);
 172     while (it.hasNext()) {
 173         const QByteArray& role = it.next();
 174         m_requestRole[roleIndex(role)] = true;
 175     }
 176
 177     if (count() > 0) {
 178         // Update m_data with the changed requested roles
 179         const int maxIndex = count() - 1;
 180         for (int i = 0; i <= maxIndex; ++i) {
 181             m_data[i] = retrieveData(m_sortedItems.at(i));
 182         }
 183
 184         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 185         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 186     }
 187 }
 188
 189 QSet<QByteArray> KFileItemModel::roles() const
 190 {
 191     QSet<QByteArray> roles;
 192     for (int i = 0; i < RolesCount; ++i) {
 193         if (m_requestRole[i]) {
 194             switch (i) {
 195             case NoRole:             break;
 196             case NameRole:           roles.insert("name"); break;
 197             case SizeRole:           roles.insert("size"); break;
 198             case DateRole:           roles.insert("date"); break;
 199             case PermissionsRole:    roles.insert("permissions"); break;
 200             case OwnerRole:          roles.insert("owner"); break;
 201             case GroupRole:          roles.insert("group"); break;
 202             case TypeRole:           roles.insert("type"); break;
 203             case DestinationRole:    roles.insert("destination"); break;
 204             case PathRole:           roles.insert("path"); break;
 205             case IsDirRole:          roles.insert("isDir"); break;
 206             case IsExpandedRole:     roles.insert("isExpanded"); break;
 207             case ExpansionLevelRole: roles.insert("expansionLevel"); break;
 208             default:                 Q_ASSERT(false); break;
 209             }
 210         }
 211     }
 212     return roles;
 213 }
 214
 215 bool KFileItemModel::setExpanded(int index, bool expanded)
 216 {
 217     if (isExpanded(index) == expanded || index < 0 || index >= count()) {
 218         return false;
 219     }
 220
 221     QHash<QByteArray, QVariant> values;
 222     values.insert("isExpanded", expanded);
 223     if (!setData(index, values)) {
 224         return false;
 225     }
 226
 227     if (expanded) {
 228         const KUrl url = m_sortedItems.at(index).url();
 229         KDirLister* dirLister = m_dirLister.data();
 230         if (dirLister) {
 231             dirLister->openUrl(url, KDirLister::Keep);
 232             return true;
 233         }
 234     } else {
 235         KFileItemList itemsToRemove;
 236         const int expansionLevel = data(index)["expansionLevel"].toInt();
 237         ++index;
 238         while (index < count() && data(index)["expansionLevel"].toInt() > expansionLevel) {
 239             itemsToRemove.append(m_sortedItems.at(index));
 240             ++index;
 241         }
 242         removeItems(itemsToRemove);
 243         return true;
 244     }
 245
 246     return false;
 247 }
 248
 249 bool KFileItemModel::isExpanded(int index) const
 250 {
 251     if (index >= 0 && index < count()) {
 252         return m_data.at(index).value("isExpanded").toBool();
 253     }
 254     return false;
 255 }
 256
 257 bool KFileItemModel::isExpandable(int index) const
 258 {
 259     if (index >= 0 && index < count()) {
 260         return m_sortedItems.at(index).isDir();
 261     }
 262     return false;
 263 }
 264
 265 void KFileItemModel::onGroupRoleChanged(const QByteArray& current, const QByteArray& previous)
 266 {
 267     Q_UNUSED(previous);
 268     m_groupRole = roleIndex(current);
 269 }
 270
 271 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 272 {
 273     Q_UNUSED(previous);
 274     const int itemCount = count();
 275     if (itemCount <= 0) {
 276         return;
 277     }
 278
 279     m_sortRole = roleIndex(current);
 280
 281     KFileItemList sortedItems = m_sortedItems;
 282     m_sortedItems.clear();
 283     m_items.clear();
 284     m_data.clear();
 285     emit itemsRemoved(KItemRangeList() << KItemRange(0, itemCount));
 286
 287     sort(sortedItems.begin(), sortedItems.end());
 288     int index = 0;
 289     foreach (const KFileItem& item, sortedItems) {
 290         m_sortedItems.append(item);
 291         m_items.insert(item, index);
 292         m_data.append(retrieveData(item));
 293
 294         ++index;
 295     }
 296
 297     emit itemsInserted(KItemRangeList() << KItemRange(0, itemCount));
 298 }
 299
 300 void KFileItemModel::slotCompleted()
 301 {
 302     if (m_minimumUpdateIntervalTimer->isActive()) {
 303         // dispatchPendingItems() will be called when the timer
 304         // has been expired.
 305         return;
 306     }
 307
 308     dispatchPendingItems();
 309     m_minimumUpdateIntervalTimer->start();
 310 }
 311
 312 void KFileItemModel::slotCanceled()
 313 {
 314     m_minimumUpdateIntervalTimer->stop();
 315     m_maximumUpdateIntervalTimer->stop();
 316     dispatchPendingItems();
 317 }
 318
 319 void KFileItemModel::slotNewItems(const KFileItemList& items)
 320 {
 321     if (!m_pendingItemsToDelete.isEmpty()) {
 322         removeItems(m_pendingItemsToDelete);
 323         m_pendingItemsToDelete.clear();
 324     }
 325     m_pendingItemsToInsert.append(items);
 326
 327     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 328         // Assure that items get dispatched if no completed() or canceled() signal is
 329         // emitted during the maximum update interval.
 330         m_maximumUpdateIntervalTimer->start();
 331     }
 332 }
 333
 334 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 335 {
 336     if (!m_pendingItemsToInsert.isEmpty()) {
 337         insertItems(m_pendingItemsToInsert);
 338         m_pendingItemsToInsert.clear();
 339     }
 340     m_pendingItemsToDelete.append(items);
 341 }
 342
 343 void KFileItemModel::slotClear()
 344 {
 345 #ifdef KFILEITEMMODEL_DEBUG
 346     kDebug() << "Clearing all items";
 347 #endif
 348
 349     m_minimumUpdateIntervalTimer->stop();
 350     m_maximumUpdateIntervalTimer->stop();
 351     m_pendingItemsToInsert.clear();
 352     m_pendingItemsToDelete.clear();
 353
 354     m_rootExpansionLevel = -1;
 355
 356     const int removedCount = m_data.count();
 357     if (removedCount > 0) {
 358         m_sortedItems.clear();
 359         m_items.clear();
 360         m_data.clear();
 361         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
 362     }
 363 }
 364
 365 void KFileItemModel::slotClear(const KUrl& url)
 366 {
 367     Q_UNUSED(url);
 368 }
 369
 370 void KFileItemModel::dispatchPendingItems()
 371 {
 372     if (!m_pendingItemsToInsert.isEmpty()) {
 373         Q_ASSERT(m_pendingItemsToDelete.isEmpty());
 374         insertItems(m_pendingItemsToInsert);
 375         m_pendingItemsToInsert.clear();
 376     } else if (!m_pendingItemsToDelete.isEmpty()) {
 377         Q_ASSERT(m_pendingItemsToInsert.isEmpty());
 378         removeItems(m_pendingItemsToDelete);
 379         m_pendingItemsToDelete.clear();
 380     }
 381 }
 382
 383 void KFileItemModel::insertItems(const KFileItemList& items)
 384 {
 385     if (items.isEmpty()) {
 386         return;
 387     }
 388
 389 #ifdef KFILEITEMMODEL_DEBUG
 390     QElapsedTimer timer;
 391     timer.start();
 392     kDebug() << "===========================================================";
 393     kDebug() << "Inserting" << items.count() << "items";
 394 #endif
 395
 396     KFileItemList sortedItems = items;
 397     sort(sortedItems.begin(), sortedItems.end());
 398
 399 #ifdef KFILEITEMMODEL_DEBUG
 400     kDebug() << "[TIME] Sorting:" << timer.elapsed();
 401 #endif
 402
 403     KItemRangeList itemRanges;
 404     int targetIndex = 0;
 405     int sourceIndex = 0;
 406     int insertedAtIndex = -1;         // Index for the current item-range
 407     int insertedCount = 0;            // Count for the current item-range
 408     int previouslyInsertedCount = 0;  // Sum of previously inserted items for all ranges
 409     while (sourceIndex < sortedItems.count()) {
 410         // Find target index from m_items to insert the current item
 411         // in a sorted order
 412         const int previousTargetIndex = targetIndex;
 413         while (targetIndex < m_sortedItems.count()) {
 414             if (!lessThan(m_sortedItems.at(targetIndex), sortedItems.at(sourceIndex))) {
 415                 break;
 416             }
 417             ++targetIndex;
 418         }
 419
 420         if (targetIndex - previousTargetIndex > 0 && insertedAtIndex >= 0) {
 421             itemRanges << KItemRange(insertedAtIndex, insertedCount);
 422             previouslyInsertedCount += insertedCount;
 423             insertedAtIndex = targetIndex - previouslyInsertedCount;
 424             insertedCount = 0;
 425         }
 426
 427         // Insert item at the position targetIndex
 428         const KFileItem item = sortedItems.at(sourceIndex);
 429         m_sortedItems.insert(targetIndex, item);
 430         m_data.insert(targetIndex, retrieveData(item));
 431         // m_items will be inserted after the loop (see comment below)
 432         ++insertedCount;
 433
 434         if (insertedAtIndex < 0) {
 435             insertedAtIndex = targetIndex;
 436             Q_ASSERT(previouslyInsertedCount == 0);
 437         }
 438         ++targetIndex;
 439         ++sourceIndex;
 440     }
 441
 442     // The indexes of all m_items must be adjusted, not only the index
 443     // of the new items
 444     for (int i = 0; i < m_sortedItems.count(); ++i) {
 445         m_items.insert(m_sortedItems.at(i), i);
 446     }
 447
 448     itemRanges << KItemRange(insertedAtIndex, insertedCount);
 449     emit itemsInserted(itemRanges);
 450
 451 #ifdef KFILEITEMMODEL_DEBUG
 452     kDebug() << "[TIME] Inserting of" << items.count() << "items:" << timer.elapsed();
 453 #endif
 454 }
 455
 456 void KFileItemModel::removeItems(const KFileItemList& items)
 457 {
 458     if (items.isEmpty()) {
 459         return;
 460     }
 461
 462 #ifdef KFILEITEMMODEL_DEBUG
 463     kDebug() << "Removing " << items.count() << "items";
 464 #endif
 465
 466     KFileItemList sortedItems = items;
 467     sort(sortedItems.begin(), sortedItems.end());
 468
 469     QList<int> indexesToRemove;
 470     indexesToRemove.reserve(items.count());
 471
 472     // Calculate the item ranges that will get deleted
 473     KItemRangeList itemRanges;
 474     int removedAtIndex = -1;
 475     int removedCount = 0;
 476     int targetIndex = 0;
 477     foreach (const KFileItem& itemToRemove, sortedItems) {
 478         const int previousTargetIndex = targetIndex;
 479         while (targetIndex < m_sortedItems.count()) {
 480             if (m_sortedItems.at(targetIndex) == itemToRemove) {
 481                 break;
 482             }
 483             ++targetIndex;
 484         }
 485         if (targetIndex >= m_sortedItems.count()) {
 486             kWarning() << "Item that should be deleted has not been found!";
 487             return;
 488         }
 489
 490         if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
 491             itemRanges << KItemRange(removedAtIndex, removedCount);
 492             removedAtIndex = targetIndex;
 493             removedCount = 0;
 494         }
 495
 496         indexesToRemove.append(targetIndex);
 497         if (removedAtIndex < 0) {
 498             removedAtIndex = targetIndex;
 499         }
 500         ++removedCount;
 501         ++targetIndex;
 502     }
 503
 504     // Delete the items
 505     for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
 506         const int indexToRemove = indexesToRemove.at(i);
 507         m_items.remove(m_sortedItems.at(indexToRemove));
 508         m_sortedItems.removeAt(indexToRemove);
 509         m_data.removeAt(indexToRemove);
 510     }
 511
 512     // The indexes of all m_items must be adjusted, not only the index
 513     // of the removed items
 514     for (int i = 0; i < m_sortedItems.count(); ++i) {
 515         m_items.insert(m_sortedItems.at(i), i);
 516     }
 517
 518     if (count() <= 0) {
 519         m_rootExpansionLevel = -1;
 520     }
 521
 522     itemRanges << KItemRange(removedAtIndex, removedCount);
 523     emit itemsRemoved(itemRanges);
 524 }
 525
 526 void KFileItemModel::removeExpandedItems()
 527 {
 528
 529     KFileItemList expandedItems;
 530
 531     const int maxIndex = m_data.count() - 1;
 532     for (int i = 0; i <= maxIndex; ++i) {
 533         if (m_data.at(i).value("expansionLevel").toInt() > 0) {
 534             const KFileItem fileItem = m_sortedItems.at(i);
 535             expandedItems.append(fileItem);
 536         }
 537     }
 538
 539     // The m_rootExpansionLevel may not get reset before all items with
 540     // a bigger expansionLevel have been removed.
 541     Q_ASSERT(m_rootExpansionLevel >= 0);
 542     removeItems(expandedItems);
 543
 544     m_rootExpansionLevel = -1;
 545 }
 546
 547 void KFileItemModel::resetRoles()
 548 {
 549     for (int i = 0; i < RolesCount; ++i) {
 550         m_requestRole[i] = false;
 551     }
 552 }
 553
 554 KFileItemModel::Role KFileItemModel::roleIndex(const QByteArray& role) const
 555 {
 556     static QHash<QByteArray, Role> rolesHash;
 557     if (rolesHash.isEmpty()) {
 558         rolesHash.insert("name", NameRole);
 559         rolesHash.insert("size", SizeRole);
 560         rolesHash.insert("date", DateRole);
 561         rolesHash.insert("permissions", PermissionsRole);
 562         rolesHash.insert("owner", OwnerRole);
 563         rolesHash.insert("group", GroupRole);
 564         rolesHash.insert("type", TypeRole);
 565         rolesHash.insert("destination", DestinationRole);
 566         rolesHash.insert("path", PathRole);
 567         rolesHash.insert("isDir", IsDirRole);
 568         rolesHash.insert("isExpanded", IsExpandedRole);
 569         rolesHash.insert("expansionLevel", ExpansionLevelRole);
 570     }
 571     return rolesHash.value(role, NoRole);
 572 }
 573
 574 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item) const
 575 {
 576     // It is important to insert only roles that are fast to retrieve. E.g.
 577     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
 578     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
 579     QHash<QByteArray, QVariant> data;
 580     data.insert("iconPixmap", QPixmap());
 581
 582     const bool isDir = item.isDir();
 583     if (m_requestRole[IsDirRole]) {
 584         data.insert("isDir", isDir);
 585     }
 586
 587     if (m_requestRole[NameRole]) {
 588         data.insert("name", item.name());
 589     }
 590
 591     if (m_requestRole[SizeRole]) {
 592         if (isDir) {
 593             data.insert("size", QVariant());
 594         } else {
 595             data.insert("size", item.size());
 596         }
 597     }
 598
 599     if (m_requestRole[DateRole]) {
 600         // Don't use KFileItem::timeString() as this is too expensive when
 601         // having several thousands of items. Instead the formatting of the
 602         // date-time will be done on-demand by the view when the date will be shown.
 603         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
 604         data.insert("date", dateTime.dateTime());
 605     }
 606
 607     if (m_requestRole[PermissionsRole]) {
 608         data.insert("permissions", item.permissionsString());
 609     }
 610
 611     if (m_requestRole[OwnerRole]) {
 612         data.insert("owner", item.user());
 613     }
 614
 615     if (m_requestRole[GroupRole]) {
 616         data.insert("group", item.group());
 617     }
 618
 619     if (m_requestRole[DestinationRole]) {
 620         QString destination = item.linkDest();
 621         if (destination.isEmpty()) {
 622             destination = i18nc("@item:intable", "No destination");
 623         }
 624         data.insert("destination", destination);
 625     }
 626
 627     if (m_requestRole[PathRole]) {
 628         data.insert("path", item.localPath());
 629     }
 630
 631     if (m_requestRole[IsExpandedRole]) {
 632         data.insert("isExpanded", false);
 633     }
 634
 635     if (m_requestRole[ExpansionLevelRole]) {
 636         if (m_rootExpansionLevel < 0) {
 637             KDirLister* dirLister = m_dirLister.data();
 638             if (dirLister) {
 639                 const QString rootDir = dirLister->url().directory(KUrl::AppendTrailingSlash);
 640                 m_rootExpansionLevel = rootDir.count('/');
 641             }
 642         }
 643         const QString dir = item.url().directory(KUrl::AppendTrailingSlash);
 644         const int level = dir.count('/') - m_rootExpansionLevel - 1;
 645         data.insert("expansionLevel", level);
 646     }
 647
 648     if (item.isMimeTypeKnown()) {
 649         data.insert("iconName", item.iconName());
 650
 651         if (m_requestRole[TypeRole]) {
 652             data.insert("type", item.mimeComment());
 653         }
 654     }
 655
 656     return data;
 657 }
 658
 659 bool KFileItemModel::lessThan(const KFileItem& a, const KFileItem& b) const
 660 {
 661     int result = 0;
 662
 663     if (m_rootExpansionLevel >= 0) {
 664         result = expansionLevelsCompare(a, b);
 665         if (result != 0) {
 666             // The items have parents with different expansion levels
 667             return result < 0;
 668         }
 669     }
 670
 671     if (m_sortFoldersFirst) {
 672         const bool isDirA = a.isDir();
 673         const bool isDirB = b.isDir();
 674         if (isDirA && !isDirB) {
 675             return true;
 676         } else if (!isDirA && isDirB) {
 677             return false;
 678         }
 679     }
 680
 681     switch (m_sortRole) {
 682     case NameRole: {
 683         result = stringCompare(a.text(), b.text());
 684         if (result == 0) {
 685             // KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
 686             result = stringCompare(a.name(m_caseSensitivity == Qt::CaseInsensitive),
 687                                    b.name(m_caseSensitivity == Qt::CaseInsensitive));
 688         }
 689         break;
 690     }
 691
 692     case DateRole: {
 693         const KDateTime dateTimeA = a.time(KFileItem::ModificationTime);
 694         const KDateTime dateTimeB = b.time(KFileItem::ModificationTime);
 695         if (dateTimeA < dateTimeB) {
 696             result = -1;
 697         } else if (dateTimeA > dateTimeB) {
 698             result = +1;
 699         }
 700         break;
 701     }
 702
 703     default:
 704         break;
 705     }
 706
 707     if (result == 0) {
 708         // It must be assured that the sort order is always unique even if two values have been
 709         // equal. In this case a comparison of the URL is done which is unique in all cases
 710         // within KDirLister.
 711         result = QString::compare(a.url().url(), b.url().url(), Qt::CaseSensitive);
 712     }
 713
 714     return result < 0;
 715 }
 716
 717 void KFileItemModel::sort(const KFileItemList::iterator& startIterator, const KFileItemList::iterator& endIterator)
 718 {
 719     KFileItemList::iterator start = startIterator;
 720     KFileItemList::iterator end = endIterator;
 721
 722     // The implementation is based on qSortHelper() from qalgorithms.h
 723     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 724     // In opposite to qSort() it allows to use a member-function for the comparison of elements.
 725     while (1) {
 726         int span = int(end - start);
 727         if (span < 2) {
 728             return;
 729         }
 730
 731         --end;
 732         KFileItemList::iterator low = start, high = end - 1;
 733         KFileItemList::iterator pivot = start + span / 2;
 734
 735         if (lessThan(*end, *start)) {
 736             qSwap(*end, *start);
 737         }
 738         if (span == 2) {
 739             return;
 740         }
 741
 742         if (lessThan(*pivot, *start)) {
 743             qSwap(*pivot, *start);
 744         }
 745         if (lessThan(*end, *pivot)) {
 746             qSwap(*end, *pivot);
 747         }
 748         if (span == 3) {
 749             return;
 750         }
 751
 752         qSwap(*pivot, *end);
 753
 754         while (low < high) {
 755             while (low < high && lessThan(*low, *end)) {
 756                 ++low;
 757             }
 758
 759             while (high > low && lessThan(*end, *high)) {
 760                 --high;
 761             }
 762             if (low < high) {
 763                 qSwap(*low, *high);
 764                 ++low;
 765                 --high;
 766             } else {
 767                 break;
 768             }
 769         }
 770
 771         if (lessThan(*low, *end)) {
 772             ++low;
 773         }
 774
 775         qSwap(*end, *low);
 776         sort(start, low);
 777
 778         start = low + 1;
 779         ++end;
 780     }
 781 }
 782
 783 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
 784 {
 785     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
 786     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
 787     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
 788     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
 789
 790     if (m_caseSensitivity == Qt::CaseInsensitive) {
 791         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
 792                                             : QString::compare(a, b, Qt::CaseInsensitive);
 793         if (result != 0) {
 794             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
 795             // comparison, still a deterministic sort order is required. A case sensitive
 796             // comparison is done as fallback.
 797             return result;
 798         }
 799     }
 800
 801     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
 802                             : QString::compare(a, b, Qt::CaseSensitive);
 803 }
 804
 805 int KFileItemModel::expansionLevelsCompare(const KFileItem& a, const KFileItem& b) const
 806 {
 807     const KUrl urlA = a.url();
 808     const KUrl urlB = b.url();
 809     if (urlA.directory() == urlB.directory()) {
 810         // Both items have the same directory as parent
 811         return 0;
 812     }
 813
 814     // Check whether one item is the parent of the other item
 815     if (urlA.isParentOf(urlB)) {
 816         return -1;
 817     } else if (urlB.isParentOf(urlA)) {
 818         return +1;
 819     }
 820
 821     // Determine the maximum common path of both items and
 822     // remember the index in 'index'
 823     const QString pathA = urlA.path();
 824     const QString pathB = urlB.path();
 825
 826     const int maxIndex = qMin(pathA.length(), pathB.length()) - 1;
 827     int index = 0;
 828     while (index <= maxIndex && pathA.at(index) == pathB.at(index)) {
 829         ++index;
 830     }
 831     if (index > maxIndex) {
 832         index = maxIndex;
 833     }
 834     while ((pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/')) && index > 0) {
 835         --index;
 836     }
 837
 838     // Determine the first sub-path after the common path and
 839     // check whether it represents a directory or already a file
 840     bool isDirA = true;
 841     const QString subPathA = subPath(a, pathA, index, &isDirA);
 842     bool isDirB = true;
 843     const QString subPathB = subPath(b, pathB, index, &isDirB);
 844
 845     if (isDirA && !isDirB) {
 846         return -1;
 847     } else if (!isDirA && isDirB) {
 848         return +1;
 849     }
 850
 851     return stringCompare(subPathA, subPathB);
 852 }
 853
 854 QString KFileItemModel::subPath(const KFileItem& item,
 855                                 const QString& itemPath,
 856                                 int start,
 857                                 bool* isDir) const
 858 {
 859     Q_ASSERT(isDir);
 860     const int pathIndex = itemPath.indexOf('/', start + 1);
 861     *isDir = (pathIndex > 0) || item.isDir();
 862     return itemPath.mid(start, pathIndex - start);
 863 }
 864
 865 bool KFileItemModel::useMaximumUpdateInterval() const
 866 {
 867     const KDirLister* dirLister = m_dirLister.data();
 868     return dirLister && !dirLister->url().isLocalFile();
 869 }
 870
 871 #include "kfileitemmodel.moc"