mfbt/tests/TestBinarySearch.cpp

   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 file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/Assertions.h"
   8 #include "mozilla/BinarySearch.h"
   9 #include "mozilla/Vector.h"
  10
  11 #include <cstdlib>
  12
  13 using mozilla::ArrayLength;
  14 using mozilla::BinarySearch;
  15 using mozilla::BinarySearchIf;
  16 using mozilla::Vector;
  17
  18 #define A(a) MOZ_RELEASE_ASSERT(a)
  19
  20 struct Person {
  21   int mAge;
  22   int mId;
  23   Person(int aAge, int aId) : mAge(aAge), mId(aId) {}
  24 };
  25
  26 struct GetAge {
  27   Vector<Person>& mV;
  28   explicit GetAge(Vector<Person>& aV) : mV(aV) {}
  29   int operator[](size_t index) const { return mV[index].mAge; }
  30 };
  31
  32 struct RangeFinder {
  33   const int mLower, mUpper;
  34   RangeFinder(int lower, int upper) : mLower(lower), mUpper(upper) {}
  35   int operator()(int val) const {
  36     if (val >= mUpper) return -1;
  37     if (val < mLower) return 1;
  38     return 0;
  39   }
  40 };
  41
  42 static void TestBinarySearch() {
  43   size_t m;
  44
  45   Vector<int> v1;
  46   MOZ_RELEASE_ASSERT(v1.append(2));
  47   MOZ_RELEASE_ASSERT(v1.append(4));
  48   MOZ_RELEASE_ASSERT(v1.append(6));
  49   MOZ_RELEASE_ASSERT(v1.append(8));
  50
  51   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, v1.length(), 1, &m) && m == 0);
  52   MOZ_RELEASE_ASSERT(BinarySearch(v1, 0, v1.length(), 2, &m) && m == 0);
  53   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, v1.length(), 3, &m) && m == 1);
  54   MOZ_RELEASE_ASSERT(BinarySearch(v1, 0, v1.length(), 4, &m) && m == 1);
  55   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, v1.length(), 5, &m) && m == 2);
  56   MOZ_RELEASE_ASSERT(BinarySearch(v1, 0, v1.length(), 6, &m) && m == 2);
  57   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, v1.length(), 7, &m) && m == 3);
  58   MOZ_RELEASE_ASSERT(BinarySearch(v1, 0, v1.length(), 8, &m) && m == 3);
  59   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, v1.length(), 9, &m) && m == 4);
  60
  61   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 1, &m) && m == 1);
  62   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 2, &m) && m == 1);
  63   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 3, &m) && m == 1);
  64   MOZ_RELEASE_ASSERT(BinarySearch(v1, 1, 3, 4, &m) && m == 1);
  65   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 5, &m) && m == 2);
  66   MOZ_RELEASE_ASSERT(BinarySearch(v1, 1, 3, 6, &m) && m == 2);
  67   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 7, &m) && m == 3);
  68   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 8, &m) && m == 3);
  69   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 1, 3, 9, &m) && m == 3);
  70
  71   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, 0, 0, &m) && m == 0);
  72   MOZ_RELEASE_ASSERT(!BinarySearch(v1, 0, 0, 9, &m) && m == 0);
  73
  74   Vector<int> v2;
  75   MOZ_RELEASE_ASSERT(!BinarySearch(v2, 0, 0, 0, &m) && m == 0);
  76   MOZ_RELEASE_ASSERT(!BinarySearch(v2, 0, 0, 9, &m) && m == 0);
  77
  78   Vector<Person> v3;
  79   MOZ_RELEASE_ASSERT(v3.append(Person(2, 42)));
  80   MOZ_RELEASE_ASSERT(v3.append(Person(4, 13)));
  81   MOZ_RELEASE_ASSERT(v3.append(Person(6, 360)));
  82
  83   A(!BinarySearch(GetAge(v3), 0, v3.length(), 1, &m) && m == 0);
  84   A(BinarySearch(GetAge(v3), 0, v3.length(), 2, &m) && m == 0);
  85   A(!BinarySearch(GetAge(v3), 0, v3.length(), 3, &m) && m == 1);
  86   A(BinarySearch(GetAge(v3), 0, v3.length(), 4, &m) && m == 1);
  87   A(!BinarySearch(GetAge(v3), 0, v3.length(), 5, &m) && m == 2);
  88   A(BinarySearch(GetAge(v3), 0, v3.length(), 6, &m) && m == 2);
  89   A(!BinarySearch(GetAge(v3), 0, v3.length(), 7, &m) && m == 3);
  90 }
  91
  92 static void TestBinarySearchIf() {
  93   const int v1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  94   const size_t len = ArrayLength(v1);
  95   size_t m;
  96
  97   A(BinarySearchIf(v1, 0, len, RangeFinder(2, 3), &m) && m == 2);
  98   A(!BinarySearchIf(v1, 0, len, RangeFinder(-5, -2), &m) && m == 0);
  99   A(BinarySearchIf(v1, 0, len, RangeFinder(3, 5), &m) && m >= 3 && m < 5);
 100   A(!BinarySearchIf(v1, 0, len, RangeFinder(10, 12), &m) && m == 10);
 101 }
 102
 103 static void TestEqualRange() {
 104   struct CompareN {
 105     int mVal;
 106     explicit CompareN(int n) : mVal(n) {}
 107     int operator()(int aVal) const { return mVal - aVal; }
 108   };
 109
 110   constexpr int kMaxNumber = 100;
 111   constexpr int kMaxRepeat = 2;
 112
 113   Vector<int> sortedArray;
 114   MOZ_RELEASE_ASSERT(sortedArray.reserve(kMaxNumber * kMaxRepeat));
 115
 116   // Make a sorted array by appending the loop counter [0, kMaxRepeat] times
 117   // in each iteration.  The array will be something like:
 118   //   [0, 0, 1, 1, 2, 2, 8, 9, ..., kMaxNumber]
 119   for (int i = 0; i <= kMaxNumber; ++i) {
 120     int repeat = rand() % (kMaxRepeat + 1);
 121     for (int j = 0; j < repeat; ++j) {
 122       MOZ_RELEASE_ASSERT(sortedArray.emplaceBack(i));
 123     }
 124   }
 125
 126   for (int i = -1; i < kMaxNumber + 1; ++i) {
 127     auto bounds = EqualRange(sortedArray, 0, sortedArray.length(), CompareN(i));
 128
 129     MOZ_RELEASE_ASSERT(bounds.first() <= sortedArray.length());
 130     MOZ_RELEASE_ASSERT(bounds.second() <= sortedArray.length());
 131     MOZ_RELEASE_ASSERT(bounds.first() <= bounds.second());
 132
 133     if (bounds.first() == 0) {
 134       MOZ_RELEASE_ASSERT(sortedArray[0] >= i);
 135     } else if (bounds.first() == sortedArray.length()) {
 136       MOZ_RELEASE_ASSERT(sortedArray[sortedArray.length() - 1] < i);
 137     } else {
 138       MOZ_RELEASE_ASSERT(sortedArray[bounds.first() - 1] < i);
 139       MOZ_RELEASE_ASSERT(sortedArray[bounds.first()] >= i);
 140     }
 141
 142     if (bounds.second() == 0) {
 143       MOZ_RELEASE_ASSERT(sortedArray[0] > i);
 144     } else if (bounds.second() == sortedArray.length()) {
 145       MOZ_RELEASE_ASSERT(sortedArray[sortedArray.length() - 1] <= i);
 146     } else {
 147       MOZ_RELEASE_ASSERT(sortedArray[bounds.second() - 1] <= i);
 148       MOZ_RELEASE_ASSERT(sortedArray[bounds.second()] > i);
 149     }
 150   }
 151 }
 152
 153 int main() {
 154   TestBinarySearch();
 155   TestBinarySearchIf();
 156   TestEqualRange();
 157   return 0;
 158 }