# Challenge: solution for this deep-iteration JavaScript function dilemma?

Posted on

Problem

Trying to implement a deep-iteration function with some constraints, I’ve noticed the faster solution is iterating it twice! Any attempt to avoid this resulted in slower code. So, the challenge: can you redesign the function below removing the code duplicate and doubled iteration, without making it slower?

Constraints:

• It must deeply iterate through a tree, providing, for a callback function, the node value and it’s path.
• It must work for arrays and objects.
• Arrays must be iterated by ascending numerical keys first and non-numerical keys last.
• It must allow for early interruption by using “return”, and must return that value.

Code:

``````function iter(obj,fn,iter_pos){
var ret, iter_pos = iter_pos || [];
for (var i=0; i<obj.length; ++i)
if (ret = typeof(obj[i]) == "object" ? iter(obj[i],fn,iter_pos.concat(i)) : fn(iter_pos.concat(i),obj[i]))
return ret;
for (var key in obj)
if (isNaN(Number(key)))
if (ret = typeof(obj[key]) == "object" ? iter(obj[key],fn,iter_pos.concat(key)) : fn(iter_pos.concat(key),obj[key]))
return ret;
};
``````

Test:

``````var tree = [1,2,[3,3,3],4];
tree.x = 5;
tree.y = {x:6,y:7,z:8};
tree.z = 9;
console.log(
iter(tree,function(path,val){
console.log("Value ",val," at path: ",path);
if (val==7)
return "Returned early!";
})
);
``````

Output:

``````Value  1  at path:  [ 0 ]
Value  2  at path:  [ 1 ]
Value  3  at path:  [ 2, 0 ]
Value  3  at path:  [ 2, 1 ]
Value  3  at path:  [ 2, 2 ]
Value  4  at path:  [ 3 ]
Value  5  at path:  [ 'x' ]
Value  6  at path:  [ 'y', 'x' ]
Value  7  at path:  [ 'y', 'y' ]
Returned early!
``````

Solution

Let me start by asking how would you like to iterate over your object? Because what you are doing is not the same as calling a function for every property of an object.

``````function iter(obj,fn,iter_pos){
var ret, iter_pos = iter_pos || [];
for (var i=0; i<obj.length; ++i)
``````

The above for loop may access elements in the array that are not even defined. For example, take this array:

``````var a = [0, 1];
a = 9;
console.log(a.length);  // -> 10
console.log(a.hasOwnProperty(0)); // -> true
console.log(a.hasOwnProperty(1)); // -> true
console.log(a.hasOwnProperty(2)); // -> false !!
console.log(a.hasOwnProperty(9)); // -> true
``````

The above array has a length of 10, but it only has three properties (it has 10 elements, but not all are defined). If you do an `a.forEach()`, you’ll iterate over the array’s properties, only those that are defined.

If you do a `for (i=0; i<a.length; i++)` loop over the array, you’ll get properties that are not defined. To avoid those, you should check `a.hasOwnProperty()`. Or just use the native `forEach`, if you can, that will iterate over the array correctly.

Note that checking against `undefined` would not be sufficient either, array elements can be present but undefined:

``````a = undefined;
console.log(a.hasOwnProperty(5)); // -> true !!
``````
``````        if (ret = typeof(obj[i]) == "object" ? iter(obj[i],fn,iter_pos.concat(i)) : fn(iter_pos.concat(i),obj[i]))
return ret;
for (var key in obj)
if (isNaN(Number(key)))
``````

Here you’re trying to do the opposite of `forEach`: enumerating properties that are not elements of the array.

But this code will miss properties that still evaluate as numbers! Have a look at the following array:

``````var a = [0, 1, 2, 3, 4];
a = 99;
a[1.5] = 'this is not an array element';
a[-1] = 'this one is not an array element either';
a['20'] = 'this one *is* an array element!';
``````

Also, watch out for rounding:

``````a[30.00000000000001] = 'this is *not* an array element';
a[30.000000000000001] = 'this *is*, however, because it rounds to 30'
``````

But also for the string representations:

``````a[30.000000000000001] = 'array element';
a['30.000000000000001'] = 'not array element';
``````

Especially the ones that evaluate the same:

``````a[1e1] = 'element number ten';
a['1e1'] = 'a completely different element';
``````

`'-1'`, `'1.5'`, `'1e1'`, `'30.000000000000001'`, etc. can all be properties of an array, but they will all evaluate `false` for `isNaN(Number(key))`.

``````            if (ret = typeof(obj[key]) == "object" ? iter(obj[key],fn,iter_pos.concat(key)) : fn(iter_pos.concat(key),obj[key]))
return ret;
};
``````

You can easily fix your script by changing the line

``````        if (isNaN(Number(key)))
``````

to

``````        if (!key.match(/^d+\$/))
``````

# TL; DR

I’ve removed the double loop from your code:

``````function iter(obj, fn, iter_pos){
var ret, iter_pos = iter_pos || [];
for (var key in obj)
if (ret = typeof(obj[key]) == "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key]))
return ret;
};
``````

and it does not seem to be any slower, or at least not according to jsperf.com/iter.

I tried it in a number of browsers I could find.

# UPDATE 1:

Here is a version that uses two loops, but is much faster. It will fix the ordering, but only in cases where the array indexes come before other array properties.

``````__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
var ret, i = 0,
iter_pos = iter_pos || [];
if (__toString.call(obj) === '[object Array]') {
obj.forEach(function (item) {
if (!ret) {
ret = typeof (obj[i]) === "object" ? iter(obj[i], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[i]);
i++;
}
});
if (ret)
return ret;
}
for (var key in obj)
if (--i < 0)
if (ret = typeof (obj[key]) === "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key])) return ret;
};
``````

# UPDATE 2:

This is your original version, with two loops, but using `forEach` and `Object.prototype.toString`. It seems to output the same result, but is about 2000× faster.

``````__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
var ret, iter_pos = iter_pos || [];
if (__toString.call(obj) === '[object Array]') {
obj.forEach(function (item) {
if (!ret)
ret = typeof (obj[i]) === "object" ? iter(obj[i], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[i]);
});
if (ret)
return ret;
}
for (var key in obj)
if (!("" + key).match(/^d+\$/))
if (ret = typeof (obj[key]) === "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key]))
return ret;
};
``````

# UPDATE 3:

This version is about as fast as the other one, but uses only `Object.prototype.toString` and does not use `typeof`.

``````__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
var ret, obj_type, iter_pos = iter_pos || [];
if (__toString.call(obj) === '[object Array]') {
obj.forEach(function (item) {
if (!ret)
ret = ((obj_type = __toString.call(item)) === "[object Object]") || (obj_type === "[object Array]") ? iter(item, fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), item);
});
if (ret)
return ret;
}
for (var key in obj)
if (!("" + key).match(/^d+\$/))
if (ret = ((obj_type = __toString.call(item)) === "[object Object]") || (obj_type === "[object Array]") ? iter(obj[key], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[key]));
return ret
};
``````