467,877 Members | 1,257 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 467,877 developers. It's quick & easy.

Walk DOM Tree in Reverse?

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.

Apr 2 '06 #1
  • viewed: 4491
Share:
22 Replies
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.

Apr 2 '06 #2
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.previousSibling....parentNode.previousSibl ing.lastChild...
..previousSibling....parentNode...

See?
PointedEars
Apr 2 '06 #3
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(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 2 '06 #4
Lasse Reichstein Nielsen wrote:
---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child =
child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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(element, action)
{
for (var child = (element || document.documentElement).lastChild;
child;
child = child.previousSibling)
{
arguments.callee(child, action);
}

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

var nodes = [];

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

return nodes;
}).join("\n"));
PointedEars
Apr 2 '06 #5
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child =
child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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.lastChild; child; child = child.previousSibling) {
childRets.push(foldDOM(child, action));
}
return action(element, childRets);
}

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

foldDOM(element, function(node,childTexts) {
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.callee 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(element, action)
{
for (var child = (element || document.documentElement).lastChild;
child;
child = child.previousSibling)
{
arguments.callee(child, action);
}

if (isMethod(action))
{
return action(element);
If you insist on having a default argument, it should also apply here,
so,
return action(element || document.documentElement);
For default parameters, I prefer setting them at the top of the function,
i.e., as first line:
element = element || document.documentElement;
}
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/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 2 '06 #6
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(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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 lessSimpleTraverseDFRTL(element, action) {
var next, prev=element.lastChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.parentNode!=(prev=next)) {
if (lcOK && (next=prev.lastChild)) continue; else action (prev);
next = prev.previousSibling || prev.parentNode; }
action(element); }

function test() {
lessSimpleTraverseDFRTL(document.body, function(node) {
alert(node.nodeName+ "\n" + outerHTML(node)); }); }

function outerHTML(elem) {
if (elem.outerHTML) return elem.outerHTML;
var dup=elem.cloneNode(true); //event handlers, some attribs omitted
var dummyDiv=elem.ownerDocument.createElement('DIV');
dummyDiv.appendChild(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

Apr 3 '06 #7
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(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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 lessSimpleTraverseDFRTL(element, action) {
var next, prev=element.lastChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.parentNode!=(prev=next)) {
if (lcOK && (next=prev.lastChild)) continue; else action (prev);
next = prev.previousSibling || 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.parentNode!=(elem=next)) {
if (lcOK && (next=elem.lastChild)) continue; else action (elem);
next = elem.previousSibling || elem.parentNode; } }

function test() {
backwalk(document.getElementById('td'), function(node) {
alert(node.nodeName+ " (" + node.nodeType +
")\n" + outerHTML(node)); }); }

function outerHTML(elem) {
if (elem.outerHTML||elem.nodeType>8) return elem.outerHTML;
var dup=elem.cloneNode(true);
var dummyDiv=elem.ownerDocument.createElement('DIV');
dummyDiv.appendChild(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

Apr 3 '06 #8
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child =
child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, 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.documentElement' 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.callee 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.callee is useful.
Hence the following suggestion:

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

function traverseDFRTL(element, action)
{
for (var child = (element || document.documentElement).lastChild;
child;
child = child.previousSibling)
{
arguments.callee(child, action);
}

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


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


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.documentElement;


I prefer

if (!element) element = document.documentElement;

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
Apr 3 '06 #9
"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.parentNode!=(elem=next)) {
if (lcOK && (next=elem.lastChild)) continue; else action (elem);
next = elem.previousSibling || 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 leftMostInnerMostDescendent(node) {
while (node.hasChildNodes()) {
node = node.lastChild;
}
return node;
}

function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);
do {
action(next);
if (next.previousSibling) {
next = leftMostInnerMostDescendent(next.previousSibling);
} 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/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #10
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Think about it. That there are function expressions, i.e. functions
are first-level objects, is precisely why arguments.callee is useful


It is useful for creating recursion on anonymous functions, but since
we also have named function expressions, with the scope of the name
being only the body of the function, that can be used for recursion
as well (and for pretty much nothing else).

The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.
Using a named function for recursion means that whoever copies
the the function and renames it must be aware that it is recursive.

On the other hand, using the name to call recursively is much more
readable (at least to me), and I don't have any scruples making code
that needs to be understood before it's copied :)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #11
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Think about it. That there are function expressions, i.e. functions
are first-level objects, is precisely why arguments.callee is useful


It is useful for creating recursion on anonymous functions, but since
we also have named function expressions, with the scope of the name
being only the body of the function, that can be used for recursion
as well (and for pretty much nothing else).

The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.


Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.
PointedEars
Apr 3 '06 #12
Lasse Reichstein Nielsen wrote:
"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.parentNode!=(elem=next)) {
if (lcOK && (next=elem.lastChild)) continue; else action (elem);
next = elem.previousSibling || 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.


your traverse is doing what my lessSimpleTraverseDFRTL is doing two
posts above. Looking at backwalk, which is essentially the same:
The basic idea is that, when we can, we go to the last child and don't
do any action. That's the 'if' (I'll get to the lcOK in a moment). If
we can't go to the last child, that means we must go to the previous
sibling, and failing that, to the parentNode. That's what the 'next='
is about. But before we do that, we take the action, which is what the
'else' is about.

So this little, "go to the lastChild, otherwise the previousSibling,
otherwise the parentSibling" has one failing. If you go to the
parentNode from a child, you'll wind up right back at the lastChild.
Therefore, better prevent going to the lastChild if the parent of the
old element is the same as the new element. And that is what the
'lcOK' (OK to go to lastChild) is doing. I set it to false at the
outset, because if we start backwards from a given elem, we don't want
to look at the starting elem's children. If you start my example from
document.getElementById('p'), it will include the TD of the table.
An iterative function that works like the original traversal could be: .... function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);
I think of .lastChild as a rightmost child

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


I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please. By putting the parent
as the last child of its first child, do you also mean that the parent
should disconnect that first child as its child? And where does the
action come in? If you would give the recursive form of the function,
at least in some pseudo code, that would be great.

Csaba

Apr 3 '06 #13
"Csaba Gabor" <da*****@gmail.com> writes:
Lasse Reichstein Nielsen wrote: your traverse is doing what my lessSimpleTraverseDFRTL is doing two
posts above.
I guess the "continue" threw me off :)
I *think* I understand it now :)
An iterative function that works like the original traversal could be:

...
function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);


I think of .lastChild as a rightmost child


*cough*right*cough*

[traversal by pointer reversal]
I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please.
I *wish* I could find a reference for this on the web (or in any of my
books). It was just something my advisor mentioned to me at some point,
as a well known method for traversing trees.
Assume that we have some node structure with the operations of DOM
nodes, but without the HTML structure requirements. Then the following
algorithm will traverse all nodes (sadly not necessarily visiting each
just once):
function traverseByPointerReversal(node, action) {
// A sentinel node for knowing when to end.
var root = new Node("fakeroot"); // or something.
root.appendChild(node);

node = root;
do { // invariant: node is the root of a tree containing all the nodes.
// node always has at least one child
var child = node.firstChild;
node.removeChild(child);
child.appendChild(node);
node = child;
if (node != root) { action(node); }
} while (node != root);
}
// example code, with "mockup" nodes to show the transformations:
function Node(name) {
this.name = name;
this.children = [];
}
Node.prototype.appendChild = function(childNode) {
this.children.push(childNode);
if (this.children.length == 1) {
this.firstChild = childNode;
}
};
Node.prototype.removeChild = function(childNode) {
this.children.shift(); // for this algorithm, only first child is removed
this.firstChild = this.children[0];
}
Node.prototype.toString = function() { // show tree structure
var cs = [];
for (var i = 0; i < this.children.length; i++) {
cs[i] = this.children[i].toString();
}
return this.name + ((cs.length > 0) ? ":[" + cs + "]" : "");
};
// example tree:
// A
// / | \
// B C D
// / \
// E F
var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
A.appendChild(B);
A.appendChild(C);
A.appendChild(D);
D.appendChild(E);
D.appendChild(F);
alert(A); // A:[B,C,D:[E,F]]

traverseByPointerReversal(A, function(node){alert(node);});

This shows how the tree looks at each step, since the node in question
is always the root at the time it is "action"'ed.
By putting the parent as the last child of its first child, do you
also mean that the parent should disconnect that first child as its
child?
It should, yes.
And where does the action come in?
That is a problem, since some nodes are traversed more than once,
and the algorithm doesn't store information about where it came
from or what nodes are really pointer-reversed parent nodes.
So for the purpose of the OP, it's not very usable. I do think it's
a neat algorithm, though :)
If you would give the recursive form of the function, at least in
some pseudo code, that would be great.


The point is to not be recursive, and not use extra space for a stack.
I believe (without knowing for sure) that a similar method is used by
garbage collectors to traverse a tree without using more than constant
extra space.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #14
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:

The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.


Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.


I won't have to change any code if I used the named function
expression either. The scope of the function name is only the function
body, so nobody else should be using it anyway (yes, I know some
browsers fails to comply with ECMAScript on this).
var deadloop = function omega() { omega(); }
var someObject = {};
someObject.liveloop = deadloop;
someObject.liveloop(); // loops just as dead!
If I had to make a function that was portable and where the user
could change its name, I would use a wrapper function:

function traverse(node, action) {
function traverseRec(node) {
// ... traverseRec(child); .... action(node) ...
}
traverseRec(node || documentElement, action);
}

It also provides a suitable point for adding default parameters
without having to do it on each recursive call where we know it's not
necessary, and it avoids passing constant parameters on every call.
All in all a win-win-win situation :)

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #15
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.


Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.


I won't have to change any code if I used the named function
expression either.


If you call the method as a method of the Variable Object, it
will work different as if called as method of another object.

And without using arguments.callee, you will have to have a
named reference to it always.
PointedEars
Apr 3 '06 #16
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.

Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.
I won't have to change any code if I used the named function
expression either.


If you call the method as a method of the Variable Object, it
will work different as if called as method of another object.


That is correct, but only it uses the "this" operator for anything.

A recursive function that calls itself by name will do so without
an object reference, so the "this" operator will refer to the global
object. Unless you actually need access to a global variable that
is shadowed by nested declaration, you don't need this reference
to the global object, so the function will probably not use it.

Calling the function recursively through arguments.callee will
have the called function's "this" operator refere to the calling
function's arguments object. While interesting, messing with
the caller's activation record is not good style for a recursive
function :)

