Re: Maintaining an ordered array of attributes in an NSTextStorage subclass
Re: Maintaining an ordered array of attributes in an NSTextStorage subclass
- Subject: Re: Maintaining an ordered array of attributes in an NSTextStorage subclass
- From: Alastair Houghton <email@hidden>
- Date: Mon, 10 Aug 2009 22:22:51 +0100
On 10 Aug 2009, at 21:07, Keith Blount wrote:
Many thanks again for the reply, much appreciated. -
replaceCharactersInRange:withString:, -setAttributes:range: (and -
addAttribute:value:range:, which also needs overriding) is in fact
exactly where I'm trying to intercept things. The problem is _how_
best to maintain and keep up to date the array of comments, though,
so that it always contains, in order, a list of the comments that
appear as attributes in the text.
OK, so as you've discovered, this particular problem is potentially a
tricky one :-)
There are two general solutions of which I am aware to efficiently
storing range information in such a way that you don't need to update
every range every time there's an edit. The first is the traditional
"gap buffer" approach, whereby you store references to locations
*after* the gap relative to the end of the buffer, and references to
locations *before* the gap relative to the start of the buffer. That
way, you only need to update references when you move the gap across
them. The gap is, generally speaking the current edit location.
The second is to store the data as a tree, but to do everything by
length rather than by absolute positions. The idea is that each tree
node contains a count of the number of elements covered by it and all
of its children; then it's easy to know the position of each tree node
(since it is just the sum of the lengths of the node's left siblings
in the tree), and when you insert or delete elements you only have to
deal with the affected leaf node and its parents. You'd want to use a
balanced tree of some sort to control the worst case performance; a
red-black or 2-3 tree would work well. (For a simplistic
implementation you could store a linear list of lengths instead of
using a tree, but that would provide relatively poor random access
performance.)
I suspect the text system is using the latter approach or some
variation thereof (since it's better, though a little trickier to
implement); there are hints that this may be the case---for instance
the fact that attribute runs appear to be split if they overlap
existing attribute runs, which is a requirement for that scheme to
work. Some of the text system people who read this list may be able
to confirm one way or another (but it doesn't really matter).
As you might gather from the above, the attribute storage and
iteration methods in the text system are extremely efficient, so the
inefficiency in your proposal is really the construction and
maintenance of the NSArray.
So the next question is whether or not it's worth your while
implementing such a thing yourself off to one side, rather than just
using the text system's implementation already. The downside of using
the text system's implementation is that it will, necessarily, split
your comment ranges, and AFAIK you won't be able to tell the
difference between two adjacent comments containing the same data and
one comment that has been split (e.g. because someone made some text
bold in an overlapping range). If this really matters you might be
best off using your own range storage instead.
Assuming you really need the NSArray interface, I think what I would
be inclined to do is to write an NSArray subclass that worked by
iterating over the attributes in the text storage (since that avoids
having to implement the range-based store yourself, which *is* doable
and would be more efficient but it isn't a trivial bit of work). To
make it more efficient, keep a cache of the location of the last
attribute run retrieved from the array (and its notional index), then
when something asks for an adjacent index (highly likely) you can just
iterate forwards or backwards as appropriate.
If you really need random access to the array, you could cache the
last few locations and work from the closest one.
Kind regards,
Alastair.
p.s. Sorry this post is quite long, but it's quite an interesting
topic, I think :-)
--
http://alastairs-place.net
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden