ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

HTML Safe Tree with Rc (Simulated)

HTML

Goal -- WPM

Ready
Exercise Algorithm Area
1<!-- Conceptual Rc (Reference Counting) for Trees in JS -->

2

3<!DOCTYPE html>

4<html>

5<head>

6<title>Rc Tree Concept</title>

7</head>

8<body>

9

10<h1>Simulating Safe Tree Structures with Rc Concept</h1>

11<p>This example demonstrates how multiple parents could potentially reference the same node.</p>

12<div id="output"></div>

13

14<script>

15// In Rust, Rc<T> provides shared ownership with reference counting.

16// JavaScript doesn't have direct Rc, but we can simulate the idea

17// of shared ownership and managing references.

18

19class RcNode {

20constructor(value) {

21this.value = value;

22this.children = []; // Nodes this node points to

23this.parents = [];  // Nodes that point to this node (simulating shared refs)

24this.refCount = 0;  // Simulate reference count

25}

26

27addChild(childNode) {

28if (childNode instanceof RcNode) {

29this.children.push(childNode);

30childNode.parents.push(this);

31childNode.incrementRef();

32}

33}

34

35incrementRef() {

36this.refCount++;

37console.log(`Node ${this.value} refCount: ${this.refCount}`);

38}

39

40decrementRef() {

41this.refCount--;

42console.log(`Node ${this.value} refCount: ${this.refCount}`);

43// In a real Rc, if refCount becomes 0, the node would be deallocated.

44// JavaScript's GC handles this, but we simulate the logic.

45if (this.refCount === 0) {

46console.log(`Node ${this.value} is now eligible for garbage collection.`);

47// In JS, GC happens automatically. We don't explicitly delete.

48}

49}

50

51// Simulate removing a parent reference

52removeParentRef(parentNode) {

53this.parents = this.parents.filter(p => p !== parentNode);

54this.decrementRef();

55}

56}

57

58// --- Simulation Setup ---

59const outputDiv = document.getElementById('output');

60

61// Create nodes

62const rootA = new RcNode('A');

63const nodeB = new RcNode('B');

64const nodeC = new RcNode('C');

65const nodeD = new RcNode('D');

66

67// Scenario 1: Simple tree

68rootA.addChild(nodeB);

69rootA.addChild(nodeC);

70nodeB.addChild(nodeD);

71

72outputDiv.innerHTML += '<p>Scenario 1: Simple Tree Structure</p>';

73outputDiv.innerHTML += `<p>Root A has children: ${rootA.children.map(c => c.value).join(', ')}</p>`;

74outputDiv.innerHTML += `<p>Node B has parent: ${nodeB.parents.map(p => p.value).join(', ')}</p>`;

75outputDiv.innerHTML += `<p>Node D has parent: ${nodeD.parents.map(p => p.value).join(', ')}</p>`;

76outputDiv.innerHTML += `<p>Node D refCount: ${nodeD.refCount}</p>`;

77

78// Scenario 2: Shared node (Diamond structure)

79// Node D is now a child of both B and C

80outputDiv.innerHTML += '<p>Scenario 2: Node D shared by B and C</p>';

81nodeC.addChild(nodeD); // Node D's refCount should increment

82outputDiv.innerHTML += `<p>Node D now has parents: ${nodeD.parents.map(p => p.value).join(', ')}</p>`;

83outputDiv.innerHTML += `<p>Node D refCount: ${nodeD.refCount}</p>`;

84

85// Simulate removing references to demonstrate refCount decrease

86outputDiv.innerHTML += '<p>Simulating reference removal:</p>';

87nodeB.children = nodeB.children.filter(child => child !== nodeD);

88nodeD.removeParentRef(nodeB); // Decrement refCount for D

89outputDiv.innerHTML += `<p>After removing B's reference to D, Node D refCount: ${nodeD.refCount}</p>`;

90

91nodeC.children = nodeC.children.filter(child => child !== nodeD);

92nodeD.removeParentRef(nodeC); // Decrement refCount for D

93outputDiv.innerHTML += `<p>After removing C's reference to D, Node D refCount: ${nodeD.refCount}</p>`;

94

95</script>

96

97</body>

98</html>
Algorithm description viewbox

HTML Safe Tree with Rc (Simulated)

Algorithm description:

This HTML/JavaScript example conceptually simulates how reference counting (like Rust's `Rc<T>`) can manage shared ownership in tree-like structures. It defines an `RcNode` class with a `refCount` property. When a node is added as a child, the child's reference count is incremented. When a reference is removed, the count is decremented, and if it reaches zero, the node is conceptually ready for garbage collection. This pattern prevents memory leaks and allows nodes to be safely shared among multiple parents.

Algorithm explanation:

The `RcNode` class simulates reference counting. Each node has a `value`, `children` (nodes it points to), `parents` (nodes pointing to it), and `refCount`. The `addChild` method adds a child, increments the child's `refCount`, and records the parent. `incrementRef` and `decrementRef` manage the count. When `refCount` reaches zero, the node is considered deallocated (though JavaScript's GC handles actual memory management). This allows for graph-like structures (diamond patterns) where a node can have multiple parents without causing memory leaks, as long as all references are eventually dropped. The time complexity for adding/removing a reference is O(1) on average, assuming efficient array operations. Space complexity is O(N + E), where N is the number of nodes and E is the number of edges (references).

Pseudocode:

1. Define an `RcNode` class with `value`, `children`, `parents`, and `refCount`.
2. Implement `addChild(childNode)`:
    a. Add `childNode` to `this.children`.
    b. Add `this` to `childNode.parents`.
    c. Call `childNode.incrementRef()`.
3. Implement `incrementRef()`: Increase `refCount`.
4. Implement `decrementRef()`: Decrease `refCount`. If 0, log that node is eligible for GC.
5. Implement `removeParentRef(parentNode)`: Remove `parentNode` from `this.parents` and call `this.decrementRef()`.