Skip to content

plan.md

Latest commit

 

History

History
453 lines (325 loc) · 16.5 KB

plan.md

File metadata and controls

453 lines (325 loc) · 16.5 KB

To wrap this up, here are the finalized instructions for your coding agent. This specification ensures the agent understands not just the how, but the why—ensuring the Treap remains balanced and the Euler Tour remains logically sound.

Specification: Euler Tour Tree (ETT) with Treap BST

1. Rationale and Architecture

We are implementing a TreeNode structure that represents a dynamic tree. The underlying representation is an Euler Tour, stored as a sequence of nodes in a Treap.

  • The Sequence: Every TreeNode has a range in the tour: [EttEnter ... descendants ... EttExit].
  • The Treap: A randomized BST that treats the Euler Tour as a sequence. It provides for Split, Merge, and GetIndex.
  • Self-Contained: Trees are defined by their root EttNode. There is no global "Tree Manager"; subtrees become independent trees as soon as they are split from a parent.

2. Constraints & Data Structure Requirements

  • Generics: Use TreeNode<T> to allow data payloads.
  • Randomized Balancing: Each EttNode must have a random Priority to ensure the Treap remains balanced regardless of insertion order.
  • Implicit Keys: The Treap does not use fixed keys. It uses Subtree Sizes to determine implicit positions in the sequence.

3. Implementation Blueprint

using System;

public class TreeNode<T>
{
    public T Value { get; set; }
    public EttNode EttEnter { get; private set; }
    public EttNode EttExit { get; private set; }

    public TreeNode(T value)
    {
        Value = value;
        // A new node is a sequence of two: [Enter, Exit]
        EttEnter = new EttNode(this);
        EttExit = new EttNode(this);
        EttNode.Merge(EttEnter, EttExit);
    }

    /// <summary>Calculates the 0-based DFS index of this node.</summary>
    public int GetDFSIndex() => EttNode.GetIndex(EttEnter);

    // --- INNER CLASS: ETT NODE (Treap Logic) ---
    public class EttNode
    {
        private static readonly Random _rng = new Random();
        public int Priority { get; } = _rng.Next();
        public int Size { get; private set; } = 1;
        public EttNode Left, Right, Parent;
        public TreeNode<T> Owner { get; }

        public EttNode(TreeNode<T> owner) => Owner = owner;

        public void UpdateSize()
        {
            Size = 1 + (Left?.Size ?? 0) + (Right?.Size ?? 0);
            if (Left != null) Left.Parent = this;
            if (Right != null) Right.Parent = this;
        }

        public static EttNode GetRoot(EttNode node)
        {
            while (node?.Parent != null) node = node.Parent;
            return node;
        }

        public static int GetIndex(EttNode node)
        {
            if (node == null) return -1;
            int index = (node.Left?.Size ?? 0);
            var curr = node;
            while (curr.Parent != null)
            {
                if (curr == curr.Parent.Right)
                    index += (curr.Parent.Left?.Size ?? 0) + 1;
                curr = curr.Parent;
            }
            return index;
        }

        // Standard Treap Merge based on Priority
        public static EttNode Merge(EttNode l, EttNode r)
        {
            if (l == null) return r;
            if (r == null) return l;
            if (l.Priority > r.Priority)
            {
                l.Right = Merge(l.Right, r);
                if (l.Right != null) l.Right.Parent = l;
                l.UpdateSize();
                return l;
            }
            else
            {
                r.Left = Merge(l, r.Left);
                if (r.Left != null) r.Left.Parent = r;
                r.UpdateSize();
                return r;
            }
        }

        // Index-based Split
        public static (EttNode L, EttNode R) Split(EttNode root, int k)
        {
            if (root == null) return (null, null);
            int leftSize = root.Left?.Size ?? 0;
            if (leftSize < k)
            {
                var (l, r) = Split(root.Right, k - leftSize - 1);
                root.Right = l;
                if (l != null) l.Parent = root;
                if (r != null) r.Parent = null;
                root.UpdateSize();
                return (root, r);
            }
            else
            {
                var (l, r) = Split(root.Left, k);
                root.Left = r;
                if (r != null) r.Parent = root;
                if (l != null) l.Parent = null;
                root.UpdateSize();
                return (l, root);
            }
        }
    }

    // --- STATIC TREE MANIPULATION ---

