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