<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>I wanted to surprise you by getting this all working by mid-week, but it&#39;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.</div>

</blockquote></div><br><div>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).</div>

<div><br></div><div>There are some operations in the original token-tree% that aren&#39;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&#39;s use of the root and replace that with a focused node in the rb tree.</div>

<div><br></div><div>Is there a particular splay-tree property that we&#39;re really depending on?</div><div><br></div><div>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&#39;m not familiar enough with the lexer state management to know if these additional operations would be useful.</div>