Add Collection#sorted, Collection#min, Collection#max

[DartBot]

This issue was originally filed by @seaneagan

---

List#sort is useful for sorting a list in place, but often you don't want to mutate the list, but rather get a sorted copy of it, and also any collection can be sorted, not just lists, but right now you have to do something like:

List sortedList = new List.from(collection);
sortedList.sort(comparator);

which is inconvenient, but more importantly means that all the elements must be sorted (slow) even to do basic calculations on the returned list, such as "list.last()". Thus, it would be nice to have a separate sorting method in Collection which returns a sorted "view" (see issue #1235) of the Collection:

// comparator optional (see issue #1305)
List<E> sorted([int compare(E a, E b)]);

The two most common use cases for sorting are to calculate a "min" or "max", so those would be nice to have in Collection as well:

E min([int compare(E a, E b)]); // => sorted(compare)[0]
E max([int compare(E a, E b)]) // => sorted(compare).last()

[dgrove]

Removed Type-Defect label.
Added Type-Enhancement, Area-Library, Triaged labels.

[DartBot]

This comment was originally written by @seaneagan

---

* If no self-mutating List#sort is needed, could rename Collection#sorted to Collection#sort

• the "contract" for "min" and "max" could be something like:

E min<T>([int compare(E a, E b)]) {
  if(compare == null) compare = (a, b) => a.compareTo(b);
  min(a, b) => compare(a, b) <= 0 ? a : b;
  return reduce(min); // Collection#reduce
}
E max<T>([int compare(E a, E b)]) {
  if(compare == null) compare = (a, b) => a.compareTo(b);
  max(a, b) => compare(a, b) >= 0 ? a : b;
  return reduce(max);
}

basically assume transitivity of the comparator(s) (in order to get O(n) performance), and when two items compare equal, keep the earliest iterated one.

[rakudrama]

A key function is often more convenient that a comparator.
These functions should take both a key and a comparator.

I like Python's min/max functions.
The min returns the element with the lowest key which we expect to be comparable.

var strs = ['short', 'medium', 'longest'];
max(strs); // --> 'short' - lexicographic compare
max(strs, key: (s) => s.length); // --> 'longest'

[DartBot]

This comment was originally written by @seaneagan

---

I'm thinking just have them take one dynamic argument, which can either be a Comparator or a key function which might be defined as:

typedef num Metric<E>(E e);

Then if/when we get union types, this single argument can be typed as a Comparator | Metric. Along with the latest library changes of moving everything to Iterable and including Stream, this could look like:

class Iterable<E> {
  //...
  E min([var sorter]);
  E max([var sorter]);
  List<E> sorted([var sorter]);
}

class Stream<E> {
  //...
  Future<E> min([var sorter]);
  Future<E> max([var sorter]);
  Future<List<E>> sorted([var sorter]);
}

[lrhn]

Issue #7430 has been merged into this issue.

[DartBot]

This comment was originally written by @seaneagan

---

Looks like min and max were added to lib_v2 in https://codereview.chromium.org/11727007/. Thanks!

Is lazy sorting of Iterables and Streams, i.e. the "sorted" method above, also planned? do we need a separate issue for it?

[lrhn]

Lazy sorting is not planned. The few operations that can be done without sorting (length, first -> min, last -> max) are not really worth the complexity. Also, it will be a dangerous "view", because you will need to sort for most operations, and any change to the underlying list will mean you need to sort again.

With cascades, it's not bad to do: (list.toList()..sort(comparator)) to get a new sorted list.

The min and max methods were removed again from Iterable.

Maybe we should add min/max functions to comparable:
  static Comparable min(Comparable a, Comparable b)
    => a.compareTo(b) <= 0 ? a : b;
  static Comparable max(Comparable a, Comparable b)
    => a.compareTo(b) >= 0 ? a : b;

Then we can find the minimum of a list of comparables as:
  list.reduce(Comparable.min);

[alan-knight]

(list.toList()..sort(comparator)) isn't too bad in terms of code length, but it's not going to be an obvious choice to anyone new to the language.

[DartBot]

This comment was originally written by @seaneagan

---

Static methods would definitely be better than nothing, but you lose the
return type then (Comparable instead of int for example). See issue #3176.

[peter-ahe-google]

Would a method named toSortedList([compare]) make sense?

[floitschG]

toSortedList() would work, but imho it's not worth it. It doesn't really buy much compared to toList()..sort().

Yes toList()..sort() is not completely obvious but the next best thing is:
var list = x.toList();
list.sort();

while this is slightly longer it isn't that bad and is readable.
I like the fact that we make it clear that sorting requires to cache all elements and therefore having it in a list is just natural.

---

Added AsDesigned label.

[DartBot]

This comment was originally written by @mezoni

---

Lazy sorting. Result is IQueryable.
Custom comparator can be passed as an argument.

import 'package:queries/collections.dart';

void main() {
  var fruits = ["grape", "passionfruit", "banana", "mango", "orange", "raspberry", "apple", "blueberry"];
  
  var sorted = new Collection(fruits)
    .orderBy((fruit) => fruit.length)
    .thenBy((fruit) => fruit);
  
  for(var fruit in sorted) {
    print(fruit);
  }
}

Output:
mango
banana
orange
blueberry
raspberry
passionfruit

Sorting algorithm is stable (Symmerge sort).

[mezoni]

???