All in all, a recursive function should not use the "this" operator,
and then there is no difference how it is called.
And without using arguments.callee, you will have to have a
named reference to it always.


Inside a named function expression, you have just that.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #17
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
[...]
All in all, a recursive function should not use the "this" operator,
Utter nonsense.
[...]
And without using arguments.callee, you will have to have a
named reference to it always.


Inside a named function expression, you have just that.


Exactly. You missed the point.
PointedEars
Apr 3 '06 #18
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
[...]
All in all, a recursive function should not use the "this" operator,


Utter nonsense.


You are entitled to your, unsupported, opinion.

A function using the "this" operator is meant to be used as a method,
operating on the object it is on.

A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.

While a method can call itself as a function (and not just as a method
on the same object), and a function can use the "this" operator in a
"novel" way that is different from its normal meaning, it is a
confusion of styles that I recommend against. It is more important
to be readable and use idioms the way the reader expects, than to
be able to reduce the code by a line and a few cycles of execution
time.
[...]
And without using arguments.callee, you will have to have a
named reference to it always.


Inside a named function expression, you have just that.


Exactly. You missed the point.


Apparently. I still can't find it.

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 3 '06 #19
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
[...]
All in all, a recursive function should not use the "this" operator, Utter nonsense.


You are entitled to your, unsupported, opinion.


