W3C home > Mailing lists > Public > www-dom@w3.org > July to September 1998

Re: NodeList interface

From: John Cowan <cowan@locke.ccil.org>
Date: Fri, 25 Sep 1998 14:39:28 -0400
Message-ID: <360BE360.307DE274@locke.ccil.org>
To: DOM List <www-dom@w3.org>
msabin@cromwellmedia.co.uk wrote:

> >The NodeList interface is absolutely hopeless: the 'get element by
> >index' model is in direct conflict with the natural implementation of
> >the DOM in terms of tree of linked nodes. The upshot is that the
> >following loop,
> >
> >       NodeList l = someNode.getChildNodes();
> >       for(int i = 0, limit = l.getLength(); i < limit; ++i)
> >               process(l.item(i));
> >
> >will have at best O(n*n) complexity (where n is the number of children).

Actually, things aren't as bad as that.  My in-progress DOM
delivers O(n) efficiency while using a pointer implementation that
identifies Node and NodeList (every node implements
both interfaces): getChildNodes() returns self.

The trick is to memoize the last argument passed to item() as well
as the result.  In cases like the above, the call "item(i)" will
effectively compute "someNode.cachedChild.nextSibling()" on every
call except the first.

John Cowan	http://www.ccil.org/~cowan		cowan@ccil.org
	You tollerday donsk?  N.  You tolkatiff scowegian?  Nn.
	You spigotty anglease?  Nnn.  You phonio saxo?  Nnnn.
		Clear all so!  'Tis a Jute.... (Finnegans Wake 16.5)
Received on Friday, 25 September 1998 14:39:51 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 20 October 2015 10:46:04 UTC