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 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:
  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 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  *   };
  56  *
  57  *   Vector<int> sortedInts = ...
  58  *
  59  *   size_t match;
  60  *   if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13), &match)) {
  61  *     printf("found 13 at %lu\n", match);
  62  *   }
  63  *
  64  */
  65
  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)
  70 {
  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 {
 103 public:
 104   BinarySearchDefaultComparator(const T& aTarget)
 105     : mTarget(aTarget)
 106   {}
 107
 108   template <class U>
 109   int operator()(const U& val) const {
 110     if (mTarget == val) {
 111       return 0;
 112     }
 113
 114     if (mTarget < val) {
 115       return -1;
 116     }
 117
 118     return 1;
 119   }
 120
 121 private:
 122   const T& mTarget;
 123 };
 124
 125 } // namespace detail
 126
 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)
 131 {
 132   return BinarySearchIf(aContainer, aBegin, aEnd,
 133                         detail::BinarySearchDefaultComparator<T>(aTarget),
 134                         aMatchOrInsertionPoint);
 135 }
 136
 137 } // namespace mozilla
 138
 139 #endif // mozilla_BinarySearch_h