CODEWITHSUNDEEP
javascriptjquery
Ozgur
Ozgur

Reputation: 1834

How to find the nearest common ancestors of two or more nodes?

Users selects two or more elements in a HTML page. What I want to accomplish is to find those elements' common ancestors (so body node would be the common ancestor if none found before)?

P.S: It can be achieved with XPath but it is not a preferable option for me. Also it may be found with css selector parsing but I think it is a dirty method.

Upvotes: 47

Views: 21306

Answers (17)

ocramz
ocramz

Reputation: 833

Did anyone say "recursion" yet?

function domNodeCommonAncestor(na, nb){
    if (na.contains(nb)){
        return na;
    } else {
        return domNodeCommonAncestor(na.parentElement, nb);
    }
}

Upvotes: 0

Morteza Faghih Shojaie
Morteza Faghih Shojaie

Reputation: 860

Here is a better and shorter way of finding the common ancestor of two or more elements:

// find the common ancestor of two nodes
const findFirstCommonAncestor = (nodeA, nodeB) => {
   if (nodeA.contains(nodeB)) return nodeA;
   if (nodeB.contains(nodeA)) return nodeB;


   const range = new Range();
   range.setStartBefore(nodeA);
   range.setEndAfter(nodeB);
   if (range.collapsed) {
      range.setStartBefore(nodeB);
      range.setEndAfter(nodeA);
   }
   return range.commonAncestorContainer;
};


// find the common ancestor of multiple nodes
const firstFirstCommonAncestorMultiple = (nodes) =>
   nodes.reduce((acc, node) => (acc === node ? acc : findFirstCommonAncestor(acc, node)), nodes[0]);

Upvotes: 0

milahu
milahu

Reputation: 3559

based on the answers from Andy E and AntonB

handle edge-cases: node1 == node2 and node1.contains(node2)

function getCommonParentNode(node1, node2) {
  if (node1 == node2) return node1;
  var parent = node1;
  do if (parent.contains(node2)) return parent
  while (parent = parent.parentNode);
  return null;
}

Upvotes: 5

Paul
Paul

Reputation: 121

Somewhat late to the party, here's a JavaScript ES6 version that uses Array.prototype.reduce() and Node.contains(), and can take any number of elements as parameters:

function closestCommonAncestor(...elements) {
    const reducer = (prev, current) => current.parentElement.contains(prev) ? current.parentElement : prev;
    return elements.reduce(reducer, elements[0]);
}

const element1 = document.getElementById('element1');
const element2 = document.getElementById('element2');
const commonAncestor = closestCommonAncestor(element1, element2);

Upvotes: 1

Eliav Louski
Eliav Louski

Reputation: 5264

did not liked any of the answers above(want pure javascript and one function). that worked perfectly for me,efficient and also easier to understand:

    const findCommonAncestor = (elem, elem2) => {
      let parent1 = elem.parentElement,parent2 = elem2.parentElement;
      let childrensOfParent1 = [],childrensOfParent2 = [];
      while (parent1 !== null && parent2 !== null) {
        if (parent1 !== !null) {
          childrensOfParent2.push(parent2);
          if (childrensOfParent2.includes(parent1)) return parent1;
        }
        if (parent2 !== !null) {
          childrensOfParent1.push(parent1);
          if (childrensOfParent1.includes(parent2)) return parent2;
        }
        parent1 = parent1.parentElement;
        parent2 = parent1.parentElement;
      }
      return null;
    };

Upvotes: 0

benpickles
benpickles

Reputation: 1560

Here's a pure JavaScript version that is a little more efficient.

function parents(node) {
  var nodes = [node]
  for (; node; node = node.parentNode) {
    nodes.unshift(node)
  }
  return nodes
}

function commonAncestor(node1, node2) {
  var parents1 = parents(node1)
  var parents2 = parents(node2)

  if (parents1[0] != parents2[0]) throw "No common ancestor!"

  for (var i = 0; i < parents1.length; i++) {
    if (parents1[i] != parents2[i]) return parents1[i - 1]
  }
}

Upvotes: 74

Flavien Volken
Flavien Volken

Reputation: 21309

PureJS

function getFirstCommonAncestor(nodeA, nodeB) {
    const parentsOfA = this.getParents(nodeA);
    const parentsOfB = this.getParents(nodeB);
    return parentsOfA.find((item) => parentsOfB.indexOf(item) !== -1);
}

function getParents(node) {
    const result = [];
    while (node = node.parentElement) {
        result.push(node);
    }
    return result;
}

Upvotes: 0

AntonB
AntonB

Reputation: 2853

