59 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
60 Q_OUTOFLINE_TEMPLATE
void qSortHelper(RandomAccessIterator
start, RandomAccessIterator
end,
const T &
t, LessThan 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>
65 Q_OUTOFLINE_TEMPLATE
void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end,
const T &t, LessThan lessThan);
66 template <
typename RandomAccessIterator,
typename T>
67 inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator,
const T &);
69 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
70 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end,
const T &
value, LessThan lessThan);
71 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
72 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end,
const T &value, LessThan lessThan);
73 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
74 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end,
const T &value, LessThan 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>
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>
165 template <
typename T>
176 template <
typename RandomAccessIterator>
183 template <
typename RandomAccessIterator,
typename LessThan>
184 inline void qSort(RandomAccessIterator
start, RandomAccessIterator
end, LessThan 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>
227 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qLowerBound(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value)
232 RandomAccessIterator middle;
238 middle = begin + half;
239 if (*middle < value) {
249 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
250 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qLowerBound(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
255 template <
typename Container,
typename T>
256 Q_OUTOFLINE_TEMPLATE
typename Container::const_iterator
qLowerBound(
const Container &container,
const T &
value)
261 template <
typename RandomAccessIterator,
typename T>
262 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qUpperBound(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value)
265 RandomAccessIterator middle;
271 middle = begin + half;
272 if (value < *middle) {
282 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
283 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qUpperBound(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
288 template <
typename Container,
typename T>
289 Q_OUTOFLINE_TEMPLATE
typename Container::const_iterator
qUpperBound(
const Container &container,
const T &
value)
294 template <
typename RandomAccessIterator,
typename T>
295 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qBinaryFind(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value)
298 RandomAccessIterator it =
qLowerBound(begin, end, value);
300 if (it == end || value < *it)
306 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
307 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qBinaryFind(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
312 template <
typename Container,
typename T>
313 Q_OUTOFLINE_TEMPLATE
typename Container::const_iterator
qBinaryFind(
const Container &container,
const T &
value)
318 template <
typename ForwardIterator>
319 Q_OUTOFLINE_TEMPLATE
void qDeleteAll(ForwardIterator begin, ForwardIterator
end)
321 while (begin != end) {
327 template <
typename Container>
339 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
340 Q_OUTOFLINE_TEMPLATE
void qSortHelper(RandomAccessIterator
start, RandomAccessIterator
end,
const T &
t, LessThan lessThan)
348 RandomAccessIterator low =
start, high = end - 1;
349 RandomAccessIterator pivot = start + span / 2;
351 if (lessThan(*end, *start))
356 if (lessThan(*pivot, *start))
357 qSwap(*pivot, *start);
358 if (lessThan(*end, *pivot))
366 while (low < high && lessThan(*low, *end))
369 while (high > low && lessThan(*end, *high))
381 if (lessThan(*low, *end))
392 template <
typename RandomAccessIterator,
typename T>
393 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &dummy)
398 template <
typename RandomAccessIterator>
399 Q_OUTOFLINE_TEMPLATE
void qReverse(RandomAccessIterator begin, RandomAccessIterator
end)
403 qSwap(*begin++, *end--);
406 template <
typename RandomAccessIterator>
407 Q_OUTOFLINE_TEMPLATE
void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator
end)
414 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
415 Q_OUTOFLINE_TEMPLATE
void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator
end, T &
t, LessThan 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>
450 Q_OUTOFLINE_TEMPLATE
void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
t, LessThan 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>
469 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
471 RandomAccessIterator middle;
472 int n =
int(end - begin);
477 middle = begin + half;
478 if (lessThan(*middle, value)) {
489 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
490 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
492 RandomAccessIterator middle;
498 middle = begin + half;
499 if (lessThan(value, *middle)) {
509 template <
typename RandomAccessIterator,
typename T,
typename LessThan>
510 Q_OUTOFLINE_TEMPLATE RandomAccessIterator
qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator
end,
const T &
value, LessThan lessThan)
514 if (it == end || lessThan(value, *it))
526 #endif // QALGORITHMS_H
unsigned int(APIENTRYP PFNGLXGETAGPOFFSETMESAPROC)(const void *pointer)
void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
void qFill(ForwardIterator first, ForwardIterator last, const T &val)
InputIterator qFind(InputIterator first, InputIterator last, const T &val)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
void qCount(InputIterator first, InputIterator last, const T &value, Size &n)
bool operator()(const T &t1, const T &t2) const
bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
#define QT_BEGIN_NAMESPACE
bool operator()(const T &t1, const T &t2) const
Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
Q_INLINE_TEMPLATE void qSwap(QScopedPointer< T, Cleanup > &p1, QScopedPointer< T, Cleanup > &p2)
Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
void qSort(RandomAccessIterator start, RandomAccessIterator end)
void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
GLsizei const GLfloat * value
Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
GLenum GLenum GLvoid GLvoid GLvoid * span
Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)