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

Re: NodeList interface

From: Mike Champion <mcc@arbortext.com>
Date: Fri, 25 Sep 1998 14:02:06 -0400
Message-Id: <>
To: <www-dom@w3.org>
At 08:07 AM 8/26/98 -0400, msabin@cromwellmedia.co.uk wrote:
>Am I too late with this?


>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).

We know; don't get the "limit" up front, but loop until l.item(i) returns
an error.  The number of items in a NodeList can change while the loop is
executing, not to mention the fact that many implementations have no way of
knowing the number of items without counting all them.  That at least makes
it an O(n) algorithm.

>This is a bit unfortunate, given that this is likely to be fairly
>typical NodeList usage.
>The alternative would be to provide an iterator style interface, ie.
>	NodeList l = someNode.getChildNodes();
>	NodeListIterator i = l.elements();
>	while(i.hasNext())
>		process(i.next());

Something like this will be in Level 2.  This is a classic religious issue
-- This is obviously the right solution to many people, and obviously wrong
to many others (especially those VB and JavaScript programmers who never
heard iterators, and are perfectly happy with the "collection" model that
we tried to capture in NodeList).

Let me assure you that this part of the spec was *intensively* discussed
(for months!!!) and the points you're making were taken into consideration.
 The current wording is a very carefully considered compromise.

Mike Champion
Received on Friday, 25 September 1998 14:05:19 UTC

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