How can custom container types be sorted by the Sort module?

[jabraham17]

The new sort API defines a generic interface of free functions for sorting container types. However, a missing piece is how user defined types can opt-in to being sortable by this interface.

The sort implementation currently needs to know some internals about how the collection is put together to be able to be sorted. For example, sorting of domains is done by having a new domain type implement a dsiSorted method.

One idea is to have a sortable interface that collection types implement. This interface would require the collection type to implement the right hooks so that proc sort (and friends) can sort the container.

This would look like the following

/// in modules/standard/Sort.chpl

proc sort(x: sortable, ...)
proc isSorted(x: sortable, ...)
iter sorted(x: sortable, ...)


/// in user code
use Sort;
record myListType: sortable {
  ...
}

var lst = new myListType();
sort(lst);