Eric Mahurin wrote:
> If you start mixing edits and movements, I don't think the performance 
> will
> be very good because a fixup is O(n) after some edits.  Consider a 
> sequence
> of n (insert_before;left).  Each left will do a full fixup making this
> sequence O(n**2).

It's about 5x slower than a gap buffer in this case for the 1000x100 
size, but breaks even by the time you do 20 insert_before()s between 
left()s.  On the other hand, I think any array-based approach has an 
O(n^2) worst case -- there's always some locality assumption.  For 
example, a gap buffer will be quadratic for a sequence of n 
(insert_before; up; insert_after; down) on a string with longish lines, 
since it has to shuffle half the buffer back and forth (try attached). 
The patch approach seems reasonable given the limitations of working in 
a high-level interpreted language with fast strings, though it wouldn't 
make sense in C.
-- 
Posted via http://www.ruby-forum.com/.