This doesn't require much code anymore to solve:

steps:

  1. grab parent of node_a
  2. if parent of node_a contains node_b return parent (in our code, the parent is referenced as node_a)
  3. if parent does not contain node_b we need to keep going up the chain
  4. end return null

code:

function getLowestCommonParent(node_a, node_b) {
    while (node_a = node_a.parentElement) {
        if (node_a.contains(node_b)) {
            return node_a;
        }
    }

    return null;
}

Upvotes: 5

windinsky
windinsky

Reputation: 44

Here is a dirtier way of doing this. It's easier to understand but requires dom modification:

function commonAncestor(node1,node2){
        var tmp1 = node1,tmp2 = node2;
        // find node1's first parent whose nodeType == 1
        while(tmp1.nodeType != 1){
            tmp1 = tmp1.parentNode;
        }
        // insert an invisible span contains a strange character that no one 
        // would use
        // if you need to use this function many times,create the span outside
        // so you can use it without creating every time
        var span = document.createElement('span')
            , strange_char = '\uee99';
        span.style.display='none';
        span.innerHTML = strange_char;
        tmp1.appendChild(span);
        // find node2's first parent which contains that odd character, that 
        // would be the node we are looking for
        while(tmp2.innerHTML.indexOf(strange_char) == -1){
            tmp2 = tmp2.parentNode; 
        }                           
        // remove that dirty span
        tmp1.removeChild(span);
        return tmp2;
    }

Upvotes: 0

Rycochet
Rycochet

Reputation: 2938

Somewhat late to the party, but here's an elegant jQuery solution (since the question is tagged jQuery) -

/**
 * Get all parents of an element including itself
 * @returns {jQuerySelector}
 */
$.fn.family = function() {
    var i, el, nodes = $();

    for (i = 0; i < this.length; i++) {
        for (el = this[i]; el !== document; el = el.parentNode) {
            nodes.push(el);
        }
    }
    return nodes;
};

/**
 * Find the common ancestors in or against a selector
 * @param selector {?(String|jQuerySelector|Element)}
 * @returns {jQuerySelector}
 */
$.fn.common = function(selector) {
    if (selector && this.is(selector)) {
        return this;
    }
    var i,
            $parents = (selector ? this : this.eq(0)).family(),
            $targets = selector ? $(selector) : this.slice(1);
    for (i = 0; i < $targets.length; i++) {
        $parents = $parents.has($targets.eq(i).family());
    }
    return $parents;
};

/**
 * Find the first common ancestor in or against a selector
 * @param selector {?(String|jQuerySelector|Element)}
 * @returns {jQuerySelector}
 */
$.fn.commonFirst = function(selector) {
    return this.common(selector).first();
};

Upvotes: 1

user3326824
user3326824

Reputation: 136

The commonAncestorContainer property of the he Range API mentioned above, alongside its selectNode, makes this a no-brainer.

Run ("display") this code in Firefox's Scratchpad or a similar editor:

var range = document.createRange();
var nodes = [document.head, document.body];  // or any other set of nodes
nodes.forEach(range.selectNode, range);
range.commonAncestorContainer;

Note that both APIs are not supported by IE 8 or below.

Upvotes: 11

Tom Hubbard
Tom Hubbard

Reputation: 16139

This is a generalized take on lonesomeday's answer. Instead of only two elements it will take a full JQuery object.

function CommonAncestor(jq) {
    var prnt = $(jq[0]);
    jq.each(function () { 
        prnt = prnt.parents().add(prnt).has(this).last(); 
    });
    return prnt;
}

Upvotes: 1

Daniel Trebbien
Daniel Trebbien

Reputation: 39208

You can also use a DOM Range (when supported by the browser, of course). If you create a Range with the startContainer set to the earlier node in the document and the endContainer set to the later node in the document, then the commonAncestorContainer attribute of such a Range is the deepest common ancestor node.

Here is some code implementing this idea:

