mfbt/BinarySearch.h
author L10n Bumper Bot <release+l10nbumper@mozilla.com>
Thu, 08 Nov 2018 03:00:11 -0800
changeset 501100 1cd4f2d571554c4dc89cf1be1d98683c0d14f797
parent 323882 bc5e02dcb4015e4c3ae674fcf68e8a53e935b6c7
child 508163 6f3709b3878117466168c40affa7bca0b60cf75b
permissions -rw-r--r--
no bug - Bumping Fennec l10n changesets r=release a=l10n-bump DONTBUILD an -> 336e061995b9 ar -> f6834a7d7374 as -> d2c76e616a66 ast -> fcb8f3455237 az -> c4caf3b07cf2 be -> 697eb1022498 bg -> 7bf1f448f743 bn-BD -> 5f7a87adee06 bn-IN -> 49ce3195c4c2 br -> 41cf35b7c5b5 bs -> 4a14aee27904 ca -> 9373e8ce86d4 cak -> a40d767541ba cs -> 4b99defb0525 cy -> 4c948fed2584 de -> 017a7e7a267a dsb -> aadebeccf5ba el -> 2d28a78dcef5 en-CA -> 55ad9171a9f0 en-GB -> 296422b495e9 en-ZA -> c1b5d2128914 eo -> c68e87667d9f es-AR -> bff0a788c711 es-CL -> 1d3efd2532ea es-ES -> 4d1feb70b0e2 es-MX -> fceda607d0f4 et -> 58a8262a0cc7 eu -> 7cebfd46208b fa -> cbc040d58476 ff -> 46f5aec275ea fi -> 235ab13d261e fr -> 8ee417b64f99

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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/. */

#ifndef mozilla_BinarySearch_h
#define mozilla_BinarySearch_h

#include "mozilla/Assertions.h"

#include <stddef.h>

namespace mozilla {

/*
 * 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 similarly, 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 aVal) const {
 *       if (mTarget < aVal) { return -1; }
 *       if (mTarget > aVal) { return 1; }
 *       return 0;
 *     }
 *     explicit Comparator(int aTarget) : mTarget(aTarget) {}
 *     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 Comparator>
bool
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 (high != low) {
    size_t middle = low + (high - low) / 2;

    // Allow any intermediate type so long as it provides a suitable ordering
    // relation.
    const int result = aCompare(aContainer[middle]);

    if (result == 0) {
      *aMatchOrInsertionPoint = middle;
      return true;
    }

    if (result < 0) {
      high = middle;
    } else {
      low = middle + 1;
    }
  }

  *aMatchOrInsertionPoint = low;
  return false;
}

namespace detail {

template<class T>
class BinarySearchDefaultComparator
{
public:
  explicit BinarySearchDefaultComparator(const T& aTarget)
    : mTarget(aTarget)
  {}

  template <class U>
  int operator()(const U& aVal) const {
    if (mTarget == aVal) {
      return 0;
    }

    if (mTarget < aVal) {
      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