chromium/third_party/skia/src/base/SkTSort.h

/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkTSort_DEFINED
#define SkTSort_DEFINED

#include "include/private/base/SkTo.h"
#include "src/base/SkMathPriv.h"

#include <cstddef>
#include <utility>

///////////////////////////////////////////////////////////////////////////////

/*  Sifts a broken heap. The input array is a heap from root to bottom
 *  except that the root entry may be out of place.
 *
 *  Sinks a hole from array[root] to leaf and then sifts the original array[root] element
 *  from the leaf level up.
 *
 *  This version does extra work, in that it copies child to parent on the way down,
 *  then copies parent to child on the way back up. When copies are inexpensive,
 *  this is an optimization as this sift variant should only be used when
 *  the potentially out of place root entry value is expected to be small.
 *
 *  @param root the one based index into array of the out-of-place root of the heap.
 *  @param bottom the one based index in the array of the last entry in the heap.
 */
template <typename T, typename C>
void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, const C& lessThan) { … }

/*  Sifts a broken heap. The input array is a heap from root to bottom
 *  except that the root entry may be out of place.
 *
 *  Sifts the array[root] element from the root down.
 *
 *  @param root the one based index into array of the out-of-place root of the heap.
 *  @param bottom the one based index in the array of the last entry in the heap.
 */
template <typename T, typename C>
void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, 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.
 *
 *  @param array the array to be sorted.
 *  @param count the number of elements in the array.
 *  @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
 */
template <typename T, typename C> void SkTHeapSort(T array[], size_t count, const C& lessThan) { … }

/** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */
template <typename T> void SkTHeapSort(T array[], size_t count) { … }

///////////////////////////////////////////////////////////////////////////////

/** Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm. */
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) { … }

/*  Introsort is a modified Quicksort.
 *  When the region to be sorted is a small constant size, it uses Insertion Sort.
 *  When depth becomes zero, it switches over to Heap Sort.
 *  This implementation recurses on the left region after pivoting and loops on the right,
 *    we already limit the stack depth by switching to heap sort,
 *    and cache locality on the data appears more important than saving a few stack frames.
 *
 *  @param depth at this recursion depth, switch to Heap Sort.
 *  @param left points to the beginning of the region to be sorted
 *  @param count number of items to be sorted
 *  @param lessThan  a functor/lambda which returns true if a comes before b.
 */
template <typename T, typename C>
void SkTIntroSort(int depth, T* left, int count, 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.
 *
 *  @param begin points to the beginning of the region to be sorted
 *  @param end points past the end of the region to be sorted
 *  @param lessThan a functor/lambda which returns true if a comes before b.
 */
template <typename T, typename C>
void SkTQSort(T* begin, T* end, const C& lessThan) { … }

/** Sorts the region from left to right using comparator 'a < b' using Introsort. */
template <typename T> void SkTQSort(T* begin, T* end) { … }

/** Sorts the region from left to right using comparator '*a < *b' using Introsort. */
template <typename T> void SkTQSort(T** begin, T** end) { … }

#endif