ecmascript 6 - Test deep equality *with sharing* of JavaScript objects -

much ink has been spilled on subject of testing 2 objects deep equality in javascript. none, however, seem care distinguishing following 2 objects:

var o1 = [{},{}]; var subitem = {}; var o2 = [subitem, subitem]; var o3 = [{}, {}]; 

most deep equality algorithms o1, o2 , o3 equal. want algorithm says o1 , o2 not equal, o1 , o3 equal. put differently, want algorithm tells me if pointer graphs have same structure or not. care because if have modification of first element reflected in second in o2, not in o1.

this means deep equality of cyclic structures should work:

var o1 = []; o1.push(o1); var o2 = []; o2.push(o2); // deepgraphequal(o1, o2) == true var o3 = [[]]; o3[0].push(o3); // deepgraphequal(o1, o3) == false 

if you're going avoid mutating items, going need ecmascript6 maps, i'll accept solutions use those.

version no es6 features runs in quadratic time:

function deepgraphequal(a, b) {     var left = [], right = [], has = object.prototype.hasownproperty;     function visit(a, b) {         var i, k;         if (typeof !== 'object' || typeof b !== 'object' || === null || b === null)             return === b;         if (object.getprototypeof(a) !== object.getprototypeof(b))             return false;         (i = 0; < left.length; i++) {             if (a === left[i])                 return b === right[i];             if (b === right[i])                 return === left[i];         }         (k in a)             if (has.call(a, k) && !has.call(b, k))                 return false;         (k in b)             if (has.call(b, k) && !has.call(a, k))                 return false;         left.push(a);         right.push(b);         (k in a)             if (has.call(a, k) && !visit(a[k], b[k]))                 return false;         return true;     }     return visit(a, b); } 

version es6 map runs in linear time:

function deepgraphequal(a, b) {     let left = new map(), right = new map(), has = object.prototype.hasownproperty;     function visit(a, b) {         if (typeof !== 'object' || typeof b !== 'object' || === null || b === null)             return === b;         if (object.getprototypeof(a) !== object.getprototypeof(b))             return false;         if (left.has(a))             return left.get(a) === b         if (right.has(b))             return right.get(b) ===         (let k in a)             if (has.call(a, k) && !has.call(b, k))                 return false;         (let k in b)             if (has.call(b, k) && !has.call(a, k))                 return false;         left.set(a, b);         right.set(b, a);         (let k in a)             if (has.call(a, k) && !visit(a[k], b[k]))                 return false;         return true;     }     return visit(a, b); }