Geek Answers Handbook

Determine if a circular reference in object A is structurally the same as a circular reference in object B

I am implementing a function that compares two JavaScript objects for "deep" equality. The skeleton of this function now looks like this:

function check_equal(actual, expected) { var stack = []; function check_equal_r(act, exp) { if (is_scalar(act) || is_scalar(exp)) { assert(act === exp); } else if (stack.indexOf(act) == -1) { assert(have_all_the_same_properties(act, exp)); stack.push(act); for (var k of Object.getOwnPropertyNames(exp)) { check_equal_r(act[k], exp[k]); } stack.pop(act); } else { // ??? cyclic reference detected } } check_equal_r(act, exp); }

The question is what to put where it says // ??? cyclic reference detected // ??? cyclic reference detected . Ideally, I would like to say that these objects are deep:

 var a = {foo:1, bar:2, baz:null}, b = {foo:1, bar:2, baz:null}; a.baz = a; b.baz = b;

and these objects are not deep:

 var a = { car: 1, cdr: { car: 2, cdr: null } }; var b = { car: 1, cdr: { car: 2, cdr: null } }; a.cdr.cdr = a; b.cdr.cdr = b.cdr;

Notes:

  • assert throws an exception if its argument is false.
  • have_all_the_same_properties(x, y) throws an exception if the getOwnPropertyNames x and y lists getOwnPropertyNames not identical.
  • is_scalar(x) actually matches typeof x !== 'object' .
  • I used the for loop in the loop above for brevity, but ES6 functions are not available in the interpreter, this will actually execute.
+5
source share
2 answers

Here's a pretty simple extension of your algorithm that checks for circular references. It stores the exp corresponding to each act object in a separate stack, so that it will have the same index as any act that refers internally.

 function is_scalar(v) { return typeof v !== 'object'; } function have_all_the_same_properties(x, y) { var xprops = Object.getOwnPropertyNames(x), yprops = Object.getOwnPropertyNames(y); if (xprops.length === yprops.length) { return xprops.every(function (prop) { return yprops.indexOf(prop) !== -1; }); } return false; } function check_equal(actual, expected) { var stack = []; var expected_stack = []; function check_equal_r(act, exp) { if (is_scalar(act) || is_scalar(exp)) { return act === exp; } else { var i = stack.indexOf(act); if (i == -1) { if (have_all_the_same_properties(act, exp)) { stack.push(act); expected_stack.push(exp); var res = Object.getOwnPropertyNames(exp).every(function (k) { return check_equal_r(act[k], exp[k]); }); expected_stack.pop(); stack.pop(); return res; } else { return false; } } else { return expected_stack[i] === exp; } } } return check_equal_r(actual, expected); } var a = {foo:1, bar:2, baz:null}, b = {foo:1, bar:2, baz:null}; a.baz = a; b.baz = b; console.log(check_equal(a, b)); var c = { car: 1, cdr: { car: 2, cdr: null } }; var d = { car: 1, cdr: { car: 2, cdr: null } }; c.cdr.cdr = c; d.cdr.cdr = d.cdr; console.log(check_equal(c, d));
+2
source

Chris's answer is correct. I recently wrote a utility function to test deep equality and should also cover circular dependencies. Here is the code on github ( https://github.com/ryancat/simple-deep-equal ), which also covers the case of NaN.

0
source

More articles:


All Articles