- From: John Cowan <cowan@locke.ccil.org>
- Date: Tue, 03 Nov 1998 15:29:42 -0500
- To: DOM List <www-dom@w3.org>
Stephen R. Savitzky wrote: > I find this quite insulting. My intent was to illustrate a rhetorical > point, not to give an optimal, industrial-strength algorithm for tree > traversal under all circumstances. No offense intended. I posted two responses (though without explaining why) in order to separate my two issues: why the DOM isn't really a tree (because it is "live" in my sense, subject to arbitrary changes from outside), and to talk about the specifics of iteration vs. recursion when walking trees. > You _do_ further illustrate my point, however: the algorithm you give fails > as miserably as mine if your visit or revisit function modifies the tree. Absolutely true. > > Because of the reliability of this algorithm vis-a-vis the recursive > > one, I believe it should be the standard way of walking DOM trees, > > and therefore it is essential that DOM implementations make the > > structural access methods fast. > > We are in agreement here, Excellent! > but I think you may have missed something. An > iterator, the state of which consists of a reference to the ``current > node'', and all of whose methods are inlineable, can be compiled by a good > optimizing compiler into the exact equivalent of your algorithm. Can you sketch this for me? I don't see how the recursive depth-search can be optimized away, since the iterative version depends on the existence of the parent pointer, which the original algorithm did not even mention. The breadth-search is obviously tail recursive and no fundamental problem. > An iterator that has to take structural changes into account _cannot_ be so > compiled; it is necessarily going to be _FAR_ less efficient. Agreed. > Similarly, > your algorithm cannot be used as the basis for a live NodeList. No, indeed. It is used in my DOMParser, which walks a (presumed static) DOM in order to generate SAX events from the nodes. > I believe > it is also essential that DOM implementations make structural _modification_ > methods fast, which is also incompatible with the kind of non-locality of > effects imposed by live NodeLists and ``robust'' (in your definition) > iterators. I hope that it is *not* utterly incompatible, but of course "fast" is a loosely defined term; if you mean O(1), you are probably correct. I concede that I don't yet see how best to do it, which is (one reason) why I have not published a DOM implementation. -- 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 Tuesday, 3 November 1998 15:28:41 UTC