============================= Django MPTT Development Notes ============================= This document contains notes related to use cases/reasoning behind and implementation details for Django MPTT features. I've not worked with this particular kind of hierarchical data structure before to any degree of complexity, so you can consider this my "working out" :) Reparenting ----------- Since it's not unreasonable to assume a good percentage of the people who use this application will also be using the ``django.contrib.admin`` application or ``forms.ModelForm`` to edit their data, and since in these cases only the parent field will be editable if users have allowed ``mptt.register`` to create tree fields for them, it would be nice if Django MPTT automatically took care of the tree when a ``Model`` instance has its parent changed. When the parent of a tree node is changed, its left, right, level and tree id may also be updated to keep the integrity of the tree structure intact. In this case, we'll assume the node which was changed should become the last child of its parent. The following diagram depicts a representation of a nested set which we'll base some basic reparenting examples on - hopefully, by observing the resulting tree structures, we can come up with algorithms for different reparenting scenarios:: __________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________| Extract Root Node (Remove Parent) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ If the node's previous parent was not ``None`` and the node's new parent is ``None``, we need to make it into a new root. For example, were we to change Child 1.2's parent to ``None``, we should end up with the following structure:: ______________________________________ | Root 1 | | ________________________________ | | | Child 1.1 | | | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | 1 2 3___________4 5___________6 7 8 | |________________________________| | |______________________________________| ____________________________________ | Root 2 | | _____________ _____________ | | | Child 2.1 | | Child 2.2 | | 1 2_____________3 4_____________5 6 |____________________________________| The following steps should translate an existing node and its descendants into the new format required: 1. The new root node's level will have to become ``0``, and the levels of any descendants will decrease by the same amount, so just subtract the root node's current level from all affected nodes:: new_level = current_level - new_root_node.level 2. The new root node's left value will have to become ``1``. Since the node's number of descendants hasn't changed, we can simply use the node's current left value to adjust all left and right values by the amount required:: new_left = current_left - new_root_node.left + 1 new_right = current_right - new_root_node.left + 1 3. A new tree id will be generated for the new root node, so update the node and all descendants with this value. This can be expressed as a single SQL query:: UPDATE nodes SET level = level - [NODE_LEVEL], left = left - [NODE_LEFT - 1], right = right - [NODE_LEFT - 1], tree_id = [NEW_TREE_ID] WHERE left BETWEEN [NODE_LEFT] AND [NODE_RIGHT] AND tree_id = [CURRENT_TREE_ID] Now we have to fix the original tree, as there's a hole the size of the node we just moved. We can calculate the size of the gap using the node's left and right values, updating the original tree accordingly:: UPDATE nodes SET left = left - [NODE_RIGHT - NODE_LEFT + 1] WHERE left > [NODE_LEFT] AND tree_id = [CURRENT_TREE_ID] UPDATE nodes SET right = right - [NODE_RIGHT - NODE_LEFT + 1] WHERE right > [NODE_RIGHT] AND tree_id = [CURRENT_TREE_ID] Insert Tree (Add Parent) ~~~~~~~~~~~~~~~~~~~~~~~~ If the node's previous parent was ``None`` and the node's new parent is not ``None``, we need to move the entire tree it was the root node for. First, we need to make some space for the tree to be moved into the new parent's tree. This is the same as the process used when creating a new child node, where we add ``2`` to all left and right values which are greater than or equal to the right value of the parent into which the new node will be inserted. In this case, we want to use the width of the tree we'll be inserting, which is ``right - left + 1``. For any node without children, this would be ``2``, which is why we add that amount when creating a new node. This seems like the kind of operation which could be extracted out into a reusable function at some stage. Steps to translate the node and its descendants to the new format required: 1. The node's level (``0``, as it's a root node) will have to become one greater than its new parent's level. We can add this amount to the node and all its descendants to get the correct levels:: new_level = current_level + new_parent.level + 1 2. The node's left value (``1``, as it's a root node) will have to become the current right value of its new parent (look at the diagrams above if this doesn't make sense - imagine inserting Root 2 back into Root 1). Add the difference between the node's left value and the new parent's right value to all left and right values of the node and its descendants:: new_left = current_left + new_parent.right - 1 new_right = current_right + new_parent.right - 1 3. Update the node and all descendants with the tree id of the tree they're moving to. This is a similar query to that used when creating new root nodes from existing child nodes. We can omit the left value from the ``WHERE`` statement in this case, since we'll be operating on a whole tree, but this also looks like something which could be extracted into a reusable function at some stage:: UPDATE nodes SET level = level + [PARENT_LEVEL + 1], left = left + [PARENT_RIGHT - 1], right = right + [PARENT_RIGHT - 1], tree_id = [PARENT_TREE_ID] WHERE tree_id = [CURRENT_TREE_ID] Move Within Tree (Change Parent, Same Tree) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Original Tree:: __________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________| C 1.2.2 -> Root 1:: ____________________________________________________________________________ | Root 1 | | ________________________________ _________________ _____________ | | | Child 1.1 | | Child 1.2 | | Child 1.3 | | | | ___________ ___________ | | ___________ | | | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | | | | 1 2 3___________4 5___________6 7 8 9___________10 11 12 13 14 | |________________________________| |_________________| |_____________| | |____________________________________________________________________________| |________________| | Affected area old_left = 11, new_left = 12 old_right = 12, new_right = 13 left_right_change = 1 target_left = 1, target_right = 14 all other affected lefts and rights decreased by 2 C 1.2.2 -> Child 1.1:: __________________________________________________________________________ | Root 1 | | _______________________________________________ _________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ ___________ | | ___________ | | | | | C 1.1.1 | | C 1.1.2 | | C 1.1.3 | | | | C 1.2.1 | | | 1 2 3___________4 5___________6 7___________8 9 10 11__________12 13 14 | |_______________________________________________| |_________________| | |__________________________________________________________________________| |________________________________| | Affected area old_left = 11, new_left = 7 old_right = 12, new_right = 8 left_right_change = -4 target_left = 2, target_right = 7 all other affected lefts and rights increased by 2 C 1.1.2 -> Root 1:: ____________________________________________________________________________ | Root 1 | | _________________ ________________________________ _____________ | | | Child 1.1 | | Child 1.2 | | Child 1.3 | | | | ___________ | | ___________ ___________ | | | | | | | C 1.1.1 | | | | C 1.2.1 | | C 1.2.2 | | | | | 1 2 3___________4 5 6 7___________8 9___________10 11 12 13 14 | |_________________| |________________________________| |_____________| | |____________________________________________________________________________| |____________________________________________________| | Affected area old_left = 5, new_left = 12 old_right = 6, new_right = 13 left_right_change = 7 target_left = 1, target_right = 14 all other affected lefts and rights decreased by 2 Child 1.2 -> Child 1.1:: ______________________________________________________________________________ | Root 1 | | ________________________________________________________________________ | | | Child 1.1 | | | | ___________ ___________ ____________________________________ | | | | | C 1.1.1 | | C 1.1.2 | | C 1.1.3 | | | | | | | | | | _____________ _____________ | | | | | | | | | | | C 1.1.3.1 | | C 1.1.3.2 | | | | 1 2 3 4 5 6 7 8_____________9 10____________11 12 13 14 | | |___________| |___________| |____________________________________| | | | |________________________________________________________________________| | |______________________________________________________________________________| |_______________________________________| | Affected area old_left = 8, new_left = 7 old_right = 13, new_right = 12 left_right_change = -1 target_left = 2, target_right = 7 all other affected lefts and rights increased by 6 From the diagrams above, the area affected by moving a subtree within the same tree appears to be confined to the section of the tree between the subtree's lower and upper bounds of the subtree's old and new left and right values. Affected nodes which are not in the subtree being moved appear to be changed by the width of the subtree, with a sign inverse to that of the left_right_change. Node Movement ------------- For automatic reparenting, we've been making the node which has had its parent changed the last child of its new parent node but, outside of that, we may want to position a node in other ways relative to a given target node, say to make it the target node's immediate sibling on either side or its first child. Drawing those trees was pretty tedious, so we'll use this kind of tree representation from now on, as seen in the tests. In order, the fields listed are: id, parent_id, tree_id, level, left, right:: 1 - 1 0 1 14 1 2 1 1 1 2 7 2 3 2 1 2 3 4 3 4 2 1 2 5 6 4 5 1 1 1 8 13 5 6 5 1 2 9 10 6 7 5 1 2 11 12 7 Same Tree, Children ~~~~~~~~~~~~~~~~~~~ Last Child Calculation (derived from previous trees):: if target_right > right: new_left = target_right - subtree_width new_right = target_right - 1 else: new_left = target_right new_right = target_right + subtree_width - 1 Moving "up" the tree:: 1 - 1 0 1 14 1 2 1 1 1 2 9 2 7 2 1 2 3 4 => 7 3 2 1 2 5 6 3 4 2 1 2 7 8 4 5 1 1 1 10 13 5 6 5 1 2 11 12 6 node = 7 target_node = 2 left = 11, right = 12 new_left = 3, new_right = 4 target_left = 2, target_right = 7 affected area = 3 to 12 all other affected lefts and rights increased by 2 1 - 1 0 1 14 1 2 1 1 1 2 13 2 5 2 1 2 3 8 => 5 6 5 1 3 4 5 6 7 5 1 3 6 7 7 3 2 1 2 9 10 3 4 2 1 2 11 12 4 node = 5 target_node = 2 left = 8, right = 13 new_left = 3, new_right = 8 target_left = 2, target_right = 7 affected area = 3 to 13 all other affected lefts and rights increased by 6 Moving "down" the tree:: 1 - 1 0 1 14 1 2 1 1 1 2 5 2 3 2 1 2 3 4 3 5 1 1 1 6 13 5 4 5 1 2 7 8 => 4 6 5 1 2 9 10 6 7 5 1 2 11 12 7 node = 4 target_node = 5 left = 5, right = 6 new_left = 7, new_right = 8 target_left = 8, target_right = 13 affected area = 5 to 8 all other affected lefts and rights decreased by 2 1 - 1 0 1 14 1 5 1 1 1 2 13 5 2 5 1 2 3 8 => 2 3 2 1 3 4 5 3 4 2 1 3 6 7 4 6 5 1 2 9 10 6 7 5 1 2 11 12 7 node = 2 target_node = 5 left = 2, right = 9 new_left = 3, new_right = 8 target_left = 8, target_right = 13 affected area = 2 to 8 all other affected lefts and rights decreased by 6 First Child Calculation:: if target_left > left: new_left = target_left - subtree_width + 1 new_right = target_left else: new_left = target_left + 1 new_right = target_left + subtree_width Same Tree, Siblings ~~~~~~~~~~~~~~~~~~~ Moving "up" the tree:: 1 - 1 0 1 14 1 2 1 1 1 2 9 2 3 2 1 2 3 4 3 7 2 1 2 5 6 => 7 4 2 1 2 7 8 4 5 1 1 1 10 13 5 6 5 1 2 11 12 6 Left sibling: node = 7 target_node = 4 left = 11, right = 12 new_left = 5, new_right = 6 target_left = 5, target_right = 6 affected area = 5 to 12 all other affected lefts and rights increased by 2 Right sibling: node = 7 target_node = 3 left = 11, right = 12 new_left = 5, new_right = 6 target_left = 3, target_right = 4 affected area = 3 to 12 all other affected lefts and rights increased by 2 1 - 1 0 1 14 1 2 1 1 1 2 13 2 3 2 1 2 3 4 3 5 2 1 2 5 10 => 5 6 5 1 3 6 7 6 7 5 1 3 8 9 7 4 2 1 2 11 12 4 Left sibling: node = 5 target_node = 4 left = 8, right = 13 new_left = 5, new_right = 10 target_left = 5, target_right = 6 affected area = 5 to 13 all other affected lefts and rights increased by 6 Right sibling: node = 5 target_node = 3 left = 8, right = 13 new_left = 5, new_right = 10 target_left = 3, target_right = 4 affected area = 3 to 13 all other affected lefts and rights increased by 6 Moving "down" the tree:: 1 - 1 0 1 14 1 2 1 1 1 2 5 2 4 2 1 2 3 4 4 5 1 1 1 6 13 5 6 5 1 2 7 8 6 3 5 1 2 9 10 => 3 7 5 1 2 11 12 7 Left sibling: node = 3 target_node = 7 left = 3, right = 4 new_left = 9, new_right = 10 target_left = 11, target_right = 12 affected area = 4 to 10 all other affected lefts and rights decreased by 2 Right sibling: node = 3 target_node = 6 left = 3, right = 4 new_left = 9, new_right = 10 target_left = 9, target_right = 10 affected area = 4 to 10 all other affected lefts and rights decreased by 2 1 - 1 0 1 14 1 5 1 1 1 2 13 5 6 5 1 2 3 4 6 2 6 1 2 5 10 => 2 3 2 1 3 6 7 3 4 2 1 3 8 9 4 7 5 1 2 11 12 7 Left sibling: node = 2 target_node = 7 left = 2, right = 7 new_left = 5, new_right = 10 target_left = 11, target_right = 12 affected area = 2 to 10 all other affected lefts and rights decreased by 6 Right sibling: node = 2 target_node = 6 left = 2, right = 7 new_left = 5, new_right = 10 target_left = 9, target_right = 10 affected area = 2 to 10 all other affected lefts and rights decreased by 6 Derived Calculations:: Left sibling: if target_left > left: new_left = target_left - subtree_width new_right = target_left - 1 else: new_left = target_left new_right = target_left + subtree_width - 1 if target_right > right: new_left = target_right - subtree_width + 1 new_right = target_right else: new_left = target_right + 1 new_right = target_right + subtree_width