Bug 1059179 - Add BinarySearchIf(). r=waldo
authorGeorg Fritzsche <georg.fritzsche@googlemail.com>
Mon, 01 Sep 2014 19:26:16 +0200
changeset 202891 62b491425fa2f7beb0071b5d18eb843bc7a52c92
parent 202890 e28ec487d050a1b3508d7944c96c08facdefe9a1
child 202892 820c379866126e404c8bbf7b906a92e4e4d2e655
push id27413
push userphilringnalda@gmail.com
push dateTue, 02 Sep 2014 05:46:30 +0000
treeherderautoland@c360f3d1c00d [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswaldo
bugs1059179
milestone34.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1059179 - Add BinarySearchIf(). r=waldo
mfbt/BinarySearch.h
mfbt/tests/TestBinarySearch.cpp
--- a/mfbt/BinarySearch.h
+++ b/mfbt/BinarySearch.h
@@ -9,64 +9,131 @@
 
 #include "mozilla/Assertions.h"
 
 #include <stddef.h>
 
 namespace mozilla {
 
 /*
- * The algorithm searches the given container |aContainer| over the sorted
- * index range [aBegin, aEnd) for an index |i| where |aContainer[i] == aTarget|.
+ * The BinarySearch() algorithm searches the given container |aContainer| over
+ * the sorted index range [aBegin, aEnd) for an index |i| where
+ * |aContainer[i] == aTarget|.
  * If such an index |i| is found, BinarySearch returns |true| and the index is
  * returned via the outparam |aMatchOrInsertionPoint|. If no index is found,
  * BinarySearch returns |false| and the outparam returns the first index in
  * [aBegin, aEnd] where |aTarget| can be inserted to maintain sorted order.
  *
  * Example:
  *
  *   Vector<int> sortedInts = ...
  *
  *   size_t match;
  *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
  *     printf("found 13 at %lu\n", match);
  *   }
+ *
+ * The BinarySearchIf() version behaves similar, but takes |aComparator|, a
+ * functor to compare the values with, instead of a value to find.
+ * That functor should take one argument - the value to compare - and return an
+ * |int| with the comparison result:
+ *
+ *   * 0, if the argument is equal to,
+ *   * less than 0, if the argument is greater than,
+ *   * greater than 0, if the argument is less than
+ *
+ * the value.
+ *
+ * Example:
+ *
+ *   struct Comparator {
+ *     int operator()(int val) const {
+ *       if (mTarget < val) return -1;
+ *       if (mValue > val) return 1;
+ *       return 0;
+ *     }
+ *     Comparator(int target) : mTarget(target) {}
+       const int mTarget;
+ *   };
+ *
+ *   Vector<int> sortedInts = ...
+ *
+ *   size_t match;
+ *   if (BinarySearchIf(sortedInts, 0, sortedInts.length(), Comparator(13), &match)) {
+ *     printf("found 13 at %lu\n", match);
+ *   }
+ *
  */
 
-template <typename Container, typename T>
+template<typename Container, typename Comparator>
 bool
-BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
-             T aTarget, size_t* aMatchOrInsertionPoint)
+BinarySearchIf(const Container& aContainer, size_t aBegin, size_t aEnd,
+               const Comparator& aCompare, size_t* aMatchOrInsertionPoint)
 {
   MOZ_ASSERT(aBegin <= aEnd);
 
   size_t low = aBegin;
   size_t high = aEnd;
-  while (low != high) {
+  while (high != low) {
     size_t middle = low + (high - low) / 2;
 
     // Allow any intermediate type so long as it provides a suitable ordering
     // relation.
-    const auto& middleValue = aContainer[middle];
+    const int result = aCompare(aContainer[middle]);
 
-    MOZ_ASSERT(aContainer[low] <= aContainer[middle]);
-    MOZ_ASSERT(aContainer[middle] <= aContainer[high - 1]);
-    MOZ_ASSERT(aContainer[low] <= aContainer[high - 1]);
-
-    if (aTarget == middleValue) {
+    if (result == 0) {
       *aMatchOrInsertionPoint = middle;
       return true;
     }
 
-    if (aTarget < middleValue) {
+    if (result < 0) {
       high = middle;
     } else {
       low = middle + 1;
     }
   }
 
   *aMatchOrInsertionPoint = low;
   return false;
 }
 
+namespace detail {
+
+template<class T>
+class BinarySearchDefaultComparator
+{
+public:
+  BinarySearchDefaultComparator(const T& aTarget)
+    : mTarget(aTarget)
+  {}
+
+  template <class U>
+  int operator()(const U& val) const {
+    if (mTarget == val) {
+      return 0;
+    }
+
+    if (mTarget < val) {
+      return -1;
+    }
+
+    return 1;
+  }
+
+private:
+  const T& mTarget;
+};
+
+} // namespace detail
+
+template <typename Container, typename T>
+bool
+BinarySearch(const Container& aContainer, size_t aBegin, size_t aEnd,
+             T aTarget, size_t* aMatchOrInsertionPoint)
+{
+  return BinarySearchIf(aContainer, aBegin, aEnd,
+                        detail::BinarySearchDefaultComparator<T>(aTarget),
+                        aMatchOrInsertionPoint);
+}
+
 } // namespace mozilla
 
 #endif // mozilla_BinarySearch_h
--- a/mfbt/tests/TestBinarySearch.cpp
+++ b/mfbt/tests/TestBinarySearch.cpp
@@ -3,35 +3,49 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/Assertions.h"
 #include "mozilla/BinarySearch.h"
 #include "mozilla/Vector.h"
 
+using mozilla::ArrayLength;
+using mozilla::BinarySearch;
+using mozilla::BinarySearchIf;
 using mozilla::Vector;
-using mozilla::BinarySearch;
+
+#define A(a) MOZ_RELEASE_ASSERT(a)
 
 struct Person
 {
   int mAge;
   int mId;
   Person(int aAge, int aId) : mAge(aAge), mId(aId) {}
 };
 
 struct GetAge
 {
   Vector<Person>& mV;
   explicit GetAge(Vector<Person>& aV) : mV(aV) {}
   int operator[](size_t index) const { return mV[index].mAge; }
 };
 
-int
-main()
+struct RangeFinder {
+  const int mLower, mUpper;
+  RangeFinder(int lower, int upper) : mLower(lower), mUpper(upper) {}
+  int operator()(int val) const {
+    if (val >= mUpper) return -1;
+    if (val < mLower) return 1;
+    return 0;
+  }
+};
+
+static void
+TestBinarySearch()
 {
   size_t m;
 
   Vector<int> v1;
   v1.append(2);
   v1.append(4);
   v1.append(6);
   v1.append(8);
@@ -63,18 +77,37 @@ main()
   MOZ_RELEASE_ASSERT(!BinarySearch(v2, 0, 0, 0, &m) && m == 0);
   MOZ_RELEASE_ASSERT(!BinarySearch(v2, 0, 0, 9, &m) && m == 0);
 
   Vector<Person> v3;
   v3.append(Person(2, 42));
   v3.append(Person(4, 13));
   v3.append(Person(6, 360));
 
-  #define A(a) MOZ_RELEASE_ASSERT(a)
   A(!BinarySearch(GetAge(v3), 0, v3.length(), 1, &m) && m == 0);
   A( BinarySearch(GetAge(v3), 0, v3.length(), 2, &m) && m == 0);
   A(!BinarySearch(GetAge(v3), 0, v3.length(), 3, &m) && m == 1);
   A( BinarySearch(GetAge(v3), 0, v3.length(), 4, &m) && m == 1);
   A(!BinarySearch(GetAge(v3), 0, v3.length(), 5, &m) && m == 2);
   A( BinarySearch(GetAge(v3), 0, v3.length(), 6, &m) && m == 2);
   A(!BinarySearch(GetAge(v3), 0, v3.length(), 7, &m) && m == 3);
+}
+
+static void
+TestBinarySearchIf()
+{
+  const int v1[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+  const size_t len = ArrayLength(v1);
+  size_t m;
+
+  A( BinarySearchIf(v1, 0, len, RangeFinder( 2,  3), &m) && m == 2);
+  A(!BinarySearchIf(v1, 0, len, RangeFinder(-5, -2), &m) && m == 0);
+  A( BinarySearchIf(v1, 0, len, RangeFinder( 3,  5), &m) && m >= 3 && m < 5);
+  A(!BinarySearchIf(v1, 0, len, RangeFinder(10, 12), &m) && m == 10);
+}
+
+int
+main()
+{
+  TestBinarySearch();
+  TestBinarySearchIf();
   return 0;
 }