[racket-dev] Replacing the splay tree token-tree% with an rb-tree?

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Fri Nov 16 14:28:30 EST 2012

On Fri, Nov 16, 2012 at 1:02 PM, Danny Yoo <dyoo at hashcollision.org> wrote:
>> I wanted to surprise you by getting this all working by mid-week, but it's
>> taking longer than I thought... :)  So I might as well run it by you to make
>> sure the idea is sound before I go further on this track.
> The core rb implementation is almost done.  The search-by-position,
> insert-before, insert-after, and delete operations appear to be solid now.
> Hopefully I can get concat and split done by today (or tomorrow).
> There are some operations in the original token-tree% that aren't directly
> applicable to rb-trees.  In particular, I assume that the add-to-root-length
> and remove-root functions can be replaced with some alternative behavior
> that preserves the final effect on the editor state.  I should be able to
> simulate the splay tree's use of the root and replace that with a focused
> node in the rb tree.
> Is there a particular splay-tree property that we're really depending on?

I don't think so, but Im not the original author of this code.

> On the other hand, the rb implementation should support tree concatenation
> and in-place insertion, not limited just to inserting at the beginning and
> end of the tree.  (And concatenation of two trees is O(log(n)).  I'm not
> familiar enough with the lexer state management to know if these additional
> operations would be useful.

I don't really know either. I'm pretty sure concatenation is not useful, tho.


Posted on the dev mailing list.