1/*
2 * Copyright 2010 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
8#ifndef GrTBSearch_DEFINED
9#define GrTBSearch_DEFINED
10
11#include "SkTypes.h"
12
13template <typename ELEM, typename KEY>
14int GrTBSearch(const ELEM array[], int count, KEY target) {
15    SkASSERT(count >= 0);
16    if (0 == count) {
17        // we should insert it at 0
18        return ~0;
19    }
20
21    int high = count - 1;
22    int low = 0;
23    while (high > low) {
24        int index = (low + high) >> 1;
25        if (LT(array[index], target)) {
26            low = index + 1;
27        } else {
28            high = index;
29        }
30    }
31
32    // check if we found it
33    if (EQ(array[high], target)) {
34        return high;
35    }
36
37    // now return the ~ of where we should insert it
38    if (LT(array[high], target)) {
39        high += 1;
40    }
41    return ~high;
42}
43
44#endif
45