Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #28516

Re: Recursive function to find a node in the DOM

Show key headers only | View raw

On 08.08.2015 at 09:33, Thomas 'PointedEars' Lahn wrote:

> Christoph M. Becker wrote:
> 
>> On 15.07.2015 at 11:59, Thomas 'PointedEars' Lahn wrote:
>>
>>> […]  And the proper approach here is iteration (walking the
>>> document tree), not recursion; because the stack size and/or nesting
>>> level is limited (the Google Groups archive has test results), but an
>>> element’s nesting level within a document tree is not.
>>
>>  Of course, that would likely need less stack space than a recursive
>> *user-land* walk, but still be of the same order of magnitude.
> 
> To begin with, you are mistaken that I had referred to "the DOM 
> implementation".  While there is W3C DOM Level 2 Traversal and Range [3] 
> indeed, you can do an iterative "user-land" walk of the document tree as 
> well; for example:
> 
>      grandparent ----------------.
>    ,-- grandparent.firstChild <--'
>    `---> grandparent.firstChild.firstChild ---------------.
>   ,----- grandparent.firstChild.firstChild.nextSibling <--'
>   `--> grandparent.firstChild.firstChild.nextSibling.parentNode.nextSibling 
> --> END.
> 
> (The algorithm and implementation are left as an exercise to the reader.)

Seems to be rather trivial:

  grandparent.firstChild.nextSibling

I don't know, however, in which way this would help to find a *certain*
*node* somewhere in the DOM (which seems to be the topic of this thread,
if I'm not mistaken).  To do this, it is necessary to inspect all DOM
nodes (at least until the node which is looked for is found).  How can
this be done with an iterative algorithm?  Of course, by using an
explicit stack (which would be stored on the heap), and assuming that
the machine heap is much larger than the machine stack, indeed that
would allow to traverse more deeply nested trees...  at the cost of
runtime performance and a considerably more complex script.  Then again,
I can hardly imagine a recursive tree searching algorithm running out of
machine stack space on a reasonably sized DOM tree on somewhat
contempory browsers/machines.

-- 
Christoph M. Becker

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-15 09:59 +0200
  Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-15 11:59 +0200
    Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-15 12:03 +0200
    Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-15 13:36 +0200
      Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-19 12:27 +0200
        Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-19 12:34 +0200
        Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-21 12:08 +0200
          Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-25 14:11 +0200
            Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-25 21:22 +0200
              Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-27 16:12 +0200
    Re: Recursive function to find a node in the DOM "Christoph M. Becker" <cmbecker69@arcor.de> - 2015-08-08 04:50 +0200
      Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-08-08 09:33 +0200
        Re: Recursive function to find a node in the DOM "Christoph M. Becker" <cmbecker69@arcor.de> - 2015-08-12 00:48 +0200
          Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-08-12 01:18 +0200
            Re: Recursive function to find a node in the DOM "Christoph M. Becker" <cmbecker69@arcor.de> - 2015-08-13 23:26 +0200
              Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-08-16 08:48 +0200
                Re: Recursive function to find a node in the DOM "Christoph M. Becker" <cmbecker69@arcor.de> - 2015-08-20 02:11 +0200
  Re: Recursive function to find a node in the DOM Scott Sauyet <scott.sauyet@gmail.com> - 2015-07-18 15:59 -0700
    Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-21 12:30 +0200
      Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-21 13:53 +0200
        Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-21 14:51 +0200
          Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-07-21 16:05 +0200
            Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-07-21 20:35 +0200
            Re: Recursive function to find a node in the DOM Scott Sauyet <scott.sauyet@gmail.com> - 2015-07-30 22:10 -0700
              Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-08-06 10:07 +0200
                Re: Recursive function to find a node in the DOM Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-08-06 20:15 +0200
                Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-08-08 01:21 +0200
        Re: Recursive function to find a node in the DOM Scott Sauyet <scott.sauyet@gmail.com> - 2015-07-30 22:09 -0700
  Re: Recursive function to find a node in the DOM Denis McMahon <denismfmcmahon@gmail.com> - 2015-07-29 03:04 +0000
    Re: Recursive function to find a node in the DOM "danca (Daniele Campagna)" <cyberdanny@tiscalinet.it> - 2015-08-06 10:20 +0200

csiph-web