Deep Cloning A Connected Graph Of Objects in C#

While this task can be straightforward for simple objects, it can become more challenging when dealing with intricate, interconnected structures.

What is a Deep Copy?

Before diving into the solution, let's clarify what we mean by "deep copy" or "deep clone." A shallow copy is the default form of copying, where only the top-level object is duplicated. In C#, this is typically done via the ICloneable interface.

For instance, if you have an object A that references another object B, a shallow copy of A would create a new object A1, but it would still reference the same B. On the other hand, a deep copy would create both a new object A1 and a new object B1, where B1 is a duplicate of B.

While a deep copy may seem simple in the case of one or two objects, the complexity increases when working with a large graph of interconnected objects.

The Object Dictionary Pattern

To efficiently handle deep copying in complex object graphs, we can use an object dictionary. The concept behind this is straightforward: as we traverse the graph and make copies, we maintain a dictionary where the keys represent the original objects, and the values store their corresponding deep copies.

Here's how the process works:

1. We start the copy process and check if an object already exists in the dictionary.
2. If the object has already been copied, we reuse the reference to the existing copy.
3. If the object has not been copied yet, we create a new copy and store it in the dictionary.

DeepCloneable Class in Action

The core of this pattern is the DeepCloneable abstract class, which provides the foundation for deep cloning. Here’s the implementation of DeepCloneable:

public abstract class DeepCloneable
{
    protected DeepCloneable() { }

    protected DeepCloneable(DeepCloneable srcObj, 
        IDictionary<DeepCloneable, DeepCloneable> mapDict)
    {
        mapDict[srcObj] = this;
    }

    public DeepCloneable DeepClone()
    {
        return DeepClone(new Dictionary<DeepCloneable, DeepCloneable>());
    }

    protected DeepCloneable DeepClone(
        IDictionary<DeepCloneable, DeepCloneable> mapDict)
    {
        if (mapDict == null)
            throw new ArgumentException("mapDict");

        return mapDict.ContainsKey(this) ? mapDict[this] : DeepCloneHelper(mapDict);
    }

    // Abstract method to be overridden by derived classes
    protected abstract DeepCloneable DeepCloneHelper(
        IDictionary<DeepCloneable, DeepCloneable> mapDict);
}

Implementing Deep Cloning for Custom Classes

To implement deep cloning for custom classes, you would inherit from DeepCloneable and override the DeepCloneHelper method.

Next, We’ll create a class Book that has a list of authors, which should also be cloned.

public class Author : DeepCloneable
{
    public string Name { get; set; }

    public Author(string name)
    {
        Name = name;
    }

    private Author(Author srcObj, IDictionary<DeepCloneable, DeepCloneable> mapDict)
        : base(srcObj, mapDict) { }

    protected override DeepCloneable DeepCloneHelper(IDictionary<DeepCloneable, DeepCloneable> mapDict)
    {
        return new Author(this, mapDict);
    }
}

In this example, the DeepCloneHelper method simply creates a new instance of MyCloneableObj, passing in the source object and the dictionary to manage references.

Handling More Complex Data

Let’s look at a more complex example where the class has additional data that needs to be copied, such as references to other objects:

public class Book : DeepCloneable
{
    public string Title { get; set; }
    private List<Author> _Authors = new List<Author>();

    public Book(string title)
    {
        Title = title;
    }

    private Book(Book srcObj, IDictionary<DeepCloneable, DeepCloneable> mapDict)
        : base(srcObj, mapDict)
    {
        Title = srcObj.Title;
        foreach (Author author in srcObj._Authors)
        {
            _Authors.Add(author.DeepClone(mapDict) as Author);
        }
    }

    public void AddAuthor(Author author)
    {
        _Authors.Add(author);
    }

    public IEnumerable<Author> Authors => _Authors;

    protected override DeepCloneable DeepCloneHelper(IDictionary<DeepCloneable, DeepCloneable> mapDict)
    {
        return new Book(this, mapDict);
    }
}

In this case, Book contains a list of references to other Author objects. During deep cloning, we recursively call DeepClone on each of these references, ensuring that they are properly copied.

Building and Cloning a Book Collection

Let’s now create a few Book objects and clone them using our deep copy mechanism.

private Book CreateBookCollection()
{
    Author author1 = new Author("J.K. Rowling");
    Author author2 = new Author("George R.R. Martin");

    Book book1 = new Book("Harry Potter and the Sorcerer's Stone");
    book1.AddAuthor(author1);

    Book book2 = new Book("Game of Thrones");
    book2.AddAuthor(author2);

    Book book3 = new Book("Harry Potter and the Chamber of Secrets");
    book3.AddAuthor(author1);

    // The books have references to the authors, so they should be copied too.

    return book1; // Return the first book in the collection
}

private void CloneBooks()
{
    Book originalBook = CreateBookCollection();
    Book clonedBook = originalBook.DeepClone() as Book;
}

Here, the CreateBookCollection() method sets up a collection of books, where each book has references to Author objects. When we clone originalBook using the DeepClone() method, the entire book collection is copied, and all author references are also duplicated.

How Deep Cloning Works

When DeepClone() is called on originalBook, the following steps happen:

1. A new dictionary is created to track copies of objects.
2. The cloning process starts by calling DeepCloneHelper() on originalBook, which creates a new Book and adds it to the dictionary.
3. The method then loops through each author in the _Authors list and calls DeepClone() on each author. Since the authors are already added to the dictionary, the cloning process ensures that existing copies are reused.

This results in a deep copy of originalBook, where all its references both the Book and Author objectsare independently copied.

Deep copying complex data structures can be challenging, but using an object dictionary pattern simplifies the process. By ensuring that objects are only copied once and that all references are correctly duplicated, we avoid errors and inefficient copying.