Bumping manifests a=b2g-bump
[gecko.git] / mfbt / BinarySearch.h
blob676b82e416c508eaf5cee7dd18b231dfb35dc0b5
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef mozilla_BinarySearch_h
8 #define mozilla_BinarySearch_h
10 #include "mozilla/Assertions.h"
12 #include <stddef.h>
14 namespace mozilla {
17 * The BinarySearch() algorithm searches the given container |aContainer| over
18 * the sorted index range [aBegin, aEnd) for an index |i| where
19 * |aContainer[i] == aTarget|.
20 * If such an index |i| is found, BinarySearch returns |true| and the index is
21 * returned via the outparam |aMatchOrInsertionPoint|. If no index is found,
22 * BinarySearch returns |false| and the outparam returns the first index in
23 * [aBegin, aEnd] where |aTarget| can be inserted to maintain sorted order.
25 * Example:
27 * Vector<int> sortedInts = ...
29 * size_t match;
30 * if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
31 * printf("found 13 at %lu\n", match);
32 * }
34 * The BinarySearchIf() version behaves similar, but takes |aComparator|, a
35 * functor to compare the values with, instead of a value to find.
36 * That functor should take one argument - the value to compare - and return an
37 * |int| with the comparison result:
39 * * 0, if the argument is equal to,
40 * * less than 0, if the argument is greater than,
41 * * greater than 0, if the argument is less than
43 * the value.
45 * Example:
47 * struct Comparator {
48 * int operator()(int val) const {
49 * if (mTarget < val) return -1;
50 * if (mValue > val) return 1;
51 * return 0;
52 * }
53 * Comparator(int target) : mTarget(target) {}
54 const int mTarget;
55 * };
57 * Vector<int> sortedInts = ...
59 * size_t match;
60 * if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13), &match)) {
61 * printf("found 13 at %lu\n", match);
62 * }
66 template<typename Container, typename Comparator>
67 bool
68 BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
69 const Comparator& aCompare, size_t* aMatchOrInsertionPoint)
71 MOZ_ASSERT(aBegin <= aEnd);
73 size_t low = aBegin;
74 size_t high = aEnd;
75 while (high != low) {
76 size_t middle = low + (high - low) / 2;
78 // Allow any intermediate type so long as it provides a suitable ordering
79 // relation.
80 const int result = aCompare(aContainer[middle]);
82 if (result == 0) {
83 *aMatchOrInsertionPoint = middle;
84 return true;
87 if (result < 0) {
88 high = middle;
89 } else {
90 low = middle + 1;
94 *aMatchOrInsertionPoint = low;
95 return false;
98 namespace detail {
100 template<class T>
101 class BinarySearchDefaultComparator
103 public:
104 BinarySearchDefaultComparator(const T& aTarget)
105 : mTarget(aTarget)
108 template <class U>
109 int operator()(const U& val) const {
110 if (mTarget == val) {
111 return 0;
114 if (mTarget < val) {
115 return -1;
118 return 1;
121 private:
122 const T& mTarget;
125 } // namespace detail
127 template <typename Container, typename T>
128 bool
129 BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
130 T aTarget, size_t* aMatchOrInsertionPoint)
132 return BinarySearchIf(aContainer, aBegin, aEnd,
133 detail::BinarySearchDefaultComparator<T>(aTarget),
134 aMatchOrInsertionPoint);
137 } // namespace mozilla
139 #endif // mozilla_BinarySearch_h