goog.math.RangeSet and goog.math.Range appear to have inconsistent semantics

[Andrew-Cottrell]

https://github.com/google/closure-library/blob/master/closure/goog/math/rangeset.js#L29

 * Ranges are treated as half-closed: that is, they are exclusive of their end
 * value [start, end).

https://github.com/google/closure-library/blob/master/closure/goog/math/range.js#L176

goog.math.Range.containsPoint = function(range, p) {
  return range.start <= p && range.end >= p;
};

It appears goog.math.RangeSet.prototype.containsValue interprets each goog.math.Range as representing a half-open interval, but goog.math.Range.containsPoint uses a closed interval interpretation.

goog.require("goog.math.Range");
goog.require("goog.math.RangeSet");

var range = new goog.math.Range(0, 1);
var rangeSet = new goog.math.RangeSet();
rangeSet.add(range);

console.log(goog.math.Range.containsPoint(range, 1)); // true
console.log(rangeSet.containsValue(1)); // false

This might be consistent if there is an undocumented implication that a numeric point is a distinct concept to a numeric value, but it seems more likely this is unintentional.

[shicks]

Wow, thanks for pointing that out. That's a pretty glaring inconsistency.

In my opinion, Range is in the wrong, and in an ideal world we would change it to be half-open. Unfortunately, Range has a number of issues - for instance, its constructor allows passing numbers in either order, so it's kind of fundamentally closed. We have thousands of usages of Range and I fear that trying to change this behavior would be infeasible. There's far fewer uses of RangeSet, but I don't really want to change it to be closed. Also, RangeSet is pretty crufty (i.e. it implements the ES4 iterator pattern) and doesn't have a number of features I'd consider essential in a range set, so I'm not convinced we even necessarily want to double down on it.

That said, I'm testing out what would happen if we were to make the change(s) to Range.

[Andrew-Cottrell]

One way forward would be to take advantage of the point vs value naming inconsistency.

goog.math.Range.containsPoint could be documented as using the closed interval interpretation. A new goog.math.Range.containsValue function could be consistent with goog.math.RangeSet#containsValue in using a half-open interval interpretation.

goog.math.Range.containsPoint might also be deprecated, with the expectation new code — and eventually old code — would use goog.math.Range.containsValue.

---

If wholesale replacement is up for consideration, I suggest replacing goog.math.Range with goog.math.Interval, and goog.math.RangeSet with goog.math.IntervalSet, where an interval set may contain disjunct intervals.

Where a !== b

var x = new goog.math.Interval(a, b); // an immutable value type
assert x.includes(a) === true; // the first argument is inclusive
assert x.includes(b) === false; // the second argument is exclusive

Where Math.sign(b - a) === Math.sign(c - b) and none of a, b, c are equal

var x = new goog.math.Interval(a, b);
var y = new goog.math.Interval(b, c);
var z = goog.math.IntervalSet.of(x, y); // logical disjunction of `x`, `y`
assert z.length === 1; // `x` and `y` were eligible to be merged
assert z[Symbol.iterator].next().value.equals(new goog.math.Interval(a, c)) === true;
assert z.includes(a) === true;
assert z.includes(b) === true;
assert z.includes(c) === false;

Where x and y do not overlap and none of a, b, c, d are equal

var x = new goog.math.Interval(a, b);
var y = new goog.math.Interval(c, d);
var z = goog.math.IntervalSet.of(x, y); // logical disjunction of `x`, `y`
assert z.length === 2; // ineligible to be merged
assert z[Symbol.iterator].next().value.equals(new goog.math.Interval(a, d)) === false;
assert z.includes(a) === true;
assert z.includes(b) === false;
assert z.includes(c) === true;
assert z.includes(d) === false;

Where y is strictly within x and none of a, b, c, d are equal

var x = new goog.math.Interval(a, b);
var y = new goog.math.Interval(c, d);
var z = goog.math.IntervalSet.of(x).not(y); // logical conjunction of `x`, not `y`
assert z.length === 2; // it was necessary to split
assert z.includes(a) === true;
assert z.includes(b) === false;
assert z.includes(c) === false;
assert z.includes(d) === true;

Any design isomorphic with that implied by the above examples would do. I recommend the design and implementation be reviewed by a suitably qualified mathematician.

[Andrew-Cottrell]

Range has a number of issues - for instance, its constructor allows passing numbers in either order, so it's kind of fundamentally closed.

For functions that take two arguments, which together specify a half-open interval, I have found it useful to name the parameters inclusive and exclusive without implication that one is less than or greater than the other. For example

goog.math.Interval = function (inclusive, exclusive) {
    this.inclusive = inclusive;
    this.exclusive = exclusive;
    if (this.constructor === goog.math.Interval) {
        Object.freeze(this);
    }
};

goog.math.Interval.prototype.includes = function (number) {
    if (this.inclusive < this.exclusive) {
        return this.inclusive <= number && number < this.exclusive;
    }
    return this.exclusive < number && number <= this.inclusive;
};

This makes these functions easier to predict and makes it easier for calling code to avoid off-by-one errors (whether 1 whole unit or 1 ulp).

var longitudePrincipalInterval = new goog.math.Interval(180, -180);
assert longitudePrincipalInterval.includes(180) === true;
assert longitudePrincipalInterval.includes(-180) === false;

var radiansPrincipalInterval = new goog.math.Interval(Math.PI, -Math.PI);
assert radiansPrincipalInterval.includes(Math.PI) === true;
assert radiansPrincipalInterval.includes(-Math.PI) === false;

[shicks]

Guava has been quite successful with named factories for ranges: Range.closed(1, 3), Range.closedOpen(2, 4), Range.lessThan(5), Range.atLeast(6), etc. Simply accepting an inclusive and exclusive parameter and allowing either order seems like not the best API. If we were to reimplement a new Range, I would take that approach, with the factories ensuring that the arguments are ordered correctly.

I looked into making the two changes I was curious about: (1) checking the order in the Range constructor, and (2) simply changing it to be open on the upper side. The precondition caused about 50-100 unique errors in our codebase and would be quite difficult to change. The semantic change was actually pretty innocuous and only seemed to break one usage, surprisingly. I'm not super happy with just that change (again, due to what I said above where the constructor parameters are interchangeably closed/open depending on the order) but we could potentially actually get away with it. Some mitigating possibilities would be to add a define to opt-out of the precondition and that would allow proper semantics while still giving us a pass for the existing breakages.

[shicks]

Also, in terms of trying to insert a semantic distinction between "point" and "value", I'm not at all keen on that option. It's not something that's at all obvious without reading the documentation or implementation, since those terms don't actually have that meaning.

[Andrew-Cottrell]

Guava has been quite successful with named factories for ranges: Range.closed(1, 3), Range.closedOpen(2, 4), Range.lessThan(5), Range.atLeast(6), etc. Simply accepting an inclusive and exclusive parameter and allowing either order seems like not the best API. If we were to reimplement a new Range, I would take that approach, with the factories ensuring that the arguments are ordered correctly.

Although I have used parts of Guava many times, I had not previously noticed the Range class or its factory methods. It clearly has a more intuitive and flexible API than what I suggested. Thank you for mentioning it here; I will certainly learn from it.