• sybrandy (10/10) Jul 23 2010 Not sure if this is what's used by an Appender, but this seems like a
• dsimcha (6/16) Jul 23 2010 Appender is just a wrapper over the builtin array that caches the capaci...
• BLS (5/15) Jul 23 2010 AFAIK ropes are implemented by using AVL or RB Trees. So every operation...
• Andrej Mitrovic (2/16) Jul 23 2010 Also see http://www.ibm.com/developerworks/java/library/j-ropes/ for a l...

sybrandy <sybrandy gmail.com> writes:

Not sure if this is what's used by an Appender, but this seems like a 
cool data structure:

http://ahmadsoft.org/ropes/

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

It's not good for indexing, but concatenation is an O(1) operation, so 
using it when you have to do a lot of appending seems to make a lot of 
sense.  And, if I understand appender correctly, it's meant only for 
appending data and that you need to convert it to a range/array before 
you work with it.

Casey

dsimcha <dsimcha yahoo.com> writes:

== Quote from sybrandy (sybrandy gmail.com)'s article
 Not sure if this is what's used by an Appender, but this seems like a
 cool data structure:
 http://ahmadsoft.org/ropes/
 http://en.wikipedia.org/wiki/Rope_%28computer_science%29
 It's not good for indexing, but concatenation is an O(1) operation, so
 using it when you have to do a lot of appending seems to make a lot of
 sense.  And, if I understand appender correctly, it's meant only for
 appending data and that you need to convert it to a range/array before
 you work with it.
 Casey

Appender is just a wrapper over the builtin array that caches the capacity
instead
of having to look it up in the bowels of the GC implementation.  Appending to a
regular array is amortized O(1) provided that the array implementation isn't
absolutely asinine.  (Most cases of concatenation, at least in my experience,
are
appending.)

BLS <windevguy hotmail.de> writes:

On 23/07/2010 23:43, sybrandy wrote:
 Not sure if this is what's used by an Appender, but this seems like a
 cool data structure:

 http://ahmadsoft.org/ropes/

 http://en.wikipedia.org/wiki/Rope_%28computer_science%29

 It's not good for indexing, but concatenation is an O(1) operation, so
 using it when you have to do a lot of appending seems to make a lot of
 sense. And, if I understand appender correctly, it's meant only for
 appending data and that you need to convert it to a range/array before
 you work with it.

 Casey

AFAIK ropes are implemented by using AVL or RB Trees. So every operation 
is similar to what you expect from the underlaying data structure.
Bjoern Lietz
Beside, some new IDE SourceCode-Editors are using Ropes as their workhorse.

Andrej Mitrovic <and.mitrovic hotmail.com> writes:

sybrandy Wrote:

 Not sure if this is what's used by an Appender, but this seems like a 
 cool data structure:
 
 http://ahmadsoft.org/ropes/
 
 http://en.wikipedia.org/wiki/Rope_%28computer_science%29
 
 It's not good for indexing, but concatenation is an O(1) operation, so 
 using it when you have to do a lot of appending seems to make a lot of 
 sense.  And, if I understand appender correctly, it's meant only for 
 appending data and that you need to convert it to a range/array before 
 you work with it.
 
 Casey

Also see http://www.ibm.com/developerworks/java/library/j-ropes/ for a lengthy
cover of ropes. SGI has an implementation of ropes in it's STL lib
http://www.sgi.com/tech/stl/Rope.html .