src/kitemviews/kfileitemmodel.cpp

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