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

Groups > comp.lang.javascript > #28509

Re: Recursive function to find a node in the DOM

Show all headers | View raw

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.
> 
> Frankly, I do not get the point here.  Wouldn't the DOM implementation
> have to *recursively* walk the DOM to find the desired elements as well?

Not necessarily.  DOM Nodes have “firstChild”, “lastChild”, 
“previousSibling”, “nextSibling”, and “parentNode” properties [1]; in newer 
implementations, they also have “firstElementChild”, “lastElementChild”, 
“previousElementSibling”, “nextElementSibling”, and “parentElement” 
properties [2]; and an efficient implementation would maintain name-to-
element-list mappings.

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

__________
[1] <http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/core.html#ID-1950641247>
[2] <http://www.w3.org/TR/2015/WD-dom-20150618/#nodes>
[3] <http://www.w3.org/TR/DOM-Level-2-Traversal-Range/traversal.html>
-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

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