search

fengshao0907 / guava-libraries

Automatically exported from code.google.com/p/guava-libraries
Apache License 2.0
0 stars 0 forks source link

Support for NavigableMap and NavigableSet in TreeMultimap #51

Closed GoogleCodeExporter closed 9 years ago

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

Original issue reported on code.google.com by buko.ob...@gmail.com on 16 Mar 2008 at 9:52

GoogleCodeExporter commented 9 years ago 
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.

Original comment by kevin...@gmail.com on 21 Mar 2008 at 10:53

GoogleCodeExporter commented 9 years ago 
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.

Original comment by jared.l....@gmail.com on 22 Mar 2008 at 12:59

GoogleCodeExporter commented 9 years ago 
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.

Original comment by jared.l....@gmail.com on 3 Apr 2008 at 5:23

GoogleCodeExporter commented 9 years ago 
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.

Original comment by kevin...@gmail.com on 27 May 2008 at 6:55

GoogleCodeExporter commented 9 years ago 
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.

Original comment by jed.wesl...@gmail.com on 14 Jun 2008 at 4:52

GoogleCodeExporter commented 9 years ago 
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.

Original comment by jared.l....@gmail.com on 12 Sep 2008 at 5:52

GoogleCodeExporter commented 9 years ago

Original comment by kevin...@gmail.com on 17 Sep 2009 at 6:02

GoogleCodeExporter commented 9 years ago 
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.

Original comment by jared.l....@gmail.com on 22 Apr 2010 at 6:14

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 30 Jul 2010 at 3:53

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 30 Jul 2010 at 3:57

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 13 Jul 2011 at 6:18

GoogleCodeExporter commented 9 years ago

Original comment by fry@google.com on 10 Dec 2011 at 3:14

GoogleCodeExporter commented 9 years ago 
Are we interested in pursuing this for guava-jdk6?

Original comment by wasserman.louis on 23 Dec 2011 at 11:32

GoogleCodeExporter commented 9 years ago

Original comment by wasserman.louis on 31 Dec 2011 at 5:17

GoogleCodeExporter commented 9 years ago 
Issue 893 has been merged into this issue.

Original comment by wasserman.louis on 5 Feb 2012 at 9:43

GoogleCodeExporter commented 9 years ago

Original comment by fry@google.com on 16 Feb 2012 at 7:17

GoogleCodeExporter commented 9 years ago 
I have a CL that makes these changes to TreeMultimap.

Original comment by wasserman.louis on 17 Apr 2012 at 10:33

GoogleCodeExporter commented 9 years ago 
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

Original comment by wasserman.louis on 19 Apr 2012 at 3:01

GoogleCodeExporter commented 9 years ago 
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.

Original comment by cpov...@google.com on 23 Apr 2012 at 3:56

GoogleCodeExporter commented 9 years ago 
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?

Original comment by wasserman.louis on 23 Apr 2012 at 4:46

GoogleCodeExporter commented 9 years ago 
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.

Original comment by cpov...@google.com on 23 Apr 2012 at 5:11

GoogleCodeExporter commented 9 years ago 
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.

Original comment by wasserman.louis on 23 Apr 2012 at 5:13

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 30 May 2012 at 7:41

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 30 May 2012 at 7:45

GoogleCodeExporter commented 9 years ago

Original comment by kevinb@google.com on 22 Jun 2012 at 6:16

GoogleCodeExporter commented 9 years ago

Original comment by lowas...@google.com on 5 Nov 2012 at 11:08

GoogleCodeExporter commented 9 years ago 
Submitted internally, should be mirrored out soon.

Original comment by lowas...@google.com on 6 Nov 2012 at 10:42

GoogleCodeExporter commented 9 years ago 
This issue has been migrated to GitHub.

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

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

GoogleCodeExporter commented 9 years ago

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