On Fri, Nov 16, 2012 at 1:02 PM, Danny Yoo <d...@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 _________________________ Racket Developers list: http://lists.racket-lang.org/dev