    public static void Remove(TreeNode<T> node)
    {
        EttNode root = EttNode.GetRoot(node.EttEnter);
        int startIdx = EttNode.GetIndex(node.EttEnter);
        int endIdx = EttNode.GetIndex(node.EttExit);
        int count = endIdx - startIdx + 1;

        var (before, temp) = EttNode.Split(root, startIdx);
        var (subtree, after) = EttNode.Split(temp, count);
        EttNode.Merge(before, after);
    }

    public static void InsertFirstChild(TreeNode<T> parent, TreeNode<T> newNode)
    {
        Remove(newNode);
        EttNode root = EttNode.GetRoot(parent.EttEnter);
        int idx = EttNode.GetIndex(parent.EttEnter) + 1;
        var (left, right) = EttNode.Split(root, idx);
        EttNode.Merge(EttNode.Merge(left, EttNode.GetRoot(newNode.EttEnter)), right);
    }

    public static void InsertSiblingAfter(TreeNode<T> target, TreeNode<T> newNode)
    {
        Remove(newNode);
        EttNode root = EttNode.GetRoot(target.EttExit);
        int idx = EttNode.GetIndex(target.EttExit) + 1;
        var (left, right) = EttNode.Split(root, idx);
        EttNode.Merge(EttNode.Merge(left, EttNode.GetRoot(newNode.EttEnter)), right);
    }
}

4. Logic for the Coding Agent

  1. Detach Before Move: In every Insert method, the code must first call Remove(newNode) to ensure the newNode is its own independent Treap before being merged into the new parent.
  2. Parent Pointer Integrity: Ensure the Parent pointers in the Treap are nullified during Split and correctly assigned during Merge. This is critical for GetIndex and GetRoot.
  3. DFS Order: * InsertFirstChild happens at Parent.Enter + 1.
  • InsertLastChild happens at Parent.Exit.
  • InsertSiblingBefore happens at Target.Enter.
  • InsertSiblingAfter happens at Target.Exit + 1.

Specification: Test Suite for Euler Tour Tree (ETT)

The following test suite is designed to verify the correctness of a Treap-based Euler Tour Tree. It focuses on three core areas: structural integrity, relative DFS ordering, and decoupling (ensuring no shared state between disconnected trees).

1. Test Case: Basic Connectivity and Indexing

Scenario: Create a root and three children. Verify their DFS indices match the insertion order.

  • Action: Create root, c1, c2, c3.
  • Action: InsertFirstChild(root, c1), InsertSiblingAfter(c1, c2), InsertSiblingAfter(c2, c3).
  • Expected: * root.GetDFSIndex() < c1.GetDFSIndex()
  • c1.GetDFSIndex() < c2.GetDFSIndex()
  • c2.GetDFSIndex() < c3.GetDFSIndex()
  • All nodes should belong to the same Treap root.

2. Test Case: Subtree Extraction (Remove)

Scenario: Removing a node should also remove its children from the main tree's sequence.

  • Action: Create root -> child -> grandchild.
  • Action: Remove(child).
  • Expected: * root.EttEnter and child.EttEnter have different Treap roots.
  • child.EttEnter and grandchild.EttEnter share the same Treap root.
  • The size of the main tree's Treap should decrease by exactly the size of the child subtree (4 nodes: 2 for child, 2 for grandchild).

3. Test Case: Deep Sibling Insertion

Scenario: Verify that InsertSiblingBefore and InsertSiblingAfter correctly shift the indices of all subsequent nodes in the tour.

  • Action: Create sequence A, B, D.
  • Action: InsertSiblingAfter(B, C).
  • Expected: * The sequence in the Treap must be A_enter...B_exit, C_enter, C_exit, D_enter....
  • GetDFSIndex(D) should increase by 2 after C is inserted.

4. Test Case: Tree Re-parenting (Move)

Scenario: Moving a subtree from one parent to another.

  • Action: Tree 1: R1 -> A. Tree 2: R2 -> B.
  • Action: InsertFirstChild(R2, A).
  • Expected: * A is no longer in R1's Treap.
  • R2's Treap size increases.
  • The DFS order of R2 becomes R2_enter, A_enter, A_exit, B_enter, B_exit, R2_exit.

5. Test Case: Stress Test (Auto-Balancing)

Scenario: Insert 1,000 nodes in a "degenerate" way (e.g., always InsertLastChild).

  • Action: Loop 1,000 times: InsertLastChild(root, new Node).
  • Expected: * The Treap height must be significantly less than 1,000 (ideally ).
  • This verifies that the random Priority is correctly balancing the tree despite a linear insertion pattern.

