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