michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #ifndef SkTSearch_DEFINED
michael@0: #define SkTSearch_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: /**
michael@0:  *  All of the SkTSearch variants want to return the index (0...N-1) of the
michael@0:  *  found element, or the bit-not of where to insert the element.
michael@0:  *
michael@0:  *  At a simple level, if the return value is negative, it was not found.
michael@0:  *
michael@0:  *  For clients that want to insert the new element if it was not found, use
michael@0:  *  the following logic:
michael@0:  *
michael@0:  *  int index = SkTSearch(...);
michael@0:  *  if (index >= 0) {
michael@0:  *      // found at index
michael@0:  *  } else {
michael@0:  *      index = ~index; // now we are positive
michael@0:  *      // insert at index
michael@0:  *  }
michael@0:  */
michael@0: 
michael@0: 
michael@0: // The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
michael@0: // used to perform comparisons. It has two function operators:
michael@0: //      bool operator() (const T& t, const K& k)
michael@0: //      bool operator() (const K& t, const T& k)
michael@0: template <typename T, typename K, typename LESS>
michael@0: int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
michael@0: {
michael@0:     SkASSERT(count >= 0);
michael@0:     if (count <= 0) {
michael@0:         return ~0;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(base != NULL); // base may be NULL if count is zero
michael@0: 
michael@0:     int lo = 0;
michael@0:     int hi = count - 1;
michael@0: 
michael@0:     while (lo < hi) {
michael@0:         int mid = (hi + lo) >> 1;
michael@0:         const T* elem = (const T*)((const char*)base + mid * elemSize);
michael@0: 
michael@0:         if (less(*elem, key))
michael@0:             lo = mid + 1;
michael@0:         else
michael@0:             hi = mid;
michael@0:     }
michael@0: 
michael@0:     const T* elem = (const T*)((const char*)base + hi * elemSize);
michael@0:     if (less(*elem, key)) {
michael@0:         hi += 1;
michael@0:         hi = ~hi;
michael@0:     } else if (less(key, *elem)) {
michael@0:         hi = ~hi;
michael@0:     }
michael@0:     return hi;
michael@0: }
michael@0: 
michael@0: // Adapts a less-than function to a functor.
michael@0: template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
michael@0:     bool operator()(const T& a, const T& b) { return LESS(a, b); }
michael@0: };
michael@0: 
michael@0: // Specialization for case when T==K and the caller wants to use a function rather than functor.
michael@0: template <typename T, bool (LESS)(const T&, const T&)>
michael@0: int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
michael@0:     static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
michael@0:     return SkTSearch(base, count, target, elemSize, functor);
michael@0: }
michael@0: 
michael@0: // Adapts operator < to a functor.
michael@0: template <typename T> struct SkTLessFunctor {
michael@0:     bool operator()(const T& a, const T& b) { return a < b; }
michael@0: };
michael@0: 
michael@0: // Specialization for T==K, compare using op <.
michael@0: template <typename T>
michael@0: int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
michael@0:     static SkTLessFunctor<T> functor;
michael@0:     return SkTSearch(base, count, target, elemSize, functor);
michael@0: }
michael@0: 
michael@0: // Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
michael@0: template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
michael@0:     bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
michael@0: };
michael@0: 
michael@0: // Specialization for case where domain is an array of T* and the key value is a T*, and you want
michael@0: // to compare the T objects, not the pointers.
michael@0: template <typename T, bool (LESS)(const T&, const T&)>
michael@0: int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
michael@0:     static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
michael@0:     return SkTSearch(base, count, target, elemSize, functor);
michael@0: }
michael@0: 
michael@0: int SkStrSearch(const char*const* base, int count, const char target[],
michael@0:                 size_t target_len, size_t elemSize);
michael@0: int SkStrSearch(const char*const* base, int count, const char target[],
michael@0:                 size_t elemSize);
michael@0: 
michael@0: /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
michael@0:     base points to a table of lower-case strings.
michael@0: */
michael@0: int SkStrLCSearch(const char*const* base, int count, const char target[],
michael@0:                   size_t target_len, size_t elemSize);
michael@0: int SkStrLCSearch(const char*const* base, int count, const char target[],
michael@0:                   size_t elemSize);
michael@0: 
michael@0: /** Helper class to convert a string to lower-case, but only modifying the ascii
michael@0:     characters. This makes the routine very fast and never changes the string
michael@0:     length, but it is not suitable for linguistic purposes. Normally this is
michael@0:     used for buiding and searching string tables.
michael@0: */
michael@0: class SkAutoAsciiToLC {
michael@0: public:
michael@0:     SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
michael@0:     ~SkAutoAsciiToLC();
michael@0: 
michael@0:     const char* lc() const { return fLC; }
michael@0:     size_t      length() const { return fLength; }
michael@0: 
michael@0: private:
michael@0:     char*   fLC;    // points to either the heap or fStorage
michael@0:     size_t  fLength;
michael@0:     enum {
michael@0:         STORAGE = 64
michael@0:     };
michael@0:     char    fStorage[STORAGE+1];
michael@0: };
michael@0: 
michael@0: // Helper when calling qsort with a compare proc that has typed its arguments
michael@0: #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
michael@0: 
michael@0: #endif