Sort array containing DOM elements according to their position in the DOM

Question

Context

I've structured a jQuery plugin I'm currently working on in a way that has me storing DOM elements in an array, mostly for being able to store more information next to these elements without having to use the not-so-fast data().

That array looks like:

[
    { element: DOMElement3, additionalData1: …, additionalData2: … },
    { element: DOMElement1, additionalData1: …, additionalData2: … },
    { element: DOMElement2, additionalData1: …, additionalData2: … },
]

The way this plugin works prevents me from pushing these elements to the array in a predictable order, which means DOMElement3 can in fact find itself at an index lower than DOMElement2's.

However, I need these array elements to be sorted in the same order as the DOM elements they contain appear in the DOM. The previous example array, once sorted, would look like this:

[
    { element: DOMElement1, additionalData1: …, additionalData2: … },
    { element: DOMElement2, additionalData1: …, additionalData2: … },
    { element: DOMElement3, additionalData1: …, additionalData2: … },
]

This is, of course, if DOMElement1 appears before DOMElement2 in the DOM, and DOMElement2 before DOMElement3.

Discarded solution

The jQuery add() method returns a set of DOM elements in the same order as they appear in the DOM. I could be using this, but the requirement is that I work with a jQuery collection – which means I'd have to refactor a huge chunk of the abovementioned plugin to use a different storage format. That's why I consider this a last-resort solution.

Another solution?

I would have imagined that map() and a sort of global DOM index tied to each DOM element would have done the trick, but there doesn't appear to be such a "global DOM index".

What approach can you think of? (If writing code, both vanilla JS and jQuery are welcome.)

Answer 1

There is a very useful function called compareDocumentPosition, which returns a number based on where two elements are relative to each other. You can use this in a .sort callback:

yourArray.sort(function(a,b) {
    if( a === b) return 0;
    if( !a.compareDocumentPosition) {
        // support for IE8 and below
        return a.sourceIndex - b.sourceIndex;
    }
    if( a.compareDocumentPosition(b) & 2) {
        // b comes before a
        return 1;
    }
    return -1;
});

Answer 2

While I don't suggest you go with this approach, it is possible with jquery to get a "global DOM index":

var $all = $("*");

// use index to get your element's index within the entire DOM
$all.index($YOUR_EL);

Answer 3

You don't have to do a lot of refactoring to take advantage of jQuery's sorting. You can use it as a temporary sorting mechanism. Here's an off-the-cuff:

function putInDocumentOrder(a) {
      var elements;

    // Get elements in order and remember the index of
    // the entry in `a`
    elements = $().add(a.map(function(entry, index){
        entry.element.__index = index;
        return entry.element;
    }));

    // Build array of entries in element order
    a = elements.map(function(){
        return a[this.__index];
    }).get();

    return a;
}

It requires an expando, but it does the job. Live Example

This has the advantage that it works on all browsers that jQuery supports, rather than your having to deal with the edge cases (IE8 not supporting compareDocumentPosition, for instance) yourself.