Support for NavigableMap and NavigableSet in TreeMultimap

[gissuebot]

Original issue created by buko.obele on 2008-03-16 at 09:52 PM

---

The TreeMultimap implementation ought to support the NavigableMap
interface. Need a quick way to get an ascending/descending iterator given
a starting key.

[gissuebot]

Original comment posted by kevinb9n on 2008-03-21 at 10:53 PM

---

TreeMultimap cannot implement NavigableMap as it is not a map. But if you clarify
your use cases we'll try to make sure it has the functionality you need.

[gissuebot]

Original comment posted by jared.l.levy on 2008-03-22 at 12:59 AM

---

TreeMultimap.keySet() returns a SortedSet. You can call
TreeMultimap.keySet().tailSet(key).iterator() to get an ascending iterator with a
starting key.

If for a given multimap, you consistently want a descending iterator, you can call
the TreeMap constructor with a comparator that reverses the natural ordering of keys.

However, there's no way to quickly generate ascending and descending iterators for a
particular multimap. For that to work, TreeMultimap.keySet() would have to return a
NavigableSet.

---

Labels: -Type-Defect, Type-Enhancement

[gissuebot]

Original comment posted by jared.l.levy on 2008-04-03 at 05:23 PM

---

I'll deal with this eventually, might it might be a while until I get to it.

There are two major factors involved. First, we want to keep supporting Java 5, which
lacks the NavigableSet and NavigableMap interfaces. Second, those interfaces have
tons of methods that we'd have to implement.

---

Status: Accepted
Owner: jared.l.levy

[gissuebot]

Original comment posted by kevinb9n on 2008-05-27 at 06:55 PM

---

My current thoughts are that we're open to possibly having implementations that
support NavigableFoo in the future, we should not get into attempting any interfaces
like NavigableKeysMultimap, NavigableValuesMultimap, etc. The complexity budget would
be way overspent at that point. Also, we'll only be able to add Navigable* support
inasmuch as we can do so without breaking any backward compatibility with 1.0. I
think this is a livable situation.

Changing to Priority-Low as a way of saying we won't be thinking about this for a while.

---

Labels: -Priority-Medium, Priority-Low

[gissuebot]

Original comment posted by jed.wesleysmith on 2008-06-14 at 04:52 AM

---

Please see http://code.google.com/p/google-collections/issues/detail?id=81 as a clean way of having Multimap
support all Collection interfaces that is not dependant on Java6.

[gissuebot]

Original comment posted by jared.l.levy on 2008-09-12 at 05:52 PM

---

I've implemented, but haven't released,
http://code.google.com/p/google-collections/issues/detail?id=81

That lets you create a multimap whose get() method returns a TreeSet.

We don't yet have the ability to create a Multimap whose asMap() view is a SortedMap
or a NavigableMap.

[gissuebot]

Original comment posted by kevinb9n on 2009-09-17 at 06:02 PM

---

(No comment entered for this change.)

---

Labels: Milestone-Post1.0

[gissuebot]

Original comment posted by jared.l.levy on 2010-04-22 at 06:14 AM

---

With an ImmutableMultimap, many of the views, such as those returned by get(), are
ImmutableCollections, which have an asList() method. Once you have a List, it's easy
to use index-based logic to iterate backwards or whatever else you want to do. While
there's isn't a sorted version of ImmutableMultimap, one copied from a TreeMultimap
will preserve the iteration ordering.

That doesn't help when use need mutability.

---

Owner: ---

[gissuebot]

Original comment posted by kevinb@google.com on 2010-07-30 at 03:53 AM

---

(No comment entered for this change.)

---

Labels: -Milestone-Post1.0

[gissuebot]

Original comment posted by kevinb@google.com on 2010-07-30 at 03:57 AM

---

(No comment entered for this change.)

---

Labels: -Priority-Low

[gissuebot]

Original comment posted by kevinb@google.com on 2011-07-13 at 06:18 PM

---

(No comment entered for this change.)

---

Status: Triaged

[gissuebot]

