In the previous part I wrote about functions for loading LeoTreeModel from xml files as well as loading external files. Now, that we have loaded outline let’s add some functions for moving nodes around.

Selecting nodes

User will need to select node previous, next, left, right. LeoTreeModel has field selectedPosition which contains position currently selected (an implementation detail - position is currently an ordinary python float). This value (position) frequently need to be converted to index, so we’ll have selectedIndex property for that purpose.

@property
def selectedIndex(self):
    try:
        i = self.positions.index(self.selectedPosition)
    except ValueError:
        i = -1
    return i

Here is select_next_node method:

def select_next_node(self, ev=None):
    i = self.selectedIndex
    if i < 0: i = 1
    if self.selectedPosition in self.expanded:
        i += 1
    else:
        i += self.attrs[self.nodes[i]][4]
    if i < len(self.positions):
        self.selectedPosition = self.positions[i]
        return self.nodes[i]

We can assume that selected node is already visible which means all of its ancestors are expanded. That means the node after tree of currently selected node must be also visible. If selected node has children and is expanded, then next node at the selectedIndex + 1. If it is collapsed, then the next node is node after tree.

For selecting previous node we have some more work to do.

def select_prev_node(self, ev=None):
    i = self.selectedIndex
    if i < 0: i = 1
    j = j0 = 1
    while j < i:
        j0 = j
        if self.positions[j] in self.expanded:
            j += 1
        else:
            j += self.attrs[self.nodes[j]][4]
    self.selectedPosition = self.positions[j0]
    return self.nodes[j0]

First we need to traverse all visible nodes and find last one whose index is less then currently selected index. This may seem inefficient but it won’t be too hard to use some kind of caching if necessary.

Selecting node to the left means select parent, or collapse this node. If this node is top level node, select previous top level node.

def select_node_left(self, ev=None):
    '''If currently selected node is collapsed or has no
       children selects parent node. If it is expanded and
       has children collapses selected node'''
    if self.selectedPosition in self.expanded:
        self.expanded.remove(self.selectedPosition)
        return
    i = self.selectedIndex
    if i < 2:return
    p = self.parPos[i]
    if p == self.positions[0]:
        # this is top level node
        # let's find previous top level (level=1) node.
        j = next(x for x in range(i - 1, 0, -1) if self.levels[x] == 1)
        p = self.positions[j]

    self.selectedPosition = p
    return self.nodes[self.positions.index(p)]

Selecting node to the right means expanding currently selected node and selecting its first child if it has children. If this node is without children, select next node.

def select_node_right(self, ev=None):
    '''If currently selected node is collapsed, expands it.
       In any case selects next node.'''
    i = self.selectedIndex
    if -1 < i < len(self.nodes) - 1:
        hasChildren = self.levels[i] < self.levels[i + 1]
        p = self.selectedPosition
        if hasChildren and p not in self.expanded:
            self.expanded.add(p)
        self.selectedPosition = self.positions[i + 1]
        return self.nodes[i + 1]

Selecting nodes is not very difficult. All that is required is some basic integer arithmetic. Modifying outline by moving nodes around is much more challenging, especially taking proper care about clones. But it still requires only basic integer arithmetic and some list manipulations.

Moving nodes

The first method I wrote in this category was promote. It turns all of its following siblings into children. After writing several other outline manipulation methods, I think this method can be improved, but let’s see what its first implementation looks like.

def promote(self, pos):
    '''Makes following siblings of pos, children of pos'''
    ( positions, nodes, attrs, levels, gnx2pos, parPos,
      expanded, marked, selPos) = self.ivars()
    # node at position pos
    i = positions.index(pos)
    gnx = nodes[i]
    lev0 = levels[i]

    # parent node
    pp = parPos[i]
    pi = positions.index(pp)
    pgnx = nodes[pi]
    psz = attrs[pgnx][4]

    # index of node after tree
    after = pi + psz

    # remember originial size
    oldsize = attrs[gnx][4]
    A = i + oldsize

    # check danger clones
    if gnx in nodes[A:after]:
        print('warning node can not be in its own subtree')
        return

    # adjust size of this node
    attrs[gnx][4] = oldsize + after - A
    @others

    # finally to show indented nodes
    expanded.add(pos)

This is just a preparation of necessary data and also we check to see if this operation is legal. If node at position pos has clone among following siblings or their subtrees this operation would make node self descendant which must not happen.

In children of this method definition operation is divided in smaller phases like this:

1. promote this part of outline
2. update clones of this node throughout the outline
3. update node sizes in outline

j = A # iterator of following siblings
while j < after:
    cgnx = nodes[j]
    parPos[j] = pos
    h, b, ps, chn, sz = attrs[cgnx]

    # let's replace pgnx with gnx in parents
    ps[ps.index(pgnx)] = gnx

    # append to children of this node
    attrs[gnx][3].append(cgnx)

    # remove from children of pgnx
    attrs[pgnx][3].remove(cgnx)

    # next sibling
    j += sz

levels[A:after] = [x + 1 for x in levels[A:after]]

In this part of the outline we don’t need to insert nor to delete any element in lists. All that is necessary is to handle links between parent node and children and to set parPos elements to point to this node as parent position. Also we need to increase levels of all following sibling nodes and their subtrees.

When we have finished promoting node in this part of outline, we need to adjust any other clone in the outline. Here we have to consider possibility that this node is cloned somewhere else in the outline under different parent. If there are such clones we have to insert new nodes in the outline to make all clones look identically as this one instance.

# we need to insert the same nodes to
# outline after each clone in the outline
allpos = [x for x in gnx2pos[gnx] if x != pos]
if not allpos: return expanded.add(pos)

# prepare data for insertion
sibgnx = nodes[A:after]
siblev = [x-lev0  for x in levels[A:after]]

# for parPosIter we need level 0
levs = [0] + siblev

while allpos:
    ipos = allpos.pop()
    ii = positions.index(ipos)

    # old index of after tree
    jj = ii + oldsize

    # insert in nodes
    nodes[jj:jj] = sibgnx

    # insert levels adjusted by level of this clone
    lev1 = levels[ii]
    levels[jj:jj] = [x + lev1 for x in siblev]

    # we need new positions for inserted nodes
    npos = [random.random() for x in siblev]
    positions[jj:jj] = npos

    # insert parPos
    npos.insert(0, ipos)
    ppos = list(parPosIter(npos, levs))
    parPos[jj:jj] = ppos[1:]

    # update gnx2pos for each new position
    for p1,x in zip(npos[1:], sibgnx):
        gnx2pos[x].append(p1)

Finally, in the third phase, sizes of all other parent nodes are updated.

def updateSize(x):
    d = attrs[x]
    d[4] += after - A
    for x1 in d[2]:
        updateSize(x1)
allparents = attrs[gnx][2][:]
allparents.remove(pgnx) # for one of them we have already updated size
for x in allparents:
    updateSize(x)