Walk DOM Tree in Reverse?

[delraydog]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling ...

For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

Thanks,
Cliff.

[VK]

de*******@gmail .com wrote:

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling ...

For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

I might be missing your problem:- an actual HTML code would be helpful.
The tree is...uhm... a tree. It means that can be a lot of children
(leaves) but only one parent (branch) for each child. Or - using
database terms - these are one-to-many relations, not many-to-many.

[Thomas 'PointedEars' Lahn]

de*******@gmail .com wrote:

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling ...
You have to recurse into the subtree of the previousSibling until
there are no more child nodes, i.e. until there is no lastChild.
For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

myText2.previou sSibling....par entNode.previou sSibling.lastCh ild...
..previousSibli ng....parentNod e...

See?
PointedEars

[Lasse Reichstein Nielsen]

de*******@gmail .com writes:

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child = child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.
If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Thomas 'PointedEars' Lahn]

Lasse Reichstein Nielsen wrote:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child =
child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.

Very nice. There is one catch, though: after the very first node of the
document tree has been processed, action() is called with `null', and if
the reference to the above function is passed as callback, there will be
a script error in the end ("null has no properties"). So either the
callback is modified so that `node.tagName' and `node.nodeType' are only
evaluated if `node' refers to an object, or the second call of `action'
should not take place if `element' does not refer to an object.
Furthermore, text nodes have no `tagName' property.

It would also be nice if one could use the return value of traverseDFTRL() ,
and to allow for another identifier without modifying the function body.

Hence the following suggestion:

function isMethod(a)
{
var t;
return (a && ((t = typeof a) == "function" || t == "object"));
}

function traverseDFRTL(e lement, action)
{
for (var child = (element || document.docume ntElement).last Child;
child;
child = child.previousS ibling)
{
arguments.calle e(child, action);
}

if (isMethod(actio n))
{
return action(element) ;
}
}

var nodes = [];

alert(traverseD FRTL(
null,
function(node)
{
if (node)
{
nodes.push(node .nodeName
+ (typeof node.nodeValue == "string"
? (' "' + node.nodeValue + '"')
: ""));
}

return nodes;
}).join("\n"));
PointedEars

[Lasse Reichstein Nielsen]

Thomas 'PointedEars' Lahn <Po*********@we b.de> writes:

Lasse Reichstein Nielsen wrote:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child =
child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.
Very nice. There is one catch, though: after the very first node of the
document tree has been processed, action() is called with `null',

I can't see how. The "action" callback function is only ever called
with the value of the "element" parameter. It can only be called with
a null value if "element" is null. The recursive calls are only made
if "child" is not null, so they can't cause it, so "action" should
only be called with null arguemnt if someone calls traverseDFRTL with
a first parameter that is null.
and if the reference to the above function is passed as callback,
there will be a script error in the end ("null has no properties").
Could you post an example, including which browser causes it?
Furthermore, text nodes have no `tagName' property.
True. It was just a quick example.
It would also be nice if one could use the return value of traverseDFTRL() ,
What would the return value be? But yes, it could easily be turned into
a catemorphism (fold-like function):

function foldDOM(element , action) {
var childRets = [];
for(var child = element.lastChi ld; child; child = child.previousS ibling) {
childRets.push( foldDOM(child, action));
}
return action(element, childRets);
}

Then you could collect the innerText of a DOM element as:

foldDOM(element , function(node,c hildTexts) {
if (node.nodeType == 3) { // Text node
return node.nodeValue;
} else { // Element node
return childTexts.join ("");
}
});
and to allow for another identifier without modifying the function body.
If you want another name for it, treat the above as a function expression,
not a function declaration. Then you can call it whatever you like:

var myOwnName = function foldDOM(...){.. .foldDOM(...).. .};

I don't find the use of arguments.calle e particularly readable.
If a function can't know its own declared name inside its body,
what can it know?
Hence the following suggestion:

function isMethod(a)
{
var t;
return (a && ((t = typeof a) == "function" || t == "object"));
}

