SkTSort.h File Reference

#include "include/private/base/SkTo.h"
#include "src/base/SkMathPriv.h"
#include <cstddef>
#include <utility>

Go to the source code of this file.

Functions
template<typename T , typename C >
void	SkTHeapSort_SiftUp (T array[], size_t root, size_t bottom, const C &lessThan)
template<typename T , typename C >
void	SkTHeapSort_SiftDown (T array[], size_t root, size_t bottom, const C &lessThan)
template<typename T , typename C >
void	SkTHeapSort (T array[], size_t count, const C &lessThan)
template<typename T >
void	SkTHeapSort (T array[], size_t count)
template<typename T , typename C >
void	SkTInsertionSort (T *left, int count, const C &lessThan)
template<typename T , typename C >
T *	SkTQSort_Partition (T *left, int count, T *pivot, const C &lessThan)
template<typename T , typename C >
void	SkTIntroSort (int depth, T *left, int count, const C &lessThan)
template<typename T , typename C >
void	SkTQSort (T *begin, T *end, const C &lessThan)
template<typename T >
void	SkTQSort (T *begin, T *end)
template<typename T >
void	SkTQSort (T **begin, T **end)

Function Documentation

SkTHeapSort() [1/2]

template<typename T >

void SkTHeapSort	(	T	array[],
		size_t	count
	)

Sorts the array of size count using comparator '<' using a Heap Sort algorithm.

Definition at line 106 of file SkTSort.h.

                                                                {
    SkTHeapSort(array, count, [](const T& a, const T& b) { return a < b; });
}

SkTHeapSort() [2/2]

template<typename T , typename C >

void SkTHeapSort	(	T	array[],
		size_t	count,
		const C &	lessThan
	)

Sorts the array of size count using comparator lessThan using a Heap Sort algorithm. Be sure to specialize swap if T has an efficient swap operation.

Parameters

array	the array to be sorted.
count	the number of elements in the array.
lessThan	a functor with bool operator()(T a, T b) which returns true if a comes before b.

Definition at line 93 of file SkTSort.h.

                                                                                               {
    for (size_t i = count >> 1; i > 0; --i) {
        SkTHeapSort_SiftDown(array, i, count, lessThan);
    }
 
    for (size_t i = count - 1; i > 0; --i) {
        using std::swap;
        swap(array[0], array[i]);
        SkTHeapSort_SiftUp(array, 1, i, lessThan);
    }
}

SkTHeapSort_SiftDown()

template<typename T , typename C >

void SkTHeapSort_SiftDown	(	T	array[],
		size_t	root,
		size_t	bottom,
		const C &	lessThan
	)

Definition at line 68 of file SkTSort.h.

                                                                                    {
    T x = array[root-1];
    size_t child = root << 1;
    while (child <= bottom) {
        if (child < bottom && lessThan(array[child-1], array[child])) {
            ++child;
        }
        if (lessThan(x, array[child-1])) {
            array[root-1] = array[child-1];
            root = child;
            child = root << 1;
        } else {
            break;
        }
    }
    array[root-1] = x;
}

SkTHeapSort_SiftUp()

template<typename T , typename C >

void SkTHeapSort_SiftUp	(	T	array[],
		size_t	root,
		size_t	bottom,
		const C &	lessThan
	)

Definition at line 34 of file SkTSort.h.

                                                                                  {
    T x = array[root-1];
    size_t start = root;
    size_t j = root << 1;
    while (j <= bottom) {
        if (j < bottom && lessThan(array[j-1], array[j])) {
            ++j;
        }
        array[root-1] = array[j-1];
        root = j;
        j = root << 1;
    }
    j = root >> 1;
    while (j >= start) {
        if (lessThan(array[j-1], x)) {
            array[root-1] = array[j-1];
            root = j;
            j = root >> 1;
        } else {
            break;
        }
    }
    array[root-1] = x;
}

SkTInsertionSort()

template<typename T , typename C >

void SkTInsertionSort	(	T *	left,
		int	count,
		const C &	lessThan
	)

Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm.

Definition at line 114 of file SkTSort.h.

                                                             {
    T* right = left + count - 1;
    for (T* next = left + 1; next <= right; ++next) {
        if (!lessThan(*next, *(next - 1))) {
            continue;
        }
        T insert = std::move(*next);
        T* hole = next;
        do {
            *hole = std::move(*(hole - 1));
            --hole;
        } while (left < hole && lessThan(insert, *(hole - 1)));
        *hole = std::move(insert);
    }
}

SkTIntroSort()

template<typename T , typename C >

void SkTIntroSort	(	int	depth,
		T *	left,
		int	count,
		const C &	lessThan
	)

Definition at line 163 of file SkTSort.h.

                                                                    {
    for (;;) {
        if (count <= 32) {
            SkTInsertionSort(left, count, lessThan);
            return;
        }
 
        if (depth == 0) {
            SkTHeapSort<T>(left, count, lessThan);
            return;
        }
        --depth;
 
        T* middle = left + ((count - 1) >> 1);
        T* pivot = SkTQSort_Partition(left, count, middle, lessThan);
        int pivotCount = pivot - left;
 
        SkTIntroSort(depth, left, pivotCount, lessThan);
        left += pivotCount + 1;
        count -= pivotCount + 1;
    }
}

SkTQSort() [1/3]

template<typename T >

void SkTQSort	(	T **	begin,
		T **	end
	)

Sorts the region from left to right using comparator '*a < *b' using Introsort.

Definition at line 210 of file SkTSort.h.

                                                        {
    SkTQSort(begin, end, [](const T* a, const T* b) { return *a < *b; });
}

SkTQSort() [2/3]

template<typename T >

void SkTQSort	(	T *	begin,
		T *	end
	)

Sorts the region from left to right using comparator 'a < b' using Introsort.

Definition at line 205 of file SkTSort.h.

                                                      {
    SkTQSort(begin, end, [](const T& a, const T& b) { return a < b; });
}

SkTQSort() [3/3]

template<typename T , typename C >

void SkTQSort	(	T *	begin,
		T *	end,
		const C &	lessThan
	)

Sorts the region from left to right using comparator lessThan using Introsort. Be sure to specialize swap if T has an efficient swap operation.

Parameters

begin	points to the beginning of the region to be sorted
end	points past the end of the region to be sorted
lessThan	a functor/lambda which returns true if a comes before b.

Definition at line 194 of file SkTSort.h.

                                                   {
    int n = SkToInt(end - begin);
    if (n <= 1) {
        return;
    }
    // Limit Introsort recursion depth to no more than 2 * ceil(log2(n-1)).
    int depth = 2 * SkNextLog2(n - 1);
    SkTIntroSort(depth, begin, n, lessThan);
}

SkTQSort_Partition()

template<typename T , typename C >

T * SkTQSort_Partition	(	T *	left,
		int	count,
		T *	pivot,
		const C &	lessThan
	)

Definition at line 133 of file SkTSort.h.

                                                                       {
    T* right = left + count - 1;
    using std::swap;
    T pivotValue = *pivot;
    swap(*pivot, *right);
    T* newPivot = left;
    while (left < right) {
        if (lessThan(*left, pivotValue)) {
            swap(*left, *newPivot);
            newPivot += 1;
        }
        left += 1;
    }
    swap(*newPivot, *right);
    return newPivot;
}