Qt 4.8
Functions
QAlgorithmsPrivate Namespace Reference

Functions

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void qMerge (RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
 
template<typename RandomAccessIterator >
Q_OUTOFLINE_TEMPLATE void qReverse (RandomAccessIterator begin, RandomAccessIterator end)
 
template<typename RandomAccessIterator >
Q_OUTOFLINE_TEMPLATE void qRotate (RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
 
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void qSortHelper (RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
 
template<typename RandomAccessIterator , typename T >
void qSortHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
 
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void qStableSortHelper (RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
 
template<typename RandomAccessIterator , typename T >
void qStableSortHelper (RandomAccessIterator, RandomAccessIterator, const T &)
 
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 

Function Documentation

◆ qBinaryFindHelper()

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator QAlgorithmsPrivate::qBinaryFindHelper ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const T &  value,
LessThan  lessThan 
)

Definition at line 510 of file qalgorithms.h.

Referenced by qBinaryFind().

511 {
512  RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);
513 
514  if (it == end || lessThan(value, *it))
515  return end;
516 
517  return it;
518 }
#define it(className, varName)
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
Definition: qalgorithms.h:469
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
static const KeyPair *const end

◆ qLowerBoundHelper()

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator QAlgorithmsPrivate::qLowerBoundHelper ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const T &  value,
LessThan  lessThan 
)

Definition at line 469 of file qalgorithms.h.

Referenced by qBinaryFindHelper(), and qLowerBound().

470 {
471  RandomAccessIterator middle;
472  int n = int(end - begin);
473  int half;
474 
475  while (n > 0) {
476  half = n >> 1;
477  middle = begin + half;
478  if (lessThan(*middle, value)) {
479  begin = middle + 1;
480  n -= half + 1;
481  } else {
482  n = half;
483  }
484  }
485  return begin;
486 }
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
static const KeyPair *const end

◆ qMerge()

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qMerge ( RandomAccessIterator  begin,
RandomAccessIterator  pivot,
RandomAccessIterator  end,
T &  t,
LessThan  lessThan 
)

Definition at line 415 of file qalgorithms.h.

Referenced by qStableSortHelper().

416 {
417  const int len1 = pivot - begin;
418  const int len2 = end - pivot;
419 
420  if (len1 == 0 || len2 == 0)
421  return;
422 
423  if (len1 + len2 == 2) {
424  if (lessThan(*(begin + 1), *(begin)))
425  qSwap(*begin, *(begin + 1));
426  return;
427  }
428 
429  RandomAccessIterator firstCut;
430  RandomAccessIterator secondCut;
431  int len2Half;
432  if (len1 > len2) {
433  const int len1Half = len1 / 2;
434  firstCut = begin + len1Half;
435  secondCut = qLowerBound(pivot, end, *firstCut, lessThan);
436  len2Half = secondCut - pivot;
437  } else {
438  len2Half = len2 / 2;
439  secondCut = pivot + len2Half;
440  firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
441  }
442 
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);
447 }
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
Definition: qalgorithms.h:262
Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
Definition: qalgorithms.h:415
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
Definition: qalgorithms.h:227
Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
Definition: qalgorithms.h:407
static const KeyPair *const end

◆ qReverse()

template<typename RandomAccessIterator >
Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qReverse ( RandomAccessIterator  begin,
RandomAccessIterator  end 
)

Definition at line 399 of file qalgorithms.h.

Referenced by QDeclarativeImportDatabase::QDeclarativeImportDatabase(), and qRotate().

400 {
401  --end;
402  while (begin < end)
403  qSwap(*begin++, *end--);
404 }
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
static const KeyPair *const end

◆ qRotate()

template<typename RandomAccessIterator >
Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qRotate ( RandomAccessIterator  begin,
RandomAccessIterator  middle,
RandomAccessIterator  end 
)

Definition at line 407 of file qalgorithms.h.

Referenced by qMerge().

408 {
409  qReverse(begin, middle);
410  qReverse(middle, end);
411  qReverse(begin, end);
412 }
Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
Definition: qalgorithms.h:399
static const KeyPair *const end

