Comparator (NumericRangeComparator<T>::operator()) should never fail

[ianbtr]

This is a feature request.

I recognize that NumericRangeComparator<T>::operator() throws a runtime error because it only produces valid results for disjoint ranges. However, the result of this behavior is that this comparator can't produce a total ordering of an arbitrary set of NumericRange objects. This comparator doesn't live up to the guarantees that most other comparators provide, and this could upset users who wanted to sort (or store in a std::map) ranges that happen to overlap. I would argue that this comparator is not as useful as some possible alternatives, and I think you should implement all three of these:

1. NumericRangeStartComparator: Compare two ranges by their minima, or starting values. Ending values serve as a tiebreaker.
2. NumericRangeEndComparator: Compare two ranges by their maxima, or ending values. Starting values serve as a tiebreaker.
3. NumericRangeCenterComparator: Compare two ranges by their center values. The length of the range (end minus start) serves as a tiebreaker.

I suspect that each of these will be a bit cleaner to implement than the original NumericRangeComparator.

All of these give total orderings of arbitrary sets of NumericRange objects, and produce deterministic results. (Don't forget the tiebreakers, because they provide this determinism).

[ianbtr]

I forgot that bound inclusion/exclusion could make these comparators non-deterministic. This means you would have to use inclusion/exclusion as a second tiebreaker in each comparator. Rather than breaking ties with multiple tiebreakers, I suggest creating a hash function and using that as a tiebreaker.

[amalbansode]

Thanks for the suggestion! It'll probably be a bit before I can get to this, but I do generally like the idea of having some kind of comparator that is guaranteed to not fail even in the presence of overlapping bounds. This isn't a use case I'd considered, but I guess it can't hurt to add this as long as users are aware of the effects. Perhaps namespacing these into a separate "danger zone" bucket could make that clear.

One immediate concern that comes to mind is how the effects of scalar-range comparison will propagate. For instance, a map indexed with overlapping numeric range keys could work with some of the comparators you suggested. However, indexing into such a map with a scalar (to essentially find a range that contains the scalar) will return something the first range match found which might be implementation/runtime dependent (STL does red-black trees iirc?). Again, if the user is aware of this, that's perfectly fine by me, but it's definitely going to be a "quirk" (having the potential for one key to match with multiple STL map elements).

I'm not sure I understand how bound (in/ex)clusion makes things "nondeterministic". I think it generally just adds complexity, thus requiring layers of tiebreakers as you said. I'm worried that a hash function might deviate from the underlying rule of "ordinality" that this library is based on. Let me know if I'm missing something!

[ianbtr]

I guess the major theme here is that determinism is more important than predictability. In any of the comparator versions I listed, you need to be able to deterministically compare the ranges [0, 1] and [0, 1). Which one comes out on top might not matter so much as that it's the same one every time. To make a rule that's easier for users to understand, you could arbitrarily use [0, 1] < [0, 1) < (0, 1] < (0, 1).

As for the scalar-range comparison, to me your desired functionality (finding a scalar contained inside a range) seems like the wrong thing to be implementing in your comparator, because it inherently prevents you from generating a total ordering. A pair of distinct scalars could both match a range that contains them, but those scalars would not compare equal.

Think back to EECS 203 and "RST" equivalence relations: your comparator is providing a measure of equality even though it is technically computing an inequality. Logically, your comparator will be used to say "A is not less than B, but B is not less than A, so A and B must be equal" and this concept of "equal" should be a valid equivalence relation. Your users might not understand this concept, but they will nevertheless expect RST behavior from your comparator.

Finding a scalar within a range seems like a good use case for std::find_if. If you just supply a function like this:

template <typename T, typename U>
bool contains(NumericRange<T> range, U scalar) { ... }

then users can easily invoke find_if and achieve that goal without too much overhead. I realize find_if wouldn't be log-time, but you can still add log-time implementations of this operation in other ways.