Text manipulation - underlying data structures

Jim Witte jswitte at bloomington.in.us
Thu May 16 14:55:00 EDT 2002


>   put tNum into item 1 of line tNum of tVar
>
> forces the engine to go through tVar looking for 4998th carriage 
> return; then when tNum is 5000 the engine has to go through again 
> looking for the

   I was thinking about this in my CS class a couple of weeks ago, and 
wondered about a data structure that would basically be an array (for 
fast random access), but every k positions (lines in this case I 
suppose) would maintain a pointer to that position, making a new 
pointer-list of length n/k.  Then another pointer list would be made off 
of this one, of length n/k^2, and so on forming a pointer tree.  Then an 
access into the original list should be able to be made close to 
logrithmic time (you'd have a small semi-constant to access up the 
pointer tree, and a linear search of O(k) once you got to the correct 
k-section of the original list.  This would probably only be useful for 
large data sets (say n>1000 maybe k=20 would make sense), but would it 
be worthwhile implementing something like this in Rev's text engine?

Jim




More information about the use-livecode mailing list