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