- From: John Cowan <cowan@locke.ccil.org>
- Date: Fri, 25 Sep 1998 14:39:28 -0400
- 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