Status

()

defect
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: gfritzsche, Assigned: gfritzsche)

Tracking

Trunk
mozilla34
Points:
3
Bug Flags:
firefox-backlog +
qe-verify -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 1 obsolete attachment)

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.
Flags: firefox-backlog+
Posted patch Add BinarySearchIf() (obsolete) — Splinter Review
Attachment #8479759 - Flags: review?(jwalden+bmo)
Flags: qe-verify-
Added to IT 34.3
Status: NEW → ASSIGNED
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.
Attachment #8479759 - Flags: review?(jwalden+bmo) → review+
Addressed review comments.
Attachment #8479759 - Attachment is obsolete: true
Attachment #8482356 - Flags: review+
Iteration: 34.3 → 35.1
https://hg.mozilla.org/mozilla-central/rev/62b491425fa2
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla34
You need to log in before you can comment on or make changes to this bug.