Support ordinal scale inversion.

[jheer]

This PR adds methods and test cases for inverting ordinal scales. The methods can be useful for supporting interaction (e.g., selection, brushing) over ordinal encodings.

For base ordinal scales, an inverted index is constructed as needed to perform simple reverse lookups. The method returns undefined if no matching domain value exists. If the scale has duplicate range values, the domain element with lowest index in the domain array is returned.

For spatial (band/point) scales, either a single point or spatial range can be inverted. Binary search of discretized range values is used to determine indices into the domain array. Adjustments are included to respect padding between bands. The return value is an array of domain elements spanned by the input range, or undefined if no valid elements are found.

[mbostock]

The new ordinal.invert feature seems reasonable. I think the only thing I’d change would be to rename the internal variable to inverseIndex because I tend to avoid abbreviations.

I’m less certain about {band,point}.invert, so if you want to merge ordinal.invert right away it’d be helpful to break it out into a separate pull request.

Perhaps part of it is that band.invert overloads the meaning of scale.invert slightly, and there are also two overloaded forms of band.invert (one- and two-argument). It makes me think of quantize.invertExtent, which is not called quantize.invert because it returns the extent of values from the domain rather than just a single value. Perhaps band.invertExtent would be a better name, here? (Although normally I think of an extent as being defined just by two values, so maybe that’s not a big improvement.)

Also I need to think through whether the upper and lower bounds should be inclusive or exclusive etc. It’s tricky.

[jheer]

Thanks. I can break this up into 2 PRs as you suggest. For our own purposes, the band/point scale inversion is the more valuable of the features, as it provides a useful mechanism for brushing and linking over ordinal spatial domains. I also thought about possibly naming this method invertExtent; I'll make that change on the subsequent PR.

One question for you regarding ordinal.invert: the current behavior returns a single element (the first found in the domain). Either as an addition or as an alternative, one could imagine an invertExtent method that returns an array of all corresponding domain elements. Do you have a preference for one, the other or both?

[mbostock]

You don’t strictly need a new API to support brushing and linking over ordinal domains. This example should be easily ported to the D3 4.0 API:

http://bl.ocks.org/mbostock/4349509

That said I do not mean to suggest that band.invert and point.invert are not useful; I think they likely are. I just need more time to think about their design before I can commit to supporting them indefinitely.

[jheer]

I've updated this PR to include only ordinal.invert; I'll open a separate PR for band/point invertExtent.

[mbostock]

It occurs to me that this also (inadvertently) exposes point.invert and band.invert because of how band and point scales are implemented…

[jheer]

Now deletes the invert property in the band constructor, as is done for unknown.

[mbostock]

Thanks. I have two minor remaining considerations:

• Is it okay that ordinal.invert implicitly coerces the range to strings? That’s symmetric with how ordinal treats the domain, but previously the code didn’t make any assumptions about the range value types. Would it be better to use array.indexOf to scan the range?
• Is it okay that ordinal.invert returns only the first string-coerced match? Should it return an array of matches instead?

I find it hard to answer these questions because I don’t have a good motivating use case: it seems like the primary use case is brushing a band or point scale, not an ordinal scale. I think I need to make some examples first. If you have other ideas for how this could be useful, please let me know.

[jheer]

I raised the array return value issue in a question for you in an earlier comment. If you'd like to provide array return values (in which case perhaps something like invertExtent may be more appropriate?) and avoid string coercion, we might simply replace this PR with something like:

scale.invertExtent = function(y) {
  return domain.filter(function(d, i) { return y === range[i]; });
};

As for use cases, you're absolutely right that band and point scales are the primary motivation for these inversion PRs. I initially included (vanilla) ordinal inversion for API parity / completeness.

[mbostock]

I appreciate you mentioning it earlier; I’m just keeping notes.

That seems like a pretty clean and simple implementation of ordinal.invertExtent. What do you think? Is it useful?