To provide heterogeneous tree structures, where a node can be any structure known to the Foundation memory manager.

• §1. Trees and nodes
• §6. Types
• §10. Hierarchy
• §13. Traversals

§1. Trees and nodes. The tree itself is really just a root node, which is initially null, so that a tree can be empty.

typedef struct heterogeneous_tree {
    struct tree_type *type;
    struct tree_node *root;
    CLASS_DEFINITION
} heterogeneous_tree;

• The structure heterogeneous_tree is accessed in 5/mrk, 5/mpi, 5/mpi2, 5/mr, 5/mv, 5/im and here.

§2.

heterogeneous_tree *Trees::new(tree_type *type) {
    heterogeneous_tree *T = CREATE(heterogeneous_tree);
    T->type = type;
    T->root = NULL;
    return T;
}

§3.

typedef struct tree_node {
    struct heterogeneous_tree *owner;
    struct tree_node_type *type;
    struct general_pointer content;
    struct tree_node *next;
    struct tree_node *parent;
    struct tree_node *child;
    CLASS_DEFINITION
} tree_node;

• The structure tree_node is accessed in 2/mmr, 4/taa, 5/mrk, 5/mpi, 5/mpi2, 5/mr, 5/mv, 5/im, 9/pl and here.

§4. A node is created in limbo, removed from its tree, but it is still somehow owned by it.

tree_node *Trees::new_node?Usage of Trees::new_node:
§5(heterogeneous_tree *T, tree_node_type *type, general_pointer wrapping) {
    if (T == NULL) internal_error("no tree");
    if (wrapping.run_time_type_code == -1)
        internal_error("no reference given");
    if (type->required_CLASS >= 0)
        if (wrapping.run_time_type_code != type->required_CLASS)
            internal_error("wrong reference type");

    tree_node *N = CREATE(tree_node);
    N->content = wrapping;
    N->owner = T;
    N->type = type;
    N->parent = NULL;
    N->child = NULL;
    N->next = NULL;
    return N;
}

§5. A convenient abbreviation for a common manoeuvre:

tree_node *Trees::new_child(tree_node *of, tree_node_type *type, general_pointer wrapping) {
    tree_node *N = Trees::new_node(of->owner, type, wrapping);
    Trees::make_child(N, of);
    return N;
}

§6. Types. The above will provide for multiple different types of tree to be used for different purposes. Heterogeneous trees allow the coder to make dangerously type-unsafe structures, so we want to hedge them in with self-imposed constraints:

typedef struct tree_type {
    struct text_stream *name;
    int (*verify_root)(struct tree_node *);  function to vet the root node
    CLASS_DEFINITION
} tree_type;

• The structure tree_type is accessed in 4/prp, 4/jsn, 5/mrk, 5/mv, 5/im, 7/ld and here.

§7.

tree_type *Trees::new_type(text_stream *name, int (*verifier)(tree_node *)) {
    tree_type *T = CREATE(tree_type);
    T->name = Str::duplicate(name);
    T->verify_root = verifier;
    return T;
}

§8. Each node in a tree also has a type. Whenever the children of a node change, they are re-verified by the verify_children.

typedef struct tree_node_type {
    struct text_stream *node_type_name;  text such as I"INVOCATION"
    int required_CLASS;  if any; or negative for no restriction
    int (*verify_children)(struct tree_node *);  function to vet the children
    CLASS_DEFINITION
} tree_node_type;

• The structure tree_node_type is private to this section.

§9.

tree_node_type *Trees::new_node_type(text_stream *name, int req,
    int (*verifier)(tree_node *)) {
    tree_node_type *NT = CREATE(tree_node_type);
    NT->node_type_name = Str::duplicate(name);
    NT->required_CLASS = req;
    NT->verify_children = verifier;
    return NT;
}

§10. Hierarchy. A special function is needed to choose the root node; and note that this is verified.

void Trees::make_root(heterogeneous_tree *T, tree_node *N) {
    if (T == NULL) internal_error("no tree");
    if (N == NULL) internal_error("no node");
    N->owner = T;
    T->root = N;
    N->parent = NULL;
    N->next = NULL;
    if (T->type->verify_root)
        if ((*(T->type->verify_root))(N) == FALSE)
            internal_error("disallowed node as root");
}

