Add abstract support superclasses for NavigableSet, NavigableMap

[GoogleCodeExporter]

This issue is a suggestion for some new classes, based on my own experience. 
Working example code is provided.

Request #1:

  Add support superclasses AbstractNavigableSet and AbstractNavigableMap

Rationale:

Creating NavigableSet and NavigableMap implementations from scratch is really 
tricky and error-prone, due to the sheer number of methods to implement and 
their semantic intersection with order reversal, optional lower & upper bounds, 
subSet(), subMap(), etc.

Fortunately, abstract superclasses can implement most methods in terms of 
others, and manage the bounds in such a way that leaves the subclass to handle 
the "essence" of the set/map.

FWIW I've done this already and these classes could be used as an basis to 
start with. See 
https://code.google.com/p/jsimpledb/source/browse/#svn%2Ftrunk%2Fsrc%2Fjava%2For
g%2Fjsimpledb%2Futil

Request #2:

  Add a NavigableSet-specific implementation of Sets.intersection()

Rationale:

  Sets.intersection() suffers from the flaw that even if the intersection of two sets is empty, iterating their intersection takes time proportional to the size of first of the two sets given, no matter how small the second set is. Since often you won't know which set is smaller, this means you have a 50% chance of getting it badly wrong. 

  For two NavigableSets that use the same Comparator, there is a more efficient algorithm that iterates in O(N) queries, where N is the number of elements in the *smallest* of the two sets - no matter in which order they are presented.

  In common scenarios such as iterating through key/value ranges in large datasets, this can make a huge difference.

I also have an implementation for this intersection iteration algorithm here: 
https://code.google.com/p/jsimpledb/source/browse/trunk/src/java/org/jsimpledb/u
til/IntersectionNavigableSet.java

Original issue reported on code.google.com by archie.c...@gmail.com on 16 Jul 2014 at 6:28

[GoogleCodeExporter]

Please file these as separate requests.

Original comment by lowas...@google.com on 16 Jul 2014 at 6:41

[GoogleCodeExporter]

"Add a NavigableSet-specific implementation of Sets.intersection()" filed as 
issue #1804.

Original comment by archie.c...@gmail.com on 16 Jul 2014 at 6:48

[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 1 Nov 2014 at 4:17

• Changed state: Migrated

[GoogleCodeExporter]

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

• Added labels: Restrict-AddIssueComment-Commit