- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- Namespace List
- Namespace Members

Functions

# QAlgorithmsPrivate Namespace Reference

## Functions
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 | qLowerBoundHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator | qUpperBoundHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
template<typename RandomAccessIterator , typename T , typename LessThan >
Q_OUTOFLINE_TEMPLATE RandomAccessIterator | qBinaryFindHelper (RandomAccessIterator begin, RandomAccessIterator end, const T &value, 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 | qMerge (RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)

## Function Documentation

Q_OUTOFLINE_TEMPLATE void qSortHelper | ( | RandomAccessIterator | start,
|  | RandomAccessIterator | end,
|  | const T & | t,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 340 of file qalgorithms.h.

    {
    top:
        int span = int(end - start);
        if (span < 2)
            return;

        --end;
        RandomAccessIterator low = start, high = end - 1;
        RandomAccessIterator pivot = start + span / 2;

        if (lessThan(*end, *start))
            qSwap(*end, *start);
        if (span == 2)
            return;

        if (lessThan(*pivot, *start))
            qSwap(*pivot, *start);
        if (lessThan(*end, *pivot))
            qSwap(*end, *pivot);
        if (span == 3)
            return;

        qSwap(*pivot, *end);

        while (low < high) {
            while (low < high && lessThan(*low, *end))
                ++low;

            while (high > low && lessThan(*end, *high))
                --high;

            if (low < high) {
                qSwap(*low, *high);
                ++low;
                --high;
            } else {
                break;
            }
        }

        if (lessThan(*low, *end))
            ++low;

        qSwap(*end, *low);
        qSortHelper(start, low, t, lessThan);

        start = low + 1;
        ++end;
        goto top;
    }

void qSortHelper | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end,
|  | const T & | dummy
| ) |  | `[inline]`

Search for all occurrences

Definition at line 393 of file qalgorithms.h.

    {
        qSortHelper(begin, end, dummy, qLess<T>());
    }

Q_OUTOFLINE_TEMPLATE void qStableSortHelper | ( | RandomAccessIterator | start,
|  | RandomAccessIterator | end,
|  | const T & | t,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 450 of file qalgorithms.h.

    {
        const int span = end - begin;
        if (span < 2)
           return;

        const RandomAccessIterator middle = begin + span / 2;
        qStableSortHelper(begin, middle, t, lessThan);
        qStableSortHelper(middle, end, t, lessThan);
        qMerge(begin, middle, end, t, lessThan);
    }

void qStableSortHelper | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end,
|  | const T & | dummy
| ) |  | `[inline]`

Search for all occurrences

Definition at line 463 of file qalgorithms.h.

    {
        qStableSortHelper(begin, end, dummy, qLess<T>());
    }

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end,
|  | const T & | value,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 469 of file qalgorithms.h.

    {
        RandomAccessIterator middle;
        int n = int(end - begin);
        int half;

        while (n > 0) {
            half = n >> 1;
            middle = begin + half;
            if (lessThan(*middle, value)) {
                begin = middle + 1;
                n -= half + 1;
            } else {
                n = half;
            }
        }
        return begin;
    }

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end,
|  | const T & | value,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 490 of file qalgorithms.h.

    {
        RandomAccessIterator middle;
        int n = end - begin;
        int half;

        while (n > 0) {
            half = n >> 1;
            middle = begin + half;
            if (lessThan(value, *middle)) {
                n = half;
            } else {
                begin = middle + 1;
                n -= half + 1;
            }
        }
        return begin;
    }

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end,
|  | const T & | value,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 510 of file qalgorithms.h.

    {
        RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);

        if (it == end || lessThan(value, *it))
            return end;

        return it;
    }

Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qReverse | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | end
| ) |  |

Search for all occurrences

Definition at line 399 of file qalgorithms.h.

    {
        --end;
        while (begin < end)
            qSwap(*begin++, *end--);
    }

Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qRotate | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | middle,
|  | RandomAccessIterator | end
| ) |  |

Search for all occurrences

Definition at line 407 of file qalgorithms.h.

    {
        qReverse(begin, middle);
        qReverse(middle, end);
        qReverse(begin, end);
    }

Q_OUTOFLINE_TEMPLATE void QAlgorithmsPrivate::qMerge | ( | RandomAccessIterator | begin,
|  | RandomAccessIterator | pivot,
|  | RandomAccessIterator | end,
|  | T & | t,
|  | LessThan | lessThan
| ) |  |

Search for all occurrences

Definition at line 415 of file qalgorithms.h.

    {
        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 = qLowerBound(pivot, end, *firstCut, lessThan);
            len2Half = secondCut - pivot;
        } else {
            len2Half = len2 / 2;
            secondCut = pivot + len2Half;
            firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
        }

        qRotate(firstCut, pivot, secondCut);
        const RandomAccessIterator newPivot = firstCut + len2Half;
        qMerge(begin, firstCut, newPivot, t, lessThan);
        qMerge(newPivot, secondCut, end, t, lessThan);
    }