Scenario: I'm searching for a specific object in a deep object. I'm using a recursive function that goes through the children and asks them if I'm searching for them or if I'm searching for their children or grandchildren and so on. When found, the found obj will be returned, else false. Basically this:

obj.find = function (match_id) {
    if (this.id == match_id) return this;
    for (var i = 0; i < this.length; i++) {
        var result = this[i].find(match_id);
        if (result !== false) return result;
    };
    return false;
}​

i'm wondering, is there something simpler than this?:

var result = this[i].find(match_id);
if (result) return result;

It annoys me to store the result in a variable (on each level!), i just want to check if it's not false and return the result. I also considered the following, but dislike it even more for obvious reasons.

if (this[i].find(match_id)) return this[i].find(match_id);

Btw I'm also wondering, is this approach even "recursive"? it isn't really calling itself that much...

Thank you very much.

[edit]

There is another possibility by using another function check_find (which just returns only true if found) in the if statement. In some really plicated cases (e.g. where you don't just find the object, but also alter it) this might be the best approach. Or am I wrong? D:

Scenario: I'm searching for a specific object in a deep object. I'm using a recursive function that goes through the children and asks them if I'm searching for them or if I'm searching for their children or grandchildren and so on. When found, the found obj will be returned, else false. Basically this:

obj.find = function (match_id) {
    if (this.id == match_id) return this;
    for (var i = 0; i < this.length; i++) {
        var result = this[i].find(match_id);
        if (result !== false) return result;
    };
    return false;
}​

i'm wondering, is there something simpler than this?:

var result = this[i].find(match_id);
if (result) return result;

It annoys me to store the result in a variable (on each level!), i just want to check if it's not false and return the result. I also considered the following, but dislike it even more for obvious reasons.

if (this[i].find(match_id)) return this[i].find(match_id);

Btw I'm also wondering, is this approach even "recursive"? it isn't really calling itself that much...

Thank you very much.

[edit]

There is another possibility by using another function check_find (which just returns only true if found) in the if statement. In some really plicated cases (e.g. where you don't just find the object, but also alter it) this might be the best approach. Or am I wrong? D:

• javascript
• object

Share Improve this question Follow edited Oct 2, 2018 at 13:28 Machavity♦ 31.7k2727 gold badges9595 silver badges105105 bronze badges asked Sep 26, 2012 at 23:16 someonelsesomeonelse 26011 gold badge33 silver badges1313 bronze badges 3

• 1 Wouldn't your check_find idea have the same problem? You'd still need to get the result from check_find and store it, or you'd need to duplicate the .find() as in the code you dislike. – I Hate Lazy Commented Sep 26, 2012 at 23:29
• Wait, you're searching through objects or arrays of objects? There might be considerably easier ways to handle this. – Erik Reppen Commented Sep 27, 2012 at 0:03
• 1 What is this syntax: obj.find(match_id) {? Is this JavaScript? Did you mean obj.find = function(match_id) {? – Nathan Wall Commented Sep 27, 2012 at 3:04

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 3

Although the solution you have is probably "best" as far as search algorithms go, and I wouldn't necessarily suggest changing it (or I would change it to use a map instead of an algorithm), the question is interesting to me, especially relating to the functional properties of the JavaScript language, and I would like to provide some thoughts.

Method 1

The following should work without having to explicitly declare variables within a function, although they are used as function arguments instead. It's also quite succinct, although a little terse.

var map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return this.id == match_id ? this : map(this, function(u) {
        return find.call(u, match_id);
    }).filter(function(u) { return u; })[0];
};​

How it works:

1. We test to see if this.id == match_id, if so, return this.
2. We use map (via Array.prototype.map) to convert this to an array of "found items", which are found using the recursive call to the find method. (Supposedly, one of these recursive calls will return our answer. The ones which don't result in an answer will return undefined.)
3. We filter the "found items" array so that any undefined results in the array are removed.
4. We return the first item in the array, and call it quits.
   • If there is no first item in the array, undefined will be returned.

Method 2

Another attempt to solve this problem could look like this:

var concat = Function.prototype.call.bind(Array.prototype.concat),
    map = Function.prototype.call.bind(Array.prototype.map);

obj.find = function find(match_id) {
    return (function buildObjArray(o) {
        return concat([ o ], map(o, buildObjArray));
    })(this).filter(function(u) { return u.id == match_id })[0];
};

How it works:

1. buildObjArray builds a single, big, 1-dimensional array containing obj and all of obj's children.
2. Then we filter based on the criteria that an object in the array must have an id of match_id.
3. We return the first match.

Both Method 1 and Method 2, while interesting, have the performance disadvantage that they will continue to search even after they've found a matching id. They don't realize they have what they need until the end of the search, and this is not very efficient.

Method 3

It is certainly possible to improve the efficiency, and now I think this one really gets close to what you were interested in.

var forEach = Function.prototype.call.bind(Array.prototype.forEach);

obj.find = function(match_id) {
    try {
        (function find(obj) {
            if(obj.id == match_id) throw this;
            forEach(obj, find);
        })(obj);
    } catch(found) {
        return found;
    }
};​

How it works:

1. We wrap the whole find function in a try/catch block so that once an item is found, we can throw and stop execution.
2. We create an internal find function (IIFE) inside the try which we reference to make recursive calls.
3. If this.id == match_id, we throw this, stopping our search algorithm.
4. If it doesn't match, we recursively call find on each child.
5. If it did match, the throw is caught by our catch block, and the found object is returned.

Since this algorithm is able to stop execution once the object is found, it would be close in performance to yours, although it still has the overhead of the try/catch block (which on old browsers can be expensive) and forEach is slower than a typical for loop. Still these are very small performance losses.

Method 4

Finally, although this method does not fit the confines of your request, it is much, much better performance if possible in your application, and something to think about. We rely on a map of ids which maps to objects. It would look something like this:

// Declare a map object.
var map = { };

// ...
// Whenever you add a child to an object...
obj[0] = new MyObject();
// .. also store it in the map.
map[obj[0].id] = obj[0];

// ...
// Whenever you want to find the object with a specific id, refer to the map:
console.log(map[match_id]); // <- This is the "found" object.

This way, no find method is needed at all!

The performance gains in your application by using this method will be HUGE. Please seriously consider it, if at all possible.

However, be careful to remove the object from the map whenever you will no longer be referencing that object.

delete map[obj.id];

This is necessary to prevent memory leaks.

No there is no other clear way, storing the result in a variable isn't that much trouble, actually this is what variables are used for.

Yes, that approach is recursive:

• you have the base case if (this.id==match_id) return this
• you have the recursive step which call itself obj.find(match_id) { ... var result = this[i].find(match_id); }

I don't see any reason, why storing the variable would be bad. It's not a copy, but a reference, so it's efficient. Plus the temporary variable is the only way, that I can see right now (I may be wrong, though).

With that in mind, I don't think, that a method check_find would make very much sense (it's most probably basically the same implementation), so if you really need this check_find method, I'd implement it as

return this.find(match_id) !== false;

Whether the method is recursive is hard to say. Basically, I'd say yes, as the implementations of 'find' are all the same for every object, so it's pretty much the same as

function find(obj, match_id) {
    if (obj.id == match_id) return obj;
    for (var i = 0; i < obj.length; ++i) {
        var result = find(obj[i], match_id);
        if (result !== false) return result;
    }
}

which is definitely recursive (the function calls itself).

However, if you'd do

onesingleobjectinmydeepobject.find = function(x) { return this; }

I'm not quite sure, if you still would call this recursive.