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