Re: Walking the DOM (was: XML APIs)

John Cowan <cowan@locke.ccil.org> writes:

> Stephen R. Savitzky wrote:
> 
> > Throwing an exception requires an O(log N) test somewhere.
> 
> No, it doesn't.  It just takes the pseudo-timestamp method I described
> earlier.  That method is O(1) if every Node has a direct reference
> to ownerDocument, which is not unreasonable considering it is
> in the "natural model".

I was thinking that you'd have to mark every ancestor of a changed node
(which would behave better in the face of frequent modification).  But in
fact even with pseudo-timestamps on the document, you need an O(log N) test
to determine whether an iterator is inside the part of the document that
changed; presumably you wouldn't want to invalidate _all_ iterators, only
the ones currently inside the affected subtree.  

So with the timestamp on the document, the test is actually O(i log N) where
i is the number of iterators actually used between mutations.

Determining the desired behavior when a subtree that contains an iterator is
_moved_ is even more difficult.  One can make a good case either way.

My current impression is that, since iterator implementations are
comparatively cheap, it should be possible for a programmer to obtain an
iterator from a factory, with the behavior under various error conditions
passed to the factory as a parameter.

-- 
 Stephen R. Savitzky   Chief Software Scientist, Ricoh Silicon Valley, Inc., 
<steve@rsv.ricoh.com>                            California Research Center
 voice: 650.496.5710   fax: 650.854.8740    URL: http://rsv.ricoh.com/~steve/
  home: <steve@starport.com> URL: http://www.starport.com/people/steve/

Received on Friday, 6 November 1998 12:59:03 UTC