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
	)

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

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
	)

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

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
	)

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
	)

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
	)

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
	)

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
	)

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
	)

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);
}