search

migrator / guava-libraries-2

Guava: Google Core Libraries for Java 1.6+
0 stars 0 forks source link

Add abstract support superclasses for NavigableSet, NavigableMap #50

Open migrator opened 9 years ago

migrator commented 9 years ago

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%2Forg%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/util/IntersectionNavigableSet.java

relevance: 2

migrator commented 9 years ago

summary: Not Defined

Please file these as separate requests.

status Not Defined creator: lowas...@google.com created at: Jul 16, 2014

migrator commented 9 years ago

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

status Not Defined creator: archie.c...@gmail.com created at: Jul 16, 2014