Original comment posted by fry@google.com on 2011-12-10 at 03:14 PM

---

(No comment entered for this change.)

---

Labels: Package-Collect

[gissuebot]

Original comment posted by wasserman.louis on 2011-12-23 at 11:32 AM

---

Are we interested in pursuing this for guava-jdk6?

[gissuebot]

Original comment posted by wasserman.louis on 2011-12-31 at 05:17 PM

---

(No comment entered for this change.)

---

Blocked On: #32

[gissuebot]

Original comment posted by wasserman.louis on 2012-02-05 at 09:43 PM

---

Issue #893 has been merged into this issue.

[gissuebot]

Original comment posted by fry@google.com on 2012-02-16 at 07:17 PM

---

(No comment entered for this change.)

---

Status: Acknowledged

[gissuebot]

Original comment posted by wasserman.louis on 2012-04-17 at 10:33 PM

---

I have a CL that makes these changes to TreeMultimap.

---

Blocked On: -#32

[gissuebot]

Original comment posted by wasserman.louis on 2012-04-19 at 03:01 PM

---

Do we have any objection to this, other than --

a) the effort involved
b) binary compatibility, which can be addressed with careful use of bridge methods

[gissuebot]

Original comment posted by cpovirk@google.com on 2012-04-23 at 03:56 PM

---

GWT support may also complicate things, since code-size concerns have kept us from introducing the Navigable* interfaces there. That's a larger decision, but it's not necessarily a blocker, as we can create a NavigableOrSortedSet (and Map equivalent) that does the right thing under both versions:

"normal Java" version:
@GwtCompatible(emulated = true)
interface NavigableOrSortedSet<E> extends NavigableSet<E> {}

GWT version:
interface NavigableOrSortedSet<E> extends SortedSet<E> {}

Then we can write:
return new NavigableOrSortedSet<E>() { ... };

I suspect that it's fine to go ahead with this, but others should speak up if they disagree.

[gissuebot]

Original comment posted by wasserman.louis on 2012-04-23 at 04:46 PM

---

My only concern with this is that the Javadoc come out right -- I'm not sure how that'll work out. We'll also have to add GWT "wrappers" to make the interfaces happy in GWT -- e.g. extending TreeMap with NavigableOrSortedMap, just for the sake of returning it, I think?

[gissuebot]

Original comment posted by cpovirk@google.com on 2012-04-23 at 05:11 PM

---

Assuming that NavigableOrSortedSet is package-private, the generated Javadoc will show NavigableSet as the superclass (or SortedSet if we were to generate from the GWT sources).

GWT wrappers: I hadn't thought of this. Previously when I'd tried NavigableOrSortedSet, it had been so that ImmutableSet could extend it. If we ever need to return a TreeSet as a NavigableOrSortedSet, we will indeed need some kind of wrapper. Maybe we'll be lucky and it won't come up.

[gissuebot]

Original comment posted by wasserman.louis on 2012-04-23 at 05:13 PM

---

To be fair...TreeSet isn't final, at least in the JDK. If we can extend it, that's only a few lines of code added. It feels evil, but it's doable and effective.

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-30 at 07:41 PM

---

(No comment entered for this change.)

---

Labels: -Type-Enhancement, Type-Enhancement-Temp

[gissuebot]

Original comment posted by kevinb@google.com on 2012-05-30 at 07:45 PM

---

(No comment entered for this change.)

---

Labels: -Type-Enhancement-Temp, Type-Enhancement

[gissuebot]

Original comment posted by kevinb@google.com on 2012-06-22 at 06:16 PM

---

(No comment entered for this change.)

---

Status: Research

[gissuebot]

Original comment posted by lowasser@google.com on 2012-11-05 at 11:08 PM

---

(No comment entered for this change.)

---

Status: Accepted
Owner: lowasser@google.com
Labels: Milestone-Release14

[gissuebot]

Original comment posted by lowasser@google.com on 2012-11-06 at 10:42 PM

---

Submitted internally, should be mirrored out soon.

---

Status: Fixed