Happy Happy Joy Joy (was: On to Hydro)

[Dan Bornstein]

Jonathan S. Shapiro writes:
>It is a straightforward adaptation of red-black trees to allow multiple
>instances of the same value -- internally you just need a counter on the
>nodes.

and then, in a later message:
>In general, if a container is to be expected to hold unorderables, then it
>must not rely purely on the < operator.  In practice, my suggestion is to
>build containers to separate the comparison operator from the objects
>compared. I should specify the comparison operator when initializing the
>container.

I agree strongly with that sentiment. I don't know how many times
the java.util collection classes have p'ed me off because I couldn't
just tell them to compare (and hash) with a different function.

However, allowing arbitrary choice of comparison means that it's not
necessarily as easy as adding a counter when you want to allow multiple
instances of the "same" value in a collection. In particular, since "same"
doesn't necessarily mean "identical object" once you allow for the choice
of comparison operator, if you are interested in letting users recover the
actual objects put into a collection, then you do have to keep all of them,
even if a newly-added object is considered "equal" to one already in the
collection.

Feeling somewhat nit-picky today,

-dan