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

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.

Robby