src/kitemviews/kfileitemmodel.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2011 by Peter Penz <peter.penz19@gmail.com>             *
   3  *                                                                         *
   4  *   This program is free software; you can redistribute it and/or modify  *
   5  *   it under the terms of the GNU General Public License as published by  *
   6  *   the Free Software Foundation; either version 2 of the License, or     *
   7  *   (at your option) any later version.                                   *
   8  *                                                                         *
   9  *   This program is distributed in the hope that it will be useful,       *
  10  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  12  *   GNU General Public License for more details.                          *
  13  *                                                                         *
  14  *   You should have received a copy of the GNU General Public License     *
  15  *   along with this program; if not, write to the                         *
  16  *   Free Software Foundation, Inc.,                                       *
  17  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
  18  ***************************************************************************/
  19
  20 #include "kfileitemmodel.h"
  21
  22 #include <KDirLister>
  23 #include <KDirModel>
  24 #include <KGlobalSettings>
  25 #include <KLocale>
  26 #include <KStringHandler>
  27 #include <KDebug>
  28
  29 #include <QMimeData>
  30 #include <QTimer>
  31
  32 // #define KFILEITEMMODEL_DEBUG
  33
  34 KFileItemModel::KFileItemModel(KDirLister* dirLister, QObject* parent) :
  35     KItemModelBase("name", parent),
  36     m_dirLister(dirLister),
  37     m_naturalSorting(KGlobalSettings::naturalSorting()),
  38     m_sortFoldersFirst(true),
  39     m_sortRole(NameRole),
  40     m_roles(),
  41     m_caseSensitivity(Qt::CaseInsensitive),
  42     m_itemData(),
  43     m_items(),
  44     m_filter(),
  45     m_filteredItems(),
  46     m_requestRole(),
  47     m_minimumUpdateIntervalTimer(0),
  48     m_maximumUpdateIntervalTimer(0),
  49     m_resortAllItemsTimer(0),
  50     m_pendingItemsToInsert(),
  51     m_pendingEmitLoadingCompleted(false),
  52     m_groups(),
  53     m_rootExpansionLevel(UninitializedRootExpansionLevel),
  54     m_expandedUrls(),
  55     m_urlsToExpand()
  56 {
  57     // Apply default roles that should be determined
  58     resetRoles();
  59     m_requestRole[NameRole] = true;
  60     m_requestRole[IsDirRole] = true;
  61     m_roles.insert("name");
  62     m_roles.insert("isDir");
  63
  64     Q_ASSERT(dirLister);
  65
  66     connect(dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  67     connect(dirLister, SIGNAL(completed(KUrl)), this, SLOT(slotCompleted()));
  68     connect(dirLister, SIGNAL(newItems(KFileItemList)), this, SLOT(slotNewItems(KFileItemList)));
  69     connect(dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  70     connect(dirLister, SIGNAL(refreshItems(QList<QPair<KFileItem,KFileItem> >)), this, SLOT(slotRefreshItems(QList<QPair<KFileItem,KFileItem> >)));
  71     connect(dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  72     connect(dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  73
  74     // Although the layout engine of KItemListView is fast it is very inefficient to e.g.
  75     // emit 50 itemsInserted()-signals each 100 ms. m_minimumUpdateIntervalTimer assures that updates
  76     // are done in 1 second intervals for equal operations.
  77     m_minimumUpdateIntervalTimer = new QTimer(this);
  78     m_minimumUpdateIntervalTimer->setInterval(1000);
  79     m_minimumUpdateIntervalTimer->setSingleShot(true);
  80     connect(m_minimumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  81
  82     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  83     // before the completed() or canceled() signal has been emitted.
  84     m_maximumUpdateIntervalTimer = new QTimer(this);
  85     m_maximumUpdateIntervalTimer->setInterval(2000);
  86     m_maximumUpdateIntervalTimer->setSingleShot(true);
  87     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  88
  89     // When changing the value of an item which represents the sort-role a resorting must be
  90     // triggered. Especially in combination with KFileItemModelRolesUpdater this might be done
  91     // for a lot of items within a quite small timeslot. To prevent expensive resortings the
  92     // resorting is postponed until the timer has been exceeded.
  93     m_resortAllItemsTimer = new QTimer(this);
  94     m_resortAllItemsTimer->setInterval(500);
  95     m_resortAllItemsTimer->setSingleShot(true);
  96     connect(m_resortAllItemsTimer, SIGNAL(timeout()), this, SLOT(resortAllItems()));
  97
  98     Q_ASSERT(m_minimumUpdateIntervalTimer->interval() <= m_maximumUpdateIntervalTimer->interval());
  99
 100     connect(KGlobalSettings::self(), SIGNAL(naturalSortingChanged()), this, SLOT(slotNaturalSortingChanged()));
 101 }
 102
 103 KFileItemModel::~KFileItemModel()
 104 {
 105     qDeleteAll(m_itemData);
 106     m_itemData.clear();
 107 }
 108
 109 int KFileItemModel::count() const
 110 {
 111     return m_itemData.count();
 112 }
 113
 114 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
 115 {
 116     if (index >= 0 && index < count()) {
 117         return m_itemData.at(index)->values;
 118     }
 119     return QHash<QByteArray, QVariant>();
 120 }
 121
 122 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
 123 {
 124     if (index < 0 || index >= count()) {
 125         return false;
 126     }
 127
 128     QHash<QByteArray, QVariant> currentValues = m_itemData.at(index)->values;
 129
 130     // Determine which roles have been changed
 131     QSet<QByteArray> changedRoles;
 132     QHashIterator<QByteArray, QVariant> it(values);
 133     while (it.hasNext()) {
 134         it.next();
 135         const QByteArray role = it.key();
 136         const QVariant value = it.value();
 137
 138         if (currentValues[role] != value) {
 139             currentValues[role] = value;
 140             changedRoles.insert(role);
 141         }
 142     }
 143
 144     if (changedRoles.isEmpty()) {
 145         return false;
 146     }
 147
 148     m_itemData[index]->values = currentValues;
 149     emit itemsChanged(KItemRangeList() << KItemRange(index, 1), changedRoles);
 150
 151     if (changedRoles.contains(sortRole())) {
 152         m_resortAllItemsTimer->start();
 153     }
 154
 155     return true;
 156 }
 157
 158 void KFileItemModel::setSortFoldersFirst(bool foldersFirst)
 159 {
 160     if (foldersFirst != m_sortFoldersFirst) {
 161         m_sortFoldersFirst = foldersFirst;
 162         resortAllItems();
 163     }
 164 }
 165
 166 bool KFileItemModel::sortFoldersFirst() const
 167 {
 168     return m_sortFoldersFirst;
 169 }
 170
 171 void KFileItemModel::setShowHiddenFiles(bool show)
 172 {
 173     KDirLister* dirLister = m_dirLister.data();
 174     if (dirLister) {
 175         dirLister->setShowingDotFiles(show);
 176         dirLister->emitChanges();
 177         if (show) {
 178             slotCompleted();
 179         }
 180     }
 181 }
 182
 183 bool KFileItemModel::showHiddenFiles() const
 184 {
 185     const KDirLister* dirLister = m_dirLister.data();
 186     return dirLister ? dirLister->showingDotFiles() : false;
 187 }
 188
 189 void KFileItemModel::setShowFoldersOnly(bool enabled)
 190 {
 191     KDirLister* dirLister = m_dirLister.data();
 192     if (dirLister) {
 193         dirLister->setDirOnlyMode(enabled);
 194     }
 195 }
 196
 197 bool KFileItemModel::showFoldersOnly() const
 198 {
 199     KDirLister* dirLister = m_dirLister.data();
 200     return dirLister ? dirLister->dirOnlyMode() : false;
 201 }
 202
 203 QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
 204 {
 205     QMimeData* data = new QMimeData();
 206
 207     // The following code has been taken from KDirModel::mimeData()
 208     // (kdelibs/kio/kio/kdirmodel.cpp)
 209     // Copyright (C) 2006 David Faure <faure@kde.org>
 210     KUrl::List urls;
 211     KUrl::List mostLocalUrls;
 212     bool canUseMostLocalUrls = true;
 213
 214     QSetIterator<int> it(indexes);
 215     while (it.hasNext()) {
 216         const int index = it.next();
 217         const KFileItem item = fileItem(index);
 218         if (!item.isNull()) {
 219             urls << item.url();
 220
 221             bool isLocal;
 222             mostLocalUrls << item.mostLocalUrl(isLocal);
 223             if (!isLocal) {
 224                 canUseMostLocalUrls = false;
 225             }
 226         }
 227     }
 228
 229     const bool different = canUseMostLocalUrls && mostLocalUrls != urls;
 230     urls = KDirModel::simplifiedUrlList(urls); // TODO: Check if we still need KDirModel for this in KDE 5.0
 231     if (different) {
 232         mostLocalUrls = KDirModel::simplifiedUrlList(mostLocalUrls);
 233         urls.populateMimeData(mostLocalUrls, data);
 234     } else {
 235         urls.populateMimeData(data);
 236     }
 237
 238     return data;
 239 }
 240
 241 int KFileItemModel::indexForKeyboardSearch(const QString& text, int startFromIndex) const
 242 {
 243     startFromIndex = qMax(0, startFromIndex);
 244     for (int i = startFromIndex; i < count(); ++i) {
 245         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 246             return i;
 247         }
 248     }
 249     for (int i = 0; i < startFromIndex; ++i) {
 250         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 251             return i;
 252         }
 253     }
 254     return -1;
 255 }
 256
 257 bool KFileItemModel::supportsDropping(int index) const
 258 {
 259     const KFileItem item = fileItem(index);
 260     return item.isNull() ? false : item.isDir();
 261 }
 262
 263 QString KFileItemModel::roleDescription(const QByteArray& role) const
 264 {
 265     QString descr;
 266
 267     switch (roleIndex(role)) {
 268     case NameRole:           descr = i18nc("@item:intable", "Name"); break;
 269     case SizeRole:           descr = i18nc("@item:intable", "Size"); break;
 270     case DateRole:           descr = i18nc("@item:intable", "Date"); break;
 271     case PermissionsRole:    descr = i18nc("@item:intable", "Permissions"); break;
 272     case OwnerRole:          descr = i18nc("@item:intable", "Owner"); break;
 273     case GroupRole:          descr = i18nc("@item:intable", "Group"); break;
 274     case TypeRole:           descr = i18nc("@item:intable", "Type"); break;
 275     case DestinationRole:    descr = i18nc("@item:intable", "Destination"); break;
 276     case PathRole:           descr = i18nc("@item:intable", "Path"); break;
 277     case CommentRole:        descr = i18nc("@item:intable", "Comment"); break;
 278     case TagsRole:           descr = i18nc("@item:intable", "Tags"); break;
 279     case RatingRole:         descr = i18nc("@item:intable", "Rating"); break;
 280     case NoRole:             break;
 281     case IsDirRole:          break;
 282     case IsExpandedRole:     break;
 283     case ExpansionLevelRole: break;
 284     default:                 Q_ASSERT(false); break;
 285     }
 286
 287     return descr;
 288 }
 289
 290 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 291 {
 292     if (!m_itemData.isEmpty() && m_groups.isEmpty()) {
 293 #ifdef KFILEITEMMODEL_DEBUG
 294         QElapsedTimer timer;
 295         timer.start();
 296 #endif
 297         switch (roleIndex(sortRole())) {
 298         case NameRole:           m_groups = nameRoleGroups(); break;
 299         case SizeRole:           m_groups = sizeRoleGroups(); break;
 300         case DateRole:           m_groups = dateRoleGroups(); break;
 301         case PermissionsRole:    m_groups = permissionRoleGroups(); break;
 302         case OwnerRole:          m_groups = genericStringRoleGroups("owner"); break;
 303         case GroupRole:          m_groups = genericStringRoleGroups("group"); break;
 304         case TypeRole:           m_groups = genericStringRoleGroups("type"); break;
 305         case DestinationRole:    m_groups = genericStringRoleGroups("destination"); break;
 306         case PathRole:           m_groups = genericStringRoleGroups("path"); break;
 307         case CommentRole:        m_groups = genericStringRoleGroups("comment"); break;
 308         case TagsRole:           m_groups = genericStringRoleGroups("tags"); break;
 309         case RatingRole:         m_groups = ratingRoleGroups(); break;
 310         case NoRole:             break;
 311         case IsDirRole:          break;
 312         case IsExpandedRole:     break;
 313         case ExpansionLevelRole: break;
 314         default:                 Q_ASSERT(false); break;
 315         }
 316
 317 #ifdef KFILEITEMMODEL_DEBUG
 318         kDebug() << "[TIME] Calculating groups for" << count() << "items:" << timer.elapsed();
 319 #endif
 320     }
 321
 322     return m_groups;
 323 }
 324
 325 KFileItem KFileItemModel::fileItem(int index) const
 326 {
 327     if (index >= 0 && index < count()) {
 328         return m_itemData.at(index)->item;
 329     }
 330
 331     return KFileItem();
 332 }
 333
 334 KFileItem KFileItemModel::fileItem(const KUrl& url) const
 335 {
 336     const int index = m_items.value(url, -1);
 337     if (index >= 0) {
 338         return m_itemData.at(index)->item;
 339     }
 340     return KFileItem();
 341 }
 342
 343 int KFileItemModel::index(const KFileItem& item) const
 344 {
 345     if (item.isNull()) {
 346         return -1;
 347     }
 348
 349     return m_items.value(item.url(), -1);
 350 }
 351
 352 int KFileItemModel::index(const KUrl& url) const
 353 {
 354     KUrl urlToFind = url;
 355     urlToFind.adjustPath(KUrl::RemoveTrailingSlash);
 356     return m_items.value(urlToFind, -1);
 357 }
 358
 359 KFileItem KFileItemModel::rootItem() const
 360 {
 361     const KDirLister* dirLister = m_dirLister.data();
 362     if (dirLister) {
 363         return dirLister->rootItem();
 364     }
 365     return KFileItem();
 366 }
 367
 368 void KFileItemModel::clear()
 369 {
 370     slotClear();
 371 }
 372
 373 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 374 {
 375     m_roles = roles;
 376
 377     if (count() > 0) {
 378         const bool supportedExpanding = m_requestRole[ExpansionLevelRole];
 379         const bool willSupportExpanding = roles.contains("expansionLevel");
 380         if (supportedExpanding && !willSupportExpanding) {
 381             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 382             // that is not 0 (and hence are part of an expanded item).
 383             removeExpandedItems();
 384         }
 385     }
 386
 387     m_groups.clear();
 388     resetRoles();
 389
 390     QSetIterator<QByteArray> it(roles);
 391     while (it.hasNext()) {
 392         const QByteArray& role = it.next();
 393         m_requestRole[roleIndex(role)] = true;
 394     }
 395
 396     if (count() > 0) {
 397         // Update m_data with the changed requested roles
 398         const int maxIndex = count() - 1;
 399         for (int i = 0; i <= maxIndex; ++i) {
 400             m_itemData[i]->values = retrieveData(m_itemData.at(i)->item);
 401         }
 402
 403         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 404         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 405     }
 406 }
 407
 408 QSet<QByteArray> KFileItemModel::roles() const
 409 {
 410     return m_roles;
 411 }
 412
 413 bool KFileItemModel::setExpanded(int index, bool expanded)
 414 {
 415     if (!isExpandable(index) || isExpanded(index) == expanded) {
 416         return false;
 417     }
 418
 419     QHash<QByteArray, QVariant> values;
 420     values.insert("isExpanded", expanded);
 421     if (!setData(index, values)) {
 422         return false;
 423     }
 424
 425     KDirLister* dirLister = m_dirLister.data();
 426     const KUrl url = m_itemData.at(index)->item.url();
 427     if (expanded) {
 428         m_expandedUrls.insert(url);
 429
 430         if (dirLister) {
 431             dirLister->openUrl(url, KDirLister::Keep);
 432             return true;
 433         }
 434     } else {
 435         m_expandedUrls.remove(url);
 436
 437         if (dirLister) {
 438             dirLister->stop(url);
 439         }
 440
 441         KFileItemList itemsToRemove;
 442         const int expansionLevel = data(index)["expansionLevel"].toInt();
 443         ++index;
 444         while (index < count() && data(index)["expansionLevel"].toInt() > expansionLevel) {
 445             itemsToRemove.append(m_itemData.at(index)->item);
 446             ++index;
 447         }
 448         removeItems(itemsToRemove);
 449         return true;
 450     }
 451
 452     return false;
 453 }
 454
 455 bool KFileItemModel::isExpanded(int index) const
 456 {
 457     if (index >= 0 && index < count()) {
 458         return m_itemData.at(index)->values.value("isExpanded").toBool();
 459     }
 460     return false;
 461 }
 462
 463 bool KFileItemModel::isExpandable(int index) const
 464 {
 465     if (index >= 0 && index < count()) {
 466         return m_itemData.at(index)->values.value("isExpandable").toBool();
 467     }
 468     return false;
 469 }
 470
 471 QSet<KUrl> KFileItemModel::expandedUrls() const
 472 {
 473     return m_expandedUrls;
 474 }
 475
 476 void KFileItemModel::restoreExpandedUrls(const QSet<KUrl>& urls)
 477 {
 478     m_urlsToExpand = urls;
 479 }
 480
 481 void KFileItemModel::setExpanded(const QSet<KUrl>& urls)
 482 {
 483     const KDirLister* dirLister = m_dirLister.data();
 484     if (!dirLister) {
 485         return;
 486     }
 487
 488     const int pos = dirLister->url().path().length();
 489
 490     // Assure that each sub-path of the URLs that should be
 491     // expanded is added to m_urlsToExpand too. KDirLister
 492     // does not care whether the parent-URL has already been
 493     // expanded.
 494     QSetIterator<KUrl> it1(urls);
 495     while (it1.hasNext()) {
 496         const KUrl& url = it1.next();
 497
 498         KUrl urlToExpand = dirLister->url();
 499         const QStringList subDirs = url.path().mid(pos).split(QDir::separator());
 500         for (int i = 0; i < subDirs.count(); ++i) {
 501             urlToExpand.addPath(subDirs.at(i));
 502             m_urlsToExpand.insert(urlToExpand);
 503         }
 504     }
 505
 506     // KDirLister::open() must called at least once to trigger an initial
 507     // loading. The pending URLs that must be restored are handled
 508     // in slotCompleted().
 509     QSetIterator<KUrl> it2(m_urlsToExpand);
 510     while (it2.hasNext()) {
 511         const int idx = index(it2.next());
 512         if (idx >= 0 && !isExpanded(idx)) {
 513             setExpanded(idx, true);
 514             break;
 515         }
 516     }
 517 }
 518
 519 void KFileItemModel::setNameFilter(const QString& nameFilter)
 520 {
 521     if (m_filter.pattern() != nameFilter) {
 522         dispatchPendingItemsToInsert();
 523
 524         m_filter.setPattern(nameFilter);
 525
 526         // Check which shown items from m_itemData must get
 527         // hidden and hence moved to m_filteredItems.
 528         KFileItemList newFilteredItems;
 529
 530         foreach (ItemData* itemData, m_itemData) {
 531             if (!m_filter.matches(itemData->item)) {
 532                 // Only filter non-expanded items as child items may never
 533                 // exist without a parent item
 534                 if (!itemData->values.value("isExpanded").toBool()) {
 535                     newFilteredItems.append(itemData->item);
 536                     m_filteredItems.insert(itemData->item);
 537                 }
 538             }
 539         }
 540
 541         removeItems(newFilteredItems);
 542
 543         // Check which hidden items from m_filteredItems should
 544         // get visible again and hence removed from m_filteredItems.
 545         KFileItemList newVisibleItems;
 546
 547         QMutableSetIterator<KFileItem> it(m_filteredItems);
 548         while (it.hasNext()) {
 549             const KFileItem item = it.next();
 550             if (m_filter.matches(item)) {
 551                 newVisibleItems.append(item);
 552                 m_filteredItems.remove(item);
 553             }
 554         }
 555
 556         insertItems(newVisibleItems);
 557     }
 558 }
 559
 560 QString KFileItemModel::nameFilter() const
 561 {
 562     return m_filter.pattern();
 563 }
 564
 565 void KFileItemModel::onGroupedSortingChanged(bool current)
 566 {
 567     Q_UNUSED(current);
 568     m_groups.clear();
 569 }
 570
 571 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 572 {
 573     Q_UNUSED(previous);
 574     m_sortRole = roleIndex(current);
 575
 576 #ifdef KFILEITEMMODEL_DEBUG
 577     if (!m_requestRole[m_sortRole]) {
 578         kWarning() << "The sort-role has been changed to a role that has not been received yet";
 579     }
 580 #endif
 581
 582     resortAllItems();
 583 }
 584
 585 void KFileItemModel::onSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous)
 586 {
 587     Q_UNUSED(current);
 588     Q_UNUSED(previous);
 589     resortAllItems();
 590 }
 591
 592 void KFileItemModel::resortAllItems()
 593 {
 594     m_resortAllItemsTimer->stop();
 595
 596     const int itemCount = count();
 597     if (itemCount <= 0) {
 598         return;
 599     }
 600
 601 #ifdef KFILEITEMMODEL_DEBUG
 602     QElapsedTimer timer;
 603     timer.start();
 604     kDebug() << "===========================================================";
 605     kDebug() << "Resorting" << itemCount << "items";
 606 #endif
 607
 608     // Remember the order of the current URLs so
 609     // that it can be determined which indexes have
 610     // been moved because of the resorting.
 611     QList<KUrl> oldUrls;
 612     oldUrls.reserve(itemCount);
 613     foreach (const ItemData* itemData, m_itemData) {
 614         oldUrls.append(itemData->item.url());
 615     }
 616
 617     m_groups.clear();
 618     m_items.clear();
 619
 620     // Resort the items
 621     sort(m_itemData.begin(), m_itemData.end());
 622     for (int i = 0; i < itemCount; ++i) {
 623         m_items.insert(m_itemData.at(i)->item.url(), i);
 624     }
 625
 626     // Determine the indexes that have been moved
 627     QList<int> movedToIndexes;
 628     movedToIndexes.reserve(itemCount);
 629     for (int i = 0; i < itemCount; i++) {
 630         const int newIndex = m_items.value(oldUrls.at(i).url());
 631         movedToIndexes.append(newIndex);
 632     }
 633
 634     // Don't check whether items have really been moved and always emit a
 635     // itemsMoved() signal after resorting: In case of grouped items
 636     // the groups might change even if the items themselves don't change their
 637     // position. Let the receiver of the signal decide whether a check for moved
 638     // items makes sense.
 639     emit itemsMoved(KItemRange(0, itemCount), movedToIndexes);
 640
 641 #ifdef KFILEITEMMODEL_DEBUG
 642     kDebug() << "[TIME] Resorting of" << itemCount << "items:" << timer.elapsed();
 643 #endif
 644 }
 645
 646 void KFileItemModel::slotCompleted()
 647 {
 648     if (m_urlsToExpand.isEmpty() && m_minimumUpdateIntervalTimer->isActive()) {
 649         // dispatchPendingItems() will be called when the timer
 650         // has been expired.
 651         m_pendingEmitLoadingCompleted = true;
 652         return;
 653     }
 654
 655     m_pendingEmitLoadingCompleted = false;
 656     dispatchPendingItemsToInsert();
 657
 658     if (!m_urlsToExpand.isEmpty()) {
 659         // Try to find a URL that can be expanded.
 660         // Note that the parent folder must be expanded before any of its subfolders become visible.
 661         // Therefore, some URLs in m_restoredExpandedUrls might not be visible yet
 662         // -> we expand the first visible URL we find in m_restoredExpandedUrls.
 663         foreach(const KUrl& url, m_urlsToExpand) {
 664             const int index = m_items.value(url, -1);
 665             if (index >= 0) {
 666                 m_urlsToExpand.remove(url);
 667                 if (setExpanded(index, true)) {
 668                     // The dir lister has been triggered. This slot will be called
 669                     // again after the directory has been expanded.
 670                     return;
 671                 }
 672             }
 673         }
 674
 675         // None of the URLs in m_restoredExpandedUrls could be found in the model. This can happen
 676         // if these URLs have been deleted in the meantime.
 677         m_urlsToExpand.clear();
 678     }
 679
 680     emit loadingCompleted();
 681     m_minimumUpdateIntervalTimer->start();
 682 }
 683
 684 void KFileItemModel::slotCanceled()
 685 {
 686     m_minimumUpdateIntervalTimer->stop();
 687     m_maximumUpdateIntervalTimer->stop();
 688     dispatchPendingItemsToInsert();
 689 }
 690
 691 void KFileItemModel::slotNewItems(const KFileItemList& items)
 692 {
 693     Q_ASSERT(!items.isEmpty());
 694
 695     if (m_requestRole[ExpansionLevelRole] && m_rootExpansionLevel >= 0) {
 696         // To be able to compare whether the new items may be inserted as children
 697         // of a parent item the pending items must be added to the model first.
 698         dispatchPendingItemsToInsert();
 699
 700         KFileItem item = items.first();
 701
 702         // If the expanding of items is enabled, the call
 703         // dirLister->openUrl(url, KDirLister::Keep) in KFileItemModel::setExpanded()
 704         // might result in emitting the same items twice due to the Keep-parameter.
 705         // This case happens if an item gets expanded, collapsed and expanded again
 706         // before the items could be loaded for the first expansion.
 707         const int index = m_items.value(item.url(), -1);
 708         if (index >= 0) {
 709             // The items are already part of the model.
 710             return;
 711         }
 712
 713         // KDirLister keeps the children of items that got expanded once even if
 714         // they got collapsed again with KFileItemModel::setExpanded(false). So it must be
 715         // checked whether the parent for new items is still expanded.
 716         KUrl parentUrl = item.url().upUrl();
 717         parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
 718         const int parentIndex = m_items.value(parentUrl, -1);
 719         if (parentIndex >= 0 && !m_itemData[parentIndex]->values.value("isExpanded").toBool()) {
 720             // The parent is not expanded.
 721             return;
 722         }
 723     }
 724
 725     if (m_filter.pattern().isEmpty()) {
 726         m_pendingItemsToInsert.append(items);
 727     } else {
 728         // The name-filter is active. Hide filtered items
 729         // before inserting them into the model and remember
 730         // the filtered items in m_filteredItems.
 731         KFileItemList filteredItems;
 732         foreach (const KFileItem& item, items) {
 733             if (m_filter.matches(item)) {
 734                 filteredItems.append(item);
 735             } else {
 736                 m_filteredItems.insert(item);
 737             }
 738         }
 739
 740         m_pendingItemsToInsert.append(filteredItems);
 741     }
 742
 743     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 744         // Assure that items get dispatched if no completed() or canceled() signal is
 745         // emitted during the maximum update interval.
 746         m_maximumUpdateIntervalTimer->start();
 747     }
 748 }
 749
 750 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 751 {
 752     dispatchPendingItemsToInsert();
 753
 754     KFileItemList itemsToRemove = items;
 755     if (m_requestRole[ExpansionLevelRole] && m_rootExpansionLevel >= 0) {
 756         // Assure that removing a parent item also results in removing all children
 757         foreach (const KFileItem& item, items) {
 758             itemsToRemove.append(childItems(item));
 759         }
 760     }
 761
 762     if (!m_filteredItems.isEmpty()) {
 763         foreach (const KFileItem& item, itemsToRemove) {
 764             m_filteredItems.remove(item);
 765         }
 766     }
 767
 768     removeItems(itemsToRemove);
 769 }
 770
 771 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 772 {
 773     Q_ASSERT(!items.isEmpty());
 774 #ifdef KFILEITEMMODEL_DEBUG
 775     kDebug() << "Refreshing" << items.count() << "items";
 776 #endif
 777
 778     m_groups.clear();
 779
 780     // Get the indexes of all items that have been refreshed
 781     QList<int> indexes;
 782     indexes.reserve(items.count());
 783
 784     QListIterator<QPair<KFileItem, KFileItem> > it(items);
 785     while (it.hasNext()) {
 786         const QPair<KFileItem, KFileItem>& itemPair = it.next();
 787         const KFileItem& oldItem = itemPair.first;
 788         const KFileItem& newItem = itemPair.second;
 789         const int index = m_items.value(oldItem.url(), -1);
 790         if (index >= 0) {
 791             m_itemData[index]->item = newItem;
 792             m_itemData[index]->values = retrieveData(newItem);
 793             m_items.remove(oldItem.url());
 794             m_items.insert(newItem.url(), index);
 795             indexes.append(index);
 796         }
 797     }
 798
 799     // If the changed items have been created recently, they might not be in m_items yet.
 800     // In that case, the list 'indexes' might be empty.
 801     if (indexes.isEmpty()) {
 802         return;
 803     }
 804
 805     // Extract the item-ranges out of the changed indexes
 806     qSort(indexes);
 807
 808     KItemRangeList itemRangeList;
 809     int previousIndex = indexes.at(0);
 810     int rangeIndex = previousIndex;
 811     int rangeCount = 1;
 812
 813     const int maxIndex = indexes.count() - 1;
 814     for (int i = 1; i <= maxIndex; ++i) {
 815         const int currentIndex = indexes.at(i);
 816         if (currentIndex == previousIndex + 1) {
 817             ++rangeCount;
 818         } else {
 819             itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 820
 821             rangeIndex = currentIndex;
 822             rangeCount = 1;
 823         }
 824         previousIndex = currentIndex;
 825     }
 826
 827     if (rangeCount > 0) {
 828         itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 829     }
 830
 831     emit itemsChanged(itemRangeList, m_roles);
 832
 833     resortAllItems();
 834 }
 835
 836 void KFileItemModel::slotClear()
 837 {
 838 #ifdef KFILEITEMMODEL_DEBUG
 839     kDebug() << "Clearing all items";
 840 #endif
 841
 842     m_filteredItems.clear();
 843     m_groups.clear();
 844
 845     m_minimumUpdateIntervalTimer->stop();
 846     m_maximumUpdateIntervalTimer->stop();
 847     m_resortAllItemsTimer->stop();
 848     m_pendingItemsToInsert.clear();
 849
 850     m_rootExpansionLevel = UninitializedRootExpansionLevel;
 851
 852     const int removedCount = m_itemData.count();
 853     if (removedCount > 0) {
 854         qDeleteAll(m_itemData);
 855         m_itemData.clear();
 856         m_items.clear();
 857         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
 858     }
 859
 860     m_expandedUrls.clear();
 861 }
 862
 863 void KFileItemModel::slotClear(const KUrl& url)
 864 {
 865     Q_UNUSED(url);
 866 }
 867
 868 void KFileItemModel::slotNaturalSortingChanged()
 869 {
 870     m_naturalSorting = KGlobalSettings::naturalSorting();
 871     resortAllItems();
 872 }
 873
 874 void KFileItemModel::dispatchPendingItemsToInsert()
 875 {
 876     if (!m_pendingItemsToInsert.isEmpty()) {
 877         insertItems(m_pendingItemsToInsert);
 878         m_pendingItemsToInsert.clear();
 879     }
 880
 881     if (m_pendingEmitLoadingCompleted) {
 882         emit loadingCompleted();
 883     }
 884 }
 885
 886 void KFileItemModel::insertItems(const KFileItemList& items)
 887 {
 888     if (items.isEmpty()) {
 889         return;
 890     }
 891
 892 #ifdef KFILEITEMMODEL_DEBUG
 893     QElapsedTimer timer;
 894     timer.start();
 895     kDebug() << "===========================================================";
 896     kDebug() << "Inserting" << items.count() << "items";
 897 #endif
 898
 899     m_groups.clear();
 900
 901     QList<ItemData*> sortedItems = createItemDataList(items);
 902     sort(sortedItems.begin(), sortedItems.end());
 903
 904 #ifdef KFILEITEMMODEL_DEBUG
 905     kDebug() << "[TIME] Sorting:" << timer.elapsed();
 906 #endif
 907
 908     KItemRangeList itemRanges;
 909     int targetIndex = 0;
 910     int sourceIndex = 0;
 911     int insertedAtIndex = -1;        // Index for the current item-range
 912     int insertedCount = 0;           // Count for the current item-range
 913     int previouslyInsertedCount = 0; // Sum of previously inserted items for all ranges
 914     while (sourceIndex < sortedItems.count()) {
 915         // Find target index from m_items to insert the current item
 916         // in a sorted order
 917         const int previousTargetIndex = targetIndex;
 918         while (targetIndex < m_itemData.count()) {
 919             if (!lessThan(m_itemData.at(targetIndex), sortedItems.at(sourceIndex))) {
 920                 break;
 921             }
 922             ++targetIndex;
 923         }
 924
 925         if (targetIndex - previousTargetIndex > 0 && insertedAtIndex >= 0) {
 926             itemRanges << KItemRange(insertedAtIndex, insertedCount);
 927             previouslyInsertedCount += insertedCount;
 928             insertedAtIndex = targetIndex - previouslyInsertedCount;
 929             insertedCount = 0;
 930         }
 931
 932         // Insert item at the position targetIndex by transfering
 933         // the ownership of the item-data from sortedItems to m_itemData.
 934         // m_items will be inserted after the loop (see comment below)
 935         m_itemData.insert(targetIndex, sortedItems.at(sourceIndex));
 936         ++insertedCount;
 937
 938         if (insertedAtIndex < 0) {
 939             insertedAtIndex = targetIndex;
 940             Q_ASSERT(previouslyInsertedCount == 0);
 941         }
 942         ++targetIndex;
 943         ++sourceIndex;
 944     }
 945
 946     // The indexes of all m_items must be adjusted, not only the index
 947     // of the new items
 948     const int itemDataCount = m_itemData.count();
 949     for (int i = 0; i < itemDataCount; ++i) {
 950         m_items.insert(m_itemData.at(i)->item.url(), i);
 951     }
 952
 953     itemRanges << KItemRange(insertedAtIndex, insertedCount);
 954     emit itemsInserted(itemRanges);
 955
 956 #ifdef KFILEITEMMODEL_DEBUG
 957     kDebug() << "[TIME] Inserting of" << items.count() << "items:" << timer.elapsed();
 958 #endif
 959 }
 960
 961 void KFileItemModel::removeItems(const KFileItemList& items)
 962 {
 963     if (items.isEmpty()) {
 964         return;
 965     }
 966
 967 #ifdef KFILEITEMMODEL_DEBUG
 968     kDebug() << "Removing " << items.count() << "items";
 969 #endif
 970
 971     m_groups.clear();
 972
 973     QList<ItemData*> sortedItems;
 974     sortedItems.reserve(items.count());
 975     foreach (const KFileItem& item, items) {
 976         const int index = m_items.value(item.url(), -1);
 977         if (index >= 0) {
 978             sortedItems.append(m_itemData.at(index));
 979         }
 980     }
 981     sort(sortedItems.begin(), sortedItems.end());
 982
 983     QList<int> indexesToRemove;
 984     indexesToRemove.reserve(items.count());
 985
 986     // Calculate the item ranges that will get deleted
 987     KItemRangeList itemRanges;
 988     int removedAtIndex = -1;
 989     int removedCount = 0;
 990     int targetIndex = 0;
 991     foreach (const ItemData* itemData, sortedItems) {
 992         const KFileItem& itemToRemove = itemData->item;
 993
 994         const int previousTargetIndex = targetIndex;
 995         while (targetIndex < m_itemData.count()) {
 996             if (m_itemData.at(targetIndex)->item.url() == itemToRemove.url()) {
 997                 break;
 998             }
 999             ++targetIndex;
1000         }
1001         if (targetIndex >= m_itemData.count()) {
1002             kWarning() << "Item that should be deleted has not been found!";
1003             return;
1004         }
1005
1006         if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
1007             itemRanges << KItemRange(removedAtIndex, removedCount);
1008             removedAtIndex = targetIndex;
1009             removedCount = 0;
1010         }
1011
1012         indexesToRemove.append(targetIndex);
1013         if (removedAtIndex < 0) {
1014             removedAtIndex = targetIndex;
1015         }
1016         ++removedCount;
1017         ++targetIndex;
1018     }
1019
1020     // Delete the items
1021     for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
1022         const int indexToRemove = indexesToRemove.at(i);
1023         ItemData* data = m_itemData.at(indexToRemove);
1024
1025         m_items.remove(data->item.url());
1026
1027         delete data;
1028         m_itemData.removeAt(indexToRemove);
1029     }
1030
1031     // The indexes of all m_items must be adjusted, not only the index
1032     // of the removed items
1033     const int itemDataCount = m_itemData.count();
1034     for (int i = 0; i < itemDataCount; ++i) {
1035         m_items.insert(m_itemData.at(i)->item.url(), i);
1036     }
1037
1038     if (count() <= 0) {
1039         m_rootExpansionLevel = UninitializedRootExpansionLevel;
1040     }
1041
1042     itemRanges << KItemRange(removedAtIndex, removedCount);
1043     emit itemsRemoved(itemRanges);
1044 }
1045
1046 QList<KFileItemModel::ItemData*> KFileItemModel::createItemDataList(const KFileItemList& items) const
1047 {
1048     QList<ItemData*> itemDataList;
1049     itemDataList.reserve(items.count());
1050
1051     foreach (const KFileItem& item, items) {
1052         ItemData* itemData = new ItemData();
1053         itemData->item = item;
1054         itemData->values = retrieveData(item);
1055         itemData->parent = 0;
1056
1057         const bool determineParent = m_requestRole[ExpansionLevelRole]
1058                                      && itemData->values["expansionLevel"].toInt() > 0;
1059         if (determineParent) {
1060             KUrl parentUrl = item.url().upUrl();
1061             parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
1062             const int parentIndex = m_items.value(parentUrl, -1);
1063             if (parentIndex >= 0) {
1064                 itemData->parent = m_itemData.at(parentIndex);
1065             } else {
1066                 kWarning() << "Parent item not found for" << item.url();
1067             }
1068         }
1069
1070         itemDataList.append(itemData);
1071     }
1072
1073     return itemDataList;
1074 }
1075
1076 void KFileItemModel::removeExpandedItems()
1077 {
1078     KFileItemList expandedItems;
1079
1080     const int maxIndex = m_itemData.count() - 1;
1081     for (int i = 0; i <= maxIndex; ++i) {
1082         const ItemData* itemData = m_itemData.at(i);
1083         if (itemData->values.value("expansionLevel").toInt() > 0) {
1084             expandedItems.append(itemData->item);
1085         }
1086     }
1087
1088     // The m_rootExpansionLevel may not get reset before all items with
1089     // a bigger expansionLevel have been removed.
1090     Q_ASSERT(m_rootExpansionLevel >= 0);
1091     removeItems(expandedItems);
1092
1093     m_rootExpansionLevel = UninitializedRootExpansionLevel;
1094     m_expandedUrls.clear();
1095 }
1096
1097 void KFileItemModel::resetRoles()
1098 {
1099     for (int i = 0; i < RolesCount; ++i) {
1100         m_requestRole[i] = false;
1101     }
1102 }
1103
1104 KFileItemModel::Role KFileItemModel::roleIndex(const QByteArray& role) const
1105 {
1106     static QHash<QByteArray, Role> rolesHash;
1107     if (rolesHash.isEmpty()) {
1108         rolesHash.insert("name", NameRole);
1109         rolesHash.insert("size", SizeRole);
1110         rolesHash.insert("date", DateRole);
1111         rolesHash.insert("permissions", PermissionsRole);
1112         rolesHash.insert("owner", OwnerRole);
1113         rolesHash.insert("group", GroupRole);
1114         rolesHash.insert("type", TypeRole);
1115         rolesHash.insert("destination", DestinationRole);
1116         rolesHash.insert("path", PathRole);
1117         rolesHash.insert("comment", CommentRole);
1118         rolesHash.insert("tags", TagsRole);
1119         rolesHash.insert("rating", RatingRole);
1120         rolesHash.insert("isDir", IsDirRole);
1121         rolesHash.insert("isExpanded", IsExpandedRole);
1122         rolesHash.insert("isExpandable", IsExpandableRole);
1123         rolesHash.insert("expansionLevel", ExpansionLevelRole);
1124     }
1125     return rolesHash.value(role, NoRole);
1126 }
1127
1128 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item) const
1129 {
1130     // It is important to insert only roles that are fast to retrieve. E.g.
1131     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
1132     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
1133     QHash<QByteArray, QVariant> data;
1134     data.insert("iconPixmap", QPixmap());
1135     data.insert("url", item.url());
1136
1137     const bool isDir = item.isDir();
1138     if (m_requestRole[IsDirRole]) {
1139         data.insert("isDir", isDir);
1140     }
1141
1142     if (m_requestRole[NameRole]) {
1143         data.insert("name", item.text());
1144     }
1145
1146     if (m_requestRole[SizeRole]) {
1147         if (isDir) {
1148             data.insert("size", QVariant());
1149         } else {
1150             data.insert("size", item.size());
1151         }
1152     }
1153
1154     if (m_requestRole[DateRole]) {
1155         // Don't use KFileItem::timeString() as this is too expensive when
1156         // having several thousands of items. Instead the formatting of the
1157         // date-time will be done on-demand by the view when the date will be shown.
1158         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
1159         data.insert("date", dateTime.dateTime());
1160     }
1161
1162     if (m_requestRole[PermissionsRole]) {
1163         data.insert("permissions", item.permissionsString());
1164     }
1165
1166     if (m_requestRole[OwnerRole]) {
1167         data.insert("owner", item.user());
1168     }
1169
1170     if (m_requestRole[GroupRole]) {
1171         data.insert("group", item.group());
1172     }
1173
1174     if (m_requestRole[DestinationRole]) {
1175         QString destination = item.linkDest();
1176         if (destination.isEmpty()) {
1177             destination = i18nc("@item:intable", "No destination");
1178         }
1179         data.insert("destination", destination);
1180     }
1181
1182     if (m_requestRole[PathRole]) {
1183         QString path;
1184         if (item.url().protocol() == QLatin1String("trash")) {
1185             path = item.entry().stringValue(KIO::UDSEntry::UDS_EXTRA);
1186         } else {
1187             path = item.localPath();
1188         }
1189
1190         const int index = path.lastIndexOf(item.text());
1191         path = path.mid(0, index - 1);
1192         data.insert("path", path);
1193     }
1194
1195     if (m_requestRole[IsExpandedRole]) {
1196         data.insert("isExpanded", false);
1197     }
1198
1199     if (m_requestRole[IsExpandableRole]) {
1200         data.insert("isExpandable", item.isDir() && item.url() == item.targetUrl());
1201     }
1202
1203     if (m_requestRole[ExpansionLevelRole]) {
1204         if (m_rootExpansionLevel == UninitializedRootExpansionLevel && m_dirLister.data()) {
1205             const KUrl rootUrl = m_dirLister.data()->url();
1206             const QString protocol = rootUrl.protocol();
1207             const bool forceRootExpansionLevel = (protocol == QLatin1String("trash") ||
1208                                                   protocol == QLatin1String("nepomuk") ||
1209                                                   protocol == QLatin1String("remote") ||
1210                                                   protocol.contains(QLatin1String("search")));
1211             if (forceRootExpansionLevel) {
1212                 m_rootExpansionLevel = ForceRootExpansionLevel;
1213             } else {
1214                 const QString rootDir = rootUrl.path(KUrl::AddTrailingSlash);
1215                 m_rootExpansionLevel = rootDir.count('/');
1216             }
1217         }
1218
1219         if (m_rootExpansionLevel == ForceRootExpansionLevel) {
1220             data.insert("expansionLevel", -1);
1221         } else {
1222             const QString dir = item.url().directory(KUrl::AppendTrailingSlash);
1223             const int level = dir.count('/') - m_rootExpansionLevel;
1224             data.insert("expansionLevel", level);
1225         }
1226     }
1227
1228     if (item.isMimeTypeKnown()) {
1229         data.insert("iconName", item.iconName());
1230
1231         if (m_requestRole[TypeRole]) {
1232             data.insert("type", item.mimeComment());
1233         }
1234     }
1235
1236     return data;
1237 }
1238
1239 bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const
1240 {
1241     int result = 0;
1242
1243     if (m_rootExpansionLevel >= 0) {
1244         result = expansionLevelsCompare(a, b);
1245         if (result != 0) {
1246             // The items have parents with different expansion levels
1247             return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
1248         }
1249     }
1250
1251     if (m_sortFoldersFirst || m_sortRole == SizeRole) {
1252         const bool isDirA = a->item.isDir();
1253         const bool isDirB = b->item.isDir();
1254         if (isDirA && !isDirB) {
1255             return true;
1256         } else if (!isDirA && isDirB) {
1257             return false;
1258         }
1259     }
1260
1261     result = sortRoleCompare(a, b);
1262
1263     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
1264 }
1265
1266 int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
1267 {
1268     const KFileItem& itemA = a->item;
1269     const KFileItem& itemB = b->item;
1270
1271     int result = 0;
1272
1273     switch (m_sortRole) {
1274     case NameRole:
1275         // The name role is handled as default fallback after the switch
1276         break;
1277
1278     case DateRole: {
1279         const KDateTime dateTimeA = itemA.time(KFileItem::ModificationTime);
1280         const KDateTime dateTimeB = itemB.time(KFileItem::ModificationTime);
1281         if (dateTimeA < dateTimeB) {
1282             result = -1;
1283         } else if (dateTimeA > dateTimeB) {
1284             result = +1;
1285         }
1286         break;
1287     }
1288
1289     case SizeRole: {
1290         if (itemA.isDir()) {
1291             Q_ASSERT(itemB.isDir()); // see "if (m_sortFoldersFirst || m_sortRole == SizeRole)" above
1292
1293             const QVariant valueA = a->values.value("size");
1294             const QVariant valueB = b->values.value("size");
1295
1296             if (valueA.isNull()) {
1297                 result = -1;
1298             } else if (valueB.isNull()) {
1299                 result = +1;
1300             } else {
1301                 result = valueA.value<KIO::filesize_t>() - valueB.value<KIO::filesize_t>();
1302             }
1303         } else {
1304             Q_ASSERT(!itemB.isDir()); // see "if (m_sortFoldersFirst || m_sortRole == SizeRole)" above
1305             result = itemA.size() - itemB.size();
1306         }
1307         break;
1308     }
1309
1310     case TypeRole: {
1311         result = QString::compare(a->values.value("type").toString(),
1312                                   b->values.value("type").toString());
1313         break;
1314     }
1315
1316     case CommentRole: {
1317         result = QString::compare(a->values.value("comment").toString(),
1318                                   b->values.value("comment").toString());
1319         break;
1320     }
1321
1322     case TagsRole: {
1323         result = QString::compare(a->values.value("tags").toString(),
1324                                   b->values.value("tags").toString());
1325         break;
1326     }
1327
1328     case RatingRole: {
1329         result = a->values.value("rating").toInt() - b->values.value("rating").toInt();
1330         break;
1331     }
1332
1333     default:
1334         break;
1335     }
1336
1337     if (result != 0) {
1338         // The current sort role was sufficient to define an order
1339         return result;
1340     }
1341
1342     // Fallback #1: Compare the text of the items
1343     result = stringCompare(itemA.text(), itemB.text());
1344     if (result != 0) {
1345         return result;
1346     }
1347
1348     // Fallback #2: KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
1349     result = stringCompare(itemA.name(m_caseSensitivity == Qt::CaseInsensitive),
1350                            itemB.name(m_caseSensitivity == Qt::CaseInsensitive));
1351     if (result != 0) {
1352         return result;
1353     }
1354
1355     // Fallback #3: It must be assured that the sort order is always unique even if two values have been
1356     // equal. In this case a comparison of the URL is done which is unique in all cases
1357     // within KDirLister.
1358     return QString::compare(itemA.url().url(), itemB.url().url(), Qt::CaseSensitive);
1359 }
1360
1361 void KFileItemModel::sort(QList<ItemData*>::iterator begin,
1362                           QList<ItemData*>::iterator end)
1363 {
1364     // The implementation is based on qStableSortHelper() from qalgorithms.h
1365     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1366     // In opposite to qStableSort() it allows to use a member-function for the comparison of elements.
1367
1368     const int span = end - begin;
1369     if (span < 2) {
1370         return;
1371     }
1372
1373     const QList<ItemData*>::iterator middle = begin + span / 2;
1374     sort(begin, middle);
1375     sort(middle, end);
1376     merge(begin, middle, end);
1377 }
1378
1379 void KFileItemModel::merge(QList<ItemData*>::iterator begin,
1380                            QList<ItemData*>::iterator pivot,
1381                            QList<ItemData*>::iterator end)
1382 {
1383     // The implementation is based on qMerge() from qalgorithms.h
1384     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1385
1386     const int len1 = pivot - begin;
1387     const int len2 = end - pivot;
1388
1389     if (len1 == 0 || len2 == 0) {
1390         return;
1391     }
1392
1393     if (len1 + len2 == 2) {
1394         if (lessThan(*(begin + 1), *(begin))) {
1395             qSwap(*begin, *(begin + 1));
1396         }
1397         return;
1398     }
1399
1400     QList<ItemData*>::iterator firstCut;
1401     QList<ItemData*>::iterator secondCut;
1402     int len2Half;
1403     if (len1 > len2) {
1404         const int len1Half = len1 / 2;
1405         firstCut = begin + len1Half;
1406         secondCut = lowerBound(pivot, end, *firstCut);
1407         len2Half = secondCut - pivot;
1408     } else {
1409         len2Half = len2 / 2;
1410         secondCut = pivot + len2Half;
1411         firstCut = upperBound(begin, pivot, *secondCut);
1412     }
1413
1414     reverse(firstCut, pivot);
1415     reverse(pivot, secondCut);
1416     reverse(firstCut, secondCut);
1417
1418     const QList<ItemData*>::iterator newPivot = firstCut + len2Half;
1419     merge(begin, firstCut, newPivot);
1420     merge(newPivot, secondCut, end);
1421 }
1422
1423 QList<KFileItemModel::ItemData*>::iterator KFileItemModel::lowerBound(QList<ItemData*>::iterator begin,
1424                                                                       QList<ItemData*>::iterator end,
1425                                                                       const ItemData* value)
1426 {
1427     // The implementation is based on qLowerBound() from qalgorithms.h
1428     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1429
1430     QList<ItemData*>::iterator middle;
1431     int n = int(end - begin);
1432     int half;
1433
1434     while (n > 0) {
1435         half = n >> 1;
1436         middle = begin + half;
1437         if (lessThan(*middle, value)) {
1438             begin = middle + 1;
1439             n -= half + 1;
1440         } else {
1441             n = half;
1442         }
1443     }
1444     return begin;
1445 }
1446
1447 QList<KFileItemModel::ItemData*>::iterator KFileItemModel::upperBound(QList<ItemData*>::iterator begin,
1448                                                                       QList<ItemData*>::iterator end,
1449                                                                       const ItemData* value)
1450 {
1451     // The implementation is based on qUpperBound() from qalgorithms.h
1452     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1453
1454     QList<ItemData*>::iterator middle;
1455     int n = end - begin;
1456     int half;
1457
1458     while (n > 0) {
1459         half = n >> 1;
1460         middle = begin + half;
1461         if (lessThan(value, *middle)) {
1462             n = half;
1463         } else {
1464             begin = middle + 1;
1465             n -= half + 1;
1466         }
1467     }
1468     return begin;
1469 }
1470
1471 void KFileItemModel::reverse(QList<ItemData*>::iterator begin,
1472                              QList<ItemData*>::iterator end)
1473 {
1474     // The implementation is based on qReverse() from qalgorithms.h
1475     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
1476
1477     --end;
1478     while (begin < end) {
1479         qSwap(*begin++, *end--);
1480     }
1481 }
1482
1483 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
1484 {
1485     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
1486     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
1487     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
1488     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
1489
1490     if (m_caseSensitivity == Qt::CaseInsensitive) {
1491         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
1492                                             : QString::compare(a, b, Qt::CaseInsensitive);
1493         if (result != 0) {
1494             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
1495             // comparison, still a deterministic sort order is required. A case sensitive
1496             // comparison is done as fallback.
1497             return result;
1498         }
1499     }
1500
1501     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
1502                             : QString::compare(a, b, Qt::CaseSensitive);
1503 }
1504
1505 int KFileItemModel::expansionLevelsCompare(const ItemData* a, const ItemData* b) const
1506 {
1507     const KUrl urlA = a->item.url();
1508     const KUrl urlB = b->item.url();
1509     if (urlA.directory() == urlB.directory()) {
1510         // Both items have the same directory as parent
1511         return 0;
1512     }
1513
1514     // Check whether one item is the parent of the other item
1515     if (urlA.isParentOf(urlB)) {
1516         return (sortOrder() == Qt::AscendingOrder) ? -1 : +1;
1517     } else if (urlB.isParentOf(urlA)) {
1518         return (sortOrder() == Qt::AscendingOrder) ? +1 : -1;
1519     }
1520
1521     // Determine the maximum common path of both items and
1522     // remember the index in 'index'
1523     const QString pathA = urlA.path();
1524     const QString pathB = urlB.path();
1525
1526     const int maxIndex = qMin(pathA.length(), pathB.length()) - 1;
1527     int index = 0;
1528     while (index <= maxIndex && pathA.at(index) == pathB.at(index)) {
1529         ++index;
1530     }
1531     if (index > maxIndex) {
1532         index = maxIndex;
1533     }
1534     while ((pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/')) && index > 0) {
1535         --index;
1536     }
1537
1538     // Determine the first sub-path after the common path and
1539     // check whether it represents a directory or already a file
1540     bool isDirA = true;
1541     const QString subPathA = subPath(a->item, pathA, index, &isDirA);
1542     bool isDirB = true;
1543     const QString subPathB = subPath(b->item, pathB, index, &isDirB);
1544
1545     if (isDirA && !isDirB) {
1546         return (sortOrder() == Qt::AscendingOrder) ? -1 : +1;
1547     } else if (!isDirA && isDirB) {
1548         return (sortOrder() == Qt::AscendingOrder) ? +1 : -1;
1549     }
1550
1551     // Compare the items of the parents that represent the first
1552     // different path after the common path.
1553     const QString parentPathA = pathA.left(index) + subPathA;
1554     const QString parentPathB = pathB.left(index) + subPathB;
1555
1556     const ItemData* parentA = a;
1557     while (parentA && parentA->item.url().path() != parentPathA) {
1558         parentA = parentA->parent;
1559     }
1560
1561     const ItemData* parentB = b;
1562     while (parentB && parentB->item.url().path() != parentPathB) {
1563         parentB = parentB->parent;
1564     }
1565
1566     if (parentA && parentB) {
1567         return sortRoleCompare(parentA, parentB);
1568     }
1569
1570     kWarning() << "Child items without parent detected:" << a->item.url() << b->item.url();
1571     return QString::compare(urlA.url(), urlB.url(), Qt::CaseSensitive);
1572 }
1573
1574 QString KFileItemModel::subPath(const KFileItem& item,
1575                                 const QString& itemPath,
1576                                 int start,
1577                                 bool* isDir) const
1578 {
1579     Q_ASSERT(isDir);
1580     const int pathIndex = itemPath.indexOf('/', start + 1);
1581     *isDir = (pathIndex > 0) || item.isDir();
1582     return itemPath.mid(start, pathIndex - start);
1583 }
1584
1585 bool KFileItemModel::useMaximumUpdateInterval() const
1586 {
1587     const KDirLister* dirLister = m_dirLister.data();
1588     return dirLister && !dirLister->url().isLocalFile();
1589 }
1590
1591 QList<QPair<int, QVariant> > KFileItemModel::nameRoleGroups() const
1592 {
1593     Q_ASSERT(!m_itemData.isEmpty());
1594
1595     const int maxIndex = count() - 1;
1596     QList<QPair<int, QVariant> > groups;
1597
1598     QString groupValue;
1599     QChar firstChar;
1600     bool isLetter = false;
1601     for (int i = 0; i <= maxIndex; ++i) {
1602         if (isChildItem(i)) {
1603             continue;
1604         }
1605
1606         const QString name = m_itemData.at(i)->values.value("name").toString();
1607
1608         // Use the first character of the name as group indication
1609         QChar newFirstChar = name.at(0).toUpper();
1610         if (newFirstChar == QLatin1Char('~') && name.length() > 1) {
1611             newFirstChar = name.at(1).toUpper();
1612         }
1613
1614         if (firstChar != newFirstChar) {
1615             QString newGroupValue;
1616             if (newFirstChar >= QLatin1Char('A') && newFirstChar <= QLatin1Char('Z')) {
1617                 // Apply group 'A' - 'Z'
1618                 newGroupValue = newFirstChar;
1619                 isLetter = true;
1620             } else if (newFirstChar >= QLatin1Char('0') && newFirstChar <= QLatin1Char('9')) {
1621                 // Apply group '0 - 9' for any name that starts with a digit
1622                 newGroupValue = i18nc("@title:group Groups that start with a digit", "0 - 9");
1623                 isLetter = false;
1624             } else {
1625                 if (isLetter) {
1626                     // If the current group is 'A' - 'Z' check whether a locale character
1627                     // fits into the existing group.
1628                     // TODO: This does not work in the case if e.g. the group 'O' starts with
1629                     // an umlaut 'O' -> provide unit-test to document this known issue
1630                     const QChar prevChar(firstChar.unicode() - ushort(1));
1631                     const QChar nextChar(firstChar.unicode() + ushort(1));
1632                     const QString currChar(newFirstChar);
1633                     const bool partOfCurrentGroup = currChar.localeAwareCompare(prevChar) > 0 &&
1634                                                     currChar.localeAwareCompare(nextChar) < 0;
1635                     if (partOfCurrentGroup) {
1636                         continue;
1637                     }
1638                 }
1639                 newGroupValue = i18nc("@title:group", "Others");
1640                 isLetter = false;
1641             }
1642
1643             if (newGroupValue != groupValue) {
1644                 groupValue = newGroupValue;
1645                 groups.append(QPair<int, QVariant>(i, newGroupValue));
1646             }
1647
1648             firstChar = newFirstChar;
1649         }
1650     }
1651     return groups;
1652 }
1653
1654 QList<QPair<int, QVariant> > KFileItemModel::sizeRoleGroups() const
1655 {
1656     Q_ASSERT(!m_itemData.isEmpty());
1657
1658     const int maxIndex = count() - 1;
1659     QList<QPair<int, QVariant> > groups;
1660
1661     QString groupValue;
1662     for (int i = 0; i <= maxIndex; ++i) {
1663         if (isChildItem(i)) {
1664             continue;
1665         }
1666
1667         const KFileItem& item = m_itemData.at(i)->item;
1668         const KIO::filesize_t fileSize = !item.isNull() ? item.size() : ~0U;
1669         QString newGroupValue;
1670         if (!item.isNull() && item.isDir()) {
1671             newGroupValue = i18nc("@title:group Size", "Folders");
1672         } else if (fileSize < 5 * 1024 * 1024) {
1673             newGroupValue = i18nc("@title:group Size", "Small");
1674         } else if (fileSize < 10 * 1024 * 1024) {
1675             newGroupValue = i18nc("@title:group Size", "Medium");
1676         } else {
1677             newGroupValue = i18nc("@title:group Size", "Big");
1678         }
1679
1680         if (newGroupValue != groupValue) {
1681             groupValue = newGroupValue;
1682             groups.append(QPair<int, QVariant>(i, newGroupValue));
1683         }
1684     }
1685
1686     return groups;
1687 }
1688
1689 QList<QPair<int, QVariant> > KFileItemModel::dateRoleGroups() const
1690 {
1691     Q_ASSERT(!m_itemData.isEmpty());
1692
1693     const int maxIndex = count() - 1;
1694     QList<QPair<int, QVariant> > groups;
1695
1696     const QDate currentDate = KDateTime::currentLocalDateTime().date();
1697
1698     int yearForCurrentWeek = 0;
1699     int currentWeek = currentDate.weekNumber(&yearForCurrentWeek);
1700     if (yearForCurrentWeek == currentDate.year() + 1) {
1701         currentWeek = 53;
1702     }
1703
1704     QDate previousModifiedDate;
1705     QString groupValue;
1706     for (int i = 0; i <= maxIndex; ++i) {
1707         if (isChildItem(i)) {
1708             continue;
1709         }
1710
1711         const KDateTime modifiedTime = m_itemData.at(i)->item.time(KFileItem::ModificationTime);
1712         const QDate modifiedDate = modifiedTime.date();
1713         if (modifiedDate == previousModifiedDate) {
1714             // The current item is in the same group as the previous item
1715             continue;
1716         }
1717         previousModifiedDate = modifiedDate;
1718
1719         const int daysDistance = modifiedDate.daysTo(currentDate);
1720
1721         int yearForModifiedWeek = 0;
1722         int modifiedWeek = modifiedDate.weekNumber(&yearForModifiedWeek);
1723         if (yearForModifiedWeek == modifiedDate.year() + 1) {
1724             modifiedWeek = 53;
1725         }
1726
1727         QString newGroupValue;
1728         if (currentDate.year() == modifiedDate.year() && currentDate.month() == modifiedDate.month()) {
1729             if (modifiedWeek > currentWeek) {
1730                 // Usecase: modified date = 2010-01-01, current date = 2010-01-22
1731                 //          modified week = 53,         current week = 3
1732                 modifiedWeek = 0;
1733             }
1734             switch (currentWeek - modifiedWeek) {
1735             case 0:
1736                 switch (daysDistance) {
1737                 case 0:  newGroupValue = i18nc("@title:group Date", "Today"); break;
1738                 case 1:  newGroupValue = i18nc("@title:group Date", "Yesterday"); break;
1739                 default: newGroupValue = modifiedTime.toString(i18nc("@title:group The week day name: %A", "%A"));
1740                 }
1741                 break;
1742             case 1:
1743                 newGroupValue = i18nc("@title:group Date", "Last Week");
1744                 break;
1745             case 2:
1746                 newGroupValue = i18nc("@title:group Date", "Two Weeks Ago");
1747                 break;
1748             case 3:
1749                 newGroupValue = i18nc("@title:group Date", "Three Weeks Ago");
1750                 break;
1751             case 4:
1752             case 5:
1753                 newGroupValue = i18nc("@title:group Date", "Earlier this Month");
1754                 break;
1755             default:
1756                 Q_ASSERT(false);
1757             }
1758         } else {
1759             const QDate lastMonthDate = currentDate.addMonths(-1);
1760             if  (lastMonthDate.year() == modifiedDate.year() && lastMonthDate.month() == modifiedDate.month()) {
1761                 if (daysDistance == 1) {
1762                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Yesterday (%B, %Y)"));
1763                 } else if (daysDistance <= 7) {
1764                     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)"));
1765                 } else if (daysDistance <= 7 * 2) {
1766                     newGroupValue = modifiedTime.toString(i18nc("@title:group Date: %B is full month name in current locale, and %Y is full year number", "Last Week (%B, %Y)"));
1767                 } else if (daysDistance <= 7 * 3) {
1768                     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)"));
1769                 } else if (daysDistance <= 7 * 4) {
1770                     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)"));
1771                 } else {
1772                     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"));
1773                 }
1774             } else {
1775                 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"));
1776             }
1777         }
1778
1779         if (newGroupValue != groupValue) {
1780             groupValue = newGroupValue;
1781             groups.append(QPair<int, QVariant>(i, newGroupValue));
1782         }
1783     }
1784
1785     return groups;
1786 }
1787
1788 QList<QPair<int, QVariant> > KFileItemModel::permissionRoleGroups() const
1789 {
1790     Q_ASSERT(!m_itemData.isEmpty());
1791
1792     const int maxIndex = count() - 1;
1793     QList<QPair<int, QVariant> > groups;
1794
1795     QString permissionsString;
1796     QString groupValue;
1797     for (int i = 0; i <= maxIndex; ++i) {
1798         if (isChildItem(i)) {
1799             continue;
1800         }
1801
1802         const ItemData* itemData = m_itemData.at(i);
1803         const QString newPermissionsString = itemData->values.value("permissions").toString();
1804         if (newPermissionsString == permissionsString) {
1805             continue;
1806         }
1807         permissionsString = newPermissionsString;
1808
1809         const QFileInfo info(itemData->item.url().pathOrUrl());
1810
1811         // Set user string
1812         QString user;
1813         if (info.permission(QFile::ReadUser)) {
1814             user = i18nc("@item:intext Access permission, concatenated", "Read, ");
1815         }
1816         if (info.permission(QFile::WriteUser)) {
1817             user += i18nc("@item:intext Access permission, concatenated", "Write, ");
1818         }
1819         if (info.permission(QFile::ExeUser)) {
1820             user += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1821         }
1822         user = user.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : user.mid(0, user.count() - 2);
1823
1824         // Set group string
1825         QString group;
1826         if (info.permission(QFile::ReadGroup)) {
1827             group = i18nc("@item:intext Access permission, concatenated", "Read, ");
1828         }
1829         if (info.permission(QFile::WriteGroup)) {
1830             group += i18nc("@item:intext Access permission, concatenated", "Write, ");
1831         }
1832         if (info.permission(QFile::ExeGroup)) {
1833             group += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1834         }
1835         group = group.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : group.mid(0, group.count() - 2);
1836
1837         // Set others string
1838         QString others;
1839         if (info.permission(QFile::ReadOther)) {
1840             others = i18nc("@item:intext Access permission, concatenated", "Read, ");
1841         }
1842         if (info.permission(QFile::WriteOther)) {
1843             others += i18nc("@item:intext Access permission, concatenated", "Write, ");
1844         }
1845         if (info.permission(QFile::ExeOther)) {
1846             others += i18nc("@item:intext Access permission, concatenated", "Execute, ");
1847         }
1848         others = others.isEmpty() ? i18nc("@item:intext Access permission, concatenated", "Forbidden") : others.mid(0, others.count() - 2);
1849
1850         const QString newGroupValue = i18nc("@title:group Files and folders by permissions", "User: %1 | Group: %2 | Others: %3", user, group, others);
1851         if (newGroupValue != groupValue) {
1852             groupValue = newGroupValue;
1853             groups.append(QPair<int, QVariant>(i, newGroupValue));
1854         }
1855     }
1856
1857     return groups;
1858 }
1859
1860 QList<QPair<int, QVariant> > KFileItemModel::ratingRoleGroups() const
1861 {
1862     Q_ASSERT(!m_itemData.isEmpty());
1863
1864     const int maxIndex = count() - 1;
1865     QList<QPair<int, QVariant> > groups;
1866
1867     int groupValue = -1;
1868     for (int i = 0; i <= maxIndex; ++i) {
1869         if (isChildItem(i)) {
1870             continue;
1871         }
1872         const int newGroupValue = m_itemData.at(i)->values.value("rating", 0).toInt();
1873         if (newGroupValue != groupValue) {
1874             groupValue = newGroupValue;
1875             groups.append(QPair<int, QVariant>(i, newGroupValue));
1876         }
1877     }
1878
1879     return groups;
1880 }
1881
1882 QList<QPair<int, QVariant> > KFileItemModel::genericStringRoleGroups(const QByteArray& role) const
1883 {
1884     Q_ASSERT(!m_itemData.isEmpty());
1885
1886     const int maxIndex = count() - 1;
1887     QList<QPair<int, QVariant> > groups;
1888
1889     bool isFirstGroupValue = true;
1890     QString groupValue;
1891     for (int i = 0; i <= maxIndex; ++i) {
1892         if (isChildItem(i)) {
1893             continue;
1894         }
1895         const QString newGroupValue = m_itemData.at(i)->values.value(role).toString();
1896         if (newGroupValue != groupValue || isFirstGroupValue) {
1897             groupValue = newGroupValue;
1898             groups.append(QPair<int, QVariant>(i, newGroupValue));
1899             isFirstGroupValue = false;
1900         }
1901     }
1902
1903     return groups;
1904 }
1905
1906 KFileItemList KFileItemModel::childItems(const KFileItem& item) const
1907 {
1908     KFileItemList items;
1909
1910     int index = m_items.value(item.url(), -1);
1911     if (index >= 0) {
1912         const int parentLevel = m_itemData.at(index)->values.value("expansionLevel").toInt();
1913         ++index;
1914         while (index < m_itemData.count() && m_itemData.at(index)->values.value("expansionLevel").toInt() > parentLevel) {
1915             items.append(m_itemData.at(index)->item);
1916             ++index;
1917         }
1918     }
1919
1920     return items;
1921 }
1922
1923 #include "kfileitemmodel.moc"