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

NodeList interface

From: <msabin@cromwellmedia.co.uk>
Date: Wed, 26 Aug 1998 08:07:10 -0400 (EDT)
Message-ID: <c=US%a=_%p=Cromwell_Media%l=ODIN-980826120412Z-33394@odin.cromwellmedia.co.uk>
To: <www-dom@w3.org>
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).
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());

which could have O(n) complexity for either an array or linked list
implementation.

With the current interface, the only way I can see of getting acceptable
performance would be for a NodeList to maintain a copy of a part of the
DOM tree in an internal array ... but that has overheads of it's own.

One other issue. You should specify whether modifications to the tree
(ie. insertBefore(), removeChild() etc.) are intended to be mirrored in
pre-existing NodeLists ... mutatis mutandis for NamedNodeMap.

Yours,


Miles Sabin
Internet Systems Architect
msabin@cromwellmedia.co.uk

Cromwell Media, 5/6 Glenthorne Mews, London, W6 0LJ, UK
tel: +44 (0)181 410 2230
Received on Friday, 25 September 1998 11:09:11 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 22 June 2012 06:13:45 GMT