michael@0: /*
michael@0:  * Copyright 2010 Google Inc.
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: #ifndef GrTBSearch_DEFINED
michael@0: #define GrTBSearch_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: 
michael@0: template <typename ELEM, typename KEY>
michael@0: int GrTBSearch(const ELEM array[], int count, KEY target) {
michael@0:     SkASSERT(count >= 0);
michael@0:     if (0 == count) {
michael@0:         // we should insert it at 0
michael@0:         return ~0;
michael@0:     }
michael@0: 
michael@0:     int high = count - 1;
michael@0:     int low = 0;
michael@0:     while (high > low) {
michael@0:         int index = (low + high) >> 1;
michael@0:         if (LT(array[index], target)) {
michael@0:             low = index + 1;
michael@0:         } else {
michael@0:             high = index;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // check if we found it
michael@0:     if (EQ(array[high], target)) {
michael@0:         return high;
michael@0:     }
michael@0: 
michael@0:     // now return the ~ of where we should insert it
michael@0:     if (LT(array[high], target)) {
michael@0:         high += 1;
michael@0:     }
michael@0:     return ~high;
michael@0: }
michael@0: 
michael@0: #endif