Guarantee RangeMap iteration order

[GoogleCodeExporter]

http://stackoverflow.com/q/25646191/28465

Original issue reported on code.google.com by cpov...@google.com on 4 Sep 2014 at 2:34

[GoogleCodeExporter]

For comparison, Range*Set* says:

"The iterators returned by its Iterable#iterator method return the ranges in 
increasing order of lower bound (equivalently, of upper bound)."

Original comment by cpov...@google.com on 4 Sep 2014 at 2:35

[GoogleCodeExporter]

Would it make sense for RangeMap.asMapOfRanges() to return SortedMap<Range<K>, 
V>? Similarly for RangeSet.asRanges().

Original comment by cgdecker@google.com on 4 Sep 2014 at 3:25

[GoogleCodeExporter]

Internally, comments on CL 23059491 and CL 23565836 touch on this, as does 
<http://go/more-on-range-collection-sorted-views>. I feel like there may have 
been other discussions, too.

In short, there is some weirdness around defining a Comparator that does the 
right thing. I think that we're required to use RANGE_LEX_ORDERING: We must 
compare the beginning of the ranges first to get order right, and we must 
compare the end of the ranges also so that contains() works. But is that 
Comparator prone to misuse with other methods?

(Part of the discussion was that few users are likely to need the 
SortedMap/SortedSet features. The one counterexample we'd come across so far 
was a need for last*() methods.)

Original comment by cpov...@google.com on 4 Sep 2014 at 5:50

[GoogleCodeExporter]

I'm comfortable guaranteeing the iteration order, but not for returning a 
SortedMap.  As Chris alluded to, I see the reasoning as similar to why 
SortedMap.entrySet() doesn't return a SortedSet.

Original comment by lowas...@google.com on 4 Sep 2014 at 5:53

[GoogleCodeExporter]

Oh, right. I forgot that the Map case is especially bad -- definitely bad news 
for any comparator we might define, since it has to be a 
Comparator<Entry<...>>, and the value isn't necessarily Comparable.

RangeSet.asRanges() might be less bad than that, since both endpoints of the 
Range object are Comparable, but it's still potentially error-prone when used 
with any kind of element-relative method.

Original comment by cpov...@google.com on 4 Sep 2014 at 6:05

[GoogleCodeExporter]

Hmm, yeah... I was just thinking in terms of the ranges that are in the 
RangeSet/Map, which are non-overlapping and as such easy to represent as 
Sorted*. But I can see that it would be confusing with sub/head/tailSet/Map etc.

Original comment by cgdecker@google.com on 4 Sep 2014 at 6:06

[GoogleCodeExporter]

Fixed internally; change will be mirrored out soon.

Original comment by lowas...@google.com on 24 Sep 2014 at 6:54

• Changed state: Fixed

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<issue id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:08

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:07

• Added labels: Restrict-AddIssueComment-Commit