Line data    Source code

       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), &match)) {
      61             :  *     printf("found 13 at %lu\n", match);
      62             :  *   }
      63             :  *
      64             :  */
      65             : 
      66             : template<typename Container, typename Comparator>
      67             : bool
      68      163565 : BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
      69             :                const Comparator& aCompare, size_t* aMatchOrInsertionPoint)
      70             : {
      71      163565 :   MOZ_ASSERT(aBegin <= aEnd);
      72             : 
      73      163565 :   size_t low = aBegin;
      74      163565 :   size_t high = aEnd;
      75     1210421 :   while (high != low) {
      76      666498 :     size_t middle = low + (high - low) / 2;
      77             : 
      78             :     // Allow any intermediate type so long as it provides a suitable ordering
      79             :     // relation.
      80      666498 :     const int result = aCompare(aContainer[middle]);
      81             : 
      82      666498 :     if (result == 0) {
      83      143070 :       *aMatchOrInsertionPoint = middle;
      84      143070 :       return true;
      85             :     }
      86             : 
      87      523428 :     if (result < 0) {
      88      251268 :       high = middle;
      89             :     } else {
      90      272160 :       low = middle + 1;
      91             :     }
      92             :   }
      93             : 
      94       20495 :   *aMatchOrInsertionPoint = low;
      95       20495 :   return false;
      96             : }
      97             : 
      98             : namespace detail {
      99             : 
     100             : template<class T>
     101             : class BinarySearchDefaultComparator
     102             : {
     103             : public:
     104        5430 :   explicit BinarySearchDefaultComparator(const T& aTarget)
     105        5430 :     : mTarget(aTarget)
     106        5430 :   {}
     107             : 
     108             :   template <class U>
     109       19835 :   int operator()(const U& aVal) const {
     110       19835 :     if (mTarget == aVal) {
     111        5114 :       return 0;
     112             :     }
     113             : 
     114       14721 :     if (mTarget < aVal) {
     115        7861 :       return -1;
     116             :     }
     117             : 
     118        6860 :     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        5415 : BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
     130             :              T aTarget, size_t* aMatchOrInsertionPoint)
     131             : {
     132       10830 :   return BinarySearchIf(aContainer, aBegin, aEnd,
     133             :                         detail::BinarySearchDefaultComparator<T>(aTarget),
     134       10830 :                         aMatchOrInsertionPoint);
     135             : }
     136             : 
     137             : } // namespace mozilla
     138             : 
     139             : #endif // mozilla_BinarySearch_h