JavaScript deep copy of an object graph

Question

I need a function which makes a deep copy of an object in JavaScript. Each object is part of a larger graph (thus the need for a deep copy function). For example,

//Node "class" with references to its parent and children
var MyNode = (function () {
    function MyNode() {
        this.children = undefined;
        this.parent = undefined;
    }
    return MyNode;
})();

The graph has no loops.

My thought was to do a depth-first-search through the graph and use a dictionary that stores a hash of each Node with its copy. As each node is visited, the copy parent is looked up from the dictionary and the node is added to its parents children collection. My problem is that for this method to work, I'd need to be able to has on the memory location of each Node.

This was my general idea:

function(rootNode) {
    var magicDictionary = {};
    var stack = {rootNode};

    while(stack.length > 0) {
        var current = stack.pop();

        //Performs a shallow copy, not including the parent or children references
        var newNode = new MyNode(current);

        //Get our new node's parent based on our old node's parent
        newNode.parent = magicDictionary[current.parent];

        //Add this new node as a child
        newNode.parent.children.push(newNode);

        //Continue the DPS
        for(var i = 0; i < current.children.length; i++)
            stack.push(current.children[i]);
    }
}

The dictionary is the big problem here. It would need to actually hash on the memory location, because even a hashcode function could not be unique per object.

Is there a better way to do this?

Answer 1

Rather than using hashcodes you can use a WeakMap. They essentially do the same thing: give you a uniqueness detector. But without the cost of the hashing algorithm, it's collision free and doesn't use much memory.

Support for WeakMaps

If you search you can find custom implementations of WeakMaps incase you're using a browser that doesn't support WeakMaps yet.