Possible improvement to AngularJS orderBy.js

[OpenSiteMobile]

As best I understand, the orderBy.js file was improved in Angular version 1.5.7 to deal with "tiebreakers" using the getComparisonObject function:

"NOTE: We are adding an extra tieBreaker value based on the element's index."

But I also noticed that the doComparison function which "compares" the values, uses the "compare" function defined under the orderByFilter function. Since the orderByFilter function can use a developer supplied comparison function (which would probably not be aware of the comparison tiebreaker code), would it not be better to have the doComparison function written as this:

    function doComparison(v1, v2) {
      for (var i = 0, ii = predicates.length; i < ii; i++) {
        var result = compare(v1.predicateValues[i], v2.predicateValues[i]);
        if (result) {
          return result * predicates[i].descending * descending;
        }
      }

      return defaultCompare(v1.tieBreaker, v2.tieBreaker) * descending;
    }

...so that the tiebreaker feature is always available regardless of whether or not the developer knew about it.

Current behavior:

Would ingnore the tieBreaker code from getComparisonObject function if the developer supplies his/her own comparison function.

Expected behavior:

Although the use case where this makes a difference may be small, adding the above change would always force the "tieBreaker" code to work where applicable. The downside might be upexpected results from developers not aware of the new "tieBreaker" comparison feature when upgrading to this version of AngularJS.

Angular version 1.5.7 is the first version I noticed the code for "tieBreaker" and should be browser independent, ref. file:

https://github.com/angular/angular.js/blob/master/src/ng/filter/orderBy.js

[gkalpak]

As best I understand, the orderBy.js file was improved in Angular version 1.5.7 to deal with "tiebreakers"

Yes and no.
Yes it was improved (adding support for custom comparators, improving docs, cleaning up the code a bit).
No, the tie-breaker feature was not introduced in 1.5.7. It has been there for a while. We just documented it more explicitly, because now that a custom comparator can be specified, the user needs to be aware of it.

Since the orderByFilter function can use a developer supplied comparison function (which would probably not be aware of the comparison tiebreaker code)

That's why we documented it, so that the developer is aware 😃

would it not be better to have the doComparison function written as this: [...]

Not really, because the developer might want to supply custom tie-breaker logic.

Current behavior: Would ingnore the tieBreaker code from getComparisonObject function if the developer supplies his/her own comparison function.

It will not ignore it. It will be passed to the developer-supplied comparator if necessary.

---

You have a point though: If the custom comparator fails to determine the order by any predicate and it fails to determine the order by the tie-breaker (i.e. compare(v1.tieBreaker, v2.tieBreaker) returns 0), there might be non-determinism (depending on the browser).

To avoid this (but at the same time allow the developer to handle this themselves if they want to), I suggest we call the default comparator only if the custom comparator can't break the tie.

I.e. change return compare(v1.tieBreaker, v2.tieBreaker) * descending in doComparison() with:

return (compare(v1.tieBreaker, v2.tieBreaker) || defaultCompare(v1.tieBreaker, v2.tieBreaker)) * descending

_{(formatted in a nicer way 😛 )}

@OpenSiteMobile , would you like to take a stab at it?

[OpenSiteMobile]

Sorry about not replying sooner. I don't think you need the "compare()" in:

return (compare(v1.tieBreaker, v2.tieBreaker) || defaultCompare(v1.tieBreaker, v2.tieBreaker)) * descending;

...just the "defaultCompare", since most often it is not going to be a tie. If the developer writes his "compare" function correctly to cover a specific "tie" he is concerned about, then his function will never reach this return (compare() || defaultCompare()) value. If he doesn't, then the "defautCompare" function is used, which is most likely what he wants anyway.

[gkalpak]

I don't think you need the "compare()" [...] just the "defaultCompare", since most often it is not going to be a tie.

Because ties are expected to be rare indeed, it doesn't mean that you don't need to compare the tie-breaker with the custom comparator (for the rare case that this is needed).

If the developer writes his "compare" function correctly to cover a specific "tie" he is concerned about, then his function will never reach this return (compare() || defaultCompare()) value.

That is not true. The custom comparator does not know anything about the predicates, so if the comparator can't decide based on the current values, it shouldn't consider it a definitive tie, since a subsequent predicate might break the tie.
The only place where you know that no predicate was able to break the tie is after you have tried them all; i.e. when comparing using the tie-breaker value.

If he doesn't, then the "defautCompare" function is used, which is most likely what he wants anyway.

True but "most likely" is not good enough. There might be cases where the user wants total control and doesn't want us to tell them how to break their ties, because "we thought that is most likely what you wanted" 😛

Based on the above, I still believe it is correct to give the user full control by passing them the tie-breaker if needed. Additionally, this is already public API and changing it would be a breaking change (for no real value imo).

tl;dr
I insist we should use both compare and defaultCompare 😄

[austinoneil]

One thing that I'm thinking is the following:

1. Follow the algorithm as is.
2. Break the sorted array into an array of arrays where each second-level array is completely tied.
3. On each of those second-level arrays, do a defaultSort.
4. "Flatten" the array and return the flattened array.

Does this seem like a fool-proof plan? Worst case scenario, it adds O(n log n) to the sort time, which sorting is generally done in O(n log n) anyway, so this should work.

I am assuming that the plan is to, essentially, add a "tiebreaker" to the end of the sort for when all the sorting is done.

[gkalpak]

@austinoneil, I don't 100% follow your suggestion, but on what aspect of the current implementation does it improve?

[austinoneil]

@gkalpak If, at some point in the future, Chrome, Firefox, and IE drift away on their sorting algorithms to no longer be stable algorithms (instead going for performance), there will still be some consistency across browsers. Is my italicized assumption correct?