src/kitemviews/kfileitemmodel.cpp

   1 /*****************************************************************************
   2  *   Copyright (C) 2011 by Peter Penz <peter.penz19@gmail.com>               *
   3  *   Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com>      *
   4  *   Copyright (C) 2013 by Emmanuel Pescosta <emmanuelpescosta099@gmail.com> *
   5  *                                                                           *
   6  *   This program is free software; you can redistribute it and/or modify    *
   7  *   it under the terms of the GNU General Public License as published by    *
   8  *   the Free Software Foundation; either version 2 of the License, or       *
   9  *   (at your option) any later version.                                     *
  10  *                                                                           *
  11  *   This program is distributed in the hope that it will be useful,         *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
  14  *   GNU General Public License for more details.                            *
  15  *                                                                           *
  16  *   You should have received a copy of the GNU General Public License       *
  17  *   along with this program; if not, write to the                           *
  18  *   Free Software Foundation, Inc.,                                         *
  19  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA              *
  20  *****************************************************************************/
  21
  22 #include "kfileitemmodel.h"
  23
  24 #include <KGlobalSettings>
  25 #include <KLocale>
  26 #include <KStringHandler>
  27 #include <KDebug>
  28
  29 #include "private/kfileitemmodelsortalgorithm.h"
  30 #include "private/kfileitemmodeldirlister.h"
  31
  32 #include <QApplication>
  33 #include <QMimeData>
  34 #include <QTimer>
  35 #include <QWidget>
  36
  37 #include <algorithm>
  38 #include <vector>
  39
  40 // #define KFILEITEMMODEL_DEBUG
  41
  42 KFileItemModel::KFileItemModel(QObject* parent) :
  43     KItemModelBase("text", parent),
  44     m_dirLister(0),
  45     m_naturalSorting(KGlobalSettings::naturalSorting()),
  46     m_sortDirsFirst(true),
  47     m_sortRole(NameRole),
  48     m_sortingProgressPercent(-1),
  49     m_roles(),
  50     m_caseSensitivity(Qt::CaseInsensitive),
  51     m_itemData(),
  52     m_items(),
  53     m_filter(),
  54     m_filteredItems(),
  55     m_requestRole(),
  56     m_maximumUpdateIntervalTimer(0),
  57     m_resortAllItemsTimer(0),
  58     m_pendingItemsToInsert(),
  59     m_groups(),
  60     m_expandedDirs(),
  61     m_urlsToExpand()
  62 {
  63     m_dirLister = new KFileItemModelDirLister(this);
  64     m_dirLister->setDelayedMimeTypes(true);
  65
  66     const QWidget* parentWidget = qobject_cast<QWidget*>(parent);
  67     if (parentWidget) {
  68         m_dirLister->setMainWindow(parentWidget->window());
  69     }
  70
  71     connect(m_dirLister, SIGNAL(started(KUrl)), this, SIGNAL(directoryLoadingStarted()));
  72     connect(m_dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  73     connect(m_dirLister, SIGNAL(completed(KUrl)), this, SLOT(slotCompleted()));
  74     connect(m_dirLister, SIGNAL(itemsAdded(KUrl,KFileItemList)), this, SLOT(slotItemsAdded(KUrl,KFileItemList)));
  75     connect(m_dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  76     connect(m_dirLister, SIGNAL(refreshItems(QList<QPair<KFileItem,KFileItem> >)), this, SLOT(slotRefreshItems(QList<QPair<KFileItem,KFileItem> >)));
  77     connect(m_dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  78     connect(m_dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  79     connect(m_dirLister, SIGNAL(infoMessage(QString)), this, SIGNAL(infoMessage(QString)));
  80     connect(m_dirLister, SIGNAL(errorMessage(QString)), this, SIGNAL(errorMessage(QString)));
  81     connect(m_dirLister, SIGNAL(redirection(KUrl,KUrl)), this, SIGNAL(directoryRedirection(KUrl,KUrl)));
  82     connect(m_dirLister, SIGNAL(urlIsFileError(KUrl)), this, SIGNAL(urlIsFileError(KUrl)));
  83
  84     // Apply default roles that should be determined
  85     resetRoles();
  86     m_requestRole[NameRole] = true;
  87     m_requestRole[IsDirRole] = true;
  88     m_requestRole[IsLinkRole] = true;
  89     m_roles.insert("text");
  90     m_roles.insert("isDir");
  91     m_roles.insert("isLink");
  92
  93     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  94     // before the completed() or canceled() signal has been emitted.
  95     m_maximumUpdateIntervalTimer = new QTimer(this);
  96     m_maximumUpdateIntervalTimer->setInterval(2000);
  97     m_maximumUpdateIntervalTimer->setSingleShot(true);
  98     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  99
 100     // When changing the value of an item which represents the sort-role a resorting must be
 101     // triggered. Especially in combination with KFileItemModelRolesUpdater this might be done
 102     // for a lot of items within a quite small timeslot. To prevent expensive resortings the
 103     // resorting is postponed until the timer has been exceeded.
 104     m_resortAllItemsTimer = new QTimer(this);
 105     m_resortAllItemsTimer->setInterval(500);
 106     m_resortAllItemsTimer->setSingleShot(true);
 107     connect(m_resortAllItemsTimer, SIGNAL(timeout()), this, SLOT(resortAllItems()));
 108
 109     connect(KGlobalSettings::self(), SIGNAL(naturalSortingChanged()), this, SLOT(slotNaturalSortingChanged()));
 110 }
 111
 112 KFileItemModel::~KFileItemModel()
 113 {
 114     qDeleteAll(m_itemData);
 115     qDeleteAll(m_filteredItems.values());
 116     qDeleteAll(m_pendingItemsToInsert);
 117 }
 118
 119 void KFileItemModel::loadDirectory(const KUrl& url)
 120 {
 121     m_dirLister->openUrl(url);
 122 }
 123
 124 void KFileItemModel::refreshDirectory(const KUrl& url)
 125 {
 126     // Refresh all expanded directories first (Bug 295300)
 127     QHashIterator<KUrl, KUrl> expandedDirs(m_expandedDirs);
 128     while (expandedDirs.hasNext()) {
 129         expandedDirs.next();
 130         m_dirLister->openUrl(expandedDirs.value(), KDirLister::Reload);
 131     }
 132
 133     m_dirLister->openUrl(url, KDirLister::Reload);
 134 }
 135
 136 KUrl KFileItemModel::directory() const
 137 {
 138     return m_dirLister->url();
 139 }
 140
 141 void KFileItemModel::cancelDirectoryLoading()
 142 {
 143     m_dirLister->stop();
 144 }
 145
 146 int KFileItemModel::count() const
 147 {
 148     return m_itemData.count();
 149 }
 150
 151 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
 152 {
 153     if (index >= 0 && index < count()) {
 154         ItemData* data = m_itemData.at(index);
 155         if (data->values.isEmpty()) {
 156             data->values = retrieveData(data->item, data->parent);
 157         }
 158
 159         return data->values;
 160     }
 161     return QHash<QByteArray, QVariant>();
 162 }
 163
 164 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
 165 {
 166     if (index < 0 || index >= count()) {
 167         return false;
 168     }
 169
 170     QHash<QByteArray, QVariant> currentValues = data(index);
 171
 172     // Determine which roles have been changed
 173     QSet<QByteArray> changedRoles;
 174     QHashIterator<QByteArray, QVariant> it(values);
 175     while (it.hasNext()) {
 176         it.next();
 177         const QByteArray role = sharedValue(it.key());
 178         const QVariant value = it.value();
 179
 180         if (currentValues[role] != value) {
 181             currentValues[role] = value;
 182             changedRoles.insert(role);
 183         }
 184     }
 185
 186     if (changedRoles.isEmpty()) {
 187         return false;
 188     }
 189
 190     m_itemData[index]->values = currentValues;
 191     if (changedRoles.contains("text")) {
 192         KUrl url = m_itemData[index]->item.url();
 193         url.setFileName(currentValues["text"].toString());
 194         m_itemData[index]->item.setUrl(url);
 195     }
 196
 197     emitItemsChangedAndTriggerResorting(KItemRangeList() << KItemRange(index, 1), changedRoles);
 198
 199     return true;
 200 }
 201
 202 void KFileItemModel::setSortDirectoriesFirst(bool dirsFirst)
 203 {
 204     if (dirsFirst != m_sortDirsFirst) {
 205         m_sortDirsFirst = dirsFirst;
 206         resortAllItems();
 207     }
 208 }
 209
 210 bool KFileItemModel::sortDirectoriesFirst() const
 211 {
 212     return m_sortDirsFirst;
 213 }
 214
 215 void KFileItemModel::setShowHiddenFiles(bool show)
 216 {
 217     m_dirLister->setShowingDotFiles(show);
 218     m_dirLister->emitChanges();
 219     if (show) {
 220         slotCompleted();
 221     }
 222 }
 223
 224 bool KFileItemModel::showHiddenFiles() const
 225 {
 226     return m_dirLister->showingDotFiles();
 227 }
 228
 229 void KFileItemModel::setShowDirectoriesOnly(bool enabled)
 230 {
 231     m_dirLister->setDirOnlyMode(enabled);
 232 }
 233
 234 bool KFileItemModel::showDirectoriesOnly() const
 235 {
 236     return m_dirLister->dirOnlyMode();
 237 }
 238
 239 QMimeData* KFileItemModel::createMimeData(const KItemSet& indexes) const
 240 {
 241     QMimeData* data = new QMimeData();
 242
 243     // The following code has been taken from KDirModel::mimeData()
 244     // (kdelibs/kio/kio/kdirmodel.cpp)
 245     // Copyright (C) 2006 David Faure <faure@kde.org>
 246     KUrl::List urls;
 247     KUrl::List mostLocalUrls;
 248     bool canUseMostLocalUrls = true;
 249     const ItemData* lastAddedItem = 0;
 250
 251     foreach (int index, indexes) {
 252         const ItemData* itemData = m_itemData.at(index);
 253         const ItemData* parent = itemData->parent;
 254
 255         while (parent && parent != lastAddedItem) {
 256             itemData = itemData->parent;
 257         }
 258
 259         if (parent && parent == lastAddedItem) {
 260             // A parent of 'itemData' has been added already.
 261             continue;
 262         }
 263
 264         lastAddedItem = itemData;
 265         const KFileItem& item = itemData->item;
 266         if (!item.isNull()) {
 267             urls << item.targetUrl();
 268
 269             bool isLocal;
 270             mostLocalUrls << item.mostLocalUrl(isLocal);
 271             if (!isLocal) {
 272                 canUseMostLocalUrls = false;
 273             }
 274         }
 275     }
 276
 277     const bool different = canUseMostLocalUrls && mostLocalUrls != urls;
 278     if (different) {
 279         urls.populateMimeData(mostLocalUrls, data);
 280     } else {
 281         urls.populateMimeData(data);
 282     }
 283
 284     return data;
 285 }
 286
 287 int KFileItemModel::indexForKeyboardSearch(const QString& text, int startFromIndex) const
 288 {
 289     startFromIndex = qMax(0, startFromIndex);
 290     for (int i = startFromIndex; i < count(); ++i) {
 291         if (fileItem(i).text().startsWith(text, Qt::CaseInsensitive)) {
 292             return i;
 293         }
 294     }
 295     for (int i = 0; i < startFromIndex; ++i) {
 296         if (fileItem(i).text().startsWith(text, Qt::CaseInsensitive)) {
 297             return i;
 298         }
 299     }
 300     return -1;
 301 }
 302
 303 bool KFileItemModel::supportsDropping(int index) const
 304 {
 305     const KFileItem item = fileItem(index);
 306     return !item.isNull() && (item.isDir() || item.isDesktopFile());
 307 }
 308
 309 QString KFileItemModel::roleDescription(const QByteArray& role) const
 310 {
 311     static QHash<QByteArray, QString> description;
 312     if (description.isEmpty()) {
 313         int count = 0;
 314         const RoleInfoMap* map = rolesInfoMap(count);
 315         for (int i = 0; i < count; ++i) {
 316             description.insert(map[i].role, i18nc(map[i].roleTranslationContext, map[i].roleTranslation));
 317         }
 318     }
 319
 320     return description.value(role);
 321 }
 322
 323 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 324 {
 325     if (!m_itemData.isEmpty() && m_groups.isEmpty()) {
 326 #ifdef KFILEITEMMODEL_DEBUG
 327         QElapsedTimer timer;
 328         timer.start();
 329 #endif
 330         switch (typeForRole(sortRole())) {
 331         case NameRole:        m_groups = nameRoleGroups(); break;
 332         case SizeRole:        m_groups = sizeRoleGroups(); break;
 333         case DateRole:        m_groups = dateRoleGroups(); break;
 334         case PermissionsRole: m_groups = permissionRoleGroups(); break;
 335         case RatingRole:      m_groups = ratingRoleGroups(); break;
 336         default:              m_groups = genericStringRoleGroups(sortRole()); break;
 337         }
 338
 339 #ifdef KFILEITEMMODEL_DEBUG
 340         kDebug() << "[TIME] Calculating groups for" << count() << "items:" << timer.elapsed();
 341 #endif
 342     }
 343
 344     return m_groups;
 345 }
 346
 347 KFileItem KFileItemModel::fileItem(int index) const
 348 {
 349     if (index >= 0 && index < count()) {
 350         return m_itemData.at(index)->item;
 351     }
 352
 353     return KFileItem();
 354 }
 355
 356 KFileItem KFileItemModel::fileItem(const KUrl& url) const
 357 {
 358     const int index = m_items.value(url, -1);
 359     if (index >= 0) {
 360         return m_itemData.at(index)->item;
 361     }
 362     return KFileItem();
 363 }
 364
 365 int KFileItemModel::index(const KFileItem& item) const
 366 {
 367     if (item.isNull()) {
 368         return -1;
 369     }
 370
 371     return m_items.value(item.url(), -1);
 372 }
 373
 374 int KFileItemModel::index(const KUrl& url) const
 375 {
 376     KUrl urlToFind = url;
 377     urlToFind.adjustPath(KUrl::RemoveTrailingSlash);
 378     return m_items.value(urlToFind, -1);
 379 }
 380
 381 KFileItem KFileItemModel::rootItem() const
 382 {
 383     return m_dirLister->rootItem();
 384 }
 385
 386 void KFileItemModel::clear()
 387 {
 388     slotClear();
 389 }
 390
 391 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 392 {
 393     if (m_roles == roles) {
 394         return;
 395     }
 396     m_roles = roles;
 397
 398     if (count() > 0) {
 399         const bool supportedExpanding = m_requestRole[ExpandedParentsCountRole];
 400         const bool willSupportExpanding = roles.contains("expandedParentsCount");
 401         if (supportedExpanding && !willSupportExpanding) {
 402             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 403             // that is not 0 (and hence are part of an expanded item).
 404             removeExpandedItems();
 405         }
 406     }
 407
 408     m_groups.clear();
 409     resetRoles();
 410
 411     QSetIterator<QByteArray> it(roles);
 412     while (it.hasNext()) {
 413         const QByteArray& role = it.next();
 414         m_requestRole[typeForRole(role)] = true;
 415     }
 416
 417     if (count() > 0) {
 418         // Update m_data with the changed requested roles
 419         const int maxIndex = count() - 1;
 420         for (int i = 0; i <= maxIndex; ++i) {
 421             m_itemData[i]->values = retrieveData(m_itemData.at(i)->item, m_itemData.at(i)->parent);
 422         }
 423
 424         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 425         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 426     }
 427 }
 428
 429 QSet<QByteArray> KFileItemModel::roles() const
 430 {
 431     return m_roles;
 432 }
 433
 434 bool KFileItemModel::setExpanded(int index, bool expanded)
 435 {
 436     if (!isExpandable(index) || isExpanded(index) == expanded) {
 437         return false;
 438     }
 439
 440     QHash<QByteArray, QVariant> values;
 441     values.insert(sharedValue("isExpanded"), expanded);
 442     if (!setData(index, values)) {
 443         return false;
 444     }
 445
 446     const KFileItem item = m_itemData.at(index)->item;
 447     const KUrl url = item.url();
 448     const KUrl targetUrl = item.targetUrl();
 449     if (expanded) {
 450         m_expandedDirs.insert(targetUrl, url);
 451         m_dirLister->openUrl(url, KDirLister::Keep);
 452
 453         const KUrl::List previouslyExpandedChildren = m_itemData.at(index)->values.value("previouslyExpandedChildren").value<KUrl::List>();
 454         foreach (const KUrl& url, previouslyExpandedChildren) {
 455             m_urlsToExpand.insert(url);
 456         }
 457     } else {
 458         m_expandedDirs.remove(targetUrl);
 459         m_dirLister->stop(url);
 460
 461         const int parentLevel = expandedParentsCount(index);
 462         const int itemCount = m_itemData.count();
 463         const int firstChildIndex = index + 1;
 464
 465         KUrl::List expandedChildren;
 466
 467         int childIndex = firstChildIndex;
 468         while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
 469             ItemData* itemData = m_itemData.at(childIndex);
 470             if (itemData->values.value("isExpanded").toBool()) {
 471                 const KUrl targetUrl = itemData->item.targetUrl();
 472                 m_expandedDirs.remove(targetUrl);
 473                 expandedChildren.append(targetUrl);
 474             }
 475             ++childIndex;
 476         }
 477         const int childrenCount = childIndex - firstChildIndex;
 478
 479         removeFilteredChildren(KItemRangeList() << KItemRange(index, 1 + childrenCount));
 480         removeItems(KItemRangeList() << KItemRange(firstChildIndex, childrenCount), DeleteItemData);
 481
 482         m_itemData.at(index)->values.insert("previouslyExpandedChildren", expandedChildren);
 483     }
 484
 485     return true;
 486 }
 487
 488 bool KFileItemModel::isExpanded(int index) const
 489 {
 490     if (index >= 0 && index < count()) {
 491         return m_itemData.at(index)->values.value("isExpanded").toBool();
 492     }
 493     return false;
 494 }
 495
 496 bool KFileItemModel::isExpandable(int index) const
 497 {
 498     if (index >= 0 && index < count()) {
 499         // Call data (instead of accessing m_itemData directly)
 500         // to ensure that the value is initialized.
 501         return data(index).value("isExpandable").toBool();
 502     }
 503     return false;
 504 }
 505
 506 int KFileItemModel::expandedParentsCount(int index) const
 507 {
 508     if (index >= 0 && index < count()) {
 509         return expandedParentsCount(m_itemData.at(index));
 510     }
 511     return 0;
 512 }
 513
 514 QSet<KUrl> KFileItemModel::expandedDirectories() const
 515 {
 516     return m_expandedDirs.values().toSet();
 517 }
 518
 519 void KFileItemModel::restoreExpandedDirectories(const QSet<KUrl>& urls)
 520 {
 521     m_urlsToExpand = urls;
 522 }
 523
 524 void KFileItemModel::expandParentDirectories(const KUrl& url)
 525 {
 526     const int pos = m_dirLister->url().path().length();
 527
 528     // Assure that each sub-path of the URL that should be
 529     // expanded is added to m_urlsToExpand. KDirLister
 530     // does not care whether the parent-URL has already been
 531     // expanded.
 532     KUrl urlToExpand = m_dirLister->url();
 533     const QStringList subDirs = url.path().mid(pos).split(QDir::separator());
 534     for (int i = 0; i < subDirs.count() - 1; ++i) {
 535         urlToExpand.addPath(subDirs.at(i));
 536         m_urlsToExpand.insert(urlToExpand);
 537     }
 538
 539     // KDirLister::open() must called at least once to trigger an initial
 540     // loading. The pending URLs that must be restored are handled
 541     // in slotCompleted().
 542     QSetIterator<KUrl> it2(m_urlsToExpand);
 543     while (it2.hasNext()) {
 544         const int idx = index(it2.next());
 545         if (idx >= 0 && !isExpanded(idx)) {
 546             setExpanded(idx, true);
 547             break;
 548         }
 549     }
 550 }
 551
 552 void KFileItemModel::setNameFilter(const QString& nameFilter)
 553 {
 554     if (m_filter.pattern() != nameFilter) {
 555         dispatchPendingItemsToInsert();
 556         m_filter.setPattern(nameFilter);
 557         applyFilters();
 558     }
 559 }
 560
 561 QString KFileItemModel::nameFilter() const
 562 {
 563     return m_filter.pattern();
 564 }
 565
 566 void KFileItemModel::setMimeTypeFilters(const QStringList& filters)
 567 {
 568     if (m_filter.mimeTypes() != filters) {
 569         dispatchPendingItemsToInsert();
 570         m_filter.setMimeTypes(filters);
 571         applyFilters();
 572     }
 573 }
 574
 575 QStringList KFileItemModel::mimeTypeFilters() const
 576 {
 577     return m_filter.mimeTypes();
 578 }
 579
 580
 581 void KFileItemModel::applyFilters()
 582 {
 583     // Check which shown items from m_itemData must get
 584     // hidden and hence moved to m_filteredItems.
 585     QVector<int> newFilteredIndexes;
 586
 587     const int itemCount = m_itemData.count();
 588     for (int index = 0; index < itemCount; ++index) {
 589         ItemData* itemData = m_itemData.at(index);
 590
 591         // Only filter non-expanded items as child items may never
 592         // exist without a parent item
 593         if (!itemData->values.value("isExpanded").toBool()) {
 594             const KFileItem item = itemData->item;
 595             if (!m_filter.matches(item)) {
 596                 newFilteredIndexes.append(index);
 597                 m_filteredItems.insert(item, itemData);
 598             }
 599         }
 600     }
 601
 602     const KItemRangeList removedRanges = KItemRangeList::fromSortedContainer(newFilteredIndexes);
 603     removeItems(removedRanges, KeepItemData);
 604
 605     // Check which hidden items from m_filteredItems should
 606     // get visible again and hence removed from m_filteredItems.
 607     QList<ItemData*> newVisibleItems;
 608
 609     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
 610     while (it != m_filteredItems.end()) {
 611         if (m_filter.matches(it.key())) {
 612             newVisibleItems.append(it.value());
 613             it = m_filteredItems.erase(it);
 614         } else {
 615             ++it;
 616         }
 617     }
 618
 619     insertItems(newVisibleItems);
 620 }
 621
 622 void KFileItemModel::removeFilteredChildren(const KItemRangeList& itemRanges)
 623 {
 624     if (m_filteredItems.isEmpty() || !m_requestRole[ExpandedParentsCountRole]) {
 625         // There are either no filtered items, or it is not possible to expand
 626         // folders -> there cannot be any filtered children.
 627         return;
 628     }
 629
 630     QSet<ItemData*> parents;
 631     foreach (const KItemRange& range, itemRanges) {
 632         for (int index = range.index; index < range.index + range.count; ++index) {
 633             parents.insert(m_itemData.at(index));
 634         }
 635     }
 636
 637     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
 638     while (it != m_filteredItems.end()) {
 639         if (parents.contains(it.value()->parent)) {
 640             delete it.value();
 641             it = m_filteredItems.erase(it);
 642         } else {
 643             ++it;
 644         }
 645     }
 646 }
 647
 648 QList<KFileItemModel::RoleInfo> KFileItemModel::rolesInformation()
 649 {
 650     static QList<RoleInfo> rolesInfo;
 651     if (rolesInfo.isEmpty()) {
 652         int count = 0;
 653         const RoleInfoMap* map = rolesInfoMap(count);
 654         for (int i = 0; i < count; ++i) {
 655             if (map[i].roleType != NoRole) {
 656                 RoleInfo info;
 657                 info.role = map[i].role;
 658                 info.translation = i18nc(map[i].roleTranslationContext, map[i].roleTranslation);
 659                 if (map[i].groupTranslation) {
 660                     info.group = i18nc(map[i].groupTranslationContext, map[i].groupTranslation);
 661                 } else {
 662                     // For top level roles, groupTranslation is 0. We must make sure that
 663                     // info.group is an empty string then because the code that generates
 664                     // menus tries to put the actions into sub menus otherwise.
 665                     info.group = QString();
 666                 }
 667                 info.requiresNepomuk = map[i].requiresNepomuk;
 668                 info.requiresIndexer = map[i].requiresIndexer;
 669                 rolesInfo.append(info);
 670             }
 671         }
 672     }
 673
 674     return rolesInfo;
 675 }
 676
 677 void KFileItemModel::onGroupedSortingChanged(bool current)
 678 {
 679     Q_UNUSED(current);
 680     m_groups.clear();
 681 }
 682
 683 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 684 {
 685     Q_UNUSED(previous);
 686     m_sortRole = typeForRole(current);
 687
 688     if (!m_requestRole[m_sortRole]) {
 689         QSet<QByteArray> newRoles = m_roles;
 690         newRoles << current;
 691         setRoles(newRoles);
 692     }
 693
 694     resortAllItems();
 695 }
 696
 697 void KFileItemModel::onSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous)
 698 {
 699     Q_UNUSED(current);
 700     Q_UNUSED(previous);
 701     resortAllItems();
 702 }
 703
 704 void KFileItemModel::resortAllItems()
 705 {
 706     m_resortAllItemsTimer->stop();
 707
 708     const int itemCount = count();
 709     if (itemCount <= 0) {
 710         return;
 711     }
 712
 713 #ifdef KFILEITEMMODEL_DEBUG
 714     QElapsedTimer timer;
 715     timer.start();
 716     kDebug() << "===========================================================";
 717     kDebug() << "Resorting" << itemCount << "items";
 718 #endif
 719
 720     // Remember the order of the current URLs so
 721     // that it can be determined which indexes have
 722     // been moved because of the resorting.
 723     QList<KUrl> oldUrls;
 724     oldUrls.reserve(itemCount);
 725     foreach (const ItemData* itemData, m_itemData) {
 726         oldUrls.append(itemData->item.url());
 727     }
 728
 729     m_items.clear();
 730
 731     // Resort the items
 732     sort(m_itemData.begin(), m_itemData.end());
 733     for (int i = 0; i < itemCount; ++i) {
 734         m_items.insert(m_itemData.at(i)->item.url(), i);
 735     }
 736
 737     // Determine the first index that has been moved.
 738     int firstMovedIndex = 0;
 739     while (firstMovedIndex < itemCount
 740            && firstMovedIndex == m_items.value(oldUrls.at(firstMovedIndex))) {
 741         ++firstMovedIndex;
 742     }
 743
 744     const bool itemsHaveMoved = firstMovedIndex < itemCount;
 745     if (itemsHaveMoved) {
 746         m_groups.clear();
 747
 748         int lastMovedIndex = itemCount - 1;
 749         while (lastMovedIndex > firstMovedIndex
 750                && lastMovedIndex == m_items.value(oldUrls.at(lastMovedIndex))) {
 751             --lastMovedIndex;
 752         }
 753
 754         Q_ASSERT(firstMovedIndex <= lastMovedIndex);
 755
 756         // Create a list movedToIndexes, which has the property that
 757         // movedToIndexes[i] is the new index of the item with the old index
 758         // firstMovedIndex + i.
 759         const int movedItemsCount = lastMovedIndex - firstMovedIndex + 1;
 760         QList<int> movedToIndexes;
 761         movedToIndexes.reserve(movedItemsCount);
 762         for (int i = firstMovedIndex; i <= lastMovedIndex; ++i) {
 763             const int newIndex = m_items.value(oldUrls.at(i));
 764             movedToIndexes.append(newIndex);
 765         }
 766
 767         emit itemsMoved(KItemRange(firstMovedIndex, movedItemsCount), movedToIndexes);
 768     } else if (groupedSorting()) {
 769         // The groups might have changed even if the order of the items has not.
 770         const QList<QPair<int, QVariant> > oldGroups = m_groups;
 771         m_groups.clear();
 772         if (groups() != oldGroups) {
 773             emit groupsChanged();
 774         }
 775     }
 776
 777 #ifdef KFILEITEMMODEL_DEBUG
 778     kDebug() << "[TIME] Resorting of" << itemCount << "items:" << timer.elapsed();
 779 #endif
 780 }
 781
 782 void KFileItemModel::slotCompleted()
 783 {
 784     dispatchPendingItemsToInsert();
 785
 786     if (!m_urlsToExpand.isEmpty()) {
 787         // Try to find a URL that can be expanded.
 788         // Note that the parent folder must be expanded before any of its subfolders become visible.
 789         // Therefore, some URLs in m_restoredExpandedUrls might not be visible yet
 790         // -> we expand the first visible URL we find in m_restoredExpandedUrls.
 791         foreach (const KUrl& url, m_urlsToExpand) {
 792             const int index = m_items.value(url, -1);
 793             if (index >= 0) {
 794                 m_urlsToExpand.remove(url);
 795                 if (setExpanded(index, true)) {
 796                     // The dir lister has been triggered. This slot will be called
 797                     // again after the directory has been expanded.
 798                     return;
 799                 }
 800             }
 801         }
 802
 803         // None of the URLs in m_restoredExpandedUrls could be found in the model. This can happen
 804         // if these URLs have been deleted in the meantime.
 805         m_urlsToExpand.clear();
 806     }
 807
 808     emit directoryLoadingCompleted();
 809 }
 810
 811 void KFileItemModel::slotCanceled()
 812 {
 813     m_maximumUpdateIntervalTimer->stop();
 814     dispatchPendingItemsToInsert();
 815
 816     emit directoryLoadingCanceled();
 817 }
 818
 819 void KFileItemModel::slotItemsAdded(const KUrl& directoryUrl, const KFileItemList& items)
 820 {
 821     Q_ASSERT(!items.isEmpty());
 822
 823     KUrl parentUrl;
 824     if (m_expandedDirs.contains(directoryUrl)) {
 825         parentUrl = m_expandedDirs.value(directoryUrl);
 826     } else {
 827         parentUrl = directoryUrl;
 828         parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
 829     }
 830
 831     if (m_requestRole[ExpandedParentsCountRole]) {
 832         KFileItem item = items.first();
 833
 834         // If the expanding of items is enabled, the call
 835         // dirLister->openUrl(url, KDirLister::Keep) in KFileItemModel::setExpanded()
 836         // might result in emitting the same items twice due to the Keep-parameter.
 837         // This case happens if an item gets expanded, collapsed and expanded again
 838         // before the items could be loaded for the first expansion.
 839         const int index = m_items.value(item.url(), -1);
 840         if (index >= 0) {
 841             // The items are already part of the model.
 842             return;
 843         }
 844
 845         if (directoryUrl != directory()) {
 846             // To be able to compare whether the new items may be inserted as children
 847             // of a parent item the pending items must be added to the model first.
 848             dispatchPendingItemsToInsert();
 849         }
 850
 851         // KDirLister keeps the children of items that got expanded once even if
 852         // they got collapsed again with KFileItemModel::setExpanded(false). So it must be
 853         // checked whether the parent for new items is still expanded.
 854         const int parentIndex = m_items.value(parentUrl, -1);
 855         if (parentIndex >= 0 && !m_itemData[parentIndex]->values.value("isExpanded").toBool()) {
 856             // The parent is not expanded.
 857             return;
 858         }
 859     }
 860
 861     QList<ItemData*> itemDataList = createItemDataList(parentUrl, items);
 862
 863     if (!m_filter.hasSetFilters()) {
 864         m_pendingItemsToInsert.append(itemDataList);
 865     } else {
 866         // The name or type filter is active. Hide filtered items
 867         // before inserting them into the model and remember
 868         // the filtered items in m_filteredItems.
 869         foreach (ItemData* itemData, itemDataList) {
 870             if (m_filter.matches(itemData->item)) {
 871                 m_pendingItemsToInsert.append(itemData);
 872             } else {
 873                 m_filteredItems.insert(itemData->item, itemData);
 874             }
 875         }
 876     }
 877
 878     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 879         // Assure that items get dispatched if no completed() or canceled() signal is
 880         // emitted during the maximum update interval.
 881         m_maximumUpdateIntervalTimer->start();
 882     }
 883 }
 884
 885 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 886 {
 887     dispatchPendingItemsToInsert();
 888
 889     QVector<int> indexesToRemove;
 890     indexesToRemove.reserve(items.count());
 891
 892     foreach (const KFileItem& item, items) {
 893         const KUrl url = item.url();
 894         const int index = m_items.value(url, -1);
 895         if (index >= 0) {
 896             indexesToRemove.append(index);
 897         } else {
 898             // Probably the item has been filtered.
 899             QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.find(item);
 900             if (it != m_filteredItems.end()) {
 901                 delete it.value();
 902                 m_filteredItems.erase(it);
 903             }
 904         }
 905     }
 906
 907     std::sort(indexesToRemove.begin(), indexesToRemove.end());
 908
 909     if (m_requestRole[ExpandedParentsCountRole] && !m_expandedDirs.isEmpty()) {
 910         // Assure that removing a parent item also results in removing all children
 911         QVector<int> indexesToRemoveWithChildren;
 912         indexesToRemoveWithChildren.reserve(m_items.count());
 913
 914         const int itemCount = m_itemData.count();
 915         foreach (int index, indexesToRemove) {
 916             indexesToRemoveWithChildren.append(index);
 917
 918             const int parentLevel = expandedParentsCount(index);
 919             int childIndex = index + 1;
 920             while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
 921                 indexesToRemoveWithChildren.append(childIndex);
 922                 ++childIndex;
 923             }
 924         }
 925
 926         indexesToRemove = indexesToRemoveWithChildren;
 927     }
 928
 929     const KItemRangeList itemRanges = KItemRangeList::fromSortedContainer(indexesToRemove);
 930     removeFilteredChildren(itemRanges);
 931     removeItems(itemRanges, DeleteItemData);
 932 }
 933
 934 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 935 {
 936     Q_ASSERT(!items.isEmpty());
 937 #ifdef KFILEITEMMODEL_DEBUG
 938     kDebug() << "Refreshing" << items.count() << "items";
 939 #endif
 940
 941     // Get the indexes of all items that have been refreshed
 942     QList<int> indexes;
 943     indexes.reserve(items.count());
 944
 945     QSet<QByteArray> changedRoles;
 946
 947     QListIterator<QPair<KFileItem, KFileItem> > it(items);
 948     while (it.hasNext()) {
 949         const QPair<KFileItem, KFileItem>& itemPair = it.next();
 950         const KFileItem& oldItem = itemPair.first;
 951         const KFileItem& newItem = itemPair.second;
 952         const int index = m_items.value(oldItem.url(), -1);
 953         if (index >= 0) {
 954             m_itemData[index]->item = newItem;
 955
 956             // Keep old values as long as possible if they could not retrieved synchronously yet.
 957             // The update of the values will be done asynchronously by KFileItemModelRolesUpdater.
 958             QHashIterator<QByteArray, QVariant> it(retrieveData(newItem, m_itemData.at(index)->parent));
 959             QHash<QByteArray, QVariant>& values = m_itemData[index]->values;
 960             while (it.hasNext()) {
 961                 it.next();
 962                 const QByteArray& role = it.key();
 963                 if (values.value(role) != it.value()) {
 964                     values.insert(role, it.value());
 965                     changedRoles.insert(role);
 966                 }
 967             }
 968
 969             m_items.remove(oldItem.url());
 970             m_items.insert(newItem.url(), index);
 971             indexes.append(index);
 972         }
 973     }
 974
 975     // If the changed items have been created recently, they might not be in m_items yet.
 976     // In that case, the list 'indexes' might be empty.
 977     if (indexes.isEmpty()) {
 978         return;
 979     }
 980
 981     // Extract the item-ranges out of the changed indexes
 982     qSort(indexes);
 983     const KItemRangeList itemRangeList = KItemRangeList::fromSortedContainer(indexes);
 984     emitItemsChangedAndTriggerResorting(itemRangeList, changedRoles);
 985 }
 986
 987 void KFileItemModel::slotClear()
 988 {
 989 #ifdef KFILEITEMMODEL_DEBUG
 990     kDebug() << "Clearing all items";
 991 #endif
 992
 993     qDeleteAll(m_filteredItems.values());
 994     m_filteredItems.clear();
 995     m_groups.clear();
 996
 997     m_maximumUpdateIntervalTimer->stop();
 998     m_resortAllItemsTimer->stop();
 999
1000     qDeleteAll(m_pendingItemsToInsert);
1001     m_pendingItemsToInsert.clear();
1002
1003     const int removedCount = m_itemData.count();
1004     if (removedCount > 0) {
1005         qDeleteAll(m_itemData);
1006         m_itemData.clear();
1007         m_items.clear();
1008         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
1009     }
1010
1011     m_expandedDirs.clear();
1012 }
1013
1014 void KFileItemModel::slotClear(const KUrl& url)
1015 {
1016     Q_UNUSED(url);
1017 }
1018
1019 void KFileItemModel::slotNaturalSortingChanged()
1020 {
1021     m_naturalSorting = KGlobalSettings::naturalSorting();
1022     resortAllItems();
1023 }
1024
1025 void KFileItemModel::dispatchPendingItemsToInsert()
1026 {
1027     if (!m_pendingItemsToInsert.isEmpty()) {
1028         insertItems(m_pendingItemsToInsert);
1029         m_pendingItemsToInsert.clear();
1030     }
1031 }
1032
1033 void KFileItemModel::insertItems(QList<ItemData*>& newItems)
1034 {
1035     if (newItems.isEmpty()) {
1036         return;
1037     }
1038
1039 #ifdef KFILEITEMMODEL_DEBUG
1040     QElapsedTimer timer;
1041     timer.start();
1042     kDebug() << "===========================================================";
1043     kDebug() << "Inserting" << newItems.count() << "items";
1044 #endif
1045
1046     m_groups.clear();
1047
1048     if (m_sortRole == NameRole && m_naturalSorting) {
1049         // Natural sorting of items can be very slow. However, it becomes much
1050         // faster if the input sequence is already mostly sorted. Therefore, we
1051         // first sort 'newItems' according to the QStrings returned by
1052         // KFileItem::text() using QString::operator<(), which is quite fast.
1053         parallelMergeSort(newItems.begin(), newItems.end(), nameLessThan, QThread::idealThreadCount());
1054     }
1055
1056     sort(newItems.begin(), newItems.end());
1057
1058 #ifdef KFILEITEMMODEL_DEBUG
1059     kDebug() << "[TIME] Sorting:" << timer.elapsed();
1060 #endif
1061
1062     KItemRangeList itemRanges;
1063     const int existingItemCount = m_itemData.count();
1064     const int newItemCount = newItems.count();
1065     const int totalItemCount = existingItemCount + newItemCount;
1066
1067     if (existingItemCount == 0) {
1068         // Optimization for the common special case that there are no
1069         // items in the model yet. Happens, e.g., when entering a folder.
1070         m_itemData = newItems;
1071         itemRanges << KItemRange(0, newItemCount);
1072     } else {
1073         m_itemData.reserve(totalItemCount);
1074         for (int i = existingItemCount; i < totalItemCount; ++i) {
1075             m_itemData.append(0);
1076         }
1077
1078         // We build the new list m_items in reverse order to minimize
1079         // the number of moves and guarantee O(N) complexity.
1080         int targetIndex = totalItemCount - 1;
1081         int sourceIndexExistingItems = existingItemCount - 1;
1082         int sourceIndexNewItems = newItemCount - 1;
1083
1084         int rangeCount = 0;
1085
1086         while (sourceIndexNewItems >= 0) {
1087             ItemData* newItem = newItems.at(sourceIndexNewItems);
1088             if (sourceIndexExistingItems >= 0 && lessThan(newItem, m_itemData.at(sourceIndexExistingItems))) {
1089                 // Move an existing item to its new position. If any new items
1090                 // are behind it, push the item range to itemRanges.
1091                 if (rangeCount > 0) {
1092                     itemRanges << KItemRange(sourceIndexExistingItems + 1, rangeCount);
1093                     rangeCount = 0;
1094                 }
1095
1096                 m_itemData[targetIndex] = m_itemData.at(sourceIndexExistingItems);
1097                 --sourceIndexExistingItems;
1098             } else {
1099                 // Insert a new item into the list.
1100                 ++rangeCount;
1101                 m_itemData[targetIndex] = newItem;
1102                 --sourceIndexNewItems;
1103             }
1104             --targetIndex;
1105         }
1106
1107         // Push the final item range to itemRanges.
1108         if (rangeCount > 0) {
1109             itemRanges << KItemRange(sourceIndexExistingItems + 1, rangeCount);
1110         }
1111
1112         // Note that itemRanges is still sorted in reverse order.
1113         std::reverse(itemRanges.begin(), itemRanges.end());
1114     }
1115
1116     // The indexes starting from the first inserted item must be adjusted.
1117     m_items.reserve(totalItemCount);
1118     for (int i = itemRanges.front().index; i < totalItemCount; ++i) {
1119         m_items.insert(m_itemData.at(i)->item.url(), i);
1120     }
1121
1122     emit itemsInserted(itemRanges);
1123
1124 #ifdef KFILEITEMMODEL_DEBUG
1125     kDebug() << "[TIME] Inserting of" << newItems.count() << "items:" << timer.elapsed();
1126 #endif
1127 }
1128
1129 void KFileItemModel::removeItems(const KItemRangeList& itemRanges, RemoveItemsBehavior behavior)
1130 {
1131     if (itemRanges.isEmpty()) {
1132         return;
1133     }
1134
1135     m_groups.clear();
1136
1137     // Step 1: Remove the items from the hash m_items, and free the ItemData.
1138     int removedItemsCount = 0;
1139     foreach (const KItemRange& range, itemRanges) {
1140         removedItemsCount += range.count;
1141
1142         for (int index = range.index; index < range.index + range.count; ++index) {
1143             const KUrl url = m_itemData.at(index)->item.url();
1144
1145             // Prevent repeated expensive rehashing by using QHash::erase(),
1146             // rather than QHash::remove().
1147             QHash<KUrl, int>::iterator it = m_items.find(url);
1148             m_items.erase(it);
1149
1150             if (behavior == DeleteItemData) {
1151                 delete m_itemData.at(index);
1152             }
1153
1154             m_itemData[index] = 0;
1155         }
1156     }
1157
1158     // Step 2: Remove the ItemData pointers from the list m_itemData.
1159     int target = itemRanges.at(0).index;
1160     int source = itemRanges.at(0).index + itemRanges.at(0).count;
1161     int nextRange = 1;
1162
1163     const int oldItemDataCount = m_itemData.count();
1164     while (source < oldItemDataCount) {
1165         m_itemData[target] = m_itemData[source];
1166         ++target;
1167         ++source;
1168
1169         if (nextRange < itemRanges.count() && source == itemRanges.at(nextRange).index) {
1170             // Skip the items in the next removed range.
1171             source += itemRanges.at(nextRange).count;
1172             ++nextRange;
1173         }
1174     }
1175
1176     m_itemData.erase(m_itemData.end() - removedItemsCount, m_itemData.end());
1177
1178     // Step 3: Adjust indexes in the hash m_items, starting from the
1179     //         index of the first removed item.
1180     const int newItemDataCount = m_itemData.count();
1181     for (int i = itemRanges.front().index; i < newItemDataCount; ++i) {
1182         m_items.insert(m_itemData.at(i)->item.url(), i);
1183     }
1184
1185     emit itemsRemoved(itemRanges);
1186 }
1187
1188 QList<KFileItemModel::ItemData*> KFileItemModel::createItemDataList(const KUrl& parentUrl, const KFileItemList& items) const
1189 {
1190     if (m_sortRole == TypeRole) {
1191         // Try to resolve the MIME-types synchronously to prevent a reordering of
1192         // the items when sorting by type (per default MIME-types are resolved
1193         // asynchronously by KFileItemModelRolesUpdater).
1194         determineMimeTypes(items, 200);
1195     }
1196
1197     const int parentIndex = m_items.value(parentUrl, -1);
1198     ItemData* parentItem = parentIndex < 0 ? 0 : m_itemData.at(parentIndex);
1199
1200     QList<ItemData*> itemDataList;
1201     itemDataList.reserve(items.count());
1202
1203     foreach (const KFileItem& item, items) {
1204         ItemData* itemData = new ItemData();
1205         itemData->item = item;
1206         itemData->parent = parentItem;
1207         itemDataList.append(itemData);
1208     }
1209
1210     switch (m_sortRole) {
1211     case PermissionsRole:
1212     case OwnerRole:
1213     case GroupRole:
1214     case DestinationRole:
1215     case PathRole:
1216         // These roles can be determined with retrieveData, and they have to be stored
1217         // in the QHash "values" for the sorting.
1218         foreach (ItemData* itemData, itemDataList) {
1219             itemData->values = retrieveData(itemData->item, parentItem);
1220         }
1221         break;
1222
1223     case TypeRole:
1224         // At least store the data including the file type for items with known MIME type.
1225         foreach (ItemData* itemData, itemDataList) {
1226             const KFileItem item = itemData->item;
1227             if (item.isDir() || item.isMimeTypeKnown()) {
1228                 itemData->values = retrieveData(itemData->item, parentItem);
1229             }
1230         }
1231         break;
1232
1233     default:
1234         // The other roles are either resolved by KFileItemModelRolesUpdater
1235         // (this includes the SizeRole for directories), or they do not need
1236         // to be stored in the QHash "values" for sorting because the data can
1237         // be retrieved directly from the KFileItem (NameRole, SiezRole for files,
1238         // DateRole).
1239         break;
1240     }
1241
1242     return itemDataList;
1243 }
1244
1245 int KFileItemModel::expandedParentsCount(const ItemData* data)
1246 {
1247     // The hash 'values' is only guaranteed to contain the key "expandedParentsCount"
1248     // if the corresponding item is expanded, and it is not a top-level item.
1249     const ItemData* parent = data->parent;
1250     if (parent) {
1251         if (parent->parent) {
1252             Q_ASSERT(parent->values.contains("expandedParentsCount"));
1253             return parent->values.value("expandedParentsCount").toInt() + 1;
1254         } else {
1255             return 1;
1256         }
1257     } else {
1258         return 0;
1259     }
1260 }
1261
1262 void KFileItemModel::removeExpandedItems()
1263 {
1264     QVector<int> indexesToRemove;
1265
1266     const int maxIndex = m_itemData.count() - 1;
1267     for (int i = 0; i <= maxIndex; ++i) {
1268         const ItemData* itemData = m_itemData.at(i);
1269         if (itemData->parent) {
1270             indexesToRemove.append(i);
1271         }
1272     }
1273
1274     removeItems(KItemRangeList::fromSortedContainer(indexesToRemove), DeleteItemData);
1275     m_expandedDirs.clear();
1276
1277     // Also remove all filtered items which have a parent.
1278     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
1279     const QHash<KFileItem, ItemData*>::iterator end = m_filteredItems.end();
1280
1281     while (it != end) {
1282         if (it.value()->parent) {
1283             delete it.value();
1284             it = m_filteredItems.erase(it);
1285         } else {
1286             ++it;
1287         }
1288     }
1289 }
1290
1291 void KFileItemModel::emitItemsChangedAndTriggerResorting(const KItemRangeList& itemRanges, const QSet<QByteArray>& changedRoles)
1292 {
1293     emit itemsChanged(itemRanges, changedRoles);
1294
1295     // Trigger a resorting if necessary. Note that this can happen even if the sort
1296     // role has not changed at all because the file name can be used as a fallback.
1297     if (changedRoles.contains(sortRole()) || changedRoles.contains(roleForType(NameRole))) {
1298         foreach (const KItemRange& range, itemRanges) {
1299             bool needsResorting = false;
1300
1301             const int first = range.index;
1302             const int last = range.index + range.count - 1;
1303
1304             // Resorting the model is necessary if
1305             // (a)  The first item in the range is "lessThan" its predecessor,
1306             // (b)  the successor of the last item is "lessThan" the last item, or
1307             // (c)  the internal order of the items in the range is incorrect.
1308             if (first > 0
1309                 && lessThan(m_itemData.at(first), m_itemData.at(first - 1))) {
1310                 needsResorting = true;
1311             } else if (last < count() - 1
1312                 && lessThan(m_itemData.at(last + 1), m_itemData.at(last))) {
1313                 needsResorting = true;
1314             } else {
1315                 for (int index = first; index < last; ++index) {
1316                     if (lessThan(m_itemData.at(index + 1), m_itemData.at(index))) {
1317                         needsResorting = true;
1318                         break;
1319                     }
1320                 }
1321             }
1322
1323             if (needsResorting) {
1324                 m_resortAllItemsTimer->start();
1325                 return;
1326             }
1327         }
1328     }
1329
1330     if (groupedSorting() && changedRoles.contains(sortRole())) {
1331         // The position is still correct, but the groups might have changed
1332         // if the changed item is either the first or the last item in a
1333         // group.
1334         // In principle, we could try to find out if the item really is the
1335         // first or last one in its group and then update the groups
1336         // (possibly with a delayed timer to make sure that we don't
1337         // re-calculate the groups very often if items are updated one by
1338         // one), but starting m_resortAllItemsTimer is easier.
1339         m_resortAllItemsTimer->start();
1340     }
1341 }
1342
1343 void KFileItemModel::resetRoles()
1344 {
1345     for (int i = 0; i < RolesCount; ++i) {
1346         m_requestRole[i] = false;
1347     }
1348 }
1349
1350 KFileItemModel::RoleType KFileItemModel::typeForRole(const QByteArray& role) const
1351 {
1352     static QHash<QByteArray, RoleType> roles;
1353     if (roles.isEmpty()) {
1354         // Insert user visible roles that can be accessed with
1355         // KFileItemModel::roleInformation()
1356         int count = 0;
1357         const RoleInfoMap* map = rolesInfoMap(count);
1358         for (int i = 0; i < count; ++i) {
1359             roles.insert(map[i].role, map[i].roleType);
1360         }
1361
1362         // Insert internal roles (take care to synchronize the implementation
1363         // with KFileItemModel::roleForType() in case if a change is done).
1364         roles.insert("isDir", IsDirRole);
1365         roles.insert("isLink", IsLinkRole);
1366         roles.insert("isExpanded", IsExpandedRole);
1367         roles.insert("isExpandable", IsExpandableRole);
1368         roles.insert("expandedParentsCount", ExpandedParentsCountRole);
1369
1370         Q_ASSERT(roles.count() == RolesCount);
1371     }
1372
1373     return roles.value(role, NoRole);
1374 }
1375
1376 QByteArray KFileItemModel::roleForType(RoleType roleType) const
1377 {
1378     static QHash<RoleType, QByteArray> roles;
1379     if (roles.isEmpty()) {
1380         // Insert user visible roles that can be accessed with
1381         // KFileItemModel::roleInformation()
1382         int count = 0;
1383         const RoleInfoMap* map = rolesInfoMap(count);
1384         for (int i = 0; i < count; ++i) {
1385             roles.insert(map[i].roleType, map[i].role);
1386         }
1387
1388         // Insert internal roles (take care to synchronize the implementation
1389         // with KFileItemModel::typeForRole() in case if a change is done).
1390         roles.insert(IsDirRole, "isDir");
1391         roles.insert(IsLinkRole, "isLink");
1392         roles.insert(IsExpandedRole, "isExpanded");
1393         roles.insert(IsExpandableRole, "isExpandable");
1394         roles.insert(ExpandedParentsCountRole, "expandedParentsCount");
1395
1396         Q_ASSERT(roles.count() == RolesCount);
1397     };
1398
1399     return roles.value(roleType);
1400 }
1401
1402 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item, const ItemData* parent) const
1403 {
1404     // It is important to insert only roles that are fast to retrieve. E.g.
1405     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
1406     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
1407     QHash<QByteArray, QVariant> data;
1408     data.insert(sharedValue("url"), item.url());
1409
1410     const bool isDir = item.isDir();
1411     if (m_requestRole[IsDirRole] && isDir) {
1412         data.insert(sharedValue("isDir"), true);
1413     }
1414
1415     if (m_requestRole[IsLinkRole] && item.isLink()) {
1416         data.insert(sharedValue("isLink"), true);
1417     }
1418
1419     if (m_requestRole[NameRole]) {
1420         data.insert(sharedValue("text"), item.text());
1421     }
1422
1423     if (m_requestRole[SizeRole] && !isDir) {
1424         data.insert(sharedValue("size"), item.size());
1425     }
1426
1427     if (m_requestRole[DateRole]) {
1428         // Don't use KFileItem::timeString() as this is too expensive when
1429         // having several thousands of items. Instead the formatting of the
1430         // date-time will be done on-demand by the view when the date will be shown.
1431         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
1432         data.insert(sharedValue("date"), dateTime.dateTime());
1433     }
1434
1435     if (m_requestRole[PermissionsRole]) {
1436         data.insert(sharedValue("permissions"), item.permissionsString());
1437     }
1438
1439     if (m_requestRole[OwnerRole]) {
1440         data.insert(sharedValue("owner"), item.user());
1441     }
1442
1443     if (m_requestRole[GroupRole]) {
1444         data.insert(sharedValue("group"), item.group());
1445     }
1446
1447     if (m_requestRole[DestinationRole]) {
1448         QString destination = item.linkDest();
1449         if (destination.isEmpty()) {
1450             destination = QLatin1String("-");
1451         }
1452         data.insert(sharedValue("destination"), destination);
1453     }
1454
1455     if (m_requestRole[PathRole]) {
1456         QString path;
1457         if (item.url().protocol() == QLatin1String("trash")) {
1458             path = item.entry().stringValue(KIO::UDSEntry::UDS_EXTRA);
1459         } else {
1460             // For performance reasons cache the home-path in a static QString
1461             // (see QDir::homePath() for more details)
1462             static QString homePath;
1463             if (homePath.isEmpty()) {
1464                 homePath = QDir::homePath();
1465             }
1466
1467             path = item.localPath();
1468             if (path.startsWith(homePath)) {
1469                 path.replace(0, homePath.length(), QLatin1Char('~'));
1470             }
1471         }
1472
1473         const int index = path.lastIndexOf(item.text());
1474         path = path.mid(0, index - 1);
1475         data.insert(sharedValue("path"), path);
1476     }
1477
1478     if (m_requestRole[IsExpandableRole] && isDir) {
1479         data.insert(sharedValue("isExpandable"), true);
1480     }
1481
1482     if (m_requestRole[ExpandedParentsCountRole]) {
1483         if (parent) {
1484             const int level = expandedParentsCount(parent) + 1;
1485             data.insert(sharedValue("expandedParentsCount"), level);
1486         }
1487     }
1488
1489     if (item.isMimeTypeKnown()) {
1490         data.insert(sharedValue("iconName"), item.iconName());
1491
1492         if (m_requestRole[TypeRole]) {
1493             data.insert(sharedValue("type"), item.mimeComment());
1494         }
1495     } else if (m_requestRole[TypeRole] && isDir) {
1496         static const QString folderMimeType = item.mimeComment();
1497         data.insert(sharedValue("type"), folderMimeType);
1498     }
1499
1500     return data;
1501 }
1502
1503 bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const
1504 {
1505     int result = 0;
1506
1507     if (a->parent != b->parent) {
1508         const int expansionLevelA = expandedParentsCount(a);
1509         const int expansionLevelB = expandedParentsCount(b);
1510
1511         // If b has a higher expansion level than a, check if a is a parent
1512         // of b, and make sure that both expansion levels are equal otherwise.
1513         for (int i = expansionLevelB; i > expansionLevelA; --i) {
1514             if (b->parent == a) {
1515                 return true;
1516             }
1517             b = b->parent;
1518         }
1519
1520         // If a has a higher expansion level than a, check if b is a parent
1521         // of a, and make sure that both expansion levels are equal otherwise.
1522         for (int i = expansionLevelA; i > expansionLevelB; --i) {
1523             if (a->parent == b) {
1524                 return false;
1525             }
1526             a = a->parent;
1527         }
1528
1529         Q_ASSERT(expandedParentsCount(a) == expandedParentsCount(b));
1530
1531         // Compare the last parents of a and b which are different.
1532         while (a->parent != b->parent) {
1533             a = a->parent;
1534             b = b->parent;
1535         }
1536     }
1537
1538     if (m_sortDirsFirst || m_sortRole == SizeRole) {
1539         const bool isDirA = a->item.isDir();
1540         const bool isDirB = b->item.isDir();
1541         if (isDirA && !isDirB) {
1542             return true;
1543         } else if (!isDirA && isDirB) {
1544             return false;
1545         }
1546     }
1547
1548     result = sortRoleCompare(a, b);
1549
1550     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
1551 }
1552
1553 /**
1554  * Helper class for KFileItemModel::sort().
1555  */
1556 class KFileItemModelLessThan
1557 {
1558 public:
1559     KFileItemModelLessThan(const KFileItemModel* model) :
1560         m_model(model)
1561     {
1562     }
1563
1564     bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const
1565     {
1566         return m_model->lessThan(a, b);
1567     }
1568
1569 private:
1570     const KFileItemModel* m_model;
1571 };
1572
1573 void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin,
1574                           QList<KFileItemModel::ItemData*>::iterator end) const
1575 {
1576     KFileItemModelLessThan lessThan(this);
1577
1578     if (m_sortRole == NameRole) {
1579         // Sorting by name can be expensive, in particular if natural sorting is
1580         // enabled. Use all CPU cores to speed up the sorting process.
1581         static const int numberOfThreads = QThread::idealThreadCount();
1582         parallelMergeSort(begin, end, lessThan, numberOfThreads);
1583     } else {
1584         // Sorting by other roles is quite fast. Use only one thread to prevent
1585         // problems caused by non-reentrant comparison functions, see
1586         // https://bugs.kde.org/show_bug.cgi?id=312679
1587         mergeSort(begin, end, lessThan);
1588     }
1589 }
1590
1591 int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
1592 {
1593     const KFileItem& itemA = a->item;
1594     const KFileItem& itemB = b->item;
1595
1596     int result = 0;
1597
1598     switch (m_sortRole) {
1599     case NameRole:
1600         // The name role is handled as default fallback after the switch
1601         break;
1602
1603     case SizeRole: {
1604         if (itemA.isDir()) {
1605             // See "if (m_sortFoldersFirst || m_sortRole == SizeRole)" in KFileItemModel::lessThan():
1606             Q_ASSERT(itemB.isDir());
1607
1608             const QVariant valueA = a->values.value("size");
1609             const QVariant valueB = b->values.value("size");
1610             if (valueA.isNull() && valueB.isNull()) {
1611                 result = 0;
1612             } else if (valueA.isNull()) {
1613                 result = -1;
1614             } else if (valueB.isNull()) {
1615                 result = +1;
1616             } else {
1617                 result = valueA.toInt() - valueB.toInt();
1618             }
1619         } else {
1620             // See "if (m_sortFoldersFirst || m_sortRole == SizeRole)" in KFileItemModel::lessThan():
1621             Q_ASSERT(!itemB.isDir());
1622             const KIO::filesize_t sizeA = itemA.size();
1623             const KIO::filesize_t sizeB = itemB.size();
1624             if (sizeA > sizeB) {
1625                 result = +1;
1626             } else if (sizeA < sizeB) {
1627                 result = -1;
1628             } else {
1629                 result = 0;
1630             }
1631         }
1632         break;
1633     }
1634
1635     case DateRole: {
1636         const KDateTime dateTimeA = itemA.time(KFileItem::ModificationTime);
1637         const KDateTime dateTimeB = itemB.time(KFileItem::ModificationTime);
1638         if (dateTimeA < dateTimeB) {
1639             result = -1;
1640         } else if (dateTimeA > dateTimeB) {
1641             result = +1;
1642         }
1643         break;
1644     }
1645
1646     case RatingRole: {
1647         result = a->values.value("rating").toInt() - b->values.value("rating").toInt();
1648         break;
1649     }
1650
1651     case ImageSizeRole: {
1652         // Alway use a natural comparing to interpret the numbers of a string like
1653         // "1600 x 1200" for having a correct sorting.
1654         result = KStringHandler::naturalCompare(a->values.value("imageSize").toString(),
1655                                                 b->values.value("imageSize").toString(),
1656                                                 Qt::CaseSensitive);
1657         break;
1658     }
1659
1660     default: {
1661         const QByteArray role = roleForType(m_sortRole);
1662         result = QString::compare(a->values.value(role).toString(),
1663                                   b->values.value(role).toString());
1664         break;
1665     }
1666
1667     }
1668
1669     if (result != 0) {
1670         // The current sort role was sufficient to define an order
1671         return result;
1672     }
1673
1674     // Fallback #1: Compare the text of the items
1675     result = stringCompare(itemA.text(), itemB.text());
1676     if (result != 0) {
1677         return result;
1678     }
1679
1680     // Fallback #2: KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
1681     result = stringCompare(itemA.name(m_caseSensitivity == Qt::CaseInsensitive),
1682                            itemB.name(m_caseSensitivity == Qt::CaseInsensitive));
1683     if (result != 0) {
1684         return result;
1685     }
1686
1687     // Fallback #3: It must be assured that the sort order is always unique even if two values have been
1688     // equal. In this case a comparison of the URL is done which is unique in all cases
1689     // within KDirLister.
1690     return QString::compare(itemA.url().url(), itemB.url().url(), Qt::CaseSensitive);
1691 }
1692
1693 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
1694 {
1695     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
1696     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
1697     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
1698     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
1699
1700     if (m_caseSensitivity == Qt::CaseInsensitive) {
1701         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
1702                                             : QString::compare(a, b, Qt::CaseInsensitive);
1703         if (result != 0) {
1704             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
1705             // comparison, still a deterministic sort order is required. A case sensitive
1706             // comparison is done as fallback.
1707             return result;
1708         }
1709     }
1710
1711     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
1712                             : QString::compare(a, b, Qt::CaseSensitive);
1713 }
1714
1715 bool KFileItemModel::useMaximumUpdateInterval() const
1716 {
1717     return !m_dirLister->url().isLocalFile();
1718 }
1719
1720 static bool localeAwareLessThan(const QChar& c1, const QChar& c2)
1721 {
1722     return QString::localeAwareCompare(c1, c2) < 0;
1723 }
1724
1725 QList<QPair<int, QVariant> > KFileItemModel::nameRoleGroups() const
1726 {
1727     Q_ASSERT(!m_itemData.isEmpty());
1728
1729     const int maxIndex = count() - 1;
1730     QList<QPair<int, QVariant> > groups;
1731
1732     QString groupValue;
1733     QChar firstChar;
1734     for (int i = 0; i <= maxIndex; ++i) {
1735         if (isChildItem(i)) {
1736             continue;
1737         }
1738
1739         const QString name = m_itemData.at(i)->item.text();
1740
1741         // Use the first character of the name as group indication
1742         QChar newFirstChar = name.at(0).toUpper();
1743         if (newFirstChar == QLatin1Char('~') && name.length() > 1) {
1744             newFirstChar = name.at(1).toUpper();
1745         }
1746
1747         if (firstChar != newFirstChar) {
1748             QString newGroupValue;
1749             if (newFirstChar.isLetter()) {
1750                 // Try to find a matching group in the range 'A' to 'Z'.
1751                 static std::vector<QChar> lettersAtoZ;
1752                 if (lettersAtoZ.empty()) {
1753                     for (char c = 'A'; c <= 'Z'; ++c) {
1754                         lettersAtoZ.push_back(QLatin1Char(c));
1755                     }
1756                 }
1757
1758                 std::vector<QChar>::iterator it = std::lower_bound(lettersAtoZ.begin(), lettersAtoZ.end(), newFirstChar, localeAwareLessThan);
1759                 if (it != lettersAtoZ.end()) {
1760                     if (localeAwareLessThan(newFirstChar, *it) && it != lettersAtoZ.begin()) {
1761                         // newFirstChar belongs to the group preceding *it.
1762                         // Example: for an umlaut 'A' in the German locale, *it would be 'B' now.
1763                         --it;
1764                     }
1765                     newGroupValue = *it;
1766                 } else {
1767                     newGroupValue = newFirstChar;
1768                 }
1769             } else if (newFirstChar >= QLatin1Char('0') && newFirstChar <= QLatin1Char('9')) {
1770                 // Apply group '0 - 9' for any name that starts with a digit
1771                 newGroupValue = i18nc("@title:group Groups that start with a digit", "0 - 9");
1772             } else {
1773                 newGroupValue = i18nc("@title:group", "Others");
1774             }
1775
1776             if (newGroupValue != groupValue) {
1777                 groupValue = newGroupValue;
1778                 groups.append(QPair<int, QVariant>(i, newGroupValue));
1779             }
1780
1781             firstChar = newFirstChar;
1782         }
1783     }
1784     return groups;
1785 }
1786
1787 QList<QPair<int, QVariant> > KFileItemModel::sizeRoleGroups() const
1788 {
1789     Q_ASSERT(!m_itemData.isEmpty());
1790
1791     const int maxIndex = count() - 1;
1792     QList<QPair<int, QVariant> > groups;
1793
1794     QString groupValue;
1795     for (int i = 0; i <= maxIndex; ++i) {
1796         if (isChildItem(i)) {
1797             continue;
1798         }
1799
1800         const KFileItem& item = m_itemData.at(i)->item;
1801         const KIO::filesize_t fileSize = !item.isNull() ? item.size() : ~0U;
1802         QString newGroupValue;
1803         if (!item.isNull() && item.isDir()) {
1804             newGroupValue = i18nc("@title:group Size", "Folders");
1805         } else if (fileSize < 5 * 1024 * 1024) {
1806             newGroupValue = i18nc("@title:group Size", "Small");
1807         } else if (fileSize < 10 * 1024 * 1024) {
1808             newGroupValue = i18nc("@title:group Size", "Medium");
1809         } else {
1810             newGroupValue = i18nc("@title:group Size", "Big");
1811         }
1812
1813         if (newGroupValue != groupValue) {
1814             groupValue = newGroupValue;
1815             groups.append(QPair<int, QVariant>(i, newGroupValue));
1816         }
1817     }
1818
1819     return groups;
1820 }
1821
1822 QList<QPair<int, QVariant> > KFileItemModel::dateRoleGroups() const
1823 {
1824     Q_ASSERT(!m_itemData.isEmpty());
1825
1826     const int maxIndex = count() - 1;
1827     QList<QPair<int, QVariant> > groups;
1828
1829     const QDate currentDate = KDateTime::currentLocalDateTime().date();
1830
1831     QDate previousModifiedDate;
1832     QString groupValue;
1833     for (int i = 0; i <= maxIndex; ++i) {
1834         if (isChildItem(i)) {
1835             continue;
1836         }
1837
1838         const KDateTime modifiedTime = m_itemData.at(i)->item.time(KFileItem::ModificationTime);
1839         const QDate modifiedDate = modifiedTime.date();
1840         if (modifiedDate == previousModifiedDate) {
1841             // The current item is in the same group as the previous item
1842             continue;
1843         }
1844         previousModifiedDate = modifiedDate;
1845
1846         const int daysDistance = modifiedDate.daysTo(currentDate);
1847
1848         QString newGroupValue;
1849         if (currentDate.year() == modifiedDate.year() && currentDate.month() == modifiedDate.month()) {
1850             switch (daysDistance / 7) {
1851             case 0:
1852                 switch (daysDistance) {
1853                 case 0:  newGroupValue = i18nc("@title:group Date", "Today"); break;
1854                 case 1:  newGroupValue = i18nc("@title:group Date", "Yesterday"); break;
1855                 default: newGroupValue = modifiedTime.toString(i18nc("@title:group The week day name: %A", "%A"));
1856                 }
1857                 break;
1858             case 1:
1859                 newGroupValue = i18nc("@title:group Date", "One Week Ago");
1860                 break;
1861             case 2:
1862                 newGroupValue = i18nc("@title:group Date", "Two Weeks Ago");
1863                 break;
1864             case 3:
1865                 newGroupValue = i18nc("@title:group Date", "Three Weeks Ago");
1866                 break;
1867             case 4:
1868             case 5:
1869                 newGroupValue = i18nc("@title:group Date", "Earlier this Month");
1870                 break;
1871             default:
1872                 Q_ASSERT(false);
1873             }
1874         } else {
1875             const QDate lastMonthDate = currentDate.addMonths(-1);
1876             if  (lastMonthDate.year() == modifiedDate.year() && lastMonthDate.month() == modifiedDate.month()) {
1877                 if (daysDistance == 1) {
1878                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Yesterday (%B, %Y)"));
1879                 } else if (daysDistance <= 7) {
1880                     newGroupValue = modifiedTime.toString(i18nc("@title:group The week day name: %A, %B is full month name in current locale, and %Y is full year number", "%A (%B, %Y)"));
1881                 } else if (daysDistance <= 7 * 2) {
1882                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "One Week Ago (%B, %Y)"));
1883                 } else if (daysDistance <= 7 * 3) {
1884                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Two Weeks Ago (%B, %Y)"));
1885                 } else if (daysDistance <= 7 * 4) {
1886                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Three Weeks Ago (%B, %Y)"));
1887                 } else {
1888                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Earlier on %B, %Y"));
1889                 }
1890             } else {
1891                 newGroupValue = modifiedTime.toString(i18nc("@title:group The month and year: %B is full month name in current locale, and %Y is full year number", "%B, %Y"));
1892             }
1893         }
1894
1895         if (newGroupValue != groupValue) {
1896             groupValue = newGroupValue;
1897             groups.append(QPair<int, QVariant>(i, newGroupValue));
1898         }
1899     }
1900
1901     return groups;
1902 }
1903
1904 QList<QPair<int, QVariant> > KFileItemModel::permissionRoleGroups() const
1905 {
1906     Q_ASSERT(!m_itemData.isEmpty());
1907
1908     const int maxIndex = count() - 1;
1909     QList<QPair<int, QVariant> > groups;
1910
1911     QString permissionsString;
1912     QString groupValue;
1913     for (int i = 0; i <= maxIndex; ++i) {
1914         if (isChildItem(i)) {
1915             continue;
1916         }
1917
1918         const ItemData* itemData = m_itemData.at(i);
1919         const QString newPermissionsString = itemData->values.value("permissions").toString();
1920         if (newPermissionsString == permissionsString) {
1921             continue;
1922         }
1923         permissionsString = newPermissionsString;
1924
1925         const QFileInfo info(itemData->item.url().pathOrUrl());
1926
1927         // Set user string
1928         QString user;
1929         if (info.permission(QFile::ReadUser)) {
1930             user = i18nc("@item:intext Access permission, concatenated", "Read, ");
1931         }
1932         if (info.permission(QFile::WriteUser)) {
1933             user += i18nc("@item:intext Access permission, concatenated", "Write, ");
1934         }
1935         if (info.permission(QFile::ExeUser)) {
1936             user += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1937         }
1938         user = user.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : user.mid(0, user.count() - 2);
1939
1940         // Set group string
1941         QString group;
1942         if (info.permission(QFile::ReadGroup)) {
1943             group = i18nc("@item:intext Access permission, concatenated", "Read, ");
1944         }
1945         if (info.permission(QFile::WriteGroup)) {
1946             group += i18nc("@item:intext Access permission, concatenated", "Write, ");
1947         }
1948         if (info.permission(QFile::ExeGroup)) {
1949             group += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1950         }
1951         group = group.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : group.mid(0, group.count() - 2);
1952
1953         // Set others string
1954         QString others;
1955         if (info.permission(QFile::ReadOther)) {
1956             others = i18nc("@item:intext Access permission, concatenated", "Read, ");
1957         }
1958         if (info.permission(QFile::WriteOther)) {
1959             others += i18nc("@item:intext Access permission, concatenated", "Write, ");
1960         }
1961         if (info.permission(QFile::ExeOther)) {
1962             others += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1963         }
1964         others = others.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : others.mid(0, others.count() - 2);
1965
1966         const QString newGroupValue = i18nc("@title:group Files and folders by permissions", "User: %1 | Group: %2 | Others: %3", user, group, others);
1967         if (newGroupValue != groupValue) {
1968             groupValue = newGroupValue;
1969             groups.append(QPair<int, QVariant>(i, newGroupValue));
1970         }
1971     }
1972
1973     return groups;
1974 }
1975
1976 QList<QPair<int, QVariant> > KFileItemModel::ratingRoleGroups() const
1977 {
1978     Q_ASSERT(!m_itemData.isEmpty());
1979
1980     const int maxIndex = count() - 1;
1981     QList<QPair<int, QVariant> > groups;
1982
1983     int groupValue = -1;
1984     for (int i = 0; i <= maxIndex; ++i) {
1985         if (isChildItem(i)) {
1986             continue;
1987         }
1988         const int newGroupValue = m_itemData.at(i)->values.value("rating", 0).toInt();
1989         if (newGroupValue != groupValue) {
1990             groupValue = newGroupValue;
1991             groups.append(QPair<int, QVariant>(i, newGroupValue));
1992         }
1993     }
1994
1995     return groups;
1996 }
1997
1998 QList<QPair<int, QVariant> > KFileItemModel::genericStringRoleGroups(const QByteArray& role) const
1999 {
2000     Q_ASSERT(!m_itemData.isEmpty());
2001
2002     const int maxIndex = count() - 1;
2003     QList<QPair<int, QVariant> > groups;
2004
2005     bool isFirstGroupValue = true;
2006     QString groupValue;
2007     for (int i = 0; i <= maxIndex; ++i) {
2008         if (isChildItem(i)) {
2009             continue;
2010         }
2011         const QString newGroupValue = m_itemData.at(i)->values.value(role).toString();
2012         if (newGroupValue != groupValue || isFirstGroupValue) {
2013             groupValue = newGroupValue;
2014             groups.append(QPair<int, QVariant>(i, newGroupValue));
2015             isFirstGroupValue = false;
2016         }
2017     }
2018
2019     return groups;
2020 }
2021
2022 void KFileItemModel::emitSortProgress(int resolvedCount)
2023 {
2024     // Be tolerant against a resolvedCount with a wrong range.
2025     // Although there should not be a case where KFileItemModelRolesUpdater
2026     // (= caller) provides a wrong range, it is important to emit
2027     // a useful progress information even if there is an unexpected
2028     // implementation issue.
2029
2030     const int itemCount = count();
2031     if (resolvedCount >= itemCount) {
2032         m_sortingProgressPercent = -1;
2033         if (m_resortAllItemsTimer->isActive()) {
2034             m_resortAllItemsTimer->stop();
2035             resortAllItems();
2036         }
2037
2038         emit directorySortingProgress(100);
2039     } else if (itemCount > 0) {
2040         resolvedCount = qBound(0, resolvedCount, itemCount);
2041
2042         const int progress = resolvedCount * 100 / itemCount;
2043         if (m_sortingProgressPercent != progress) {
2044             m_sortingProgressPercent = progress;
2045             emit directorySortingProgress(progress);
2046         }
2047     }
2048 }
2049
2050 const KFileItemModel::RoleInfoMap* KFileItemModel::rolesInfoMap(int& count)
2051 {
2052     static const RoleInfoMap rolesInfoMap[] = {
2053     //  | role         | roleType       | role translation                                | group translation           | requires Nepomuk | requires indexer
2054         { 0,             NoRole,          0, 0,                                             0, 0,                                     false, false },
2055         { "text",        NameRole,        I18N_NOOP2_NOSTRIP("@label", "Name"),             0, 0,                                     false, false },
2056         { "size",        SizeRole,        I18N_NOOP2_NOSTRIP("@label", "Size"),             0, 0,                                     false, false },
2057         { "date",        DateRole,        I18N_NOOP2_NOSTRIP("@label", "Date"),             0, 0,                                     false, false },
2058         { "type",        TypeRole,        I18N_NOOP2_NOSTRIP("@label", "Type"),             0, 0,                                     false, false },
2059         { "rating",      RatingRole,      I18N_NOOP2_NOSTRIP("@label", "Rating"),           0, 0,                                     true,  false },
2060         { "tags",        TagsRole,        I18N_NOOP2_NOSTRIP("@label", "Tags"),             0, 0,                                     true,  false },
2061         { "comment",     CommentRole,     I18N_NOOP2_NOSTRIP("@label", "Comment"),          0, 0,                                     true,  false },
2062         { "wordCount",   WordCountRole,   I18N_NOOP2_NOSTRIP("@label", "Word Count"),       I18N_NOOP2_NOSTRIP("@label", "Document"), true,  true  },
2063         { "lineCount",   LineCountRole,   I18N_NOOP2_NOSTRIP("@label", "Line Count"),       I18N_NOOP2_NOSTRIP("@label", "Document"), true,  true  },
2064         { "imageSize",   ImageSizeRole,   I18N_NOOP2_NOSTRIP("@label", "Image Size"),       I18N_NOOP2_NOSTRIP("@label", "Image"),    true,  true  },
2065         { "orientation", OrientationRole, I18N_NOOP2_NOSTRIP("@label", "Orientation"),      I18N_NOOP2_NOSTRIP("@label", "Image"),    true,  true  },
2066         { "artist",      ArtistRole,      I18N_NOOP2_NOSTRIP("@label", "Artist"),           I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2067         { "album",       AlbumRole,       I18N_NOOP2_NOSTRIP("@label", "Album"),            I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2068         { "duration",    DurationRole,    I18N_NOOP2_NOSTRIP("@label", "Duration"),         I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2069         { "track",       TrackRole,       I18N_NOOP2_NOSTRIP("@label", "Track"),            I18N_NOOP2_NOSTRIP("@label", "Audio"),    true,  true  },
2070         { "path",        PathRole,        I18N_NOOP2_NOSTRIP("@label", "Path"),             I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2071         { "destination", DestinationRole, I18N_NOOP2_NOSTRIP("@label", "Link Destination"), I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2072         { "copiedFrom",  CopiedFromRole,  I18N_NOOP2_NOSTRIP("@label", "Copied From"),      I18N_NOOP2_NOSTRIP("@label", "Other"),    true,  false },
2073         { "permissions", PermissionsRole, I18N_NOOP2_NOSTRIP("@label", "Permissions"),      I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2074         { "owner",       OwnerRole,       I18N_NOOP2_NOSTRIP("@label", "Owner"),            I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2075         { "group",       GroupRole,       I18N_NOOP2_NOSTRIP("@label", "User Group"),       I18N_NOOP2_NOSTRIP("@label", "Other"),    false, false },
2076     };
2077
2078     count = sizeof(rolesInfoMap) / sizeof(RoleInfoMap);
2079     return rolesInfoMap;
2080 }
2081
2082 void KFileItemModel::determineMimeTypes(const KFileItemList& items, int timeout)
2083 {
2084     QElapsedTimer timer;
2085     timer.start();
2086     foreach (const KFileItem& item, items) { // krazy:exclude=foreach
2087         // Only determine mime types for files here. For directories,
2088         // KFileItem::determineMimeType() reads the .directory file inside to
2089         // load the icon, but this is not necessary at all if we just need the
2090         // type. Some special code for setting the correct mime type for
2091         // directories is in retrieveData().
2092         if (!item.isDir()) {
2093             item.determineMimeType();
2094         }
2095
2096         if (timer.elapsed() > timeout) {
2097             // Don't block the user interface, let the remaining items
2098             // be resolved asynchronously.
2099             return;
2100         }
2101     }
2102 }
2103
2104 QByteArray KFileItemModel::sharedValue(const QByteArray& value)
2105 {
2106     static QSet<QByteArray> pool;
2107     const QSet<QByteArray>::const_iterator it = pool.constFind(value);
2108
2109     if (it != pool.constEnd()) {
2110         return *it;
2111     } else {
2112         pool.insert(value);
2113         return value;
2114     }
2115 }
2116
2117 bool KFileItemModel::isConsistent() const
2118 {
2119     if (m_items.count() != m_itemData.count()) {
2120         return false;
2121     }
2122
2123     for (int i = 0; i < count(); ++i) {
2124         // Check if m_items and m_itemData are consistent.
2125         const KFileItem item = fileItem(i);
2126         if (item.isNull()) {
2127             qWarning() << "Item" << i << "is null";
2128             return false;
2129         }
2130
2131         const int itemIndex = index(item);
2132         if (itemIndex != i) {
2133             qWarning() << "Item" << i << "has a wrong index:" << itemIndex;
2134             return false;
2135         }
2136
2137         // Check if the items are sorted correctly.
2138         if (i > 0 && !lessThan(m_itemData.at(i - 1), m_itemData.at(i))) {
2139             qWarning() << "The order of items" << i - 1 << "and" << i << "is wrong:"
2140                 << fileItem(i - 1) << fileItem(i);
2141             return false;
2142         }
2143
2144         // Check if all parent-child relationships are consistent.
2145         const ItemData* data = m_itemData.at(i);
2146         const ItemData* parent = data->parent;
2147         if (parent) {
2148             if (expandedParentsCount(data) != expandedParentsCount(parent) + 1) {
2149                 qWarning() << "expandedParentsCount is inconsistent for parent" << parent->item << "and child" << data->item;
2150                 return false;
2151             }
2152
2153             const int parentIndex = index(parent->item);
2154             if (parentIndex >= i) {
2155                 qWarning() << "Index" << parentIndex << "of parent" << parent->item << "is not smaller than index" << i << "of child" << data->item;
2156                 return false;
2157             }
2158         }
2159     }
2160
2161     return true;
2162 }
2163
2164 #include "kfileitemmodel.moc"