As per MDN,
The Node.contains() method returns a Boolean value indicating whether a node is a descendant of a given node, i.e. the node itself, one of its direct children (childNodes), one of the children's direct children, and so on.
But wait, Node.prototype.contains(...)
already exists. I want another name for our custom function. Let's google synonym of contains
coz
Intense googling later......
Certainly we ain't going with swallow. I think includes would be cool as both Array
and String
have includes as well in their prototypes.
Before we proceed one important thing to know is that when adding new method to prototype
and expecting to use it like so :-
document.includes(document.body)
,
the method should not be an arrow function so that document
can be accessed inside the includes
function via this
keyword.
Alright then, let's implement Node.prototype.includes
in 4 different ways :-
The recursive DFS
1 Node.prototype.includes = function(node){
2 const currentNode = this;
3 if(!currentNode)
4 return false;
5 if(currentNode===node)
6 return true;
7 let isNodeFound = false;
8 for(let index = 0;index<currentNode.childNodes.length;index++){
9 isNodeFound = isNodeFound || currentNode.childNodes[index].includes(node);
10 if(isNodeFound) return true;
11 }
12 return false;
13 }
Explanation :-
- Line 2 to 4 - Set
currentNode
tothis
and IfcurrentNode
doesn't exist, simply returnfalse
. - Line 5 to 6 - if
currentNode
is equal tonode
returntrue
. - Line 7 to 13 - Initialize
isNodeFound
tofalse
. Then loop overchildNodes
of thecurrentNode
and on each child, call theincludes
method again to check if they include thenode
element. If they do,isNodeFound
will ultimately becometrue
since it is being Orrrrrrd with the results coming from respectivechildNodes
and reassigned to itself. OnceisNodeFound
istrue
, we don't need to loop over rest of thechildNodes
ofcurrentNode
and exit early by returningtrue
else ultimately returnfalse
.
The iterative BFS
1 Node.prototype.includes = function (node) {
2 const queue = [];
3 let currentNode = this;
4 queue.push(currentNode);
5 while (queue.length) {
6 currentNode = queue.shift();
7 if (currentNode === node) return true;
8 if (currentNode.hasChildNodes()) {
9 queue.push(...currentNode.childNodes);
10 }
11 }
12 return false;
13 };
Explanation :-
- Line 2 to 4 - Initialize an empty list as
queue
. SetcurrentNode
tothis
andpush
(or enqueue to be specific) it. - Line 5 to 12 - While the
queue
is not empty, dequeue thecurrentNode
from front of thequeue
(usingshift
here). IfcurrentNode
is equal tonode
then returntrue
. Otherwise enqueue thechildNodes
ofcurrentNode
(usingpush
here). Once we are out of thewhile
loop, we have traversed all the nodes and can safely say that we couldn't find thenode
and returnfalse
.
Note - The above can be transformed to iterative DFS by using pop
instead of shift
and obviously for the sake of consistency, rename queue
to stack
.
Till now both the approaches followed the classic DS/Algo traversal with DFS and BFS. We are now going to see 2 more approaches which take benefit of certain properties that are specifically applicable to DOM nodes.
LCRS (Left Child Right Sibling) form
1 Node.prototype.includes = function (node) {
2 const currentNode = this;
3 if (!currentNode)
4 return false;
5 if (currentNode === node) return true;
6 return !!(currentNode.firstChild?.includes(node) || currentNode.nextSibling?.includes(node))
7 };
Explanation :-
- Line 2 to 5 -
- Initialize
currentNode
tothis
and ifcurrentNode
doesn't exist, returnfalse
. - If
currentNode
is equal tonode
returntrue
- Initialize
- Line 6 - DOM nodes not only have pointers to their childNodes but also to their sibling nodes as well as parent nodes. Here we are going to leverage the sibling factor for easy traversal. So, we can now check whether the current node's
firstChild
includes thenode
OR current node'snextSibling
includes thenode
. Also notice the!!
. That's because I have used the?
operator due to which we can end up withundefined || undefined
condition orfalse || undefined
condition where both evaluate toundefined
which is a falsy value and so!!
will ensureundefined
coerces tofalse
.
Using parentNode
1 Node.prototype.includes = function(node){
2 const currentNode = this;
3 while(node){
4 if(currentNode===node) return true;
5 node = node.parentNode;
6 }
7 return false;
8 }
Explanation :-
- Line 2 to 7 - Remember DOM node being so attached to it's siblings and parent ? The latter one works well for this use-case as well. While
node
exists, we check ifcurrentNode
is equal tonode
and if it is we returntrue
, else thenode
is made to point to it'sparentNode
for further comparisons. If we exit thewhile
loop, it's safe to say that thenode
isn't a contained within thecurrentNode
and thus, returnfalse
.
And here is a working codepen with all 4 implementations. Comment the rest for any one to reflect โจ.
Have more ways to implement the same ? Feel free to share your approach in the comment section ๐.