1059179 - Add BinarySearchIf()

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Georg Fritzsche [:gfritzsche]]

As discussed on IRC:
We now have the BinarySearch() algorithm implementation in MFBT, but not all use-cases can directly pass a value to search for.
Hence we need a variation that takes a functor for the comparisons.

Comment 1

[Georg Fritzsche [:gfritzsche]]

Attachment: Add BinarySearchIf()

Comment 2

[Marco Mucci [:MarcoM]]

Added to IT 34.3

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 8479759 [details] [diff] [review]
Add BinarySearchIf()

Review of attachment 8479759 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/BinarySearch.h
@@ +13,5 @@
>  
>  namespace mozilla {
>  
>  /*
> + * The BinarySearch() algorithm searches the given container |aContainer| over the sorted

Needs rewrapping to 80ch.

@@ +29,5 @@
>   *   if (BinarySearch(sortedInts, 0, sortedInts.length(), 13, &match)) {
>   *     printf("found 13 at %lu\n", match);
>   *   }
> + *
> + * The BinarySearchIf() version behaves similar, but takes |aComparator|,

Looks like this paragraph should be wrapped to 80ch too.

@@ +35,5 @@
> + * 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,
> + * * -1, if the argument is greater than,
> + * * 1, if the argument is less than

Please put blank lines before/after this bullet list, and indent the bullets two spaces.  This all blends into the surrounding text and left margin, as it is now.

There's no reason not to say 0 if equal, less than 0 if greater than, +1 if less than, right?  Right now the interface claims only -1/0/1 but accepts values outside that range.  We should be consistent.

@@ +92,5 @@
>    return false;
>  }
>  
> +namespace detail {
> +  template<class T>

Don't indent the contents of the namespace, please.

@@ +93,5 @@
>  }
>  
> +namespace detail {
> +  template<class T>
> +  class BinarySearchDefaultComparator {

{ on new line.

::: mfbt/tests/TestBinarySearch.cpp
@@ +10,5 @@
>  
>  using mozilla::Vector;
>  using mozilla::BinarySearch;
> +using mozilla::BinarySearchIf;
> +using mozilla::ArrayLength;

Please alphabetize these.

@@ +26,5 @@
>    explicit GetAge(Vector<Person>& aV) : mV(aV) {}
>    int operator[](size_t index) const { return mV[index].mAge; }
>  };
>  
> +struct RangeFinder {

{ on new line, please.

@@ +47,5 @@
>    v1.append(4);
>    v1.append(6);
>    v1.append(8);
>  
> +  #define A(a) MOZ_RELEASE_ASSERT(a)

Just leave these as they were, I think, in terms of A/MOZ_RELEASE_ASSERT.

@@ +89,5 @@
>    A( BinarySearch(GetAge(v3), 0, v3.length(), 6, &m) && m == 2);
>    A(!BinarySearch(GetAge(v3), 0, v3.length(), 7, &m) && m == 3);
> +
> +  const int v4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
> +  const size_t len = ArrayLength(v4);

It might be nice to put the BinarySearch tests in one method and the BinarySearchIf methods in another, TestBinarySearch and TestBinarySearchIf.  A little nicer for debugging and all.  And it accords with what we've generally done in other bugs.

Comment 4

[Georg Fritzsche [:gfritzsche]]

Attachment: Add BinarySearchIf()

Addressed review comments.

Comment 5

[Georg Fritzsche [:gfritzsche]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/62b491425fa2

Comment 6

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/62b491425fa2