One SkTSearch to rule them all. Allow key to be of different type than the array.

include/core/SkTSearch.h

Index: include/core/SkTSearch.h
diff --git a/include/core/SkTSearch.h b/include/core/SkTSearch.h
index eaf5ee5934941e2552b6b519369854c7835b15d2..57de6a4ae852f82adca5c715f1ed15b77b680cbd 100644
--- a/include/core/SkTSearch.h
+++ b/include/core/SkTSearch.h
@@ -30,41 +30,13 @@
  *  }
  */
 
-template <typename T>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
-
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = (const T*)((const char*)base + mid * elemSize);
 
-        if (*elem < target)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = (const T*)((const char*)base + hi * elemSize);
-    if (*elem != target)
-    {
-        if (*elem < target)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
-}
-
-template <typename T, int (COMPARE)(const T*, const T*)>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
+// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
+// used to perform comparisons. It has two function operators:
+//      bool operator() (const T& t, const K& k)
+//      bool operator() (const K& t, const T& k)
+template <typename T, typename K, typename LESS>
+int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
 {
     SkASSERT(count >= 0);
     if (count <= 0) {
@@ -80,124 +52,66 @@ int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
         int mid = (hi + lo) >> 1;
         const T* elem = (const T*)((const char*)base + mid * elemSize);
 
-        if (COMPARE(elem, &target) < 0)
+        if (less(*elem, key))
             lo = mid + 1;
         else
             hi = mid;
     }
 
     const T* elem = (const T*)((const char*)base + hi * elemSize);
-    int pred = COMPARE(elem, &target);
-    if (pred != 0) {
-        if (pred < 0)
-            hi += 1;
+    if (less(*elem, key)) {
+        hi += 1;
         hi = ~hi;
-    }
-    return hi;
-}
-
-template <typename T>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
-              int (*compare)(const T*, const T*))
-{
-    SkASSERT(count >= 0);
-    if (count <= 0) {
-        return ~0;
-    }
-
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi) {
-        int mid = (hi + lo) >> 1;
-        const T* elem = (const T*)((const char*)base + mid * elemSize);
-
-        if ((*compare)(elem, &target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = (const T*)((const char*)base + hi * elemSize);
-    int pred = (*compare)(elem, &target);
-    if (pred != 0) {
-        if (pred < 0)
-            hi += 1;
+    } else if (less(key, *elem)) {
         hi = ~hi;
     }
     return hi;
 }
 
-template <typename T>
-int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
-    int (*compare)(const T*, const T*))
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
-
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = *(const T**)((const char*)base + mid * elemSize);
-
-        if ((*compare)(elem, target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
+// Adapts a less-than function to a functor.
+template <typename T, bool (LESS)(const T&, const T&)>
+class SkTLessFunctionToFunctorAdaptor {

[bungeman-skia, 2013/05/16 22:00:39]

If this were a struct there would be no need for the 'public' on the next line.

[bsalomon, 2013/05/17 14:24:30]

Done.

+public:
+    bool operator()(const T& a, const T& b) { return LESS(a, b); }
+};
 
-    const T* elem = *(const T**)((const char*)base + hi * elemSize);
-    int pred = (*compare)(elem, target);
-    if (pred != 0)
-    {
-        if (pred < 0)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
+// Specialization for case when T==K and the caller wants to use a function rather than functor.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    typedef SkTLessFunctionToFunctorAdaptor<T, LESS> Functor;
+    Functor functor;
+    return SkTSearch<T, T, Functor>(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

I think this can just be

return SkTSearch(base, count, target, elemSize, Functor());

and the previous line removed. All of the function template parameters should be
inferred.

Actually the line

return SkTSearch(base, count, target, elemSize,
SkTLessFunctionToFunctorAdaptor<T, LESS>());

appears to be 97 characters (after adding the four leading spaces). This allows
this function to be one line.

[bsalomon, 2013/05/17 14:24:30]

Done.

 }
 
-template <typename T,  int (COMPARE)(const T*, const T*)>
-int SkTSearch(const T** base, int count, const T* target, size_t elemSize)
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
-
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
+// Adapts operator < to a functor.
+template <typename T> struct SkTLessFunctor {
+public:

[bungeman-skia, 2013/05/16 22:00:39]

nit: This is a struct, so public is already implied.

[bsalomon, 2013/05/17 14:24:30]

Done.

+    bool operator()(const T& a, const T& b) { return a < b; }
+};
 
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = *(const T**)((const char*)base + mid * elemSize);
+// Specialization for T==K, compare using op <.
+template <typename T>
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    SkTLessFunctor<T> functor;
+    return SkTSearch<T, T, SkTLessFunctor<T> >(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

This line can probably be

return SkTSearch(base, count, target, elemSize, SkTLessFunctor<T>());

and the previous line removed.

I wonder if this helps with the 'const' issues, since the compiler will be the
one figuring out the types.

[bsalomon, 2013/05/17 14:24:30]

Done. I'll leave fighting the const battle for another day ( or at least another
changelist).

+}
 
-        if (COMPARE(elem, target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
+// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
+template <typename T, bool (LESS)(const T&, const T&)>
+class SkTLessFunctionToPtrFunctorAdaptor {

[bungeman-skia, 2013/05/16 22:00:39]

If this were a struct there would be no need for the 'public' on the next line.

[bsalomon, 2013/05/17 14:24:30]

Done.

+public:
+    bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
+};
 
-    const T* elem = *(const T**)((const char*)base + hi * elemSize);
-    int pred = COMPARE(elem, target);
-    if (pred != 0)
-    {
-        if (pred < 0)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
+// Specialization for case where domain is an array of T* and the key value is a T*, and you want
+// to compare the T objects, not the pointers.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
+    typedef SkTLessFunctionToPtrFunctorAdaptor<T, LESS> Functor;
+    Functor functor;
+    return SkTSearch<T*, T*, Functor>(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

Likewise, this line can probably be

return SkTSearch(base, count, target, elemSize,
SkTLessFunctionToPtrFunctorAdaptor<T, LESS>());

for a single line (exactly 100 columns with the four leading spaces).

[bsalomon, 2013/05/17 14:24:30]

Actually only 99!

 }
+
 int SkStrSearch(const char*const* base, int count, const char target[],
                 size_t target_len, size_t elemSize);
 int SkStrSearch(const char*const* base, int count, const char target[],