void Trees::remove_root?Usage of Trees::remove_root:
§11, §12(heterogeneous_tree *T) {
    if (T == NULL) internal_error("no tree");
    T->root = NULL;
}

§11. Otherwise, nodes are placed in a tree with respect to other nodes:

void Trees::make_child?Usage of Trees::make_child:
§5(tree_node *N, tree_node *of) {
    if (N == NULL) internal_error("no node");
    if (of == NULL) internal_error("no node");
    if (N == N->owner->root) Trees::remove_root(N->owner);
    N->owner = of->owner;
    N->parent = of;
    N->next = NULL;
    if (of->child == NULL)
        of->child = N;
    else
        for (tree_node *S = of->child; S; S = S->next)
            if (S->next == NULL) {
                S->next = N; break;
            }
    Trees::verify_children(of);
}

void Trees::make_eldest_child(tree_node *N, tree_node *of) {
    if (N == NULL) internal_error("no node");
    if (of == NULL) internal_error("no node");
    if (N == N->owner->root) Trees::remove_root(N->owner);
    N->owner = of->owner;
    N->parent = of;
    N->next = of->child;
    of->child = N;
    Trees::verify_children(of);
}

void Trees::make_sibling(tree_node *N, tree_node *of) {
    if (N == NULL) internal_error("no node");
    if (of == NULL) internal_error("no node");
    if (N == N->owner->root) Trees::remove_root(N->owner);
    if (of == of->owner->root)
        internal_error("nodes cannot be siblings of the root");
    N->owner = of->owner;
    N->parent = of->parent;
    N->next = of->next;
    of->next = N;
    if (of->parent) Trees::verify_children(of->parent);
}

§12. Removing a node from a tree does not change its ownership — it still belongs to that tree.

void Trees::remove?Usage of Trees::remove:
§14(tree_node *N) {
    if (N == NULL) internal_error("no node");
    if (N == N->owner->root) { Trees::remove_root(N->owner); return; }
    tree_node *p = N->parent;
    if (N->parent->child == N)
        N->parent->child = N->next;
    else
        for (tree_node *S = N->parent->child; S; S = S->next)
            if (S->next == N)
                S->next = N->next;
    N->parent = NULL;
    N->next = NULL;
    if (p) Trees::verify_children(p);
}

int Trees::verify_children?Usage of Trees::verify_children:
§11(tree_node *N) {
    if (N == NULL) internal_error("no node");
    if (N->type->verify_children)
        return (*(N->type->verify_children))(N);
    return TRUE;
}

§13. Traversals. These two functions allow us to traverse the tree, visiting each node along the way and carrying a state as we do. The distinction is that Trees::traverse_from iterates from and then below the given node, but doesn't go through its siblings, whereas Trees::traverse does.

Note that it is legal to traverse the empty node, and does nothing.

void Trees::traverse_tree(heterogeneous_tree *T,
    int (*visitor)(tree_node *, void *, int L), void *state) {
    if (T == NULL) internal_error("no tree");
    Trees::traverse_from(T->root, visitor, state, 0);
}

void Trees::traverse_from(tree_node *N,
    int (*visitor)(tree_node *, void *, int L), void *state, int L) {
    if (N)
        if ((*visitor)(N, state, L))
            Trees::traverse(N->child, visitor, state, L+1);
}

void Trees::traverse(tree_node *N,
    int (*visitor)(tree_node *, void *, int L), void *state, int L) {
    for (tree_node *M = N; M; M = M->next)
        if ((*visitor)(M, state, L))
            Trees::traverse(M->child, visitor, state, L+1);
}

§14.

void Trees::prune_tree(heterogeneous_tree *T,
    int (*visitor)(tree_node *, void *), void *state) {
    if (T == NULL) internal_error("no tree");
    Trees::prune_from(T->root, visitor, state);
}

void Trees::prune_from(tree_node *N,
    int (*visitor)(tree_node *, void *), void *state) {
    if (N) {
        if ((*visitor)(N, state))
            Trees::remove(N);
        else
            Trees::prune(N->child, visitor, state);
    }
}

void Trees::prune(tree_node *N,
    int (*visitor)(tree_node *, void *), void *state) {
    for (tree_node *M = N, *next_M = N?(N->next):NULL; M; M = next_M, next_M = M?(M->next):NULL)
        if ((*visitor)(M, state))
            Trees::remove(M);
        else
            Trees::prune(M->child, visitor, state);
}