In the previous post, I have explained how delete_node works. Now, I am going to explain clone_node command. First let’s see picture of this operation.

A snapshot of tree model data before and after executing clone_node(P5)
A snapshot of tree model data before and after executing clone_node(P5)

Please note: we are continuing to modify outline from the previous post, but positions are renumbered. In the previous post after deleting node at the position P5, new position at index 5 becomes position that used to be at index 12 (P12). However, every time we are generating picture, positions are renumbered so that we can more easily see what is changing. Actual values of positions are persistent but their labels on diagrams are not, and that is intentional.

Method clone_node

This operation makes clone of the node at the given position and places new cloned node just after this one. Here is the definition of clone_node(pos) method.

Nothing special here. Lines 5-16 are collecting necessary data about the node we are cloning and its parent.

In lines 19-20 we are calcualting relative distance of this node from its parent.

After updating size of all ancestors (line 22), we have a for loop (lines 23-28), that iterates through each occurrence of the parent node, and for each occurrence we are just inserting cloned block of data. Inserted positions are newly generated, gnxes and levels are just copied.

And finally in line 30 we add one more link to parent node. At the end (line 31) we are just updating list of children in parent node.

Method indent_node

A snapshot of tree model data before and after executing indent_node(P9)
A snapshot of tree model data before and after executing indent_node(P9)

The example outline is slightly changed to illustrate some special cases that we must handle proprely when idnenting node. Here is the definition of method indent_node:

def indent_node(self, pos):
    '''Moves right node at position pos'''
    (positions, nodes, attrs, levels, expanded, marked) = self.data

    # this node
    i = positions.index(pos)
    if levels[i-1] == levels[i] - 1:
        # if there is no previous siblings node
        # can't be moved right
        return
    gnx = nodes[i]
    h, b, mps, chn, sz0 = attrs[gnx]
    lev0 = levels[i]

    # parent node
    pi = parent_index(levels, i)
    pp = positions[i]
    pgnx = nodes[pi]
    psz = attrs[pgnx].size

    chindex = levels[pi:i].count(lev0)
    pdist = i - pi

    # new parent
    npi = prev_sibling_index(levels, pi, i)
    npp = positions[npi]
    npgnx = nodes[npi]

    if npgnx in nodes[i:i+sz0]:
        # can not move node in its own subtree
        return

    # link node to the new parent
    mps[mps.index(pgnx)] = npgnx
    attrs[npgnx].children.append(gnx)

    del attrs[pgnx].children[chindex]

    # indent nodes in all clones of parent node
    done_positions = []
    for pxi in gnx_iter(nodes, pgnx, psz):
        a = pxi + pdist
        b = a + sz0
        done_positions.append(positions[a])
        done_positions.append(positions[pxi+npi-pi])
        levels[a:b] = (x+1 for x in levels[a:b])

    # preserve nodes that are being indented
    ns = nodes[i:i+sz0]
    levs = levels[i:i+sz0]

    # now we need to insert it to the destination parent and update outline
    sz1 = attrs[npgnx].size
    for pxi in gnx_iter(nodes, npgnx, sz1):
        if positions[pxi] not in done_positions:
            a = pxi + sz1
            positions[a:a] = [random.random() for x in levs]
            dl = levels[pxi] + 1 - levs[0]
            levels[a:a] = [x+dl for x in levs]
            nodes[a:a] = ns

    update_size(attrs, pgnx, -sz0)
    update_size(attrs, npgnx, sz0)

First it should be noted that levels in the outline may increase only by one. Any two adjacent items in the levels list (let’s name them a and b) must satisfy one of the following expressions:

a == b
a + 1 == b
b < a

Indenting node requires increasing its level and if it is already greater than the node to the left, then the operation indent_node can’t be performed. In essence this is the case only when we try to indent node that is first among its siblings. In lines 7-10 we check for this condition and return immediately if this is the case.

Lines 11-27 are collecting necessary data about this node, its parent and its new parent. What is new here is in line 21 calculating the index of this node among its siblings. We count how many nodes have the same level as this node starting from the parent index plus one. We have already checked that this node is not the first one. Then with all data collected we check once again that this operation is legal and no node will become part of its own subtree (lines 29-31).

In lines 33-37 we change links as required for this operation.

In the loop (lines 39-46) we process all occurrences of our old parent node. In all this occurrences all nodes are already there, and we only need to increase levels in the block that is at the distance pdist. We also gather all positions that are processed, so that we don’t process them again in the next phase. In our example outline we would have here processed positions P7 and P18, but not P4.

Now we have to insert indented subtree to every other occurrence of our new parent node (position P4). Lines 52-60 process all these remaining occurrences by inserting indented subtree at level one greater than the new parent level (lines 58-59). We need to allocate new positions for these inserted nodes (line 57).

At the end we need to update sizes of both old and new parent node and all their ancestors (lines 62-63).

In the next post you can find description of the other tree operations.