Functions that require a sorted range to take a SortedRange?

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2013-07-23T13:00:25Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=10706

CC List

• collin.reeser
• witold.baryluk+d (@baryluk)

Description

In Phobos we have std.range.assumeSorted, std.algorithm.isSorted, and various sort() functions that return a SortedRange. If you call a release() on a SortedRange you get the range that's under it (often an array).

(A SortedRange was so far only a RandomAccessRange, but lately the it has emerged the idea that a ForwardRange is OK too, so it will probably be expanded for all input ranges.)

So isn't it good to have the "set operations" (that actually work on _sorted bags_, so their name is in my opinion misleading) of std.algorithm, like std.algorithm.setDifference accept only SortedRanges?

SetDifference!(less, SortedRange1, SortedRange2) 
setDifference(alias less = "a < b", R1, R2)(SortedRange1 r1, SortedRange2 r2);

The disadvantage is that such functions become a bit more fussy, so you can't give them normal arrays. The advantage is that if you have to keep around sorted data, you can perform on it all kinds of elaborations available only with sorted data and the type system will catch you mistakes like using unsorted data where sorted is required.

The functions in discussion are:

largestPartialIntersection
largestPartialIntersectionWeighted
NWayUnion
SetDifference
SetIntersection
SetSymmetricDifference
SetUnion

[dlangBugzillaToGithub]

collin.reeser commented on 2015-08-12T03:37:28Z

I was actually burned by this today. Coinciding with the release of 2.068 (though I didn't initially know the release was upon us!), Travis builds for my project started inexplicably failing. The root cause was that a setSymmetricDifference call, which had been working for many months, was suddenly giving nonsense results.

One of the inputs to the call was a .keys() on an associative array.

Presumably, it just-so-happened that the .keys() was yielding sorted output, but with the change to the internals of the associative arrays this release, it just-so-happened that the .keys() result wasn't sorted! Since I misunderstood the documentation of setSymmetricDifference to mean "is-sortable-by 'less'", and not "must have been, prior to input, sorted by 'less'", I didn't initially put the .sort() call after the .keys() call.

Too bad so sad. Figured it out, but lost some time to it.

[dlangBugzillaToGithub]

dlang-bot commented on 2021-11-16T12:47:49Z

@burner updated dlang/phobos pull request #6795 "Fix Issue 10706 setops functions need to require SortedRanges" fixing this issue:

- Fix Issue #10706 setops functions need to require SortedRanges
  
  https://issues.dlang.org/show_bug.cgi?id=10706
  
  * largestPartialIntersection
  * largestPartialIntersectionWeighted
  * multiwayMerge
  * multiwayUnion
  * setDifference
  * setIntersection
  * setSymmetricDifference
  
  Now all require SortedRanges to be passed, as that is what they expect
  implicitly anyway.
  
  A new public symbol `isSortedRange` was added to std.range.
  Comment about usage with non SortedRange ranges
  Add `deprecated` for PR 6795 except on multiwayMerge & largestPartialIntersectionWeighted
  pragma msg because deprecated will not compile

https://github.com/dlang/phobos/pull/6795