Moving nodes in a tree, adding them to a tree, removing them from a tree.

• §4. Level correction

§1. Each node contains pointers to its previous and next child of the same parent; to its parent node; and to its first child node. There are many implied invariants in that arrangement (e.g., that if X has a child then the parent of that child is X), and it would be eaxy to get all this wrong.

All modifications of the links between nodes must therefore be made by one of only three functions:

• ● NodePlacement::remove(C) removes the node C from the tree.
• ● NodePlacement::move_to(C, IBM) moves the node C to the position bookmarked by IBM. C can but need not already be in the tree.
• ● NodePlacement::move_to_moving_bookmark(C, IBM) moves the node F to the position bookmarked by IBM, but also adjusts IBM to be the natural next write position.

void NodePlacement::remove?Usage of NodePlacement::remove:
Symbols - §16(inter_tree_node *C) {
    Extricate C from its current tree position1.1;
}

void NodePlacement::move_to?Usage of NodePlacement::move_to:
§3(inter_tree_node *C, inter_bookmark IBM) {
    Extricate C from its current tree position1.1;
    switch (IBM.placement_wrt_R) {
        case AS_FIRST_CHILD_OF_NODEPLACEMENT:
            Make C the first child of R1.2;
            break;
        case AS_LAST_CHILD_OF_NODEPLACEMENT:
            Make C the last child of R1.3;
            break;
        case AFTER_NODEPLACEMENT:
        case IMMEDIATELY_AFTER_NODEPLACEMENT:
            Insert C after R1.4;
            break;
        case BEFORE_NODEPLACEMENT:
            Insert C before R1.5;
            break;
        default:
            internal_error("unimplemented");
    }
}

§1.1. Extricate C from its current tree position1.1 =

    inter_tree_node *OP = InterTree::parent(C);
    if (OP) {
        if (InterTree::first_child(OP) == C)
            NodePlacement::set_first_child_UNSAFE(OP, InterTree::next(C));
        if (InterTree::last_child(OP) == C)
            NodePlacement::set_last_child_UNSAFE(OP, InterTree::previous(C));
    }
    inter_tree_node *OB = InterTree::previous(C);
    inter_tree_node *OD = InterTree::next(C);
    if (OB) {
        NodePlacement::set_next_UNSAFE(OB, OD);
    }
    if (OD) {
        NodePlacement::set_previous_UNSAFE(OD, OB);
    }
    NodePlacement::set_parent_UNSAFE(C, NULL);
    NodePlacement::set_previous_UNSAFE(C, NULL);
    NodePlacement::set_next_UNSAFE(C, NULL);

• This code is used in §1 (twice).

§1.2. Make C the first child of R1.2 =

    NodePlacement::set_parent_UNSAFE(C, IBM.R);
    inter_tree_node *D = InterTree::first_child(IBM.R);
    if (D == NULL) {
        NodePlacement::set_last_child_UNSAFE(IBM.R, C);
        NodePlacement::set_next_UNSAFE(C, NULL);
    } else {
        NodePlacement::set_previous_UNSAFE(D, C);
        NodePlacement::set_next_UNSAFE(C, D);
    }
    NodePlacement::set_first_child_UNSAFE(IBM.R, C);

• This code is used in §1.

§1.3. Make C the last child of R1.3 =

    NodePlacement::set_parent_UNSAFE(C, IBM.R);
    inter_tree_node *B = InterTree::last_child(IBM.R);
    if (B == NULL) {
        NodePlacement::set_first_child_UNSAFE(IBM.R, C);
        NodePlacement::set_previous_UNSAFE(C, NULL);
    } else {
        NodePlacement::set_next_UNSAFE(B, C);
        NodePlacement::set_previous_UNSAFE(C, B);
    }
    NodePlacement::set_last_child_UNSAFE(IBM.R, C);

• This code is used in §1.

