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