function traverseDFRTL(e lement, action)
{
for (var child = (element || document.docume ntElement).last Child;
child;
child = child.previousS ibling)
{
arguments.calle e(child, action);
}

if (isMethod(actio n))
{
return action(element) ;
If you insist on having a default argument, it should also apply here,
so,
return action(element || document.docume ntElement);
For default parameters, I prefer setting them at the top of the function,
i.e., as first line:
element = element || document.docume ntElement;
}
if you make this test (and I wouldn't - someone callig the function
should know that he is expected to pass a function as second argument),
I would at least fail if it's not:
else {
throw Error("Not a function as second argument!");
}

function(node)
{
if (node)

So here you depend on having the documentElement being traversed, but
null still being passed to the action function. That seems awfully
fragile and not very generic. I prefer to have a more generic, and
preferably simpler, function like my original traversal or the foldDOM
above, and then create a specialized function to call it with special
arguments that makes sense to the page it is used on.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

[Csaba Gabor]

Lasse Reichstein Nielsen wrote:

de*******@gmail .com writes:

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child = child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.
If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

<body onload="test()" ><table><tr><td >Help</td></tr></table>
<script type='text/javascript'>

function lessSimpleTrave rseDFRTL(elemen t, action) {
var next, prev=element.la stChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.paren tNode!=(prev=ne xt)) {
if (lcOK && (next=prev.last Child)) continue; else action (prev);
next = prev.previousSi bling || prev.parentNode ; }
action(element) ; }

function test() {
lessSimpleTrave rseDFRTL(docume nt.body, function(node) {
alert(node.node Name+ "\n" + outerHTML(node) ); }); }

function outerHTML(elem) {
if (elem.outerHTML ) return elem.outerHTML;
var dup=elem.cloneN ode(true); //event handlers, some attribs omitted
var dummyDiv=elem.o wnerDocument.cr eateElement('DI V');
dummyDiv.append Child(dup);
var outer=dummyDiv. innerHTML;
delete dummyDiv;
return outer;
}
</script>
<div><span>Hi mom</span><p>Hi dad</p></div>
</body>
Tested with IE 6, FF 1.5.0.1,
Csaba Gabor from Vienna

[Csaba Gabor]

Csaba Gabor wrote:

Lasse Reichstein Nielsen wrote:

de*******@gmail .com writes:

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child = child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.
If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

<body onload="test()" ><table><tr><td >Help</td></tr></table>
<script type='text/javascript'>

function lessSimpleTrave rseDFRTL(elemen t, action) {
var next, prev=element.la stChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.paren tNode!=(prev=ne xt)) {
if (lcOK && (next=prev.last Child)) continue; else action (prev);
next = prev.previousSi bling || prev.parentNode ; }
action(element) ; }

Kidding aside, the iterative version does offer something that the
recursive version doesn't because the recursive version only does
subtrees. The iterative version is happy to walk all the way back to
the root, from a given element. I found it quite instructive.

<body onload="test()" ><table><tr>< td id=td>Help</td></tr></table>
<script type='text/javascript'>

function backwalk(elem, action) {
// iterative reverse depth first traversal to root from elem
for (var next, lcOK=false; elem; lcOK=elem.paren tNode!=(elem=ne xt)) {
if (lcOK && (next=elem.last Child)) continue; else action (elem);
next = elem.previousSi bling || elem.parentNode ; } }

function test() {
backwalk(docume nt.getElementBy Id('td'), function(node) {
alert(node.node Name+ " (" + node.nodeType +
")\n" + outerHTML(node) ); }); }

function outerHTML(elem) {
if (elem.outerHTML ||elem.nodeType >8) return elem.outerHTML;
var dup=elem.cloneN ode(true);
var dummyDiv=elem.o wnerDocument.cr eateElement('DI V');
dummyDiv.append Child(dup);
var outer=dummyDiv. innerHTML;
delete dummyDiv;
return outer; }

</script>
<div><span>Hi mom</span><p id=p>Hi dad</p></div>
</body>
Plus the code is simpler. ;)
Csaba Gabor from Vienna

