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 <KLocale>
  25 #include <KStringHandler>
  26 #include <KDebug>
  27
  28 #include <QMimeData>
  29 #include <QTimer>
  30
  31 #define KFILEITEMMODEL_DEBUG
  32
  33 KFileItemModel::KFileItemModel(KDirLister* dirLister, QObject* parent) :
  34     KItemModelBase("name", parent),
  35     m_dirLister(dirLister),
  36     m_naturalSorting(true),
  37     m_sortFoldersFirst(true),
  38     m_sortRole(NameRole),
  39     m_caseSensitivity(Qt::CaseInsensitive),
  40     m_sortedItems(),
  41     m_items(),
  42     m_data(),
  43     m_requestRole(),
  44     m_minimumUpdateIntervalTimer(0),
  45     m_maximumUpdateIntervalTimer(0),
  46     m_pendingItemsToInsert(),
  47     m_pendingEmitLoadingCompleted(false),
  48     m_rootExpansionLevel(-1),
  49     m_expandedUrls(),
  50     m_restoredExpandedUrls()
  51 {
  52     resetRoles();
  53     m_requestRole[NameRole] = true;
  54     m_requestRole[IsDirRole] = true;
  55
  56     Q_ASSERT(dirLister);
  57
  58     connect(dirLister, SIGNAL(canceled()), this, SLOT(slotCanceled()));
  59     connect(dirLister, SIGNAL(completed()), this, SLOT(slotCompleted()));
  60     connect(dirLister, SIGNAL(newItems(KFileItemList)), this, SLOT(slotNewItems(KFileItemList)));
  61     connect(dirLister, SIGNAL(itemsDeleted(KFileItemList)), this, SLOT(slotItemsDeleted(KFileItemList)));
  62     connect(dirLister, SIGNAL(refreshItems(QList<QPair<KFileItem,KFileItem> >)), this, SLOT(slotRefreshItems(QList<QPair<KFileItem,KFileItem> >)));
  63     connect(dirLister, SIGNAL(clear()), this, SLOT(slotClear()));
  64     connect(dirLister, SIGNAL(clear(KUrl)), this, SLOT(slotClear(KUrl)));
  65
  66     // Although the layout engine of KItemListView is fast it is very inefficient to e.g.
  67     // emit 50 itemsInserted()-signals each 100 ms. m_minimumUpdateIntervalTimer assures that updates
  68     // are done in 1 second intervals for equal operations.
  69     m_minimumUpdateIntervalTimer = new QTimer(this);
  70     m_minimumUpdateIntervalTimer->setInterval(1000);
  71     m_minimumUpdateIntervalTimer->setSingleShot(true);
  72     connect(m_minimumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  73
  74     // For slow KIO-slaves like used for searching it makes sense to show results periodically even
  75     // before the completed() or canceled() signal has been emitted.
  76     m_maximumUpdateIntervalTimer = new QTimer(this);
  77     m_maximumUpdateIntervalTimer->setInterval(2000);
  78     m_maximumUpdateIntervalTimer->setSingleShot(true);
  79     connect(m_maximumUpdateIntervalTimer, SIGNAL(timeout()), this, SLOT(dispatchPendingItemsToInsert()));
  80
  81     Q_ASSERT(m_minimumUpdateIntervalTimer->interval() <= m_maximumUpdateIntervalTimer->interval());
  82 }
  83
  84 KFileItemModel::~KFileItemModel()
  85 {
  86 }
  87
  88 int KFileItemModel::count() const
  89 {
  90     return m_data.count();
  91 }
  92
  93 QHash<QByteArray, QVariant> KFileItemModel::data(int index) const
  94 {
  95     if (index >= 0 && index < count()) {
  96         return m_data.at(index);
  97     }
  98     return QHash<QByteArray, QVariant>();
  99 }
 100
 101 bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& values)
 102 {
 103     if (index >= 0 && index < count()) {
 104         QHash<QByteArray, QVariant> currentValue = m_data.at(index);
 105
 106         QSet<QByteArray> changedRoles;
 107         QHashIterator<QByteArray, QVariant> it(values);
 108         while (it.hasNext()) {
 109             it.next();
 110             const QByteArray role = it.key();
 111             const QVariant value = it.value();
 112
 113             if (currentValue[role] != value) {
 114                 currentValue[role] = value;
 115                 changedRoles.insert(role);
 116             }
 117         }
 118
 119         if (!changedRoles.isEmpty()) {
 120             m_data[index] = currentValue;
 121             emit itemsChanged(KItemRangeList() << KItemRange(index, 1), changedRoles);
 122         }
 123
 124         return true;
 125     }
 126     return false;
 127 }
 128
 129 void KFileItemModel::setSortFoldersFirst(bool foldersFirst)
 130 {
 131     if (foldersFirst != m_sortFoldersFirst) {
 132         m_sortFoldersFirst = foldersFirst;
 133         resortAllItems();
 134     }
 135 }
 136
 137 bool KFileItemModel::sortFoldersFirst() const
 138 {
 139     return m_sortFoldersFirst;
 140 }
 141
 142 QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
 143 {
 144     QMimeData* data = new QMimeData();
 145
 146     // The following code has been taken from KDirModel::mimeData()
 147     // (kdelibs/kio/kio/kdirmodel.cpp)
 148     // Copyright (C) 2006 David Faure <faure@kde.org>
 149     KUrl::List urls;
 150     KUrl::List mostLocalUrls;
 151     bool canUseMostLocalUrls = true;
 152
 153     QSetIterator<int> it(indexes);
 154     while (it.hasNext()) {
 155         const int index = it.next();
 156         const KFileItem item = fileItem(index);
 157         if (!item.isNull()) {
 158             urls << item.url();
 159
 160             bool isLocal;
 161             mostLocalUrls << item.mostLocalUrl(isLocal);
 162             if (!isLocal) {
 163                 canUseMostLocalUrls = false;
 164             }
 165         }
 166     }
 167
 168     const bool different = canUseMostLocalUrls && mostLocalUrls != urls;
 169     urls = KDirModel::simplifiedUrlList(urls); // TODO: Check if we still need KDirModel for this in KDE 5.0
 170     if (different) {
 171         mostLocalUrls = KDirModel::simplifiedUrlList(mostLocalUrls);
 172         urls.populateMimeData(mostLocalUrls, data);
 173     } else {
 174         urls.populateMimeData(data);
 175     }
 176
 177     return data;
 178 }
 179
 180 int KFileItemModel::indexForKeyboardSearch(const QString& text, int startFromIndex) const
 181 {
 182     startFromIndex = qMax(0, startFromIndex);
 183     for (int i = startFromIndex; i < count(); ++i) {
 184         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 185             return i;
 186         }
 187     }
 188     for (int i = 0; i < startFromIndex; ++i) {
 189         if (data(i)["name"].toString().startsWith(text, Qt::CaseInsensitive)) {
 190             return i;
 191         }
 192     }
 193     return -1;
 194 }
 195
 196 bool KFileItemModel::supportsDropping(int index) const
 197 {
 198     const KFileItem item = fileItem(index);
 199     return item.isNull() ? false : item.isDir();
 200 }
 201
 202 QString KFileItemModel::roleDescription(const QByteArray& role) const
 203 {
 204     QString descr;
 205
 206     switch (roleIndex(role)) {
 207     case NameRole:           descr = i18nc("@item:intable", "Name"); break;
 208     case SizeRole:           descr = i18nc("@item:intable", "Size"); break;
 209     case DateRole:           descr = i18nc("@item:intable", "Date"); break;
 210     case PermissionsRole:    descr = i18nc("@item:intable", "Permissions"); break;
 211     case OwnerRole:          descr = i18nc("@item:intable", "Owner"); break;
 212     case GroupRole:          descr = i18nc("@item:intable", "Group"); break;
 213     case TypeRole:           descr = i18nc("@item:intable", "Type"); break;
 214     case DestinationRole:    descr = i18nc("@item:intable", "Destination"); break;
 215     case PathRole:           descr = i18nc("@item:intable", "Path"); break;
 216     case NoRole:             break;
 217     case IsDirRole:          break;
 218     case IsExpandedRole:     break;
 219     case ExpansionLevelRole: break;
 220     default:                 Q_ASSERT(false); break;
 221     }
 222
 223     return descr;
 224 }
 225
 226 QList<QPair<int, QVariant> > KFileItemModel::groups() const
 227 {
 228     // TODO: dirty hack for initial testing of grouping functionality
 229     QPair<int, QVariant> group1(0, "Group 1");
 230     QPair<int, QVariant> group2(2, "Group 2");
 231     QPair<int, QVariant> group3(10, "Group 3");
 232     QPair<int, QVariant> group4(11, "Group 4");
 233     QPair<int, QVariant> group5(40, "Group 5");
 234
 235     QList<QPair<int, QVariant> > groups;
 236     groups.append(group1);
 237     groups.append(group2);
 238     groups.append(group3);
 239     groups.append(group4);
 240     groups.append(group5);
 241     return groups;
 242 }
 243
 244 KFileItem KFileItemModel::fileItem(int index) const
 245 {
 246     if (index >= 0 && index < count()) {
 247         return m_sortedItems.at(index);
 248     }
 249
 250     return KFileItem();
 251 }
 252
 253 KFileItem KFileItemModel::fileItem(const KUrl& url) const
 254 {
 255     const int index = m_items.value(url, -1);
 256     if (index >= 0) {
 257         return m_sortedItems.at(index);
 258     }
 259     return KFileItem();
 260 }
 261
 262 int KFileItemModel::index(const KFileItem& item) const
 263 {
 264     if (item.isNull()) {
 265         return -1;
 266     }
 267
 268     return m_items.value(item.url(), -1);
 269 }
 270
 271 int KFileItemModel::index(const KUrl& url) const
 272 {
 273     KUrl urlToFind = url;
 274     urlToFind.adjustPath(KUrl::RemoveTrailingSlash);
 275     return m_items.value(urlToFind, -1);
 276 }
 277
 278 KFileItem KFileItemModel::rootItem() const
 279 {
 280     const KDirLister* dirLister = m_dirLister.data();
 281     if (dirLister) {
 282         return dirLister->rootItem();
 283     }
 284     return KFileItem();
 285 }
 286
 287 void KFileItemModel::clear()
 288 {
 289     slotClear();
 290 }
 291
 292 void KFileItemModel::setRoles(const QSet<QByteArray>& roles)
 293 {
 294     if (count() > 0) {
 295         const bool supportedExpanding = m_requestRole[IsExpandedRole] && m_requestRole[ExpansionLevelRole];
 296         const bool willSupportExpanding = roles.contains("isExpanded") && roles.contains("expansionLevel");
 297         if (supportedExpanding && !willSupportExpanding) {
 298             // No expanding is supported anymore. Take care to delete all items that have an expansion level
 299             // that is not 0 (and hence are part of an expanded item).
 300             removeExpandedItems();
 301         }
 302     }
 303
 304     resetRoles();
 305     QSetIterator<QByteArray> it(roles);
 306     while (it.hasNext()) {
 307         const QByteArray& role = it.next();
 308         m_requestRole[roleIndex(role)] = true;
 309     }
 310
 311     if (count() > 0) {
 312         // Update m_data with the changed requested roles
 313         const int maxIndex = count() - 1;
 314         for (int i = 0; i <= maxIndex; ++i) {
 315             m_data[i] = retrieveData(m_sortedItems.at(i));
 316         }
 317
 318         kWarning() << "TODO: Emitting itemsChanged() with no information what has changed!";
 319         emit itemsChanged(KItemRangeList() << KItemRange(0, count()), QSet<QByteArray>());
 320     }
 321 }
 322
 323 QSet<QByteArray> KFileItemModel::roles() const
 324 {
 325     QSet<QByteArray> roles;
 326     for (int i = 0; i < RolesCount; ++i) {
 327         if (m_requestRole[i]) {
 328             switch (i) {
 329             case NoRole:             break;
 330             case NameRole:           roles.insert("name"); break;
 331             case SizeRole:           roles.insert("size"); break;
 332             case DateRole:           roles.insert("date"); break;
 333             case PermissionsRole:    roles.insert("permissions"); break;
 334             case OwnerRole:          roles.insert("owner"); break;
 335             case GroupRole:          roles.insert("group"); break;
 336             case TypeRole:           roles.insert("type"); break;
 337             case DestinationRole:    roles.insert("destination"); break;
 338             case PathRole:           roles.insert("path"); break;
 339             case IsDirRole:          roles.insert("isDir"); break;
 340             case IsExpandedRole:     roles.insert("isExpanded"); break;
 341             case ExpansionLevelRole: roles.insert("expansionLevel"); break;
 342             default:                 Q_ASSERT(false); break;
 343             }
 344         }
 345     }
 346     return roles;
 347 }
 348
 349 bool KFileItemModel::setExpanded(int index, bool expanded)
 350 {
 351     if (isExpanded(index) == expanded || index < 0 || index >= count()) {
 352         return false;
 353     }
 354
 355     QHash<QByteArray, QVariant> values;
 356     values.insert("isExpanded", expanded);
 357     if (!setData(index, values)) {
 358         return false;
 359     }
 360
 361     const KUrl url = m_sortedItems.at(index).url();
 362     if (expanded) {
 363         m_expandedUrls.insert(url);
 364
 365         KDirLister* dirLister = m_dirLister.data();
 366         if (dirLister) {
 367             dirLister->openUrl(url, KDirLister::Keep);
 368             return true;
 369         }
 370     } else {
 371         m_expandedUrls.remove(url);
 372
 373         KFileItemList itemsToRemove;
 374         const int expansionLevel = data(index)["expansionLevel"].toInt();
 375         ++index;
 376         while (index < count() && data(index)["expansionLevel"].toInt() > expansionLevel) {
 377             itemsToRemove.append(m_sortedItems.at(index));
 378             ++index;
 379         }
 380         removeItems(itemsToRemove);
 381         return true;
 382     }
 383
 384     return false;
 385 }
 386
 387 bool KFileItemModel::isExpanded(int index) const
 388 {
 389     if (index >= 0 && index < count()) {
 390         return m_data.at(index).value("isExpanded").toBool();
 391     }
 392     return false;
 393 }
 394
 395 bool KFileItemModel::isExpandable(int index) const
 396 {
 397     if (index >= 0 && index < count()) {
 398         return m_sortedItems.at(index).isDir();
 399     }
 400     return false;
 401 }
 402
 403 QSet<KUrl> KFileItemModel::expandedUrls() const
 404 {
 405     return m_expandedUrls;
 406 }
 407
 408 void KFileItemModel::restoreExpandedUrls(const QSet<KUrl>& urls)
 409 {
 410     m_restoredExpandedUrls = urls;
 411 }
 412
 413 void KFileItemModel::onGroupedSortingChanged(bool current)
 414 {
 415     Q_UNUSED(current);
 416 }
 417
 418 void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArray& previous)
 419 {
 420     Q_UNUSED(previous);
 421     m_sortRole = roleIndex(current);
 422     resortAllItems();
 423 }
 424
 425 void KFileItemModel::onSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous)
 426 {
 427     Q_UNUSED(current);
 428     Q_UNUSED(previous);
 429     resortAllItems();
 430 }
 431
 432 void KFileItemModel::slotCompleted()
 433 {
 434     if (m_restoredExpandedUrls.isEmpty() && m_minimumUpdateIntervalTimer->isActive()) {
 435         // dispatchPendingItems() will be called when the timer
 436         // has been expired.
 437         m_pendingEmitLoadingCompleted = true;
 438         return;
 439     }
 440
 441     m_pendingEmitLoadingCompleted = false;
 442     dispatchPendingItemsToInsert();
 443
 444     if (!m_restoredExpandedUrls.isEmpty()) {
 445         // Try to find a URL that can be expanded.
 446         // Note that the parent folder must be expanded before any of its subfolders become visible.
 447         // Therefore, some URLs in m_restoredExpandedUrls might not be visible yet
 448         // -> we expand the first visible URL we find in m_restoredExpandedUrls.
 449         foreach(const KUrl& url, m_restoredExpandedUrls) {
 450             const int index = m_items.value(url, -1);
 451             if (index >= 0) {
 452                 // We have found an expandable URL. Expand it and return - when
 453                 // the dir lister has finished, this slot will be called again.
 454                 m_restoredExpandedUrls.remove(url);
 455                 setExpanded(index, true);
 456                 return;
 457             }
 458         }
 459
 460         // None of the URLs in m_restoredExpandedUrls could be found in the model. This can happen
 461         // if these URLs have been deleted in the meantime.
 462         m_restoredExpandedUrls.clear();
 463     }
 464
 465     emit loadingCompleted();
 466     m_minimumUpdateIntervalTimer->start();
 467 }
 468
 469 void KFileItemModel::slotCanceled()
 470 {
 471     m_minimumUpdateIntervalTimer->stop();
 472     m_maximumUpdateIntervalTimer->stop();
 473     dispatchPendingItemsToInsert();
 474 }
 475
 476 void KFileItemModel::slotNewItems(const KFileItemList& items)
 477 {
 478     m_pendingItemsToInsert.append(items);
 479
 480     if (useMaximumUpdateInterval() && !m_maximumUpdateIntervalTimer->isActive()) {
 481         // Assure that items get dispatched if no completed() or canceled() signal is
 482         // emitted during the maximum update interval.
 483         m_maximumUpdateIntervalTimer->start();
 484     }
 485 }
 486
 487 void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 488 {
 489     if (!m_pendingItemsToInsert.isEmpty()) {
 490         insertItems(m_pendingItemsToInsert);
 491         m_pendingItemsToInsert.clear();
 492     }
 493     removeItems(items);
 494 }
 495
 496 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 497 {
 498     Q_ASSERT(!items.isEmpty());
 499 #ifdef KFILEITEMMODEL_DEBUG
 500     kDebug() << "Refreshing" << items.count() << "items";
 501 #endif
 502
 503     // Get the indexes of all items that have been refreshed
 504     QList<int> indexes;
 505     indexes.reserve(items.count());
 506
 507     QListIterator<QPair<KFileItem, KFileItem> > it(items);
 508     while (it.hasNext()) {
 509         const QPair<KFileItem, KFileItem>& itemPair = it.next();
 510         const int index = m_items.value(itemPair.second.url(), -1);
 511         if (index >= 0) {
 512             indexes.append(index);
 513         }
 514     }
 515
 516     // If the changed items have been created recently, they might not be in m_items yet.
 517     // In that case, the list 'indexes' might be empty.
 518     if (indexes.isEmpty()) {
 519         return;
 520     }
 521
 522     // Extract the item-ranges out of the changed indexes
 523     qSort(indexes);
 524
 525     KItemRangeList itemRangeList;
 526     int rangeIndex = 0;
 527     int rangeCount = 1;
 528     int previousIndex = indexes.at(0);
 529
 530     const int maxIndex = indexes.count() - 1;
 531     for (int i = 1; i <= maxIndex; ++i) {
 532         const int currentIndex = indexes.at(i);
 533         if (currentIndex == previousIndex + 1) {
 534             ++rangeCount;
 535         } else {
 536             itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 537
 538             rangeIndex = currentIndex;
 539             rangeCount = 1;
 540         }
 541         previousIndex = currentIndex;
 542     }
 543
 544     if (rangeCount > 0) {
 545         itemRangeList.append(KItemRange(rangeIndex, rangeCount));
 546     }
 547
 548     emit itemsChanged(itemRangeList, QSet<QByteArray>());
 549 }
 550
 551 void KFileItemModel::slotClear()
 552 {
 553 #ifdef KFILEITEMMODEL_DEBUG
 554     kDebug() << "Clearing all items";
 555 #endif
 556
 557     m_minimumUpdateIntervalTimer->stop();
 558     m_maximumUpdateIntervalTimer->stop();
 559     m_pendingItemsToInsert.clear();
 560
 561     m_rootExpansionLevel = -1;
 562
 563     const int removedCount = m_data.count();
 564     if (removedCount > 0) {
 565         m_sortedItems.clear();
 566         m_items.clear();
 567         m_data.clear();
 568         emit itemsRemoved(KItemRangeList() << KItemRange(0, removedCount));
 569     }
 570
 571     m_expandedUrls.clear();
 572 }
 573
 574 void KFileItemModel::slotClear(const KUrl& url)
 575 {
 576     Q_UNUSED(url);
 577 }
 578
 579 void KFileItemModel::dispatchPendingItemsToInsert()
 580 {
 581     if (!m_pendingItemsToInsert.isEmpty()) {
 582         insertItems(m_pendingItemsToInsert);
 583         m_pendingItemsToInsert.clear();
 584     }
 585
 586     if (m_pendingEmitLoadingCompleted) {
 587         emit loadingCompleted();
 588     }
 589 }
 590
 591 void KFileItemModel::insertItems(const KFileItemList& items)
 592 {
 593     if (items.isEmpty()) {
 594         return;
 595     }
 596
 597 #ifdef KFILEITEMMODEL_DEBUG
 598     QElapsedTimer timer;
 599     timer.start();
 600     kDebug() << "===========================================================";
 601     kDebug() << "Inserting" << items.count() << "items";
 602 #endif
 603
 604     KFileItemList sortedItems = items;
 605     sort(sortedItems.begin(), sortedItems.end());
 606
 607 #ifdef KFILEITEMMODEL_DEBUG
 608     kDebug() << "[TIME] Sorting:" << timer.elapsed();
 609 #endif
 610
 611     KItemRangeList itemRanges;
 612     int targetIndex = 0;
 613     int sourceIndex = 0;
 614     int insertedAtIndex = -1;         // Index for the current item-range
 615     int insertedCount = 0;            // Count for the current item-range
 616     int previouslyInsertedCount = 0;  // Sum of previously inserted items for all ranges
 617     while (sourceIndex < sortedItems.count()) {
 618         // Find target index from m_items to insert the current item
 619         // in a sorted order
 620         const int previousTargetIndex = targetIndex;
 621         while (targetIndex < m_sortedItems.count()) {
 622             if (!lessThan(m_sortedItems.at(targetIndex), sortedItems.at(sourceIndex))) {
 623                 break;
 624             }
 625             ++targetIndex;
 626         }
 627
 628         if (targetIndex - previousTargetIndex > 0 && insertedAtIndex >= 0) {
 629             itemRanges << KItemRange(insertedAtIndex, insertedCount);
 630             previouslyInsertedCount += insertedCount;
 631             insertedAtIndex = targetIndex - previouslyInsertedCount;
 632             insertedCount = 0;
 633         }
 634
 635         // Insert item at the position targetIndex
 636         const KFileItem item = sortedItems.at(sourceIndex);
 637         m_sortedItems.insert(targetIndex, item);
 638         m_data.insert(targetIndex, retrieveData(item));
 639         // m_items will be inserted after the loop (see comment below)
 640         ++insertedCount;
 641
 642         if (insertedAtIndex < 0) {
 643             insertedAtIndex = targetIndex;
 644             Q_ASSERT(previouslyInsertedCount == 0);
 645         }
 646         ++targetIndex;
 647         ++sourceIndex;
 648     }
 649
 650     // The indexes of all m_items must be adjusted, not only the index
 651     // of the new items
 652     for (int i = 0; i < m_sortedItems.count(); ++i) {
 653         m_items.insert(m_sortedItems.at(i).url(), i);
 654     }
 655
 656     itemRanges << KItemRange(insertedAtIndex, insertedCount);
 657     emit itemsInserted(itemRanges);
 658
 659 #ifdef KFILEITEMMODEL_DEBUG
 660     kDebug() << "[TIME] Inserting of" << items.count() << "items:" << timer.elapsed();
 661 #endif
 662 }
 663
 664 void KFileItemModel::removeItems(const KFileItemList& items)
 665 {
 666     if (items.isEmpty()) {
 667         return;
 668     }
 669
 670 #ifdef KFILEITEMMODEL_DEBUG
 671     kDebug() << "Removing " << items.count() << "items";
 672 #endif
 673
 674     KFileItemList sortedItems = items;
 675     sort(sortedItems.begin(), sortedItems.end());
 676
 677     QList<int> indexesToRemove;
 678     indexesToRemove.reserve(items.count());
 679
 680     // Calculate the item ranges that will get deleted
 681     KItemRangeList itemRanges;
 682     int removedAtIndex = -1;
 683     int removedCount = 0;
 684     int targetIndex = 0;
 685     foreach (const KFileItem& itemToRemove, sortedItems) {
 686         const int previousTargetIndex = targetIndex;
 687         while (targetIndex < m_sortedItems.count()) {
 688             if (m_sortedItems.at(targetIndex).url() == itemToRemove.url()) {
 689                 break;
 690             }
 691             ++targetIndex;
 692         }
 693         if (targetIndex >= m_sortedItems.count()) {
 694             kWarning() << "Item that should be deleted has not been found!";
 695             return;
 696         }
 697
 698         if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
 699             itemRanges << KItemRange(removedAtIndex, removedCount);
 700             removedAtIndex = targetIndex;
 701             removedCount = 0;
 702         }
 703
 704         indexesToRemove.append(targetIndex);
 705         if (removedAtIndex < 0) {
 706             removedAtIndex = targetIndex;
 707         }
 708         ++removedCount;
 709         ++targetIndex;
 710     }
 711
 712     // Delete the items
 713     for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
 714         const int indexToRemove = indexesToRemove.at(i);
 715         m_items.remove(m_sortedItems.at(indexToRemove).url());
 716         m_sortedItems.removeAt(indexToRemove);
 717         m_data.removeAt(indexToRemove);
 718     }
 719
 720     // The indexes of all m_items must be adjusted, not only the index
 721     // of the removed items
 722     for (int i = 0; i < m_sortedItems.count(); ++i) {
 723         m_items.insert(m_sortedItems.at(i).url(), i);
 724     }
 725
 726     if (count() <= 0) {
 727         m_rootExpansionLevel = -1;
 728     }
 729
 730     itemRanges << KItemRange(removedAtIndex, removedCount);
 731     emit itemsRemoved(itemRanges);
 732 }
 733
 734 void KFileItemModel::resortAllItems()
 735 {
 736     const int itemCount = count();
 737     if (itemCount <= 0) {
 738         return;
 739     }
 740
 741     const KFileItemList oldSortedItems = m_sortedItems;
 742     const QHash<KUrl, int> oldItems = m_items;
 743     const QList<QHash<QByteArray, QVariant> > oldData = m_data;
 744
 745     m_items.clear();
 746     m_data.clear();
 747
 748     sort(m_sortedItems.begin(), m_sortedItems.end());
 749     int index = 0;
 750     foreach (const KFileItem& item, m_sortedItems) {
 751         m_items.insert(item.url(), index);
 752
 753         const int oldItemIndex = oldItems.value(item.url());
 754         m_data.append(oldData.at(oldItemIndex));
 755
 756         ++index;
 757     }
 758
 759     bool emitItemsMoved = false;
 760     QList<int> movedToIndexes;
 761     movedToIndexes.reserve(m_sortedItems.count());
 762     for (int i = 0; i < itemCount; i++) {
 763         const int newIndex = m_items.value(oldSortedItems.at(i).url());
 764         movedToIndexes.append(newIndex);
 765         if (!emitItemsMoved && newIndex != i) {
 766             emitItemsMoved = true;
 767         }
 768     }
 769
 770     if (emitItemsMoved) {
 771         emit itemsMoved(KItemRange(0, itemCount), movedToIndexes);
 772     }
 773 }
 774
 775 void KFileItemModel::removeExpandedItems()
 776 {
 777     KFileItemList expandedItems;
 778
 779     const int maxIndex = m_data.count() - 1;
 780     for (int i = 0; i <= maxIndex; ++i) {
 781         if (m_data.at(i).value("expansionLevel").toInt() > 0) {
 782             const KFileItem fileItem = m_sortedItems.at(i);
 783             expandedItems.append(fileItem);
 784         }
 785     }
 786
 787     // The m_rootExpansionLevel may not get reset before all items with
 788     // a bigger expansionLevel have been removed.
 789     Q_ASSERT(m_rootExpansionLevel >= 0);
 790     removeItems(expandedItems);
 791
 792     m_rootExpansionLevel = -1;
 793     m_expandedUrls.clear();
 794 }
 795
 796 void KFileItemModel::resetRoles()
 797 {
 798     for (int i = 0; i < RolesCount; ++i) {
 799         m_requestRole[i] = false;
 800     }
 801 }
 802
 803 KFileItemModel::Role KFileItemModel::roleIndex(const QByteArray& role) const
 804 {
 805     static QHash<QByteArray, Role> rolesHash;
 806     if (rolesHash.isEmpty()) {
 807         rolesHash.insert("name", NameRole);
 808         rolesHash.insert("size", SizeRole);
 809         rolesHash.insert("date", DateRole);
 810         rolesHash.insert("permissions", PermissionsRole);
 811         rolesHash.insert("owner", OwnerRole);
 812         rolesHash.insert("group", GroupRole);
 813         rolesHash.insert("type", TypeRole);
 814         rolesHash.insert("destination", DestinationRole);
 815         rolesHash.insert("path", PathRole);
 816         rolesHash.insert("isDir", IsDirRole);
 817         rolesHash.insert("isExpanded", IsExpandedRole);
 818         rolesHash.insert("expansionLevel", ExpansionLevelRole);
 819     }
 820     return rolesHash.value(role, NoRole);
 821 }
 822
 823 QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item) const
 824 {
 825     // It is important to insert only roles that are fast to retrieve. E.g.
 826     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
 827     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
 828     QHash<QByteArray, QVariant> data;
 829     data.insert("iconPixmap", QPixmap());
 830
 831     const bool isDir = item.isDir();
 832     if (m_requestRole[IsDirRole]) {
 833         data.insert("isDir", isDir);
 834     }
 835
 836     if (m_requestRole[NameRole]) {
 837         data.insert("name", item.name());
 838     }
 839
 840     if (m_requestRole[SizeRole]) {
 841         if (isDir) {
 842             data.insert("size", QVariant());
 843         } else {
 844             data.insert("size", item.size());
 845         }
 846     }
 847
 848     if (m_requestRole[DateRole]) {
 849         // Don't use KFileItem::timeString() as this is too expensive when
 850         // having several thousands of items. Instead the formatting of the
 851         // date-time will be done on-demand by the view when the date will be shown.
 852         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
 853         data.insert("date", dateTime.dateTime());
 854     }
 855
 856     if (m_requestRole[PermissionsRole]) {
 857         data.insert("permissions", item.permissionsString());
 858     }
 859
 860     if (m_requestRole[OwnerRole]) {
 861         data.insert("owner", item.user());
 862     }
 863
 864     if (m_requestRole[GroupRole]) {
 865         data.insert("group", item.group());
 866     }
 867
 868     if (m_requestRole[DestinationRole]) {
 869         QString destination = item.linkDest();
 870         if (destination.isEmpty()) {
 871             destination = i18nc("@item:intable", "No destination");
 872         }
 873         data.insert("destination", destination);
 874     }
 875
 876     if (m_requestRole[PathRole]) {
 877         data.insert("path", item.localPath());
 878     }
 879
 880     if (m_requestRole[IsExpandedRole]) {
 881         data.insert("isExpanded", false);
 882     }
 883
 884     if (m_requestRole[ExpansionLevelRole]) {
 885         if (m_rootExpansionLevel < 0) {
 886             KDirLister* dirLister = m_dirLister.data();
 887             if (dirLister) {
 888                 const QString rootDir = dirLister->url().directory(KUrl::AppendTrailingSlash);
 889                 m_rootExpansionLevel = rootDir.count('/');
 890             }
 891         }
 892         const QString dir = item.url().directory(KUrl::AppendTrailingSlash);
 893         const int level = dir.count('/') - m_rootExpansionLevel - 1;
 894         data.insert("expansionLevel", level);
 895     }
 896
 897     if (item.isMimeTypeKnown()) {
 898         data.insert("iconName", item.iconName());
 899
 900         if (m_requestRole[TypeRole]) {
 901             data.insert("type", item.mimeComment());
 902         }
 903     }
 904
 905     return data;
 906 }
 907
 908 bool KFileItemModel::lessThan(const KFileItem& a, const KFileItem& b) const
 909 {
 910     int result = 0;
 911
 912     if (m_rootExpansionLevel >= 0) {
 913         result = expansionLevelsCompare(a, b);
 914         if (result != 0) {
 915             // The items have parents with different expansion levels
 916             return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
 917         }
 918     }
 919
 920     if (m_sortFoldersFirst || m_sortRole == SizeRole) {
 921         const bool isDirA = a.isDir();
 922         const bool isDirB = b.isDir();
 923         if (isDirA && !isDirB) {
 924             return true;
 925         } else if (!isDirA && isDirB) {
 926             return false;
 927         }
 928     }
 929
 930     switch (m_sortRole) {
 931     case NameRole: {
 932         result = stringCompare(a.text(), b.text());
 933         if (result == 0) {
 934             // KFileItem::text() may not be unique in case UDS_DISPLAY_NAME is used
 935             result = stringCompare(a.name(m_caseSensitivity == Qt::CaseInsensitive),
 936                                    b.name(m_caseSensitivity == Qt::CaseInsensitive));
 937         }
 938         break;
 939     }
 940
 941     case DateRole: {
 942         const KDateTime dateTimeA = a.time(KFileItem::ModificationTime);
 943         const KDateTime dateTimeB = b.time(KFileItem::ModificationTime);
 944         if (dateTimeA < dateTimeB) {
 945             result = -1;
 946         } else if (dateTimeA > dateTimeB) {
 947             result = +1;
 948         }
 949         break;
 950     }
 951
 952     case SizeRole: {
 953         // TODO: Implement sorting folders by the number of items inside.
 954         // This is more tricky to get right because this number is retrieved
 955         // asynchronously by KFileItemModelRolesUpdater.
 956         const KIO::filesize_t sizeA = a.size();
 957         const KIO::filesize_t sizeB = b.size();
 958         if (sizeA < sizeB) {
 959             result = -1;
 960         } else if (sizeA > sizeB) {
 961             result = +1;
 962         }
 963         break;
 964     }
 965
 966     default:
 967         break;
 968     }
 969
 970     if (result == 0) {
 971         // It must be assured that the sort order is always unique even if two values have been
 972         // equal. In this case a comparison of the URL is done which is unique in all cases
 973         // within KDirLister.
 974         result = QString::compare(a.url().url(), b.url().url(), Qt::CaseSensitive);
 975     }
 976
 977     return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
 978 }
 979
 980 void KFileItemModel::sort(const KFileItemList::iterator& startIterator, const KFileItemList::iterator& endIterator)
 981 {
 982     KFileItemList::iterator start = startIterator;
 983     KFileItemList::iterator end = endIterator;
 984
 985     // The implementation is based on qSortHelper() from qalgorithms.h
 986     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 987     // In opposite to qSort() it allows to use a member-function for the comparison of elements.
 988     while (1) {
 989         int span = int(end - start);
 990         if (span < 2) {
 991             return;
 992         }
 993
 994         --end;
 995         KFileItemList::iterator low = start, high = end - 1;
 996         KFileItemList::iterator pivot = start + span / 2;
 997
 998         if (lessThan(*end, *start)) {
 999             qSwap(*end, *start);
1000         }
1001         if (span == 2) {
1002             return;
1003         }
1004
1005         if (lessThan(*pivot, *start)) {
1006             qSwap(*pivot, *start);
1007         }
1008         if (lessThan(*end, *pivot)) {
1009             qSwap(*end, *pivot);
1010         }
1011         if (span == 3) {
1012             return;
1013         }
1014
1015         qSwap(*pivot, *end);
1016
1017         while (low < high) {
1018             while (low < high && lessThan(*low, *end)) {
1019                 ++low;
1020             }
1021
1022             while (high > low && lessThan(*end, *high)) {
1023                 --high;
1024             }
1025             if (low < high) {
1026                 qSwap(*low, *high);
1027                 ++low;
1028                 --high;
1029             } else {
1030                 break;
1031             }
1032         }
1033
1034         if (lessThan(*low, *end)) {
1035             ++low;
1036         }
1037
1038         qSwap(*end, *low);
1039         sort(start, low);
1040
1041         start = low + 1;
1042         ++end;
1043     }
1044 }
1045
1046 int KFileItemModel::stringCompare(const QString& a, const QString& b) const
1047 {
1048     // Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
1049     // Copyright (C) 2006 by Peter Penz <peter.penz@gmx.at>
1050     // Copyright (C) 2006 by Dominic Battre <dominic@battre.de>
1051     // Copyright (C) 2006 by Martin Pool <mbp@canonical.com>
1052
1053     if (m_caseSensitivity == Qt::CaseInsensitive) {
1054         const int result = m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseInsensitive)
1055                                             : QString::compare(a, b, Qt::CaseInsensitive);
1056         if (result != 0) {
1057             // Only return the result, if the strings are not equal. If they are equal by a case insensitive
1058             // comparison, still a deterministic sort order is required. A case sensitive
1059             // comparison is done as fallback.
1060             return result;
1061         }
1062     }
1063
1064     return m_naturalSorting ? KStringHandler::naturalCompare(a, b, Qt::CaseSensitive)
1065                             : QString::compare(a, b, Qt::CaseSensitive);
1066 }
1067
1068 int KFileItemModel::expansionLevelsCompare(const KFileItem& a, const KFileItem& b) const
1069 {
1070     const KUrl urlA = a.url();
1071     const KUrl urlB = b.url();
1072     if (urlA.directory() == urlB.directory()) {
1073         // Both items have the same directory as parent
1074         return 0;
1075     }
1076
1077     // Check whether one item is the parent of the other item
1078     if (urlA.isParentOf(urlB)) {
1079         return -1;
1080     } else if (urlB.isParentOf(urlA)) {
1081         return +1;
1082     }
1083
1084     // Determine the maximum common path of both items and
1085     // remember the index in 'index'
1086     const QString pathA = urlA.path();
1087     const QString pathB = urlB.path();
1088
1089     const int maxIndex = qMin(pathA.length(), pathB.length()) - 1;
1090     int index = 0;
1091     while (index <= maxIndex && pathA.at(index) == pathB.at(index)) {
1092         ++index;
1093     }
1094     if (index > maxIndex) {
1095         index = maxIndex;
1096     }
1097     while ((pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/')) && index > 0) {
1098         --index;
1099     }
1100
1101     // Determine the first sub-path after the common path and
1102     // check whether it represents a directory or already a file
1103     bool isDirA = true;
1104     const QString subPathA = subPath(a, pathA, index, &isDirA);
1105     bool isDirB = true;
1106     const QString subPathB = subPath(b, pathB, index, &isDirB);
1107
1108     if (isDirA && !isDirB) {
1109         return -1;
1110     } else if (!isDirA && isDirB) {
1111         return +1;
1112     }
1113
1114     return stringCompare(subPathA, subPathB);
1115 }
1116
1117 QString KFileItemModel::subPath(const KFileItem& item,
1118                                 const QString& itemPath,
1119                                 int start,
1120                                 bool* isDir) const
1121 {
1122     Q_ASSERT(isDir);
1123     const int pathIndex = itemPath.indexOf('/', start + 1);
1124     *isDir = (pathIndex > 0) || item.isDir();
1125     return itemPath.mid(start, pathIndex - start);
1126 }
1127
1128 bool KFileItemModel::useMaximumUpdateInterval() const
1129 {
1130     const KDirLister* dirLister = m_dirLister.data();
1131     return dirLister && !dirLister->url().isLocalFile();
1132 }
1133
1134 #include "kfileitemmodel.moc"