Deep Copy 2 Dimensional Array

Question

I've been trying to do deep copy of a 2 dimensional array but never succeeded. Here is my code.

class node {
    public node head;
    public node left;
    public node right;
    public node up;
    public node down;
}

node[][] OriginalArrayOfNode = new node[100][200];

//filling original node
for (int n = 0; n < 200; n++) {
     for(int m = 0; m < 100; m++) {
        OriginalArrayOfNode[m][n].head = OriginalArrayOfNode[m][0];
        OriginalArrayOfNode[m][n].left = ...
        //etc
     }
}

node[][]CopyArrayOfNode = new node[100][200];
//The code to copy the original array to new array should be here.

My question is how can i make a deep copy of my the OriginalArrayOfNode to CopyArrayOfNode ? Thanks in advance.

EDIT :

Im trying to make a copy of circular doubly-linked list with 4 pointers for Knuth's Dancing Link Algorithm. It's pretty hard to trace where is the problem, but i assume if the original-array give "x" as a result from Knuth's DL Algorithm, then a correct deep copy of the original-array will also give "x" as a result, provided that there are no other variable change and no random modifier. However, ive tried clone() method, arrayutil.copy() method, and none of them give a "correct" deep copy based on my assumption above.

Answer 1

In my opinion, you're copying this in a very strange way; almost like you're trying to copy the wrong way around.

I'd do it more like this:

for (int m = 0; n < 200; m++) {
     for(int n = 1; n < 100; n++) {
        OriginalArrayOfNode[m][n].head = OriginalArrayOfNode[m][0].head;
        OriginalArrayOfNode[m][n].left = OriginalArrayOfNode[m][0].left;
        //etc
     }
}

Note: You should start n at 1, as you're copying from as you're copying from 0 to the others.

What I would suggest you do however, is add into your class node a clone() method. Clone would then provide an exact copy of the original class.

class node {
    public node head;
    public node left;
    public node right;
    public node up;
    public node down;

    public node clone() {
        final node clonedNode = new node();
        node.head = this.head;
        node.left = this.left;
        node.right = this.right;
        node.up = this.up;
        node.down = this.down;
    }
}


for (int n = 1; n < 200; n++) {
    OriginalArrayOfNode[n] = OriginalArrayOfNode[m].clone(); }

That's not the exact code at all, but you get what I'm meaning.

Finally, another thing to note is that if you're trying to deep copy in the way you're doing, you could easily just populate from index 1 - 200 using ArrayUtil.copy(...).

Hope all this helps.

Answer 2

I presume the OriginalArrayOfNode contains nodes that refer to other nodes in the same array? You're not going to be able to do a deep copy in that case, unless you beef up the node data structure to contain its own 2d index. For example, if OriginalArrayOfNode[0][0].right happens to refer to OriginalArrayOfNode[15][27], you won't be able to figure out that you need to do a deep copy of index [15][27] from the old array to the new before assigning the result to CopyArrayOfNode[0][0].right unless you search the old array exhaustively using object identity.

Even if you could stomach doing that brute force search for all nodes, or you could modify the node data structure to contain its own index, there will also likely be cycles formed by following these links around, greatly complicating any attempt to determine the correct order to copy things. If you can guarantee that there is a certain chain of links to follow that won't cause a cycle, and you can efficiently determine the 2d index of every node, you might have a chance.