Yes, I am.
A function using the "this" operator is meant to be used as a method,
operating on the object it is on.
True.
A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.


That is shortsighted thinking at best. Why should a recursive method not
be allowed in object-oriented programming? If a feature can be implemented
with a recursive call, you would dare force a developer to use the
iterative approach, or write less easier maintainable code instead? Just
because it does not fit your argumentation, I presume. Fortunately, your
own, unfounded opinion does not count for all developers.
PointedEars
Apr 3 '06 #20
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.


That is shortsighted thinking at best. Why should a recursive method not
be allowed in object-oriented programming?


Never said it shouldn't, only that it has nothing inherently to do
with object orientation. If a language can support both OO and
recursive functions, nothing prevents you from using the better
feature for a given job.
If a feature can be implemented with a recursive call, you would
dare force a developer to use the iterative approach, or write less
easier maintainable code instead?
Ofcourse not.
Just because it does not fit your argumentation, I presume.


I'm not arguing against either way of working, but I am questioning
the need, and reasoning, for a recursive function in Javascript that
uses the "this" operator. Especially if the "this" operator gives
a reference to the aruguments object of the calling activation
record, which is the case when the function calls itself as
arguments.callee(...).

/L
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Apr 4 '06 #21
Lasse Reichstein Nielsen wrote:
Thomas 'PointedEars' Lahn <Po*********@web.de> writes:
Lasse Reichstein Nielsen wrote:
A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.


