Closed Bug 1060742 Opened 7 years ago Closed 7 years ago

BinarySearch.jsm: Reorder arguments for curried search functions

Categories

(Toolkit :: General, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla35

People

(Reporter: WeirdAl, Assigned: WeirdAl)

References

Details

Attachments

(1 file)

I'm really glad someone wrote a BinarySearch module.  It should be pretty useful.  I have a couple suggestions, though:

(1) Could you reorder the arguments?  (comparator, array, target)  This would make it practical to call BinarySearch.insertionIndexOf.bind(comparator [, array]).
(2) Could you provide a default comparator?  BinarySearch.DefaultComparator = function(a, b) { return Math.sign(a - b) } (or b - a, I never can remember which)

I realize that changing the API is not something that should be done lightly, but this module only has one Firefox consumer so far.
Actually, a BinarySearch constructor that took a comparator and/or a target array would be really nice.
(In reply to Alex Vincent [:WeirdAl] from comment #0)
> (1) Could you reorder the arguments?  (comparator, array, target)  This
> would make it practical to call
> BinarySearch.insertionIndexOf.bind(comparator [, array]).

That's a good idea.  I always prefer for a function argument to come last since I think it makes callers looks better, but in this case being able to easily make a curried search function is probably worth it, and I think it probably is more common to want to capture the comparator rather than the array.  But I should point out that it's still possible and very simple to make one regardless of the argument order, even though it's a little more verbose.

> (2) Could you provide a default comparator?  BinarySearch.DefaultComparator
> = function(a, b) { return Math.sign(a - b) } (or b - a, I never can remember
> which)

Hmm, that seems not as useful because there's no broadly applicable comparator I don't think.  Ascending or descending?  What kind of elements are in your array?

> I realize that changing the API is not something that should be done
> lightly, but this module only has one Firefox consumer so far.

Yeah, changing it for the better is fine with me.

(In reply to Alex Vincent [:WeirdAl] from comment #1)
> Actually, a BinarySearch constructor that took a comparator and/or a target
> array would be really nice.

I'm not really keen on that either because I don't think it would be broadly useful, and fundamentally I don't think binary search needs to be a method you call on an object.
Assignee: nobody → ajvincent
Status: NEW → ASSIGNED
Attachment #8486222 - Flags: review?(adw)
Summary: BinarySearch.jsm: Reorder arguments, provide default comparator → BinarySearch.jsm: Reorder arguments for curried search functions
Comment on attachment 8486222 [details] [diff] [review]
reorganize BinarySearch.jsm arguments for easier JavaScript .bind() calls

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

Thanks.  r+ with comments below.

::: toolkit/modules/NewTabUtils.jsm
@@ +870,5 @@
>     * @return A negative number if aLink1 is ordered before aLink2, zero if
>     *         aLink1 and aLink2 have the same ordering, or a positive number if
>     *         aLink1 is ordered after aLink2.
> +   *
> +   * @note compareLinks's this object is bound to Links below.

Instead of doing a whole other statement below, you can do:

  compareLinks: function (...) {
    ...
  }.bind(Links),

Or to make it more obvious by reading only the first line that something unusual is going on here, add parens around the function:

  compareLinks: (function (...) {
    ...
  }).bind(Links),

@@ +1033,4 @@
>      return this._binsearch(aArray, aLink, "indexOf");
>    },
>  
>    _insertionIndexOf: function Links__insertionIndexOf(aArray, aLink) {

Let's take advantage of your API change here by writing this as:

  _insertionIndexOf: BinarySearch.insertionIndexOf.bind(
    BinarySearch,
    Links.compareLinks
  ),

I haven't tested but that should work, right?  Same for _indexOf above this.

@@ +1036,5 @@
>    _insertionIndexOf: function Links__insertionIndexOf(aArray, aLink) {
>      return this._binsearch(aArray, aLink, "insertionIndexOf");
>    },
>  
>    _binsearch: function Links__binsearch(aArray, aLink, aMethod) {

And then we can remove this method.
Attachment #8486222 - Flags: review?(adw) → review+
(In reply to Drew Willcoxon :adw from comment #4)
> @@ +1033,4 @@
> >      return this._binsearch(aArray, aLink, "indexOf");
> >    },
> >  
> >    _insertionIndexOf: function Links__insertionIndexOf(aArray, aLink) {
> 
> Let's take advantage of your API change here by writing this as:
> 
>   _insertionIndexOf: BinarySearch.insertionIndexOf.bind(
>     BinarySearch,
>     Links.compareLinks
>   ),

Oh, I guess there's one subtlety, which is that Links.compareLinks must have been bound to Links before this method definition is reached.  To avoid a problem when moving around code in the future, we should probably just write this as:

  _insertionIndexOf: BinarySearch.insertionIndexOf.bind(
    BinarySearch,
    Links.compareLinks.bind(Links)
  ),

And forget about setting compareLinks to the bound compareLinks.

Or we could forget my idea altogether, but then we can't use your API change, or at least it's harder.

What do you think?
(In reply to Drew Willcoxon :adw from comment #4)
> ::: toolkit/modules/NewTabUtils.jsm

I don't think your suggestions will work, since it's inside lines where we define Links:

Links = {
// ...
>   compareLinks: (function (...) {
>     ...
>   }).bind(Links),
// ...
}

We have to finish defining Links before we can bind to it.  Ditto for your other changes.  Now, if we defined compareLinks as a separate function before we started declaring the Links object, it'd be fine.
True, let's forget everything I said then, r+. :-)
Attachment #8486222 - Flags: checkin?(adw)
Comment on attachment 8486222 [details] [diff] [review]
reorganize BinarySearch.jsm arguments for easier JavaScript .bind() calls

https://hg.mozilla.org/integration/fx-team/rev/bbb5359c296a
Attachment #8486222 - Flags: checkin?(adw) → checkin+
https://hg.mozilla.org/mozilla-central/rev/bbb5359c296a
Status: ASSIGNED → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
You need to log in before you can comment on or make changes to this bug.