Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

List.sort() should make the compare function optional. #1235

Closed
munificent opened this issue Jan 19, 2012 · 16 comments
Closed

List.sort() should make the compare function optional. #1235

munificent opened this issue Jan 19, 2012 · 16 comments

Comments

@munificent
Copy link
Member

Every time I call List.sort(), I end up doing:

    list.sort((a, b) => a.compareTo(b));

It would be really nice if the compare argument was optional and defaulted to that.

@rakudrama
Copy link
Member

I keep copying this function into wherever I need sorting.

List sorted(Iterable input, [compare, key]) {
  comparator(compare, key) {
    if (compare == null && key == null)
      return (a, b) => a.compareTo(b);
    if (compare == null)
      return (a, b) => key(a).compareTo(key(b));
    if (key == null)
      return compare;
    return (a, b) => compare(key(a), key(b));
  }
  List copy = new List.from(input);
  copy.sort(comparator(compare, key));
  return copy;
}

Example usage:

for (Element e in sorted(elements, key: (e) => e.name)) {
  ...
}

I find I use key: just as often as compare:, so I would encourage the more versatile interface.
The sort algorithm might be able to exploit a separate key function.

@dgrove
Copy link
Contributor

dgrove commented Jun 8, 2012

Issue #3432 has been merged into this issue.

@lrhn
Copy link
Member

lrhn commented Oct 15, 2012

Issue #5870 has been merged into this issue.

@lrhn
Copy link
Member

lrhn commented Oct 15, 2012

Added Accepted label.

@lrhn
Copy link
Member

lrhn commented Oct 16, 2012

For the key-sorting, it seems to be a property of the comparison, not of the sort.
What you do is exactly the correct thing: You create a new compare function from an old one.
That is, if you have a:

  Comparator projectCompare(key(var object), 
                           [Comparator compare = Comparable.compare]) {
    return (a,b) => compare(key(a), key(b));
  }

(name subject to change and/or ridicule) you don't need to change sort.

In some cases, that's too slow - you don't want to call the key function twice for each comparison. In that case you need a separate algorithm that optimizes differently, but which one will not be something that can be answered generally.

@alan-knight
Copy link
Contributor

I find that with key-sorting, the more useful generalization is to multiple keys. If you're doing a lot of sorting, writing the comparison that if these two are equal, compare based on that one, and so forth, is tedious. So being able to say to sort on different criteria by just specifying the way to get the sortable keys is quite useful. But that doesn't necessarily require any changes to sorting itself, it's just a convenience for generating the compare function. And a call operator would probably be useful for that.

@justinfagnani
Copy link
Contributor

See Guava's Ordering class for a nice way to handle projections, compound comparators, nulls, etc.

http://code.google.com/p/guava-libraries/wiki/OrderingExplained

@alan-knight
Copy link
Contributor

That looks powerful, although quite verbose. My standard of comparison is more like
   people sorted: #lastName ascending, #firstName, #middleName

@justinfagnani
Copy link
Contributor

Well, it's Java, it has to be verbose :) In Dart I'm sure we could come up with a much more concise analog.

@DartBot
Copy link

DartBot commented Dec 1, 2012

This comment was originally written by devdanke...@gmail.com


I support making the sort() comparator optional. I like the design principle, "Make the common case simple". I also agree with the other commentor who complained about Java's excessive verboseness. Eliminating and preventing unneeded verboseness makes Dart more accessible to new developers and less annoying to experienced developers.

@lrhn
Copy link
Member

lrhn commented Apr 18, 2013

The compare function argument of List.sort is now optional.
We have no plans of adding further functionality to sort.


Added Fixed label.

@kamleshwebtech
Copy link

someObjects.sort((a, b) => a.someProperty.compareTo(b.someProperty));

@maxdiable
Copy link

hi,
it's possible compare a nullable property ?

@munificent
Copy link
Member Author

it's possible compare a nullable property ?

Nullable types don't implement Comparable<T> directly, but you can sort nullable values by providing your own comparison function that handles the null directly and then it's up to you do decide whether you consider null to come before or after other values:

main() {
  var numbers = [5, 3, null, 2, null, 1, 4];

  numbers.sort((a, b) {
    if (a == null) {
      if (b == null) {
        return 0; // Null is equal to itself.
      } else {
        return -1; // Sort null first.
      }
    } else {
      if (b == null) {
        return 1; // Sort null first.
      } else {
        return a.compareTo(b);
      }
    }
  });

  print(numbers);
}

This prints [null, null, 1, 2, 3, 4, 5]. If you want to use the new Dart 3.0 features, you could write:

main() {
  var numbers = [5, 3, null, 2, null, 1, 4];

  numbers.sort((a, b) {
    return switch ((a, b)) {
      (null, null) => 0, // Null is equal to itself.
      (int _, null) => 1, // Sort null first.
      (null, int _) => -1, // Sort null first.
      (int a, int b) => a.compareTo(b),
    };
  });

  print(numbers);
}

@maxdiable
Copy link

maxdiable commented Jan 25, 2024 via email

@lrhn
Copy link
Member

lrhn commented Jan 26, 2024

One can also create helper functions like:

int Function(T?, T?) compareNullsFirst<T extends Object?>(
        int Function(T, T) compare) =>
    (T? a, T? b) => a == null ? b == null ? 0 : -1 : b == null ? 1 : compare(a, b);
int Function(T?, T?) compareNullsLast<T extends Object?>(
        int Function(T, T) compare) =>
    (T? a, T? b) => a == null ? b == null ? 0 : 1 : b == null ? -1 : compare(a, b);

which allows any other comparison function to be extended to nullable values.

void main() {
  print([6, 1, 3, null, 4, null, 2]..sort(
      compareNullsFirst(Comparable.compare))); // [null, null, 1, 2, 3, 4, 6]
  print([6, 1, 3, null, 4, null, 2]..sort(
      compareNullsLast(Comparable.compare))); // [1, 2, 3, 4, 6, null, null]
}

This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

9 participants