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

> 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?

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20121116/488849b2/attachment.html>