◆ qSortHelper() [1/2]

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qSortHelper ( RandomAccessIterator  start,
RandomAccessIterator  end,
const T &  t,
LessThan  lessThan 
)

Definition at line 340 of file qalgorithms.h.

Referenced by qSort().

341 {
342 top:
343  int span = int(end - start);
344  if (span < 2)
345  return;
346 
347  --end;
348  RandomAccessIterator low = start, high = end - 1;
349  RandomAccessIterator pivot = start + span / 2;
350 
351  if (lessThan(*end, *start))
352  qSwap(*end, *start);
353  if (span == 2)
354  return;
355 
356  if (lessThan(*pivot, *start))
357  qSwap(*pivot, *start);
358  if (lessThan(*end, *pivot))
359  qSwap(*end, *pivot);
360  if (span == 3)
361  return;
362 
363  qSwap(*pivot, *end);
364 
365  while (low < high) {
366  while (low < high && lessThan(*low, *end))
367  ++low;
368 
369  while (high > low && lessThan(*end, *high))
370  --high;
371 
372  if (low < high) {
373  qSwap(*low, *high);
374  ++low;
375  --high;
376  } else {
377  break;
378  }
379  }
380 
381  if (lessThan(*low, *end))
382  ++low;
383 
384  qSwap(*end, *low);
385  qSortHelper(start, low, t, lessThan);
386 
387  start = low + 1;
388  ++end;
389  goto top;
390 }
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
Definition: qalgorithms.h:393
static const KeyPair *const end

◆ qSortHelper() [2/2]

template<typename RandomAccessIterator , typename T >
void QAlgorithmsPrivate::qSortHelper ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const T &  dummy 
)
inline

Definition at line 393 of file qalgorithms.h.

Referenced by qSortHelper().

394 {
395  qSortHelper(begin, end, dummy, qLess<T>());
396 }
void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
Definition: qalgorithms.h:393
static const KeyPair *const end

◆ qStableSortHelper() [1/2]

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qStableSortHelper ( RandomAccessIterator  start,
RandomAccessIterator  end,
const T &  t,
LessThan  lessThan 
)

Definition at line 450 of file qalgorithms.h.

Referenced by qStableSort().

451 {
452  const int span = end - begin;
453  if (span < 2)
454  return;
455 
456  const RandomAccessIterator middle = begin + span / 2;
457  qStableSortHelper(begin, middle, t, lessThan);
458  qStableSortHelper(middle, end, t, lessThan);
459  qMerge(begin, middle, end, t, lessThan);
460 }
Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
Definition: qalgorithms.h:415
void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &)
Definition: qalgorithms.h:463
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
static const KeyPair *const end

◆ qStableSortHelper() [2/2]

template<typename RandomAccessIterator , typename T >
void QAlgorithmsPrivate::qStableSortHelper ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const T &  dummy 
)
inline

Definition at line 463 of file qalgorithms.h.

Referenced by qStableSortHelper().

464 {
465  qStableSortHelper(begin, end, dummy, qLess<T>());
466 }
void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &)
Definition: qalgorithms.h:463
static const KeyPair *const end

◆ qUpperBoundHelper()

template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator QAlgorithmsPrivate::qUpperBoundHelper ( RandomAccessIterator  begin,
RandomAccessIterator  end,
const T &  value,
LessThan  lessThan 
)

Definition at line 490 of file qalgorithms.h.

Referenced by qUpperBound().

491 {
492  RandomAccessIterator middle;
493  int n = end - begin;
494  int half;
495 
496  while (n > 0) {
497  half = n >> 1;
498  middle = begin + half;
499  if (lessThan(value, *middle)) {
500  n = half;
501  } else {
502  begin = middle + 1;
503  n -= half + 1;
504  }
505  }
506  return begin;
507 }
static bool lessThan(const QChar *a, int l, const char *c)
Definition: qurl.cpp:3253
static const KeyPair *const end