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

RE: NodeList interface

From: <msabin@cromwellmedia.co.uk>
Date: Mon, 28 Sep 1998 12:33:32 +0100
Message-ID: <c=US%a=_%p=Cromwell_Media%l=ODIN-980928113332Z-56799@odin.cromwellmedia.co.uk>
To: <www-dom@w3.org>
Hi all,

> From: Miles Sabin 
> Sent: 26 August 1998 1:07 pm
        ^^^^^^^^^^^^^^
> To: www-dom@w3.org
> Subject: NodeList interface

I'm not quite sure why this has only just appeared: my
comments were the result of a rushed reading of the spec
and some first thoughts on implementation strategies.
I've since re-read the spec rather more thoroughly
(which has cleared up a few confusions) and discovered
this list ... thanks for the helpful replies anyway.

I've been looking at variations on the caching schemes
that various people have mentioned, and whilst they
look quite workable for the for the NodeLists returned
by getChildNodes(), they're much more problematic for
getElementsByTagName() if you want to hang on to O(1)
insert and delete ... which is my main motive for opting
for a tree representation of the DOM heirarchy.

After much head scratching I've come to the conclusion
that there's no sensible way of implementing the DOM spec
that supports *both* efficient editing *and* indexed
access. This suggest (to me anyway) that a better
approach might be to accomodate the duplication of a
DOM (sub)tree from one implementation (eg. tuned for
editing) to another (eg. tuned for indexed access). Even
though this might seem to involve an unacceptable amount
of copying, it might be preferable for many applications.
There's a precedent for this from the graph algorthms
world: it's not uncommon to see conversions back and 
forth between linked and adjacency matrix representations
as context demands.

That said, if anyone knows of a method of obtaining the
preorder sequence number of a Node in amortized constant
or logarithmic time that would cheer me up no end ;-)

Cheers,


Miles
-- 
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 Monday, 28 September 1998 07:37:28 GMT

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