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: Keith Blount <email@hidden>
- Date: Wed, 12 Aug 2009 09:02:42 -0700 (PDT)
Hi,
Many thanks for the detailed and thoughtful reply, and apologies for not replying sooner myself.
Having taken all your (and Graham's) suggestions and thoughts on board, after a lot of head-scratching and working things out on paper first, I think I have - tentatively - cracked it. I stuck with the text system's built-in attributes for the sake of simplicity, and this is basically the approach I have taken:
- My NSTextStorage subclass keeps a -comments NSMutableArray.
- Its primitive methods (-replaceCharactersInRange:..., -setAttributes:... and -addAttribute:... all check to see if a comment is being deleted or added during the current edit. If not, nothing special happens, so that normal typing isn't affected in any way. If a comment has been deleted or added, an internal flag is set, recording that the comments need rebuilding.
- From -fixAttributesInRange:, I call my own -fixCommentAttributeInRange: method. This fixes things up so that if a comment has been split, it re-joins it. i.e. If the same comment exists directly before and directly after the passed-in range, that comment is applied to the intermediate range too. This method also checks the internal flag to see if the comments array needs rebuilding. If so, it finds the previous comment before the passed-in range and then removes all comments after it from the comments array, and goes through the text from that point on looking for comments and adding them to the array. If it finds any comments that are already in the array, it alters them them to ensure that they are unique objects.
So far, this seems to work well. I've tested it on a 50,000 word document and it seems speedy, and the comments are kept up-to-date. There are still minor issues to address (such as how this implementation won't allow the adding of a comment to text that already has a comment associated with it), and it needs a lot more work and a lot more testing, but I'm hopeful.
Many thanks again for the replies and help - much appreciated.
All the best,
Keith
--- On Mon, 8/10/09, Alastair Houghton <email@hidden> wrote:
> From: Alastair Houghton <email@hidden>
> Subject: Re: Maintaining an ordered array of attributes in an NSTextStorage subclass
> To: "Keith Blount" <email@hidden>
> Cc: "Graham Cox" <email@hidden>, email@hidden
> Date: Monday, August 10, 2009, 9:22 PM
> 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