addressing general tree

main.d

/+
       0
    /  |  \
   1   2   3
  / \    / | \
 4   5  6  7  8

address(0) = []      // root
address(1) = [0]     // root.children[0]
address(2) = [1]     // etc
address(3) = [2]
address(4) = [0,0]   // root.children[0].children[0]
address(5) = [0,1]   // etc
address(6) = [2,0]
address(7) = [2,1]
address(8) = [2,2]   // root.children[2].children[2]
+/

import std.stdio, std.algorithm.searching;
import std.typecons;

struct Node {
    Node* parent;
    Node*[] children;

    void addChild(Node* c){
        c.parent = &this;
        children ~= c;
    }
}

long[] addressForNode(Node* node) {
    if (!node.parent) return null;
    auto parent = node.parent;
    auto siblings = parent.children;
    auto index = countUntil(siblings, node);
    return addressForNode(parent) ~ [index];
}

Tuple!(Node*, long[]) _nodeWithAddress(Node* tree, long[] address) {
    if (address == null)
        return tuple(tree, address);
    auto last = address[address.length-1];
    address = address[0..address.length-1];
    auto childIndex = last;
    auto childNode = tree.children[childIndex];
    return _nodeWithAddress(childNode, address);
}

Node* nodeWithAddress(Node* tree, long[] address){
    return _nodeWithAddress(tree, address)[0];
}

void main() {
    Node root = Node();

    auto n1 = Node();
    auto n2 = Node();
    auto n3 = Node();

    root.addChild(&n1);
    root.addChild(&n2);
    root.addChild(&n3);

    auto n4 = Node();
    auto n5 = Node();
    auto n6 = Node();
    auto n7 = Node();
    auto n8 = Node();

    n1.addChild(&n4);
    n1.addChild(&n5);
    n3.addChild(&n6);
    n3.addChild(&n7);
    n3.addChild(&n8);

    assert(addressForNode(&n8) == [2, 2]);
    assert(nodeWithAddress(&root, [2, 2]) == &n8);

    assert(addressForNode(&n5) == [0, 1]);
    
}