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;
 407     int insertedCount = 0;
 408     while (sourceIndex < sortedItems.count()) {
 409         // Find target index from m_items to insert the current item
 410         // in a sorted order
 411         const int previousTargetIndex = targetIndex;
 412         while (targetIndex < m_sortedItems.count()) {
 413             if (!lessThan(m_sortedItems.at(targetIndex), sortedItems.at(sourceIndex))) {
 414                 break;
 415             }
 416             ++targetIndex;
 417         }
 418
 419         if (targetIndex - previousTargetIndex > 0 && insertedAtIndex >= 0) {
 420             itemRanges << KItemRange(insertedAtIndex, insertedCount);
 421             insertedAtIndex = targetIndex;
 422             insertedCount = 0;
 423         }
 424
 425         // Insert item at the position targetIndex
 426         const KFileItem item = sortedItems.at(sourceIndex);
 427         m_sortedItems.insert(targetIndex, item);
 428         m_data.insert(targetIndex, retrieveData(item));
 429         // m_items will be inserted after the loop (see comment below)
 430         ++insertedCount;
 431
 432         if (insertedAtIndex < 0) {
 433             insertedAtIndex = targetIndex;
 434         }
 435         ++targetIndex;
 436         ++sourceIndex;
 437     }
 438
 439     // The indexes of all m_items must be adjusted, not only the index
 440     // of the new items
 441     for (int i = 0; i < m_sortedItems.count(); ++i) {
 442         m_items.insert(m_sortedItems.at(i), i);
 443     }
 444
 445     itemRanges << KItemRange(insertedAtIndex, insertedCount);
 446     emit itemsInserted(itemRanges);
 447
 448 #ifdef KFILEITEMMODEL_DEBUG
 449     kDebug() << "[TIME] Inserting of" << items.count() << "items:" << timer.elapsed();
 450 #endif
 451 }
 452
 453 void KFileItemModel::removeItems(const KFileItemList& items)
 454 {
 455     if (items.isEmpty()) {
 456         return;
 457     }
 458
 459 #ifdef KFILEITEMMODEL_DEBUG
 460     kDebug() << "Removing " << items.count() << "items";
 461 #endif
 462
 463     KFileItemList sortedItems = items;
 464     sort(sortedItems.begin(), sortedItems.end());
 465
 466     QList<int> indexesToRemove;
 467     indexesToRemove.reserve(items.count());
 468
 469     // Calculate the item ranges that will get deleted
 470     KItemRangeList itemRanges;
 471     int removedAtIndex = -1;
 472     int removedCount = 0;
 473     int targetIndex = 0;
 474     foreach (const KFileItem& itemToRemove, sortedItems) {
 475         const int previousTargetIndex = targetIndex;
 476         while (targetIndex < m_sortedItems.count()) {
 477             if (m_sortedItems.at(targetIndex) == itemToRemove) {
 478                 break;
 479             }
 480             ++targetIndex;
 481         }
 482         if (targetIndex >= m_sortedItems.count()) {
 483             kWarning() << "Item that should be deleted has not been found!";
 484             return;
 485         }
 486
 487         if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
 488             itemRanges << KItemRange(removedAtIndex, removedCount);
 489             removedAtIndex = targetIndex;
 490             removedCount = 0;
 491         }
 492
 493         indexesToRemove.append(targetIndex);
 494         if (removedAtIndex < 0) {
 495             removedAtIndex = targetIndex;
 496         }
 497         ++removedCount;
 498         ++targetIndex;
 499     }
 500
 501     // Delete the items
 502     for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
 503         const int indexToRemove = indexesToRemove.at(i);
 504         m_items.remove(m_sortedItems.at(indexToRemove));
 505         m_sortedItems.removeAt(indexToRemove);
 506         m_data.removeAt(indexToRemove);
 507     }
 508
 509     // The indexes of all m_items must be adjusted, not only the index
 510     // of the removed items
 511     for (int i = 0; i < m_sortedItems.count(); ++i) {
 512         m_items.insert(m_sortedItems.at(i), i);
 513     }
 514
 515     if (count() <= 0) {
 516         m_rootExpansionLevel = -1;
 517     }
 518
 519     itemRanges << KItemRange(removedAtIndex, removedCount);
 520     emit itemsRemoved(itemRanges);
 521 }
 522
 523 void KFileItemModel::removeExpandedItems()
 524 {
 525
 526     KFileItemList expandedItems;
 527
 528     const int maxIndex = m_data.count() - 1;
 529     for (int i = 0; i <= maxIndex; ++i) {
 530         if (m_data.at(i).value("expansionLevel").toInt() > 0) {
 531             const KFileItem fileItem = m_sortedItems.at(i);
 532             expandedItems.append(fileItem);
 533         }
 534     }
 535
 536     // The m_rootExpansionLevel may not get reset before all items with
 537     // a bigger expansionLevel have been removed.
 538     Q_ASSERT(m_rootExpansionLevel >= 0);
 539     removeItems(expandedItems);
 540
 541     m_rootExpansionLevel = -1;
 542 }
 543
 544 void KFileItemModel::resetRoles()
 545 {
 546     for (int i = 0; i < RolesCount; ++i) {
 547         m_requestRole[i] = false;
 548     }
 549 }
 550
 551 KFileItemModel::Role KFileItemModel::roleIndex(const QByteArray& role) const
 552 {
 553     static QHash<QByteArray, Role> rolesHash;
 554     if (rolesHash.isEmpty()) {
 555         rolesHash.insert("name", NameRole);
 556         rolesHash.insert("size", SizeRole);
 557         rolesHash.insert("date", DateRole);
 558         rolesHash.insert("permissions", PermissionsRole);
 559         rolesHash.insert("owner", OwnerRole);
 560         rolesHash.insert("group", GroupRole);
 561         rolesHash.insert("type", TypeRole);
 562         rolesHash.insert("destination", DestinationRole);
 563         rolesHash.insert("path", PathRole);
 564         rolesHash.insert("isDir", IsDirRole);
 565         rolesHash.insert("isExpanded", IsExpandedRole);
 566         rolesHash.insert("expansionLevel", ExpansionLevelRole);
 567     }
 568     return rolesHash.value(role, NoRole);
 569 }
 570
 571 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item) const
 572 {
 573     // It is important to insert only roles that are fast to retrieve. E.g.
 574     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
 575     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
 576     QHash<QByteArray, QVariant> data;
 577     data.insert("iconPixmap", QPixmap());
 578
 579     const bool isDir = item.isDir();
 580     if (m_requestRole[IsDirRole]) {
 581         data.insert("isDir", isDir);
 582     }
 583
 584     if (m_requestRole[NameRole]) {
 585         data.insert("name", item.name());
 586     }
 587
 588     if (m_requestRole[SizeRole]) {
 589         if (isDir) {
 590             data.insert("size", QVariant());
 591         } else {
 592             data.insert("size", item.size());
 593         }
 594     }
 595
 596     if (m_requestRole[DateRole]) {
 597         // Don't use KFileItem::timeString() as this is too expensive when
 598         // having several thousands of items. Instead the formatting of the
 599         // date-time will be done on-demand by the view when the date will be shown.
 600         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
 601         data.insert("date", dateTime.dateTime());
 602     }
 603
 604     if (m_requestRole[PermissionsRole]) {
 605         data.insert("permissions", item.permissionsString());
 606     }
 607
 608     if (m_requestRole[OwnerRole]) {
 609         data.insert("owner", item.user());
 610     }
 611
 612     if (m_requestRole[GroupRole]) {
 613         data.insert("group", item.group());
 614     }
 615
 616     if (m_requestRole[DestinationRole]) {
 617         QString destination = item.linkDest();
 618         if (destination.isEmpty()) {
 619             destination = i18nc("@item:intable", "No destination");
 620         }
 621         data.insert("destination", destination);
 622     }
 623
 624     if (m_requestRole[PathRole]) {
 625         data.insert("path", item.localPath());
 626     }
 627
 628     if (m_requestRole[IsExpandedRole]) {
 629         data.insert("isExpanded", false);
 630     }
 631
 632     if (m_requestRole[ExpansionLevelRole]) {
 633         if (m_rootExpansionLevel < 0) {
 634             KDirLister* dirLister = m_dirLister.data();
 635             if (dirLister) {
 636                 const QString rootDir = dirLister->url().directory(KUrl::AppendTrailingSlash);
 637                 m_rootExpansionLevel = rootDir.count('/');
 638             }
 639         }
 640         const QString dir = item.url().directory(KUrl::AppendTrailingSlash);
 641         const int level = dir.count('/') - m_rootExpansionLevel - 1;
 642         data.insert("expansionLevel", level);
 643     }
 644
 645     if (item.isMimeTypeKnown()) {
 646         data.insert("iconName", item.iconName());
 647
 648         if (m_requestRole[TypeRole]) {
 649             data.insert("type", item.mimeComment());
 650         }
 651     }
 652
 653     return data;
 654 }
 655
 656 bool KFileItemModel::lessThan(const KFileItem& a, const KFileItem& b) const
 657 {
 658     int result = 0;
 659
 660     if (m_rootExpansionLevel >= 0) {
 661         result = expansionLevelsCompare(a, b);
 662         if (result != 0) {
 663             // The items have parents with different expansion levels
 664             return result < 0;
 665         }
 666     }
 667
 668     if (m_sortFoldersFirst) {
 669         const bool isDirA = a.isDir();
 670         const bool isDirB = b.isDir();
 671         if (isDirA && !isDirB) {
 672             return true;
 673         } else if (!isDirA && isDirB) {
 674             return false;
 675         }
 676     }
 677
 678     switch (m_sortRole) {
 679     case NameRole: {
 680         result = stringCompare(a.text(), b.text());
 681         if (result == 0) {
 682             // KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
 683             result = stringCompare(a.name(m_caseSensitivity == Qt::CaseInsensitive),
 684                                    b.name(m_caseSensitivity == Qt::CaseInsensitive));
 685         }
 686         break;
 687     }
 688
 689     case DateRole: {
 690         const KDateTime dateTimeA = a.time(KFileItem::ModificationTime);
 691         const KDateTime dateTimeB = b.time(KFileItem::ModificationTime);
 692         if (dateTimeA < dateTimeB) {
 693             result = -1;
 694         } else if (dateTimeA > dateTimeB) {
 695             result = +1;
 696         }
 697         break;
 698     }
 699
 700     default:
 701         break;
 702     }
 703
 704     if (result == 0) {
 705         // It must be assured that the sort order is always unique even if two values have been
 706         // equal. In this case a comparison of the URL is done which is unique in all cases
 707         // within KDirLister.
 708         result = QString::compare(a.url().url(), b.url().url(), Qt::CaseSensitive);
 709     }
 710
 711     return result < 0;
 712 }
 713
 714 void KFileItemModel::sort(const KFileItemList::iterator& startIterator, const KFileItemList::iterator& endIterator)
 715 {
 716     KFileItemList::iterator start = startIterator;
 717     KFileItemList::iterator end = endIterator;
 718
 719     // The implementation is based on qSortHelper() from qalgorithms.h
 720     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 721     // In opposite to qSort() it allows to use a member-function for the comparison of elements.
 722     while (1) {
 723         int span = int(end - start);
 724         if (span < 2) {
 725             return;
 726         }
 727
 728         --end;
 729         KFileItemList::iterator low = start, high = end - 1;
 730         KFileItemList::iterator pivot = start + span / 2;
 731
 732         if (lessThan(*end, *start)) {
 733             qSwap(*end, *start);
 734         }
 735         if (span == 2) {
 736             return;
 737         }
 738
 739         if (lessThan(*pivot, *start)) {
 740             qSwap(*pivot, *start);
 741         }
 742         if (lessThan(*end, *pivot)) {
 743             qSwap(*end, *pivot);
 744         }
 745         if (span == 3) {
 746             return;
 747         }
 748
 749         qSwap(*pivot, *end);
 750
 751         while (low < high) {
 752             while (low < high && lessThan(*low, *end)) {
 753                 ++low;
 754             }
 755
 756             while (high > low && lessThan(*end, *high)) {
 757                 --high;
 758             }
 759             if (low < high) {
 760                 qSwap(*low, *high);
 761                 ++low;
 762                 --high;
 763             } else {
 764                 break;
 765             }
 766         }
 767
 768         if (lessThan(*low, *end)) {
 769             ++low;
 770         }
 771
 772         qSwap(*end, *low);
 773         sort(start, low);
 774
 775         start = low + 1;
 776         ++end;
 777     }
 778 }
 779
 780 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
 781 {
 782     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
 783     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
 784     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
 785     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
 786
 787     if (m_caseSensitivity == Qt::CaseInsensitive) {
 788         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
 789                                             : QString::compare(a, b, Qt::CaseInsensitive);
 790         if (result != 0) {
 791             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
 792             // comparison, still a deterministic sort order is required. A case sensitive
 793             // comparison is done as fallback.
 794             return result;
 795         }
 796     }
 797
 798     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
 799                             : QString::compare(a, b, Qt::CaseSensitive);
 800 }
 801
 802 int KFileItemModel::expansionLevelsCompare(const KFileItem& a, const KFileItem& b) const
 803 {
 804     const KUrl urlA = a.url();
 805     const KUrl urlB = b.url();
 806     if (urlA.directory() == urlB.directory()) {
 807         // Both items have the same directory as parent
 808         return 0;
 809     }
 810
 811     // Check whether one item is the parent of the other item
 812     if (urlA.isParentOf(urlB)) {
 813         return -1;
 814     } else if (urlB.isParentOf(urlA)) {
 815         return +1;
 816     }
 817
 818     // Determine the maximum common path of both items and
 819     // remember the index in 'index'
 820     const QString pathA = urlA.path();
 821     const QString pathB = urlB.path();
 822
 823     const int maxIndex = qMin(pathA.length(), pathB.length()) - 1;
 824     int index = 0;
 825     while (index <= maxIndex && pathA.at(index) == pathB.at(index)) {
 826         ++index;
 827     }
 828     if (index > maxIndex) {
 829         index = maxIndex;
 830     }
 831     while (pathA.at(index) != QLatin1Char('/') && index > 0) {
 832         --index;
 833     }
 834
 835     // Determine the first sub-path after the common path and
 836     // check whether it represents a directory or already a file
 837     bool isDirA = true;
 838     const QString subPathA = subPath(a, pathA, index, &isDirA);
 839     bool isDirB = true;
 840     const QString subPathB = subPath(b, pathB, index, &isDirB);
 841
 842     if (isDirA && !isDirB) {
 843         return -1;
 844     } else if (!isDirA && isDirB) {
 845         return +1;
 846     }
 847
 848     return stringCompare(subPathA, subPathB);
 849 }
 850
 851 QString KFileItemModel::subPath(const KFileItem& item,
 852                                 const QString& itemPath,
 853                                 int start,
 854                                 bool* isDir) const
 855 {
 856     Q_ASSERT(isDir);
 857     const int pathIndex = itemPath.indexOf('/', start + 1);
 858     *isDir = (pathIndex > 0) || item.isDir();
 859     return itemPath.mid(start, pathIndex - start);
 860 }
 861
 862 bool KFileItemModel::useMaximumUpdateInterval() const
 863 {
 864     const KDirLister* dirLister = m_dirLister.data();
 865     return dirLister && !dirLister->url().isLocalFile();
 866 }
 867
 868 #include "kfileitemmodel.moc"