Simulating a Mark and Sweep Garbage Collector in JavaScript

This challenge asks you to implement a simplified simulation of a mark and sweep garbage collector in JavaScript. Understanding garbage collection is crucial for efficient memory management, especially in dynamic languages like JavaScript. This simulation will help you grasp the core concepts of how a garbage collector identifies and reclaims unused memory.

Problem Description

You are tasked with creating a rudimentary garbage collector that uses the mark and sweep algorithm. The collector will manage a pool of "objects" that can be allocated and deallocated. Your simulation should track object allocation, marking reachable objects, and sweeping (reclaiming) memory occupied by unreachable objects.

What needs to be achieved:

1. Object Allocation: Implement a function to allocate new objects into the memory pool. Each object should have a unique ID and a reference to other objects (simulated by storing IDs).
2. Marking: Implement a function that traverses the object graph starting from a set of "root" objects (objects known to be in use) and marks all reachable objects. Marking can be represented by adding a marked property to each object.
3. Sweeping: Implement a function that iterates through the memory pool and reclaims (removes) any objects that have not been marked. This involves removing the object from the pool and potentially freeing the memory it occupied (in this simulation, simply removing it from the objects array).
4. Root Objects: Maintain a list of "root" objects. These are objects that are considered always in use and should never be collected.

Key Requirements:

• The garbage collector should be able to handle circular references between objects.
• The simulation should accurately identify and reclaim unreachable objects.
• The code should be well-structured and easy to understand.

Expected Behavior:

The garbage collector should correctly identify and remove objects that are no longer reachable from the root objects. The simulation should demonstrate the mark and sweep process.

Edge Cases to Consider:

• Circular references: Objects referencing each other, but not reachable from any root object.
• Empty memory pool: The collector should handle the case where there are no objects to sweep.
• No root objects: The collector should handle the case where there are no root objects.
• Objects referencing themselves.

Examples

Example 1:

Input:
objects = [
  { id: 1, references: [2], marked: false },
  { id: 2, references: [3], marked: false },
  { id: 3, references: [1], marked: false } // Circular reference
];
roots = [1];

Output:
objects = [
  { id: 1, references: [2], marked: true },
  { id: 2, references: [3], marked: true },
  { id: 3, references: [1], marked: true }
]
Explanation: Starting from root 1, objects 1, 2, and 3 are reachable due to the circular reference. All are marked.

Example 2:

Input:
objects = [
  { id: 1, references: [2], marked: false },
  { id: 2, references: [], marked: false },
  { id: 3, references: [4], marked: false },
  { id: 4, references: [], marked: false }
];
roots = [1];

Output:
objects = [
  { id: 1, references: [2], marked: true },
  { id: 2, references: [], marked: true }
]
Explanation: Starting from root 1, object 2 is reachable. Objects 3 and 4 are unreachable and are swept away.

Example 3: (Edge Case - Circular Reference Unreachable)

Input:
objects = [
  { id: 1, references: [2], marked: false },
  { id: 2, references: [1], marked: false }
];
roots = [];

Output:
objects = []
Explanation: There are no root objects. The circular reference between 1 and 2 is unreachable, so both objects are swept.

Constraints

• The number of objects in the memory pool will be between 0 and 100.
• Object IDs will be unique positive integers.
• References will be valid object IDs within the pool.
• The simulation should complete within a reasonable time (e.g., less than 1 second).
• The marked property should be a boolean.

Notes

• You can represent the memory pool as a JavaScript array of objects.
• The mark function should recursively traverse the object graph.
• The sweep function should iterate through the memory pool and remove unmarked objects.
• Focus on the core logic of the mark and sweep algorithm. You don't need to implement a full-fledged memory management system.
• Consider using a separate array to store the root objects.
• Think about how to handle circular references correctly during the marking phase.
• The simulation should be deterministic; given the same input, it should always produce the same output.