Re: NodeList interface

>> The standard kluge-around for almost tolerable efficiency seems to be to
>> have NodeList cache everything it finds,
>Is this really necessary, as opposed to just caching the current
>(i.e. last fetched) position?

Depends on how you expect people to use this monstrosity, and how
inefficient you're willing to be if they insist on accessing nodes out of
order.

>> refresh that cache if the tree structure has changed
>This is the really expensive item, I think.  Does anyone have a
>quick'n'dirty way of doing this?

Have each note be aware of how often the tree structure below it has
changed (ripple this up the tree when insertions/deletions occur). Have the
NodeList be aware of what that count was at the starting node last time the
NodeList was accessed. Have NodeList methods check its recorded count
against the actual count before they operate, and if different discard
previous work and recalculate at least as much as is required to answer the
current question.

Not elegant, but easy to implement, yields the right behavior, and is
better than redoing the search from the start every time. Obviously there
are approaches that attempt to determine which subtrees have changed and
limit recalculation to those... but you have to think about how much code
space and memory you're willing to spend on optimizing something that you
hope people won't be using very long.

The lack of a NodeList.destroy() method kept me from trying some approaches
I would otherwise have preferred; they would have led to memory leaks.
______________________________________
Joe Kesselman  / IBM Research
Unless stated otherwise, all opinions are solely those of the author.

Received on Friday, 25 September 1998 15:39:39 UTC