Implementation Template for Agent (C# / NUnit)

[Test]
public void Test_DFS_Index_Consistency_After_Move()
{
    var root1 = new TreeNode<string>("Root1");
    var root2 = new TreeNode<string>("Root2");
    var nodeA = new TreeNode<string>("A");
    var nodeB = new TreeNode<string>("B");

    // Build Root1 -> A
    TreeNode<string>.InsertFirstChild(root1, nodeA);
    // Build Root2 -> B
    TreeNode<string>.InsertFirstChild(root2, nodeB);

    int initialIndexB = nodeB.GetDFSIndex();

    // Move A to be a sibling after B: Root2 -> B, A
    TreeNode<string>.InsertSiblingAfter(nodeB, nodeA);

    Assert.Multiple(() => {
        // A should now be after B
        Assert.That(nodeA.GetDFSIndex(), Is.GreaterThan(nodeB.GetDFSIndex()));
        // A should be in Root2's treap
        Assert.That(TreeNode<string>.EttNode.GetRoot(nodeA.EttEnter), 
                    Is.EqualTo(TreeNode<string>.EttNode.GetRoot(root2.EttEnter)));
        // Root1 should now be empty (size 2: Enter/Exit)
        Assert.That(TreeNode<string>.EttNode.GetRoot(root1.EttEnter).Size, Is.EqualTo(2));
    });
}

Specification: Edge-Case Test Suite for Euler Tour Tree (ETT)

This suite focuses on "boundary" conditions—operations on single nodes, root-level maneuvers, and empty-to-full transitions. These tests ensure the Treap logic doesn't crash on null references and that the Euler Tour logic maintains integrity at the smallest possible scales.

1. Test Case: The "Lone Node" Operation

Scenario: Verify that a node's EttEnter and EttExit are correctly linked even before it is joined to any tree.

  • Action: Create a single TreeNode.
  • Expected: * node.EttEnter.Size + node.EttExit.Size should be equal to 2.
  • GetIndex(node.EttEnter) should be 0.
  • GetIndex(node.EttExit) should be 1.
  • EttNode.GetRoot(node.EttEnter) should equal EttNode.GetRoot(node.EttExit).

2. Test Case: Circular Sibling Injection (Before/After Start)

Scenario: Inserting a sibling before the first child or after the last child.

  • Action: Create Parent -> [ChildA].
  • Action: InsertSiblingBefore(ChildA, ChildB).
  • Action: InsertSiblingAfter(ChildA, ChildC).
  • Expected: * DFS order must be Parent_Enter, ChildB, ChildA, ChildC, Parent_Exit.
  • GetIndex(ChildB) < GetIndex(ChildA) < GetIndex(ChildC).

3. Test Case: Root-to-Root Merger

Scenario: Merging two standalone nodes (treating one as a sibling of another).

  • Action: Create NodeA and NodeB (both roots).
  • Action: InsertSiblingAfter(NodeA, NodeB).
  • Expected: * Both nodes now share the same Treap root.
  • Total Treap size is 4.
  • GetIndex(NodeB.EttEnter) is 2.

4. Test Case: Subtree Re-Entry (Loop Prevention)

Scenario: Removing a node and then re-inserting it into its own previous parent in a different position.

  • Action: Root -> A -> B.
  • Action: Remove(B).
  • Action: InsertFirstChild(Root, B).
  • Expected: * The tour should be Root_Enter, B_Enter, B_Exit, A_Enter, A_Exit, Root_Exit.
  • Verifies that Remove effectively "cleaned" the Treap pointers so B doesn't drag A along in a way that creates cycles or duplicate nodes.

5. Test Case: Multi-Level Extraction

Scenario: Removing a "middle" node that has both a parent and a child.

  • Action: Root -> Mid -> Leaf.
  • Action: Remove(Mid).
  • Expected: * Root's Treap now has a size of 2 (Root_Enter, Root_Exit).
  • Mid's Treap has a size of 4 (Mid_Enter, Leaf_Enter, Leaf_Exit, Mid_Exit).
  • This confirms that the count calculation in the Remove logic (ExitIdx - EnterIdx + 1) correctly captures the entire nested range.

Implementation Template for Agent (C# / NUnit)

[Test]
public void Test_EdgeCase_RemoveMiddleNodeWithChildren()
{
    var root = new TreeNode<string>("Root");
    var mid = new TreeNode<string>("Mid");
    var leaf = new TreeNode<string>("Leaf");

    // Build Root -> Mid -> Leaf
    TreeNode<string>.InsertFirstChild(root, mid);
    TreeNode<string>.InsertFirstChild(mid, leaf);

    Assert.That(TreeNode<string>.EttNode.GetRoot(root.EttEnter).Size, Is.EqualTo(6));

    // Remove the middle node
    TreeNode<string>.Remove(mid);

    Assert.Multiple(() => {
        // Main tree is now just the root
        Assert.That(TreeNode<string>.EttNode.GetRoot(root.EttEnter).Size, Is.EqualTo(2));
        
        // Detached tree contains Mid and Leaf
        var detachedRoot = TreeNode<string>.EttNode.GetRoot(mid.EttEnter);
        Assert.That(detachedRoot.Size, Is.EqualTo(4));
        
        // Mid and Leaf are still together
        Assert.That(TreeNode<string>.EttNode.GetRoot(leaf.EttEnter), Is.EqualTo(detachedRoot));
    });
}

Specification: Relative Index Comparison Test Suite

This final suite ensures that the GetDFSIndex() method remains a reliable source of truth for "who comes before whom" in a DFS traversal, even as the tree's topology is aggressively modified. These tests are vital for any logic that relies on nodeA.GetDFSIndex() < nodeB.GetDFSIndex() to determine tree order.

1. Test Case: Sibling Swap Consistency

Scenario: Swapping the order of two siblings and verifying the index comparison flips.

  • Action: Create Parent -> [A, B].
  • Verify: A.GetDFSIndex() < B.GetDFSIndex() is true.
  • Action: InsertSiblingAfter(B, A).
  • Verify: A.GetDFSIndex() < B.GetDFSIndex() is now false.

2. Test Case: Ancestor vs. Descendant Indexing

Scenario: In a DFS tour, a parent must always have a lower index than its children.

  • Action: Build a deep chain: A -> B -> C -> D.
  • Verify: A.Idx < B.Idx < C.Idx < D.Idx.
  • Action: Move D to be a child of A (InsertFirstChild(A, D)).
  • Verify: A.Idx < D.Idx < B.Idx < C.Idx. (D now jumps ahead of B).

3. Test Case: Independent Tree Comparison

Scenario: Comparing indices of nodes in two different trees.

  • Action: Create Root1 and Root2.
  • Verify: While they have indices within their own Treaps, comparing them across trees is logically invalid (or should be handled by checking GetRoot()).
  • Action: Merge Root1 as a child of Root2.
  • Verify: Their indices now exist in a shared coordinate space and are comparable.

4. Test Case: Stability During "Last Child" Appending

Scenario: Adding nodes to the end of a long list of siblings should not change the indices of existing siblings.

  • Action: Create Parent with 10 children. Record Child[0].GetDFSIndex().
  • Action: Add Child[11] using InsertLastChild.
  • Verify: Child[0].GetDFSIndex() remains identical. (This confirms that appending to the end of the sequence doesn't shift the "left-count" of nodes at the beginning).

Implementation Template for Agent (C# / NUnit)

[Test]
public void Test_RelativeIndexStability_DuringSwaps()
{
    var root = new TreeNode<string>("Root");
    var a = new TreeNode<string>("A");
    var b = new TreeNode<string>("B");
    var c = new TreeNode<string>("C");

    // Order: Root, A, B, C
    TreeNode<string>.InsertLastChild(root, a);
    TreeNode<string>.InsertLastChild(root, b);
    TreeNode<string>.InsertLastChild(root, c);

    Assert.That(a.GetDFSIndex(), Is.LessThan(b.GetDFSIndex()));
    Assert.That(b.GetDFSIndex(), Is.LessThan(c.GetDFSIndex()));

    // Move C to the front: Root, C, A, B
    TreeNode<string>.InsertFirstChild(root, c);

    Assert.Multiple(() => {
        Assert.That(c.GetDFSIndex(), Is.LessThan(a.GetDFSIndex()), "C should now be first child");
        Assert.That(a.GetDFSIndex(), Is.LessThan(b.GetDFSIndex()), "A and B relative order should be preserved");
        Assert.That(root.GetDFSIndex(), Is.LessThan(c.GetDFSIndex()), "Root must still be before all children");
    });
}