Greetings,
"Etienne M. Gagnon" wrote:
>
> Hi Morgan.
>
> You should read the book:
>
> Introduction to Algorithms
> by Cormen, Leiserson & Rivest
>
> In particular, chapter 15 "Augmenting Data Structures" exposes
> techniques to decorate balanced binary trees with auxiliary data. The
> book both explains the algorithms and the detailed time complexity
> analysis.
Whoa... How weird. I had referred to that book, as the one I'd
read through (misnaming the author as Comer, from too much TCP/IP I
guess), and I must have spaced entirely on that chapter. I plead not
enough comprehension of the subject matter at the time I read it,
despite having read it explicitly to find that information...
That chapter describes EXACTLY (and much more theoretically strong)
what I described, happily. It's fascinating that this isn't part of any
standardized collections (STL, Collections API, etc.), but is so cleanly
described right there.
> While these algorithms are quite interesting, the "official" JDK API
> documentation does not define any class that provide their
> functionality. In other words, you shouldn't encode such an algorithm
> in java.util.TreeMap, as the additional functionality is not part of
> the specification.
That's something I'm concerned with as well. I'm very interested in
this being implemented, but I can recognize that it's not something that
should be necessarily done within the Classpath project. I suppose this
would be a place for another small Open Source library, instead?
> I am not really involved in the Classpath project, so you can take my
> opinion for what it is: an opinion. I do not mean that these
> algorithm should not be part of Classpath, just that they should
> probably be provided in the gnu.util package (or org.gnu.util, or
> whatever;-).
I guess I basically agree, although I'd like to ask a side question
about the Classpath classes... Is there any reason to automatically
mark 'private' instead of 'protected' the member functions of classes
done to the specification of the JDK API?
For instance, just looking at the JavaDoc for TreeMap on Sun's site
tells me that there are no 'protected' members, so I couldn't
straightforwardly extend TreeMap with my own implementation for only a
few key functions, I'd have to rewrite the important parts (any tree
rotations, insertion/deletion details, etc.) nearly entirely myself. Is
it necessary, for the specification, to carry over this practice? Is it
a cleanliness/abstraction issue? While the source IS available with
Classpath to modify freely, I feel it'd still be nicer to be able to
derive, rather than copy and modify.
> Have fun!
>
> Etienne
-- Morgan Schweers