[Thomas 'PointedEars' Lahn]

Lasse Reichstein Nielsen wrote:

Thomas 'PointedEars' Lahn <Po*********@we b.de> writes:

Lasse Reichstein Nielsen wrote:

---
function traverseDFRTL(e lement, action) {
for(var child = element.lastChi ld; child; child =
child.previousS ibling) {
traverseDFRTL(c hild, action);
}
action(element) ;
}
---

Calling
---
traverseDFRTL(s omeElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.
Very nice. There is one catch, though: after the very first node of the
document tree has been processed, action() is called with `null',

I can't see how. The "action" callback function is only ever called
with the value of the "element" parameter. It can only be called with
a null value if "element" is null. The recursive calls are only made
if "child" is not null, so they can't cause it, so "action" should
only be called with null arguemnt if someone calls traverseDFRTL with
a first parameter that is null.

You are correct, the original code runs without error. It was in fact my
optimization which caused the problem. I passed `null' for triggering the
default value `document.docum entElement' and forgot that this would not
affect the value of `element' as passed to the second action() call.

It would also be nice [...] to allow for another identifier without
modifying the function body.

If you want another name for it, treat the above as a function expression,
not a function declaration. Then you can call it whatever you like:

var myOwnName = function foldDOM(...){.. .foldDOM(...).. .};

I don't find the use of arguments.calle e particularly readable.
If a function can't know its own declared name inside its body,
what can it know?

Think about it. That there are function expressions, i.e. functions
are first-level objects, is precisely why arguments.calle e is useful.

Hence the following suggestion:

function isMethod(a)
{
var t;
return (a && ((t = typeof a) == "function" || t == "object"));
}

function traverseDFRTL(e lement, action)
{
for (var child = (element || document.docume ntElement).last Child;
child;
child = child.previousS ibling)
{
arguments.calle e(child, action);
}

if (isMethod(actio n))
{
return action(element) ;

If you insist on having a default argument, it should also apply here,
so,
return action(element || document.docume ntElement);

In fact, it MUST then, unless one sets a requirement for checking
the argument of the callback in the callback. See above.
For default parameters, I prefer setting them at the top of the function,
i.e., as first line:
element = element || document.docume ntElement;

I prefer

if (!element) element = document.docume ntElement;

as it strikes me as being more efficient.

}

if you make this test (and I wouldn't - someone callig the function
should know that he is expected to pass a function as second argument),
I would at least fail if it's not:
else {
throw Error("Not a function as second argument!");
}

Agreed, although I would consider an alternative to a plain `throw'.
PointedEars

[Lasse Reichstein Nielsen]

"Csaba Gabor" <da*****@gmail. com> writes:

function backwalk(elem, action) {
// iterative reverse depth first traversal to root from elem
for (var next, lcOK=false; elem; lcOK=elem.paren tNode!=(elem=ne xt)) {
if (lcOK && (next=elem.last Child)) continue; else action (elem);
next = elem.previousSi bling || elem.parentNode ; } }

I'm not entirely sure I read this correctly, but doesn't it follow
just a path through prevous siblings and parents from a note to the
root? It doesn't traverse children of the siblings, nor later
siblings at the same level.

An iterative function that works like the original traversal could be:
---
function leftMostInnerMo stDescendent(no de) {
while (node.hasChildN odes()) {
node = node.lastChild;
}
return node;
}

function traverse(elemen t, action) {
var next = leftMostInnerMo stDescendent(el ement);
do {
action(next);
if (next.previousS ibling) {
next = leftMostInnerMo stDescendent(ne xt.previousSibl ing);
} else {
next = next.parentNode ;
}
} while (next != element);
action(element) ;
}
---

A much more engenious (but probably dangerous) method is to use
rotation of the tree, putting the parent as the last child of its
first child and continuing that until the original shape is
restored (as it will be eventually). It's probably not doable in
general in a tree structure like HTML where not every node can
be a child of every other node. :)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'