45 #include <QtCore/qglobal.h> 59 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
61 template <
typename RandomAccessIterator,
typename T>
62 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end,
const T &dummy);
64 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
66 template <
typename RandomAccessIterator,
typename T>
67 inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator,
const T &);
69 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
71 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
73 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
78 template <
typename InputIterator,
typename OutputIterator>
79 inline OutputIterator
qCopy(InputIterator begin, InputIterator
end, OutputIterator dest)
86 template <
typename BiIterator1,
typename BiIterator2>
94 template <
typename InputIterator1,
typename InputIterator2>
95 inline bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
97 for (; first1 != last1; ++first1, ++first2)
98 if (!(*first1 == *first2))
103 template <
typename ForwardIterator,
typename T>
104 inline void qFill(ForwardIterator first, ForwardIterator last,
const T &val)
106 for (; first != last; ++first)
110 template <
typename Container,
typename T>
111 inline void qFill(Container &container,
const T &val)
113 qFill(container.begin(), container.end(), val);
116 template <
typename InputIterator,
typename T>
117 inline InputIterator
qFind(InputIterator first, InputIterator last,
const T &val)
119 while (first != last && !(*first == val))
124 template <
typename Container,
typename T>
125 inline typename Container::const_iterator
qFind(
const Container &container,
const T &val)
127 return qFind(container.constBegin(), container.constEnd(), val);
130 template <
typename InputIterator,
typename T,
typename Size>
131 inline void qCount(InputIterator first, InputIterator last,
const T &value, Size &n)
133 for (; first != last; ++first)
138 template <
typename Container,
typename T,
typename Size>
139 inline void qCount(
const Container &container,
const T &value, Size &n)
141 qCount(container.constBegin(), container.constEnd(), value, n);
145 template <
typename T>
150 template <
typename T>
155 template <
typename T>
159 inline bool operator()(
const T &t1,
const T &t2)
const 165 template <
typename T>
169 inline bool operator()(
const T &t1,
const T &t2)
const 176 template <
typename RandomAccessIterator>
177 inline void qSort(RandomAccessIterator start, RandomAccessIterator
end)
183 template <
typename RandomAccessIterator,
typename LessThan>
190 template<
typename Container>
201 template <
typename RandomAccessIterator>
208 template <
typename RandomAccessIterator,
typename LessThan>
215 template<
typename Container>
226 template <
typename RandomAccessIterator,
typename T>
232 RandomAccessIterator middle;
238 middle = begin + half;
239 if (*middle < value) {
249 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
255 template <
typename Container,
typename T>
261 template <
typename RandomAccessIterator,
typename T>
265 RandomAccessIterator middle;
271 middle = begin + half;
272 if (value < *middle) {
282 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
288 template <
typename Container,
typename T>
294 template <
typename RandomAccessIterator,
typename T>
300 if (it == end || value < *it)
306 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
312 template <
typename Container,
typename T>
318 template <
typename ForwardIterator>
321 while (begin != end) {
327 template <
typename Container>
339 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
343 int span = int(end - start);
348 RandomAccessIterator low = start, high = end - 1;
349 RandomAccessIterator pivot = start + span / 2;
357 qSwap(*pivot, *start);
366 while (low < high &&
lessThan(*low, *end))
369 while (high > low &&
lessThan(*end, *high))
392 template <
typename RandomAccessIterator,
typename T>
393 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &dummy)
398 template <
typename RandomAccessIterator>
403 qSwap(*begin++, *end--);
406 template <
typename RandomAccessIterator>
414 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
417 const int len1 = pivot - begin;
418 const int len2 = end - pivot;
420 if (len1 == 0 || len2 == 0)
423 if (len1 + len2 == 2) {
424 if (
lessThan(*(begin + 1), *(begin)))
425 qSwap(*begin, *(begin + 1));
429 RandomAccessIterator firstCut;
430 RandomAccessIterator secondCut;
433 const int len1Half = len1 / 2;
434 firstCut = begin + len1Half;
435 secondCut =
qLowerBound(pivot, end, *firstCut, lessThan);
436 len2Half = secondCut - pivot;
439 secondCut = pivot + len2Half;
440 firstCut =
qUpperBound(begin, pivot, *secondCut, lessThan);
443 qRotate(firstCut, pivot, secondCut);
444 const RandomAccessIterator newPivot = firstCut + len2Half;
445 qMerge(begin, firstCut, newPivot, t, lessThan);
446 qMerge(newPivot, secondCut, end, t, lessThan);
449 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
452 const int span = end - begin;
456 const RandomAccessIterator middle = begin + span / 2;
459 qMerge(begin, middle, end, t, lessThan);
462 template <
typename RandomAccessIterator,
typename T>
468 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
471 RandomAccessIterator middle;
472 int n = int(end - begin);
477 middle = begin + half;
489 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
492 RandomAccessIterator middle;
498 middle = begin + half;
509 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
514 if (it == end ||
lessThan(value, *it))
526 #endif // QALGORITHMS_H Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
void qFill(ForwardIterator first, ForwardIterator last, const T &val)
Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
#define QT_END_NAMESPACE
This macro expands to.
#define it(className, varName)
InputIterator qFind(InputIterator first, InputIterator last, const T &val)
void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &)
Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
void qCount(InputIterator first, InputIterator last, const T &value, Size &n)
bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
#define QT_BEGIN_NAMESPACE
This macro expands to.
static bool lessThan(const QChar *a, int l, const char *c)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
void qSort(RandomAccessIterator start, RandomAccessIterator end)
void qSwap(T &value1, T &value2)
void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
static const KeyPair *const end
#define Q_OUTOFLINE_TEMPLATE
Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)