ludo@gnu.org (Ludovic Court$(D+2(Bs) writes:

> I wonder if there$B!G(Bs some other data structure with similar properties
> that doesn$B!G(Bt have the thread-safety issue.  Maybe Ian has an idea?

HAMTs (another Bagwell creation) might be a reasonable option, but I
don't have a complete implementation. I ran into some issues with it a
while back, but I have completely forgotten what it was. I do want them
in pfds, so I guess I could take this as the kick-up-the-arse to finish
it.

> The weight-balanced trees in MIT/GNU Scheme look interesting:
>
>   http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Weight_002dBalanced-Trees.html

I have those in pfds under the name bbtrees (for balanced binary
trees). They are pretty flexible, and you get reasonable times for a lot
of operations, but like a lot of tree structures not particularly cache
friendly.

-- 
Ian Price -- shift-reset.com

"Programming is like pinball. The reward for doing it well is
the opportunity to do it again" - from "The Wizardy Compiled"