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