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