That is shortsighted thinking at best. Why should a recursive
method not be allowed in object-oriented programming?

[...]
Just because it does not fit your argumentation, I presume.


I'm not arguing against either way of working, but I am questioning
the need, and reasoning, for a recursive function in Javascript that
uses the "this" operator. Especially if the "this" operator gives
a reference to the aruguments object of the calling activation
record, which is the case when the function calls itself as
arguments.callee(...).


I see your point.
PointedEars
Apr 4 '06 #22
Lasse Reichstein Nielsen wrote:
"Csaba Gabor" <da*****@gmail.com> writes:
[traversal by pointer reversal]
I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please.


I *wish* I could find a reference for this on the web (or in any of my
books). It was just something my advisor mentioned to me at some point,
as a well known method for traversing trees.

Assume that we have some node structure with the operations of DOM
nodes, but without the HTML structure requirements. Then the following
algorithm will traverse all nodes (sadly not necessarily visiting each
just once):


In fact, it will visit each node (1 + #-of-node's-children) times

.... very nice code details ...
By putting the parent as the last child of its first child, do you
also mean that the parent should disconnect that first child as its
child?


It should, yes.
And where does the action come in?


That is a problem, since some nodes are traversed more than once,
and the algorithm doesn't store information about where it came
from or what nodes are really pointer-reversed parent nodes.
So for the purpose of the OP, it's not very usable. I do think it's
a neat algorithm, though :)


Indeed, if we are not allowed to mark nodes as visited, then it becomes
an interesting problem. What I puzzled out was that to do a DFS, the
action should be taken whenever the original root node is contained in
the right child of the current root (plus at the beginning of the
initial call). To get a pseudo intuitive feeling for this, consider
that the nodes underneath a given top level node (because all nodes
become top level, eventually) are being barrel rotated, so at most one
of these rotations should be used for an action - the first one, which
is when the original root is in its rightmost subtree.

Hmmm, how to find out whether a given node is in a subtree? Well,
maybe we could just make use of the same algorithm. But is it
reentrant? ... Yes! However, you must walk the entire subtree (even if
you find the answer to be yes right away) otherwise your tree will be
corrupted. So this single requirement imposes a quite a high time
overhead, but if marking is allowed, then there will be exactly n+m
node visits (same as traversal, number of nodes plus number of edges),
since each node is visited once for itself, and its parent receives a
corresponding visit, too.

As an example, I programmed up the non marking variant as traversal and
as a DFS, leveraging off the code you provided. The complete cut and
paste example is below. The central engine is:

function funkyTraverse (elem, action) {
var rootCt = elem.childNodes.length, startNode = elem;
var fakeParent = !elem.parentNode;
if (fakeParent) elem.parentNode = elem; // for .replaceNode on root

for (action.apply(elem); rootCt;
(rootCt-=((elem=elem.parentNode)==startNode))
? action.apply(elem): "")
elem.firstChild.appendChild(
elem.parentNode.replaceChild(
elem.removeChild(elem.firstChild),elem));

if (fakeParent) delete (elem.parentNode);
}

