RE: Alternative to the Live NodeIterator

At 01:15 AM 5/1/98 , Andrew n marshall wrote:
>> -----Original Message-----
>> From: Mike Champion [mailto:mcc@arbortext.com]
>> Subject: Re: Alternative to the Live NodeIterator
> . . .
>>>  It seems to require that a globale list of all NodeIterators be
maintained
>>> somewhere, each with a abstract description of the search criteria.  Every
>>> time a node is added (or worse, an entire tree), it has to compared every
>>> search criteria and additional processing may be require to determine
>>> ordering.
>>
>> I certainly hope not!  It has always been my assumption that each
>> NodeIterator knows where it points to in the tree (e.g., "after the Node at
>> address 0xbeef0666"), and when a call comes to re-position the iterator or
>> return its next or previous node, it would use the tree itself to
>> re-position it properly.
>
>The reference cannot be directly to the node; what if the referenced node is
>removed?
>
>So the reference must begin from some parent.  Then I have to ask how does
>this work if the reference node is deleted?  What if several nodes are
>deleted, destroying both indexes and identity references?
>
>I think either a backend event interface or a marker node within the tree are
>required.  Both concepts require references to the node iterators.
>
I am going to answer these questions using fuzzy references to a possible
implementation. Don't take that to imply that I am recommending any particular
implementation, but it should give you some ideas about how I think iterators
can be efficiently implemented. Your mail makes it clear that you have already
thought about at least some of the things I'm going to say.

Any object which contains a reference to one or more nodes in the tree will
have
to be "maintained" during editing operations. There are many ways to implement
this, obviously, but one way, conceptually at least, is to have methods like
beforeDelete(Node nodeBeingDeleted), afterInsert(Node nodeBeingInserted), etc.
If you implement your iterators as a linked list then on a Node delete
operation
you can call
  myIteratorClass::beforeDelete(Node nodeBeingDeleted) {
    if nodeBeingDeleted is something I reference then
       fix up my reference by finding an appropriate node that will still
       be around after nodeBeingDeleted is gone.
    }
    nextIterator()->beforeDelete(nodeBeingDeleted);
  }
It is easy and cheap to implement the iterators as a linked list, array, or
similar and the fixups that they have to do on a delete is very simple. I
don't see why you need to instead keep a reference to some parent.

In fact, I don't see how it would help you to have a reference to a parent
anyway
since you will want your iterators to work with Ranges as well and Ranges can
remove large portions of the tree including all parents except the top-level
document node. (Note that to support Range editing operations beforeDelete()
should be overloaded to take a Range rather than a Node. The fixups won't
be much
harder.)

I don't understand your comment about updating based on search criteria. As
long
as you fix up the reference in the iterator you can apply the search criteria
the next time the iterator is moved. Unless maybe you are imagining creating a
list of all hits and storing that. I would not recommend doing that as it
would
restrict the usefulness of your application to small documents that need to be
completely parsed and, probably, in memory.

Peter
---------------------------------------------------------------------------
Peter Sharpe, Chief Scientist, SoftQuad Inc.  Tel: +1 604 585 8394 ext. 312
#108-10070 King George Highway, Surrey, B.C., CANADA V3T 2W4  Fax: 585 1926
Internet: peter@sq.com or peter@sqwest.bc.ca     World Wide Web:
<http://www.sq.com/>www.sq.com

Received on Friday, 1 May 1998 11:55:28 UTC