[racket-dev] augmented rb-tree with customizable combinator

From: Danny Yoo (dyoo at hashcollision.org)
Date: Fri Nov 30 19:02:53 EST 2012

Hi Matthew,

Ok, I've generalized the code so you can use a custom node combinator to
compute the metadata at each node.  I've tried to write comprehensive
documentation's in collects/syntax-color/augmented-red-black.scrbl.  Maybe
it's a candidate for the data collection?

I don't think the red-black trees should replace the splay trees anymore:
although they have similar performance, the splay tree is just slightly
faster despite not being as balanced.  I believe the overhead of
maintaining all the pointers in the rb tree structure contributes to this.
 Still, the rb-tree stuff should hopefully be helpful to someone out there.

Should I keep collects/syntax-color/private/red-black.rkt
and collects/syntax-color/private/rb-token-tree.rkt in the repository, or
should I drop those two?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20121130/efb5c38c/attachment.html>

Posted on the dev mailing list.