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