Implementing Deep Copy in Python

Python's built-in copy module provides copy.deepcopy() for creating independent copies of complex objects. This challenge asks you to implement your own deepcopy function, understanding the nuances of copying mutable objects nested within other mutable objects. This exercise will deepen your understanding of object identity, mutability, and recursion in Python.

Problem Description

Your task is to create a Python function named my_deepcopy that mimics the behavior of copy.deepcopy(). This function should take a single argument, obj, which can be any Python object. It should return a new object that is a deep copy of the original.

A deep copy means that not only the top-level object is copied, but also any mutable objects (like lists, dictionaries, sets) nested within it are also copied recursively. Changes to the deep copy should not affect the original object, and vice-versa.

Key Requirements:

• The function must handle basic immutable types (integers, floats, strings, booleans, None) by returning them directly.
• It must correctly copy mutable types like lists, dictionaries, and sets.
• It must handle nested mutable structures. For example, a list containing dictionaries, or a dictionary containing lists.
• It must correctly handle circular references. If an object contains a reference to itself (directly or indirectly), your my_deepcopy should not enter an infinite recursion.

Expected Behavior:

• For immutable types, the returned object should be identical to the original (e.g., id(original) == id(copy) is acceptable for immutables, but it's more about the value).
• For mutable types, the returned object should be a new object, distinct from the original in memory (e.g., id(original) != id(copy)).
• Changes made to elements or items within the copied mutable objects should not affect the original.

Edge Cases to Consider:

• Empty lists, dictionaries, or sets.
• Objects containing references to other objects that have already been copied (to ensure sharing of shared references where appropriate, and distinct copies when needed).
• Circular references.

Examples

Example 1: Simple List

Input: my_list = [1, 2, 3]
Output: A new list [1, 2, 3] where id(my_list) != id(copied_list)
Explanation: The function should create a new list object with the same elements.

Example 2: Nested List

Input: my_nested_list = [1, [2, 3], 4]
Output: A new list [1, [2, 3], 4] where id(my_nested_list) != id(copied_list) and id(my_nested_list[1]) != id(copied_list[1])
Explanation: Both the outer list and the inner list should be new, independent objects.

Example 3: Dictionary with Mutable Values

Input: my_dict = {"a": [1, 2], "b": {"c": 3}}
Output: A new dictionary {"a": [1, 2], "b": {"c": 3}} where id(my_dict) != id(copied_dict), id(my_dict["a"]) != id(copied_dict["a"]), and id(my_dict["b"]) != id(copied_dict["b"])
Explanation: The dictionary and its nested list and dictionary values should all be copied independently.

Example 4: Circular Reference

Input:
  original_list = [1]
  original_list.append(original_list) # Creates a circular reference
Output:
  A new list that is a deep copy of original_list, including the circular reference.
  The copied list should also have a circular reference, but the inner reference should point to the *copied* outer list, not the original.
  id(original_list) != id(copied_list)
  id(original_list[1]) == id(original_list) # Original self-reference
  id(copied_list[1]) == id(copied_list) # Copied self-reference
Explanation: The function must detect and correctly handle circular references to avoid infinite recursion and ensure that the copied structure mirrors the original's structure, including its self-references.

Constraints

• Your my_deepcopy function should aim to replicate the behavior of copy.deepcopy for common built-in Python types (lists, tuples, dictionaries, sets, and basic immutables).
• You are not expected to handle custom class instances unless they are composed solely of the basic types mentioned above.
• The solution must be implemented in pure Python without importing the copy module itself.
• Performance is a secondary concern to correctness, but avoid demonstrably inefficient recursive patterns that would lead to stack overflows on moderately complex structures.

Notes

• Consider using a dictionary to keep track of objects that have already been copied during the recursion. This dictionary will map original object IDs to their corresponding copied objects, which is crucial for handling shared references and preventing infinite recursion with circular structures.
• Think about how to determine if an object is mutable or immutable.
• Remember that tuples are immutable, but they can contain mutable objects. A deep copy of a tuple should copy the mutable objects inside if they are found.