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