§1.4. Insert C after R1.4 =

    inter_tree_node *P = InterTree::parent(IBM.R);
    if (P == NULL) internal_error("can't move C before R when R is nowhere");
    NodePlacement::set_parent_UNSAFE(C, P);
    if (InterTree::last_child(P) == IBM.R)
        NodePlacement::set_last_child_UNSAFE(P, C);
    else {
        inter_tree_node *D = InterTree::next(IBM.R);
        if (D == NULL) internal_error("inter tree broken");
        NodePlacement::set_next_UNSAFE(C, D);
        NodePlacement::set_previous_UNSAFE(D, C);
    }
    NodePlacement::set_next_UNSAFE(IBM.R, C);
    NodePlacement::set_previous_UNSAFE(C, IBM.R);

• This code is used in §1.

§1.5. Insert C before R1.5 =

    inter_tree_node *P = InterTree::parent(IBM.R);
    if (P == NULL) internal_error("can't move C before R when R is nowhere");
    NodePlacement::set_parent_UNSAFE(C, P);
    if (InterTree::first_child(P) == IBM.R)
        NodePlacement::set_first_child_UNSAFE(P, C);
    else {
        inter_tree_node *B = InterTree::previous(IBM.R);
        if (B == NULL) internal_error("inter tree broken");
        NodePlacement::set_previous_UNSAFE(C, B);
        NodePlacement::set_next_UNSAFE(B, C);
    }
    NodePlacement::set_next_UNSAFE(C, IBM.R);
    NodePlacement::set_previous_UNSAFE(IBM.R, C);

• This code is used in §1.

§2. The names of these functions are intended to discourage their use. They should only be used by NodePlacement::move_to.

void NodePlacement::set_previous_UNSAFE?Usage of NodePlacement::set_previous_UNSAFE:
§1.1, §1.2, §1.3, §1.4, §1.5(inter_tree_node *C, inter_tree_node *V) {
    if (C) C->previous_itn = V;
}

void NodePlacement::set_next_UNSAFE?Usage of NodePlacement::set_next_UNSAFE:
§1.1, §1.2, §1.3, §1.4, §1.5(inter_tree_node *C, inter_tree_node *V) {
    if (C) C->next_itn = V;
}

void NodePlacement::set_first_child_UNSAFE?Usage of NodePlacement::set_first_child_UNSAFE:
§1.1, §1.2, §1.3, §1.5(inter_tree_node *C, inter_tree_node *V) {
    if (C) C->first_child_itn = V;
}

void NodePlacement::set_last_child_UNSAFE?Usage of NodePlacement::set_last_child_UNSAFE:
§1.1, §1.2, §1.3, §1.4(inter_tree_node *C, inter_tree_node *V) {
    if (C) C->last_child_itn = V;
}

void NodePlacement::set_parent_UNSAFE?Usage of NodePlacement::set_parent_UNSAFE:
§1.1, §1.2, §1.3, §1.4, §1.5(inter_tree_node *C, inter_tree_node *V) {
    if (C) C->parent_itn = V;
}

§3. This is more intricate than NodePlacement::move_to. The differences are basically that:

• ● IBM is considered to be a write position which should move along with each forwards write that is made, as if it's a sort of cursor. By "forwards write", we mean anything other than BEFORE_NODEPLACEMENT; the cursor does not move backwards. So if we call this function to write A, B, C, ... after R, the result is ... R, A, B, C..., the cursor advancing one position each time; and if we call it to write A, B, C, ... before R, the result is ... A, B, C, R, ..., with the cursor staying put at R.
• ● In the two "after" placements, we look at the level assigned to the new node C, which tells us what hierarchical depth it should be at in the tree; if this is a different level from the bookmark's level, the bookmark is moved to that new level.

For example, suppose we have this fragment of tree:

    Level   6...7...8...
    Nodes   node1
                node2
                node3
                    node4   <--- Bookmark is AFTER_NODEPLACEMENT wrt node4
                node5
            node6

If C is to be at level 8, the same level as the bookmark, we get:

    Level   6...7...8...
    Nodes   node1
                node2
                node3
                    node4
                    C       <--- Bookmark is AFTER_NODEPLACEMENT wrt C
                node5
            node6