function getCommonAncestor(node1, node2) {
    var dp = node1.compareDocumentPosition(node2);
    // If the bitmask includes the DOCUMENT_POSITION_DISCONNECTED bit, 0x1, or the
    // DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC bit, 0x20, then the order is implementation
    // specific.
    if (dp & (0x1 | 0x20)) {
        if (node1 === node2) return node1;

        var node1AndAncestors = [node1];
        while ((node1 = node1.parentNode) != null) {
            node1AndAncestors.push(node1);
        }
        var node2AndAncestors = [node2];
        while ((node2 = node2.parentNode) != null) {
            node2AndAncestors.push(node2);
        }

        var len1 = node1AndAncestors.length;
        var len2 = node2AndAncestors.length;

        // If the last element of the two arrays is not the same, then `node1' and `node2' do
        // not share a common ancestor.
        if (node1AndAncestors[len1 - 1] !== node2AndAncestors[len2 - 1]) {
            return null;
        }

        var i = 1;
        for (;;) {
            if (node1AndAncestors[len1 - 1 - i] !== node2AndAncestors[len2 - 1 - i]) {
                // assert node1AndAncestors[len1 - 1 - i - 1] === node2AndAncestors[len2 - 1 - i - 1];
                return node1AndAncestors[len1 - 1 - i - 1];
            }
            ++i;
        }
        // assert false;
        throw "Shouldn't reach here!";
    }

    // "If the two nodes being compared are the same node, then no flags are set on the return."
    // http://www.w3.org/TR/DOM-Level-3-Core/core.html#DocumentPosition
    if (dp == 0) {
        // assert node1 === node2;
        return node1;

    } else if (dp & 0x8) {
        // assert node2.contains(node1);
        return node2;

    } else if (dp & 0x10) {
        // assert node1.contains(node2);
        return node1;
    }

    // In this case, `node2' precedes `node1'. Swap `node1' and `node2' so that `node1' precedes
    // `node2'.
    if (dp & 0x2) {
        var tmp = node1;
        node1 = node2;
        node2 = tmp;
    } else {
        // assert dp & 0x4;
    }

    var range = node1.ownerDocument.createRange();
    range.setStart(node1, 0);
    range.setEnd(node2, 0);
    return range.commonAncestorContainer;
}

Upvotes: 4

Andy E
Andy E

Reputation: 344575

Here's another pure method that uses element.compareDocumentPosition() and element.contains(), the former being a standards method and the latter being a method supported by most major browsers excluding Firefox:

Comparing two nodes

function getCommonAncestor(node1, node2) {
    var method = "contains" in node1 ? "contains" : "compareDocumentPosition",
        test   = method === "contains" ? 1 : 0x10;

    while (node1 = node1.parentNode) {
        if ((node1[method](node2) & test) === test)
            return node1;
    }

    return null;
}

Working demo: http://jsfiddle.net/3FaRr/ (using lonesomeday's test case)

This should be, more or less, as efficient as possible since it is pure DOM and has only one loop.

Comparing two or more nodes

Taking another look at the question, I noticed the "or more" part of the "two or more" requirement had gone ignored by the answers. So I decided to tweak mine slightly to allow any number of nodes to be specified:

function getCommonAncestor(node1 /*, node2, node3, ... nodeN */) {
    if (arguments.length < 2)
        throw new Error("getCommonAncestor: not enough parameters");

    var i,
        method = "contains" in node1 ? "contains" : "compareDocumentPosition",
        test   = method === "contains" ? 1 : 0x0010,
        nodes  = [].slice.call(arguments, 1);

    rocking:
    while (node1 = node1.parentNode) {
        i = nodes.length;    
        while (i--) {
            if ((node1[method](nodes[i]) & test) !== test)
                continue rocking;
        }
        return node1;
    }

    return null;
}

Working demo: http://jsfiddle.net/AndyE/3FaRr/1

Upvotes: 13

lonesomeday
lonesomeday

Reputation: 237875

The solutions involving manually going through the ancestor elements are far more complicated than necessary. You don't need to do the loops manually. Get all the ancestor elements of one element with parents(), reduce it to the ones that contain the second element with has(), then get the first ancestor with first().

var a = $('#a'),
    b = $('#b'),
    closestCommonAncestor = a.parents().has(b).first();

jsFiddle example

Upvotes: 49

Bobby Jack
Bobby Jack

Reputation: 16018

Try this:

function get_common_ancestor(a, b)
{
    $parentsa = $(a).parents();
    $parentsb = $(b).parents();

    var found = null;

    $parentsa.each(function() {
        var thisa = this;

        $parentsb.each(function() {
            if (thisa == this)
            {
                found = this;
                return false;
            }
        });

        if (found) return false;
    });

    return found;
}

Use it like this:

var el = get_common_ancestor("#id_of_one_element", "#id_of_another_element");

That's just rattled out pretty quickly, but it should work. Should be easy to amend if you want something slightly different (e.g. jQuery object returned instead of DOM element, DOM elements as arguments rather than IDs, etc.)

Upvotes: 9

Pointy
Pointy

Reputation: 413737

You should be able to use the jQuery .parents() function and then walk through the results looking for the first match. (Or I guess you could start from the end and go backwards until you see the first difference; that's probably better.)

Upvotes: 4

Related Questions