Home | History | Annotate | Download | only in Intersection 
      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 
     12 template <typename T>
     13 static 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 
     29 template <typename T>
     30 void 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 
     41 template <typename T>
     42 static 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 
     58 template <typename T>
     59 void 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 
     70 template <typename S, typename T>
     71 static 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 
     88 template <typename S, typename T>
     89 void 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