If instead it is to be at level 6:

    Level   6...7...8...
    Nodes   node1
                node2
                node3
                    node4
                node5
            node6
            C               <--- Bookmark is AFTER_NODEPLACEMENT wrt C

Here, C has "bubbled up" the tree. Finally, if it is to be at level 9:

    Level   6...7...8...
    Nodes   node1
                node2
                node3
                    node4
                        C   <--- Bookmark is AFTER_NODEPLACEMENT wrt C
                node5
            node6

Note that if C is to be at level 10, an internal error is thrown; there is no way to reach as low as that from node4.

void NodePlacement::move_to_moving_bookmark?Usage of NodePlacement::move_to_moving_bookmark:
Transmigration - §3.4, §4.1.1, §4.2.1.1
Inter in Binary Files - §10.1.5
The Comment Construct - §2
The Constant Construct - §2, §4
The Insert Construct - §2
The Instance Construct - §2
The Nop Construct - §2
The Origin Construct - §2
The Package Construct - §4
The PackageType Construct - §2
The Permission Construct - §2
The Pragma Construct - §2
The Primitive Construct - §2
The Property Construct - §2
The PropertyValue Construct - §2
The Provenance Construct - §2
The Typename Construct - §2
The Variable Construct - §2
The Assembly Construct - §2
The Cast Construct - §2
The Code Construct - §2
The Evaluation Construct - §2
The Inv Construct - §3
The Lab Construct - §2
The Label Construct - §2
The Local Construct - §2
The Ref Construct - §2
The Reference Construct - §2
The Splat Construct - §2
The Val Construct - §2(inter_tree_node *C, inter_bookmark *IBM) {
    if (C == NULL) internal_error("no node to insert");
    if (IBM == NULL) internal_error("nowhere to insert");
    NodePlacement::move_to(C, NodePlacement::to_position(C, InterBookmark::snapshot(IBM)));
    if (IBM->placement_wrt_R != BEFORE_NODEPLACEMENT) {
        IBM->R = C;
        IBM->placement_wrt_R = AFTER_NODEPLACEMENT;
    }
}

inter_bookmark NodePlacement::to_position(inter_tree_node *C, inter_bookmark IBM) {
    if (InterTree::parent(IBM.R) == NULL)
        return InterBookmark::at_end_of_root(InterBookmark::tree(&IBM));

    if ((IBM.placement_wrt_R == AFTER_NODEPLACEMENT) ||
        (IBM.placement_wrt_R == IMMEDIATELY_AFTER_NODEPLACEMENT))
        Nodes placed after may need to bubble up or down3.1

    return IBM;
}

§3.1. Nodes placed after may need to bubble up or down3.1 =

    inter_tree_node *R = IBM.R;
    inter_ti C_level = (inter_ti) Inode::get_level(C);
    inter_ti R_level = (inter_ti) Inode::get_level(R);
    while (C_level < R_level) {
        R = InterTree::parent(R);
        R_level--;
        if (R == NULL) internal_error("bubbled up out of tree");
    }
    if (C_level == R_level) {
        return InterBookmark::after_this_node(R);
    } else if (C_level == R_level + 1) {
        if (IBM.placement_wrt_R == IMMEDIATELY_AFTER_NODEPLACEMENT)
            return InterBookmark::first_child_of(R);
        else
            return InterBookmark::last_child_of(R);
    } else {
        WRITE_TO(STDERR, "C level: %d, R level: %d\n", C_level, R_level);
        InterErrors::backtrace(STDERR, R);
        internal_error("bubbled down off of tree");  see above for why
    }

• This code is used in §3.

§4. Level correction. When material is moved around in code optimisation, the level markers on the nodes (which cache the tree depth) can become incorrect. So:

void NodePlacement::set_levels(inter_tree_node *P, int L) {
    Inode::set_level(P, L);
    LOOP_THROUGH_INTER_CHILDREN(C, P)
        NodePlacement::set_levels(C, L+1);
}