diff options
Diffstat (limited to 'src/kitemviews')
| -rw-r--r-- | src/kitemviews/kfileitemmodel.cpp | 191 | ||||
| -rw-r--r-- | src/kitemviews/kfileitemmodel.h | 14 | ||||
| -rw-r--r-- | src/kitemviews/private/kfileitemmodelsortalgorithm.cpp | 190 | ||||
| -rw-r--r-- | src/kitemviews/private/kfileitemmodelsortalgorithm.h | 180 |
4 files changed, 272 insertions, 303 deletions
diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp index 6c015db37..ab39e55e5 100644 --- a/src/kitemviews/kfileitemmodel.cpp +++ b/src/kitemviews/kfileitemmodel.cpp @@ -58,7 +58,6 @@ KFileItemModel::KFileItemModel(QObject* parent) : m_urlsToExpand() { m_dirLister = new KFileItemModelDirLister(this); - m_dirLister->setAutoUpdate(true); m_dirLister->setDelayedMimeTypes(true); const QWidget* parentWidget = qobject_cast<QWidget*>(parent); @@ -658,7 +657,7 @@ void KFileItemModel::resortAllItems() m_items.clear(); // Resort the items - KFileItemModelSortAlgorithm::sort(this, m_itemData.begin(), m_itemData.end()); + sort(m_itemData.begin(), m_itemData.end()); for (int i = 0; i < itemCount; ++i) { m_items.insert(m_itemData.at(i)->item.url(), i); } @@ -941,7 +940,7 @@ void KFileItemModel::insertItems(const KFileItemList& items) m_groups.clear(); QList<ItemData*> sortedItems = createItemDataList(items); - KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); + sort(sortedItems.begin(), sortedItems.end()); #ifdef KFILEITEMMODEL_DEBUG kDebug() << "[TIME] Sorting:" << timer.elapsed(); @@ -1000,6 +999,36 @@ void KFileItemModel::insertItems(const KFileItemList& items) #endif } +static KItemRangeList sortedIndexesToKItemRangeList(const QList<int> sortedNumbers) +{ + if (sortedNumbers.empty()) { + return KItemRangeList(); + } + + KItemRangeList result; + + QList<int>::const_iterator it = sortedNumbers.begin(); + int index = *it; + int count = 1; + + ++it; + + QList<int>::const_iterator end = sortedNumbers.end(); + while (it != end) { + if (*it == index + count) { + ++count; + } else { + result << KItemRange(index, count); + index = *it; + count = 1; + } + ++it; + } + + result << KItemRange(index, count); + return result; +} + void KFileItemModel::removeItems(const KFileItemList& items) { if (items.isEmpty()) { @@ -1012,68 +1041,55 @@ void KFileItemModel::removeItems(const KFileItemList& items) m_groups.clear(); - QList<ItemData*> sortedItems; - sortedItems.reserve(items.count()); - foreach (const KFileItem& item, items) { - const int index = m_items.value(item.url(), -1); - if (index >= 0) { - sortedItems.append(m_itemData.at(index)); - } - } - KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); - + // Step 1: Determine the indexes of the removed items, remove them from + // the hash m_items, and free the ItemData. QList<int> indexesToRemove; indexesToRemove.reserve(items.count()); + foreach (const KFileItem& item, items) { + const KUrl url = item.url(); + const int index = m_items.value(url, -1); + if (index >= 0) { + indexesToRemove.append(index); - // Calculate the item ranges that will get deleted - KItemRangeList itemRanges; - int removedAtIndex = -1; - int removedCount = 0; - int targetIndex = 0; - foreach (const ItemData* itemData, sortedItems) { - const KFileItem& itemToRemove = itemData->item; + // Prevent repeated expensive rehashing by using QHash::erase(), + // rather than QHash::remove(). + QHash<KUrl, int>::iterator it = m_items.find(url); + m_items.erase(it); - const int previousTargetIndex = targetIndex; - while (targetIndex < m_itemData.count()) { - if (m_itemData.at(targetIndex)->item.url() == itemToRemove.url()) { - break; - } - ++targetIndex; - } - if (targetIndex >= m_itemData.count()) { + ItemData* data = m_itemData.at(index); + delete data; + m_itemData[index] = 0; + } else { kWarning() << "Item that should be deleted has not been found!"; - return; - } - - if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) { - itemRanges << KItemRange(removedAtIndex, removedCount); - removedAtIndex = targetIndex; - removedCount = 0; - } - - indexesToRemove.append(targetIndex); - if (removedAtIndex < 0) { - removedAtIndex = targetIndex; } - ++removedCount; - ++targetIndex; } - // Delete the items - for (int i = indexesToRemove.count() - 1; i >= 0; --i) { - const int indexToRemove = indexesToRemove.at(i); - ItemData* data = m_itemData.at(indexToRemove); + std::sort(indexesToRemove.begin(), indexesToRemove.end()); - m_items.remove(data->item.url()); + // Step 2: Remove the ItemData pointers from the list m_itemData. + const KItemRangeList itemRanges = sortedIndexesToKItemRangeList(indexesToRemove); + int target = itemRanges.at(0).index; + int source = itemRanges.at(0).index + itemRanges.at(0).count; + int nextRange = 1; - delete data; - m_itemData.removeAt(indexToRemove); + const int oldItemDataCount = m_itemData.count(); + while (source < oldItemDataCount) { + if (nextRange < itemRanges.count() - 1 && source == itemRanges.at(nextRange).index) { + // Skip the items in the next removed range. + source += itemRanges.at(nextRange).count; + ++nextRange; + } + m_itemData[target] = m_itemData[source]; + ++target; + ++source; } - // The indexes of all m_items must be adjusted, not only the index - // of the removed items - const int itemDataCount = m_itemData.count(); - for (int i = 0; i < itemDataCount; ++i) { + m_itemData.erase(m_itemData.end() - indexesToRemove.count(), m_itemData.end()); + + // Step 3: Adjust indexes in the hash m_items. Note that all indexes + // might have been changed by the removal of the items. + const int newItemDataCount = m_itemData.count(); + for (int i = 0; i < newItemDataCount; ++i) { m_items.insert(m_itemData.at(i)->item.url(), i); } @@ -1081,7 +1097,6 @@ void KFileItemModel::removeItems(const KFileItemList& items) m_expandedParentsCountRoot = UninitializedExpandedParentsCountRoot; } - itemRanges << KItemRange(removedAtIndex, removedCount); emit itemsRemoved(itemRanges); } @@ -1346,6 +1361,44 @@ bool KFileItemModel::lessThan(const ItemData* a, const ItemData* b) const return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0; } +/** + * Helper class for KFileItemModel::sort(). + */ +class KFileItemModelLessThan +{ +public: + KFileItemModelLessThan(const KFileItemModel* model) : + m_model(model) + { + } + + bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const + { + return m_model->lessThan(a, b); + } + +private: + const KFileItemModel* m_model; +}; + +void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin, + QList<KFileItemModel::ItemData*>::iterator end) const +{ + KFileItemModelLessThan lessThan(this); + + if (m_sortRole == NameRole) { + // Sorting by name can be expensive, in particular if natural sorting is + // enabled. Use all CPU cores to speed up the sorting process. + static const int numberOfThreads = QThread::idealThreadCount(); + parallelMergeSort(begin, end, lessThan, numberOfThreads); + } else { + // Sorting by other roles is quite fast. Use only one thread to prevent + // problems caused by non-reentrant comparison functions, see + // https://bugs.kde.org/show_bug.cgi?id=312679 + mergeSort(begin, end, lessThan); + } +} + int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const { const KFileItem& itemA = a->item; @@ -1963,4 +2016,34 @@ void KFileItemModel::determineMimeTypes(const KFileItemList& items, int timeout) } } +bool KFileItemModel::isConsistent() const +{ + // Check that m_items and m_itemData are consistent, and that the items are sorted. + if (m_items.count() != m_itemData.count()) { + return false; + } + + for (int i = 0; i < count(); ++i) { + const KFileItem item = fileItem(i); + if (item.isNull()) { + qWarning() << "Item" << i << "is null"; + return false; + } + + const int itemIndex = index(item); + if (itemIndex != i) { + qWarning() << "Item" << i << "has a wrong index:" << itemIndex; + return false; + } + + if (i > 0 && !lessThan(m_itemData.at(i - 1), m_itemData.at(i))) { + qWarning() << "The order of items" << i - 1 << "and" << i << "is wrong:" + << fileItem(i - 1) << fileItem(i); + return false; + } + } + + return true; +} + #include "kfileitemmodel.moc" diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h index ef9dc98b9..903291a4c 100644 --- a/src/kitemviews/kfileitemmodel.h +++ b/src/kitemviews/kfileitemmodel.h @@ -342,6 +342,12 @@ private: bool lessThan(const ItemData* a, const ItemData* b) const; /** + * Sorts the items between \a begin and \a end using the comparison + * function lessThan(). + */ + void sort(QList<ItemData*>::iterator begin, QList<ItemData*>::iterator end) const; + + /** * Helper method for lessThan() and expandedParentsCountCompare(): Compares * the passed item-data using m_sortRole as criteria. Both items must * have the same parent item, otherwise the comparison will be wrong. @@ -428,6 +434,11 @@ private: */ static void determineMimeTypes(const KFileItemList& items, int timeout); + /** + * Checks if the model's internal data structures are consistent. + */ + bool isConsistent() const; + private: KFileItemModelDirLister* m_dirLister; @@ -476,9 +487,10 @@ private: // and done step after step in slotCompleted(). QSet<KUrl> m_urlsToExpand; - friend class KFileItemModelSortAlgorithm; // Accesses lessThan() method + friend class KFileItemModelLessThan; // Accesses lessThan() method friend class KFileItemModelRolesUpdater; // Accesses emitSortProgress() method friend class KFileItemModelTest; // For unit testing + friend class KFileItemModelBenchmark; // For unit testing friend class KFileItemListViewTest; // For unit testing friend class DolphinPart; // Accesses m_dirLister }; diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp b/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp deleted file mode 100644 index ab650efea..000000000 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.cpp +++ /dev/null @@ -1,190 +0,0 @@ -/*************************************************************************** - * Copyright (C) 2012 by Peter Penz <[email protected]> * - * * - * This program is free software; you can redistribute it and/or modify * - * it under the terms of the GNU General Public License as published by * - * the Free Software Foundation; either version 2 of the License, or * - * (at your option) any later version. * - * * - * This program is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this program; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * - ***************************************************************************/ - -#include "kfileitemmodelsortalgorithm.h" - -#include <QThread> -#include <QtCore> - -void KFileItemModelSortAlgorithm::sort(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end) -{ - if (model->sortRole() == model->roleForType(KFileItemModel::NameRole)) { - // Sorting by name can be expensive, in particular if natural sorting is - // enabled. Use all CPU cores to speed up the sorting process. - static const int numberOfThreads = QThread::idealThreadCount(); - parallelSort(model, begin, end, numberOfThreads); - } else { - // Sorting by other roles is quite fast. Use only one thread to prevent - // problems caused by non-reentrant comparison functions, see - // https://bugs.kde.org/show_bug.cgi?id=312679 - sequentialSort(model, begin, end); - } -} - -void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model, - QList< KFileItemModel::ItemData* >::iterator begin, - QList< KFileItemModel::ItemData* >::iterator end) -{ - // The implementation is based on qStableSortHelper() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - const int span = end - begin; - if (span < 2) { - return; - } - - const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2; - sequentialSort(model, begin, middle); - sequentialSort(model, middle, end); - merge(model, begin, middle, end); -} - -void KFileItemModelSortAlgorithm::parallelSort(KFileItemModel* model, - QList< KFileItemModel::ItemData* >::iterator begin, - QList< KFileItemModel::ItemData* >::iterator end, - const int numberOfThreads) -{ - const int span = end - begin; - - if (numberOfThreads > 1 && span > 100) { - const int newNumberOfThreads = numberOfThreads / 2; - const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2; - - QFuture<void> future = QtConcurrent::run(parallelSort, model, begin, middle, newNumberOfThreads); - parallelSort(model, middle, end, newNumberOfThreads); - - future.waitForFinished(); - - merge(model, begin, middle, end); - } else { - sequentialSort(model, begin, end); - } -} - -void KFileItemModelSortAlgorithm::merge(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator pivot, - QList<KFileItemModel::ItemData*>::iterator end) -{ - // The implementation is based on qMerge() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - const int len1 = pivot - begin; - const int len2 = end - pivot; - - if (len1 == 0 || len2 == 0) { - return; - } - - if (len1 + len2 == 2) { - if (model->lessThan(*(begin + 1), *(begin))) { - qSwap(*begin, *(begin + 1)); - } - return; - } - - QList<KFileItemModel::ItemData*>::iterator firstCut; - QList<KFileItemModel::ItemData*>::iterator secondCut; - int len2Half; - if (len1 > len2) { - const int len1Half = len1 / 2; - firstCut = begin + len1Half; - secondCut = lowerBound(model, pivot, end, *firstCut); - len2Half = secondCut - pivot; - } else { - len2Half = len2 / 2; - secondCut = pivot + len2Half; - firstCut = upperBound(model, begin, pivot, *secondCut); - } - - reverse(firstCut, pivot); - reverse(pivot, secondCut); - reverse(firstCut, secondCut); - - const QList<KFileItemModel::ItemData*>::iterator newPivot = firstCut + len2Half; - merge(model, begin, firstCut, newPivot); - merge(model, newPivot, secondCut, end); -} - - -QList<KFileItemModel::ItemData*>::iterator -KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end, - const KFileItemModel::ItemData* value) -{ - // The implementation is based on qLowerBound() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - QList<KFileItemModel::ItemData*>::iterator middle; - int n = int(end - begin); - int half; - - while (n > 0) { - half = n >> 1; - middle = begin + half; - if (model->lessThan(*middle, value)) { - begin = middle + 1; - n -= half + 1; - } else { - n = half; - } - } - return begin; -} - -QList<KFileItemModel::ItemData*>::iterator -KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end, - const KFileItemModel::ItemData* value) -{ - // The implementation is based on qUpperBound() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - QList<KFileItemModel::ItemData*>::iterator middle; - int n = end - begin; - int half; - - while (n > 0) { - half = n >> 1; - middle = begin + half; - if (model->lessThan(value, *middle)) { - n = half; - } else { - begin = middle + 1; - n -= half + 1; - } - } - return begin; -} - -void KFileItemModelSortAlgorithm::reverse(QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end) -{ - // The implementation is based on qReverse() from qalgorithms.h - // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - - --end; - while (begin < end) { - qSwap(*begin++, *end--); - } -} diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.h b/src/kitemviews/private/kfileitemmodelsortalgorithm.h index 07e5d4a81..1d5689432 100644 --- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h +++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h @@ -1,79 +1,143 @@ -/*************************************************************************** - * Copyright (C) 2012 by Peter Penz <[email protected]> * - * * - * This program is free software; you can redistribute it and/or modify * - * it under the terms of the GNU General Public License as published by * - * the Free Software Foundation; either version 2 of the License, or * - * (at your option) any later version. * - * * - * This program is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * - * GNU General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this program; if not, write to the * - * Free Software Foundation, Inc., * - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * - ***************************************************************************/ +/***************************************************************************** + * Copyright (C) 2012 by Peter Penz <[email protected]> * + * Copyright (C) 2012 by Emmanuel Pescosta <[email protected]> * + * Copyright (C) 2013 by Frank Reininghaus <[email protected]> * + * * + * This program is free software; you can redistribute it and/or modify * + * it under the terms of the GNU General Public License as published by * + * the Free Software Foundation; either version 2 of the License, or * + * (at your option) any later version. * + * * + * This program is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * + * GNU General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program; if not, write to the * + * Free Software Foundation, Inc., * + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * + *****************************************************************************/ #ifndef KFILEITEMMODELSORTALGORITHM_H #define KFILEITEMMODELSORTALGORITHM_H -#include <libdolphin_export.h> +#include <QtCore> -#include <kitemviews/kfileitemmodel.h> +#include <algorithm> /** - * @brief Sort algorithm for sorting items of KFileItemModel. - * - * Sorts the items by using KFileItemModel::lessThan() as comparison criteria. - * The merge sort algorithm is used to assure a worst-case - * of O(n * log(n)) and to keep the number of comparisons low. + * Sorts the items using the merge sort algorithm is used to assure a + * worst-case of O(n * log(n)) and to keep the number of comparisons low. * * The implementation is based on qStableSortHelper() from qalgorithms.h * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). - * The sorting implementations of qAlgorithms could not be used as they - * don't support having a member-function as comparison criteria. */ -class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm + +template <typename RandomAccessIterator, typename LessThan> +static void mergeSort(RandomAccessIterator begin, + RandomAccessIterator end, + LessThan lessThan) { -public: - static void sort(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end); + // The implementation is based on qStableSortHelper() from qalgorithms.h + // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). -private: - static void sequentialSort(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end); + const int span = end - begin; + if (span < 2) { + return; + } - static void parallelSort(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end, - const int numberOfThreads); + const RandomAccessIterator middle = begin + span / 2; + mergeSort(begin, middle, lessThan); + mergeSort(middle, end, lessThan); + merge(begin, middle, end, lessThan); +} - static void merge(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator pivot, - QList<KFileItemModel::ItemData*>::iterator end); +/** + * Uses up to \a numberOfThreads threads to sort the items between + * \a begin and \a end. Only item ranges longer than + * \a parallelMergeSortingThreshold are split to be sorted by two different + * threads. + * + * The comparison function \a lessThan must be reentrant. + */ - static QList<KFileItemModel::ItemData*>::iterator - lowerBound(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end, - const KFileItemModel::ItemData* value); +template <typename RandomAccessIterator, typename LessThan> +static void parallelMergeSort(RandomAccessIterator begin, + RandomAccessIterator end, + LessThan lessThan, + int numberOfThreads, + int parallelMergeSortingThreshold = 100) +{ + const int span = end - begin; - static QList<KFileItemModel::ItemData*>::iterator - upperBound(KFileItemModel* model, - QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end, - const KFileItemModel::ItemData* value); + if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) { + const int newNumberOfThreads = numberOfThreads / 2; + const RandomAccessIterator middle = begin + span / 2; - static void reverse(QList<KFileItemModel::ItemData*>::iterator begin, - QList<KFileItemModel::ItemData*>::iterator end); -}; + QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold); + parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold); -#endif + future.waitForFinished(); + + merge(begin, middle, end, lessThan); + } else { + mergeSort(begin, end, lessThan); + } +} + +/** + * Merges the sorted item ranges between \a begin and \a pivot and + * between \a pivot and \a end into a single sorted range between + * \a begin and \a end. + * + * The implementation is based on qMerge() from qalgorithms.h + * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). + */ + +template <typename RandomAccessIterator, typename LessThan> +static void merge(RandomAccessIterator begin, + RandomAccessIterator pivot, + RandomAccessIterator end, + LessThan lessThan) +{ + // The implementation is based on qMerge() from qalgorithms.h + // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). + + const int len1 = pivot - begin; + const int len2 = end - pivot; + + if (len1 == 0 || len2 == 0) { + return; + } + if (len1 + len2 == 2) { + if (lessThan(*(begin + 1), *(begin))) { + qSwap(*begin, *(begin + 1)); + } + return; + } + + RandomAccessIterator firstCut; + RandomAccessIterator secondCut; + int len2Half; + if (len1 > len2) { + const int len1Half = len1 / 2; + firstCut = begin + len1Half; + secondCut = std::lower_bound(pivot, end, *firstCut, lessThan); + len2Half = secondCut - pivot; + } else { + len2Half = len2 / 2; + secondCut = pivot + len2Half; + firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan); + } + + std::rotate(firstCut, pivot, secondCut); + + RandomAccessIterator newPivot = firstCut + len2Half; + merge(begin, firstCut, newPivot, lessThan); + merge(newPivot, secondCut, end, lessThan); +} + +#endif |