[Unimplemented feature]: ability to sort an array of ranges

[lydia-duncan]

Summary of Problem

Description:
I obtained an array of ranges (populated by calling the range type's leader iterator for a larger, single range). This array was not in order, so I wanted to sort it. Calling sort on it resulted in a compiler resolution error.

I was able to work around this problem by defining my own comparator subtype and using that instead of the default comparator:

record rangeComparator : relativeComparator { }

proc rangeComparator.compare(x, y) {
  if x.low < y.low {
    if (x.high < y.low) {
      return x.high - y.low;
    } else {
      halt("ranges overlap");
      return x.high - y.low;
    }
  } else if (x.low > y.low) {
    if (x.low > y.high) {
      return x.low - y.high;
    } else {
      halt("ranges overlap");
      return x.low - y.high;
    }
  } else {
    halt("ranges overlap");
    return x.low - y.low;
  }
}

That solution only worked if the ranges were unique and non-overlapping, and I mostly wrote it that way to find a quick fix for the problem at hand.

Is this issue currently blocking your progress?
no, I'm encountering other issues that make it less relevant

Steps to Reproduce

Source Code:

use Sort;

var arr: [0..4] range = [1..2, 3..4, 6..7, 5..5, -1..0];

writeln(arr);

sort(arr);

writeln(arr);

Compile command:
chpl foo.chpl

Execution command:
N/A

Associated Future Test(s):
test/library/standard/Sort/correctness/arrayOfRanges.chpl #26619

Configuration Information

• Output of chpl --version: 2.4.0 pre-release
• Output of $CHPL_HOME/util/printchplenv --anonymize: any
• Back-end compiler and version, e.g. gcc --version or clang --version: any
• (For Cray systems only) Output of module list: N/A

[lydia-duncan]

I imagine this is probably low priority, since I think the main use case is when developing iterators that are weird. Still, seemed worth reporting as it would have made my life easier

[mppf]

In order to support this by default, we would have to create a default order on ranges. I'm not sure such a thing exists. (E.g., can you < on two ranges? Does that just use promotion and give an iterable / array back?).

In particular you might say, sorting by the start points is the most reasonable; but perhaps sorting by the range sizes is more reasonable, or maybe sorting by the end points. It all depends on what you are doing and I'm not sure there's something likely enough to be what somebody wants to have a default here.

[lydia-duncan]

Yeah. I think for my case, I'd want to sort by the low bounds, and it would be sufficient to assume that the lower bound of one doesn't overlap with the high bound of another (except in the case where empty ranges were included). But when sorting ranges that can overlap, it'd be a more complicated idea. I could see resolving this by providing a helper set of comparators, where one cares about low point, one cares about size, and one cares about high point, though stride can also play into things . . .

[lydia-duncan]

And again, I'm not sure how many other use cases there would be outside of use in writing weird iterators

[lydia-duncan]

And at the very least, it shouldn't barf resolution errors at me, it should give a nice "we don't know how to sort ranges, please give us feedback on your expectations" message