The business with the fakeroot is so that either a subtree or original
tree may be passed in. The one line body of the for does the tree
rotation. Only then elem is the child of the new root, so that is what
the elem=elem.parentNode is for. The way we figure out when we're done
is that on entry, we count the number of children the root has. When
the original root has surfaced that many times, we're done. On the
very last pass, when we get the original tree back, we don't want to
take an action on it (since we've already seen it) - the ? ... : form
is because javascript doesn't want an if within the for (...)
declaration.

I've also added p=parent and fc=first child to the string
representation of a node, because debugging this can be a bear. Make
one teeny tiny little mistake and your tree is blown to pieces - you
will have not the slightest clue about the source of the mistake. Add
reentrancy into the mix and it's a real party.
If you would give the recursive form of the function, at least in
some pseudo code, that would be great.


The point is to not be recursive, and not use extra space for a stack.
I believe (without knowing for sure) that a similar method is used by
garbage collectors to traverse a tree without using more than constant
extra space.


My bad. I meant to put functional form of the algorithm. I've seen
tree rotations before, but never like this. Thanks for sharing a very
interesting approach.

Complete code example below,
Csaba Gabor from Vienna
<html><head><title>funky traversals with tree rotations</title></head>
<body onload="test()">
<script type='text/javascript'>

function funkyTraverse (elem, action) {
var rootCt = elem.childNodes.length, startNode = elem;
var fakeParent = !elem.parentNode;
if (fakeParent) elem.parentNode = elem; // for .replaceNode on root

for (action.apply(elem); rootCt;
(rootCt-=((elem=elem.parentNode)==startNode))
? action.apply(elem): "")
elem.firstChild.appendChild(
elem.parentNode.replaceChild(
elem.removeChild(elem.firstChild),elem));

if (fakeParent) delete (elem.parentNode); }

function test() {
var root = initTree();

alert("Depth First Search (DFS):");
funkyTraverse(root, function (oRoot, fcoRoot) { return function() {
// 1st half of if for root; 2nd part for all others
if ((this==oRoot && this.firstChild==fcoRoot) ||
inTree(this.childNodes[this.childNodes.length-1], oRoot))
alert("Step: "+this); } }(root, root.firstChild));

alert("<br>Full traverse details:");
funkyTraverse(root, function () { alert("Step: " + this) } ); }

function inTree(root, node) {
// returns true iff node is in the subtree rooted at root
inTree.res = false;
funkyTraverse(root, function(nod) { return function() {
if (!inTree.res) inTree.res = (this==nod); } }(node));
return inTree.res; }

function alert(item) {
// writes a new line to the div instead of popping up
document.getElementById('log').innerHTML += item + "<br>"; }

Node.prototype.appendChild = function(childNode) {
this.childNodes.push(childNode);
childNode.parentNode = this;
if (this.childNodes.length == 1) this.firstChild = childNode;
return childNode; }

Node.prototype.removeChild = function(childNode) {
for (var i=this.childNodes.length;i--;)
if (this.childNodes[i]==childNode) {
if (!i) {
if (this.childNodes.length>1) this.firstChild =
this.childNodes[1];
else delete (this.firstChild); }
delete (childNode.parentNode);
return this.childNodes.splice(i,1).pop(); } }

Node.prototype.replaceChild = function (newChild, oldChild) {
delete (oldChild.parentNode);
for (var i=this.childNodes.length;i--;)
if (this.childNodes[i]==oldChild) {
if (!i) this.firstChild = newChild;
newChild.parentNode = this;
return this.childNodes.splice(i, 1, newChild).pop(); }
newChild.parentNode = newChild; // fake roots section
return oldChild; }

Node.prototype.toString = function() { // show tree structure
for (var i = 0, cs=[]; i < this.childNodes.length; i++) {
cs[i] = this.childNodes[i].toString(); }
return this.name +
(this.parentNode ? " p="+this.parentNode.name : "") +
(this.firstChild ? " fc="+this.firstChild.name : "") +
((cs.length > 0) ? ": [" + cs + "]" : ""); };

function Node(name) { // create a new node
this.name = name; this.childNodes = []; }

function initTree() {
var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
var G = new Node("G");
var H = new Node("H");

A.appendChild(B);
B.appendChild(C);
B.appendChild(D);
D.appendChild(E);
D.appendChild(F);
B.appendChild(G);
A.appendChild(H);
return A;
}
</script>
<div id=log>Tree Rotations<br><br></div>
</body>
</html>

Apr 4 '06 #23

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

9 posts views Thread by Marcello Pietrobon | last post: by
7 posts views Thread by pembed2003 | last post: by
6 posts views Thread by Zri Man | last post: by
7 posts views Thread by KraftDiner | last post: by
6 posts views Thread by Bruce | last post: by
8 posts views Thread by Andre Meyer | last post: by
9 posts views Thread by silverburgh.meryl | last post: by
2 posts views Thread by Martin Marcher | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.