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
  12 #include <stddef.h>
  13
  14 namespace mozilla {
  15
  16 /*
  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.
  24  *
  25  * Example:
  26  *
  27  *   Vector<int> sortedInts = ...
  28  *
  29  *   size_t match;
  30  *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
  31  *     printf("found 13 at %lu\n", match);
  32  *   }
  33  *
  34  * The BinarySearchIf() version behaves similarly, 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:
  38  *
  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
  42  *
  43  * the value.
  44  *
  45  * Example:
  46  *
  47  *   struct Comparator {
  48  *     int operator()(int aVal) const {
  49  *       if (mTarget < aVal) { return -1; }
  50  *       if (mTarget > aVal) { return 1; }
  51  *       return 0;
  52  *     }
  53  *     explicit Comparator(int aTarget) : mTarget(aTarget) {}
  54  *     const int mTarget;
  55  *   };
  56  *
  57  *   Vector<int> sortedInts = ...
  58  *
  59  *   size_t match;
  60  *   if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13),
  61  * &match)) { printf("found 13 at %lu\n", match);
  62  *   }
  63  *
  64  */
  65
  66 template <typename Container, typename Comparator>
  67 bool BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
  68                     const Comparator& aCompare,
  69                     size_t* aMatchOrInsertionPoint) {
  70   MOZ_ASSERT(aBegin <= aEnd);
  71
  72   size_t low = aBegin;
  73   size_t high = aEnd;
  74   while (high != low) {
  75     size_t middle = low + (high - low) / 2;
  76
  77     // Allow any intermediate type so long as it provides a suitable ordering
  78     // relation.
  79     const int result = aCompare(aContainer[middle]);
  80
  81     if (result == 0) {
  82       *aMatchOrInsertionPoint = middle;
  83       return true;
  84     }
  85
  86     if (result < 0) {
  87       high = middle;
  88     } else {
  89       low = middle + 1;
  90     }
  91   }
  92
  93   *aMatchOrInsertionPoint = low;
  94   return false;
  95 }
  96
  97 namespace detail {
  98
  99 template <class T>
 100 class BinarySearchDefaultComparator {
 101  public:
 102   explicit BinarySearchDefaultComparator(const T& aTarget) : mTarget(aTarget) {}
 103
 104   template <class U>
 105   int operator()(const U& aVal) const {
 106     if (mTarget == aVal) {
 107       return 0;
 108     }
 109
 110     if (mTarget < aVal) {
 111       return -1;
 112     }
 113
 114     return 1;
 115   }
 116
 117  private:
 118   const T& mTarget;
 119 };
 120
 121 }  // namespace detail
 122
 123 template <typename Container, typename T>
 124 bool BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
 125                   T aTarget, size_t* aMatchOrInsertionPoint) {
 126   return BinarySearchIf(aContainer, aBegin, aEnd,
 127                         detail::BinarySearchDefaultComparator<T>(aTarget),
 128                         aMatchOrInsertionPoint);
 129 }
 130
 131 }  // namespace mozilla
 132
 133 #endif  // mozilla_BinarySearch_h