1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#ifndef TSearch_DEFINED
8#define TSearch_DEFINED
9
10// FIXME: Move this templated version into SKTSearch.h
11
12template <typename T>
13static T* QSort_Partition(T* left, T* right, T* pivot)
14{
15    T pivotValue = *pivot;
16    SkTSwap(*pivot, *right);
17    T* newPivot = left;
18    while (left < right) {
19        if (*left < pivotValue) {
20            SkTSwap(*left, *newPivot);
21            newPivot += 1;
22        }
23        left += 1;
24    }
25    SkTSwap(*newPivot, *right);
26    return newPivot;
27}
28
29template <typename T>
30void QSort(T* left, T* right)
31{
32    if (left >= right) {
33        return;
34    }
35    T* pivot = left + (right - left >> 1);
36    pivot = QSort_Partition(left, right, pivot);
37    QSort(left, pivot - 1);
38    QSort(pivot + 1, right);
39}
40
41template <typename T>
42static T** QSort_Partition(T** left, T** right, T** pivot)
43{
44    T* pivotValue = *pivot;
45    SkTSwap(*pivot, *right);
46    T** newPivot = left;
47    while (left < right) {
48        if (**left < *pivotValue) {
49            SkTSwap(*left, *newPivot);
50            newPivot += 1;
51        }
52        left += 1;
53    }
54    SkTSwap(*newPivot, *right);
55    return newPivot;
56}
57
58template <typename T>
59void QSort(T** left, T** right)
60{
61    if (left >= right) {
62        return;
63    }
64    T** pivot = left + (right - left >> 1);
65    pivot = QSort_Partition(left, right, pivot);
66    QSort(left, pivot - 1);
67    QSort(pivot + 1, right);
68}
69
70template <typename S, typename T>
71static T* QSort_Partition(S& context, T* left, T* right, T* pivot,
72        bool (*lessThan)(S&, const T, const T))
73{
74    T pivotValue = *pivot;
75    SkTSwap(*pivot, *right);
76    T* newPivot = left;
77    while (left < right) {
78        if (lessThan(context, *left, pivotValue)) {
79            SkTSwap(*left, *newPivot);
80            newPivot += 1;
81        }
82        left += 1;
83    }
84    SkTSwap(*newPivot, *right);
85    return newPivot;
86}
87
88template <typename S, typename T>
89void QSort(S& context, T* left, T* right,
90        bool (*lessThan)(S& , const T, const T))
91{
92    if (left >= right) {
93        return;
94    }
95    T* pivot = left + (right - left >> 1);
96    pivot = QSort_Partition(context, left, right, pivot, lessThan);
97    QSort(context, left, pivot - 1, lessThan);
98    QSort(context, pivot + 1, right, lessThan);
99}
100
101#endif
102