mfbt/BinarySearch.h

   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/. */
   6
   7 #ifndef mozilla_BinarySearch_h
   8 #define mozilla_BinarySearch_h
   9
  10 #include "mozilla/Assertions.h"
  11 #include "mozilla/CompactPair.h"
  12
  13 #include <stddef.h>
  14
  15 namespace mozilla {
  16
  17 /*
  18  * The BinarySearch() algorithm searches the given container |aContainer| over
  19  * the sorted index range [aBegin, aEnd) for an index |i| where
  20  * |aContainer[i] == aTarget|.
  21  * If such an index |i| is found, BinarySearch returns |true| and the index is
  22  * returned via the outparam |aMatchOrInsertionPoint|. If no index is found,
  23  * BinarySearch returns |false| and the outparam returns the first index in
  24  * [aBegin, aEnd] where |aTarget| can be inserted to maintain sorted order.
  25  *
  26  * Example:
  27  *
  28  *   Vector<int> sortedInts = ...
  29  *
  30  *   size_t match;
  31  *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
  32  *     printf("found 13 at %lu\n", match);
  33  *   }
  34  *
  35  * The BinarySearchIf() version behaves similarly, but takes |aComparator|, a
  36  * functor to compare the values with, instead of a value to find.
  37  * That functor should take one argument - the value to compare - and return an
  38  * |int| with the comparison result:
  39  *
  40  *   * 0, if the argument is equal to,
  41  *   * less than 0, if the argument is greater than,
  42  *   * greater than 0, if the argument is less than
  43  *
  44  * the value.
  45  *
  46  * Example:
  47  *
  48  *   struct Comparator {
  49  *     int operator()(int aVal) const {
  50  *       if (mTarget < aVal) { return -1; }
  51  *       if (mTarget > aVal) { return 1; }
  52  *       return 0;
  53  *     }
  54  *     explicit Comparator(int aTarget) : mTarget(aTarget) {}
  55  *     const int mTarget;
  56  *   };
  57  *
  58  *   Vector<int> sortedInts = ...
  59  *
  60  *   size_t match;
  61  *   if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13),
  62  * &match)) { printf("found 13 at %lu\n", match);
  63  *   }
  64  *
  65  */
  66
  67 template <typename Container, typename Comparator>
  68 bool BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
  69                     const Comparator& aCompare,
  70                     size_t* aMatchOrInsertionPoint) {
  71   MOZ_ASSERT(aBegin <= aEnd);
  72
  73   size_t low = aBegin;
  74   size_t high = aEnd;
  75   while (high != low) {
  76     size_t middle = low + (high - low) / 2;
  77
  78     // Allow any intermediate type so long as it provides a suitable ordering
  79     // relation.
  80     const int result = aCompare(aContainer[middle]);
  81
  82     if (result == 0) {
  83       *aMatchOrInsertionPoint = middle;
  84       return true;
  85     }
  86
  87     if (result < 0) {
  88       high = middle;
  89     } else {
  90       low = middle + 1;
  91     }
  92   }
  93
  94   *aMatchOrInsertionPoint = low;
  95   return false;
  96 }
  97
  98 namespace detail {
  99
 100 template <class T>
 101 class BinarySearchDefaultComparator {
 102  public:
 103   explicit BinarySearchDefaultComparator(const T& aTarget) : mTarget(aTarget) {}
 104
 105   template <class U>
 106   int operator()(const U& aVal) const {
 107     if (mTarget == aVal) {
 108       return 0;
 109     }
 110
 111     if (mTarget < aVal) {
 112       return -1;
 113     }
 114
 115     return 1;
 116   }
 117
 118  private:
 119   const T& mTarget;
 120 };
 121
 122 }  // namespace detail
 123
 124 template <typename Container, typename T>
 125 bool BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
 126                   T aTarget, size_t* aMatchOrInsertionPoint) {
 127   return BinarySearchIf(aContainer, aBegin, aEnd,
 128                         detail::BinarySearchDefaultComparator<T>(aTarget),
 129                         aMatchOrInsertionPoint);
 130 }
 131
 132 /*
 133  * LowerBound(), UpperBound(), and EqualRange() are equivalent to
 134  * std::lower_bound(), std::upper_bound(), and std::equal_range() respectively.
 135  *
 136  * LowerBound() returns an index pointing to the first element in the range
 137  * in which each element is considered *not less than* the given value passed
 138  * via |aCompare|, or the length of |aContainer| if no such element is found.
 139  *
 140  * UpperBound() returns an index pointing to the first element in the range
 141  * in which each element is considered *greater than* the given value passed
 142  * via |aCompare|, or the length of |aContainer| if no such element is found.
 143  *
 144  * EqualRange() returns a range [first, second) containing all elements are
 145  * considered equivalent to the given value via |aCompare|.  If you need
 146  * either the first or last index of the range, LowerBound() or UpperBound(),
 147  * which is slightly faster than EqualRange(), should suffice.
 148  *
 149  * Example (another example is given in TestBinarySearch.cpp):
 150  *
 151  *   Vector<const char*> sortedStrings = ...
 152  *
 153  *   struct Comparator {
 154  *     const nsACString& mStr;
 155  *     explicit Comparator(const nsACString& aStr) : mStr(aStr) {}
 156  *     int32_t operator()(const char* aVal) const {
 157  *       return Compare(mStr, nsDependentCString(aVal));
 158  *     }
 159  *   };
 160  *
 161  *   auto bounds = EqualRange(sortedStrings, 0, sortedStrings.length(),
 162  *                            Comparator("needle I'm looking for"_ns));
 163  *   printf("Found the range [%zd %zd)\n", bounds.first(), bounds.second());
 164  *
 165  */
 166 template <typename Container, typename Comparator>
 167 size_t LowerBound(const Container& aContainer, size_t aBegin, size_t aEnd,
 168                   const Comparator& aCompare) {
 169   MOZ_ASSERT(aBegin <= aEnd);
 170
 171   size_t low = aBegin;
 172   size_t high = aEnd;
 173   while (high != low) {
 174     size_t middle = low + (high - low) / 2;
 175
 176     // Allow any intermediate type so long as it provides a suitable ordering
 177     // relation.
 178     const int result = aCompare(aContainer[middle]);
 179
 180     // The range returning from LowerBound does include elements
 181     // equivalent to the given value i.e. aCompare(element) == 0
 182     if (result <= 0) {
 183       high = middle;
 184     } else {
 185       low = middle + 1;
 186     }
 187   }
 188
 189   return low;
 190 }
 191
 192 template <typename Container, typename Comparator>
 193 size_t UpperBound(const Container& aContainer, size_t aBegin, size_t aEnd,
 194                   const Comparator& aCompare) {
 195   MOZ_ASSERT(aBegin <= aEnd);
 196
 197   size_t low = aBegin;
 198   size_t high = aEnd;
 199   while (high != low) {
 200     size_t middle = low + (high - low) / 2;
 201
 202     // Allow any intermediate type so long as it provides a suitable ordering
 203     // relation.
 204     const int result = aCompare(aContainer[middle]);
 205
 206     // The range returning from UpperBound does NOT include elements
 207     // equivalent to the given value i.e. aCompare(element) == 0
 208     if (result < 0) {
 209       high = middle;
 210     } else {
 211       low = middle + 1;
 212     }
 213   }
 214
 215   return high;
 216 }
 217
 218 template <typename Container, typename Comparator>
 219 CompactPair<size_t, size_t> EqualRange(const Container& aContainer,
 220                                        size_t aBegin, size_t aEnd,
 221                                        const Comparator& aCompare) {
 222   MOZ_ASSERT(aBegin <= aEnd);
 223
 224   size_t low = aBegin;
 225   size_t high = aEnd;
 226   while (high != low) {
 227     size_t middle = low + (high - low) / 2;
 228
 229     // Allow any intermediate type so long as it provides a suitable ordering
 230     // relation.
 231     const int result = aCompare(aContainer[middle]);
 232
 233     if (result < 0) {
 234       high = middle;
 235     } else if (result > 0) {
 236       low = middle + 1;
 237     } else {
 238       return MakeCompactPair(
 239           LowerBound(aContainer, low, middle, aCompare),
 240           UpperBound(aContainer, middle + 1, high, aCompare));
 241     }
 242   }
 243
 244   return MakeCompactPair(low, high);
 245 }
 246
 247 }  // namespace mozilla
 248
 249 #endif  // mozilla_BinarySearch_h