How can I filter a Javascript array and maintain it's indices?

Question

Here is what I have currently:

var myArray = [];
myArray[15] = 2;
myArray[6323] = 1;
myArray[349022] = 3;
myArray = myArray.filter(function(i,v,a){return ! (typeof v == 'undefined')});
myArray = myArray.sort(function(a,b){return (a - b)});

When I console.log() allocationOrder after the "filter" function, I get the values that I expect, but the indices are not maintained. How can I maintain the indices but also remove the undefined values (due to having spread out indices)? Keep in mind that I need to sort the array by value afterwards (which is why I avoided objects as a solution).

Answer 1

You can't have your cake and eat it too.

You can't have a sparse array (only some values filled in) and have no undefined values in between. That's just not how javascript arrays work. Further, you can remove the elements that have undefined values and expect the other values to stay at the same index. By defintion, removing those other values, collapses the array (changing indexes).

Perhaps if you can describe what you're really trying to accomplish we can figure out a better way to approach the problem.

I'm thinking that what you want is an array of objects where each object in the array has an index and a value. The indexes on the objects in the array will never change, but the container array can be sorted by those indexes.

var mySortedArray = [
    {index:15, value: 2},
    {index:6323, value: 1},
    {index:349022, value: 3}
];

mySortedArray = myArray.sort(function(a, b) {a.value - b.value});

Now you have a sorted array that's three elements long and it's sorted by value and the original index is preserved and available.

The only drawback is that you can't easily access it by the index. If you wanted to be able to have both ordered, sorted access and access by the index key, you could make a parallel data structure that make key access quick. In Javascript, there is no single data structure that supports both key access and sorted order access.

If you want to build a parallel data structure that would support fast access by key (and would include the value and the sortOrder value, you could build such an object like this:

// build a parallel data structure for keyed access
var myKeyedObject = {}, temp, item;
for (var i = 0; i < mySortedArray.length; i++) {
    item = mySortedArray[i];
    temp = {};
    temp.value = item.value;
    temp.index = item.index;
    temp.sortOrder = i;
    myKeyedObject[item.index] = temp;
}

Answer 2

While JavaScript arrays behave rather nicely if you delete their entries, there is sadly no built-in function that does this. However, it isn't too hard to write one:

Array.prototype.filterAssoc = function(callback) {
    var a = this.slice();
    a.map(function(v, k, a) {
        if(!callback(v, k, a)) delete a[k];
    });
    return a;
};

With this added to the array prototype, myArray.filterAssoc(...).map(...) will map over only the key-value pairs that were filtered for, just as expected.

That answers the question in the title. As for your side note about wanting to sort the array afterward... sort does not behave nicely on sparse arrays. The easiest way to do that really is to sort an array of objects.