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)

---

Function Documentation

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 486 of file qalgorithms.h.

References i, and l.

Referenced by qBinaryFind().

{
    int l = 0;
    int r = end - begin - 1;
    if (r < 0)
        return end;
    int i = (l + r + 1) / 2;

    while (r != l) {
        if (lessThan(value, begin[i]))
            r = i - 1;
        else
            l = i;
        i = (l + r + 1) / 2;
    }
    if (lessThan(begin[i], value) || lessThan(value, begin[i]))
        return end;
    else
        return begin + i;
}

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 445 of file qalgorithms.h.

References n.

Referenced by qLowerBound().

{
    RandomAccessIterator middle;
    int n = 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;
}

template<typename RandomAccessIterator, typename T>

void QAlgorithmsPrivate::qSortHelper	(	RandomAccessIterator	begin,
		RandomAccessIterator	end,
		const T &	dummy
	)			[inline]

Definition at line 399 of file qalgorithms.h.

References qSortHelper().

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

Here is the call graph for this function:

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 346 of file qalgorithms.h.

References qSwap().

Referenced by qSort(), and qSortHelper().

{
top:
    int span = 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;
}

Here is the call graph for this function:

template<typename RandomAccessIterator, typename T>

void QAlgorithmsPrivate::qStableSortHelper	(	RandomAccessIterator	,
		RandomAccessIterator	,
		const T &
	)			[inline]

Definition at line 439 of file qalgorithms.h.

References qStableSortHelper().

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

Here is the call graph for this function:

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 405 of file qalgorithms.h.

References i, T, and value.

Referenced by qStableSort(), and qStableSortHelper().

{
    const int span = end - start;
    if (span < 2)
       return;
        
    // Split in half and sort halves.
    RandomAccessIterator middle = start + span / 2;
    qStableSortHelper(start, middle, t, lessThan);
    qStableSortHelper(middle, end, t, lessThan);
    
    // Merge
    RandomAccessIterator lo = start;
    RandomAccessIterator hi = middle;
    
    while (lo != middle && hi != end) {
        if (!lessThan(*hi, *lo)) {
            ++lo; // OK, *lo is in its correct position
        } else {
            // Move *hi to lo's position, shift values
            // between lo and hi - 1 one place up.
            T value = *hi;
            for (RandomAccessIterator i = hi; i != lo; --i) {
                *i = *(i-1); 
            }
            *lo = value;
            ++hi;
            ++lo;
            ++middle;
        } 
    }
}

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 466 of file qalgorithms.h.

References n.

Referenced by qUpperBound().

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

---