- From: Stephen R. Savitzky <steve@rsv.ricoh.com>
- Date: 06 Nov 1998 10:01:44 -0800
- To: DOM List <www-dom@w3.org>
- Message-ID: <qcpvb066pj.fsf@gelion.crc.ricoh.com>
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