NOTES

=============================
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 descendents 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 descendents 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