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