src/kitemviews/kfileitemmodel.cpp

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