Mercurial > hg > agora-dellsystem
changeset 42:ab608f27ecd5
Copy preliminary django-paste code for snippets along with mptt. Works clunkily. Still need to adapt it for Agora.
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/apps/mptt/__init__.py @@ -0,0 +1,94 @@ +VERSION = (0, 3, 'pre') + +__all__ = ('register',) + +class AlreadyRegistered(Exception): + """ + An attempt was made to register a model for MPTT more than once. + """ + pass + +registry = [] + +def register(model, parent_attr='parent', left_attr='lft', right_attr='rght', + tree_id_attr='tree_id', level_attr='level', + tree_manager_attr='tree', order_insertion_by=None): + """ + Sets the given model class up for Modified Preorder Tree Traversal. + """ + try: + from functools import wraps + except ImportError: + from django.utils.functional import wraps # Python 2.3, 2.4 fallback + + from django.db.models import signals as model_signals + from django.db.models import FieldDoesNotExist, PositiveIntegerField + from django.utils.translation import ugettext as _ + + from agora.apps.mptt import models + from agora.apps.mptt.signals import pre_save + from agora.apps.mptt.managers import TreeManager + + if model in registry: + raise AlreadyRegistered( + _('The model %s has already been registered.') % model.__name__) + registry.append(model) + + # Add tree options to the model's Options + opts = model._meta + opts.parent_attr = parent_attr + opts.right_attr = right_attr + opts.left_attr = left_attr + opts.tree_id_attr = tree_id_attr + opts.level_attr = level_attr + opts.tree_manager_attr = tree_manager_attr + opts.order_insertion_by = order_insertion_by + + # Add tree fields if they do not exist + for attr in [left_attr, right_attr, tree_id_attr, level_attr]: + try: + opts.get_field(attr) + except FieldDoesNotExist: + PositiveIntegerField( + db_index=True, editable=False).contribute_to_class(model, attr) + + # Add tree methods for model instances + setattr(model, 'get_ancestors', models.get_ancestors) + setattr(model, 'get_children', models.get_children) + setattr(model, 'get_descendants', models.get_descendants) + setattr(model, 'get_descendant_count', models.get_descendant_count) + setattr(model, 'get_next_sibling', models.get_next_sibling) + setattr(model, 'get_previous_sibling', models.get_previous_sibling) + setattr(model, 'get_root', models.get_root) + setattr(model, 'get_siblings', models.get_siblings) + setattr(model, 'insert_at', models.insert_at) + setattr(model, 'is_child_node', models.is_child_node) + setattr(model, 'is_leaf_node', models.is_leaf_node) + setattr(model, 'is_root_node', models.is_root_node) + setattr(model, 'move_to', models.move_to) + + # Add a custom tree manager + TreeManager(parent_attr, left_attr, right_attr, tree_id_attr, + level_attr).contribute_to_class(model, tree_manager_attr) + setattr(model, '_tree_manager', getattr(model, tree_manager_attr)) + + # Set up signal receiver to manage the tree when instances of the + # model are about to be saved. + model_signals.pre_save.connect(pre_save, sender=model) + + # Wrap the model's delete method to manage the tree structure before + # deletion. This is icky, but the pre_delete signal doesn't currently + # provide a way to identify which model delete was called on and we + # only want to manage the tree based on the topmost node which is + # being deleted. + def wrap_delete(delete): + def _wrapped_delete(self): + opts = self._meta + tree_width = (getattr(self, opts.right_attr) - + getattr(self, opts.left_attr) + 1) + target_right = getattr(self, opts.right_attr) + tree_id = getattr(self, opts.tree_id_attr) + self._tree_manager._close_gap(tree_width, target_right, tree_id) + delete(self) + return wraps(delete)(_wrapped_delete) + model.delete = wrap_delete(model.delete)
new file mode 100644 --- /dev/null +++ b/apps/mptt/exceptions.py @@ -0,0 +1,11 @@ +""" +MPTT exceptions. +""" + +class InvalidMove(Exception): + """ + An invalid node move was attempted. + + For example, attempting to make a node a child of itself. + """ + pass
new file mode 100644 --- /dev/null +++ b/apps/mptt/forms.py @@ -0,0 +1,129 @@ +""" +Form components for working with trees. +""" +from django import forms +from django.forms.forms import NON_FIELD_ERRORS +from django.forms.util import ErrorList +from django.utils.encoding import smart_unicode +from django.utils.translation import ugettext_lazy as _ + +from mptt.exceptions import InvalidMove + +__all__ = ('TreeNodeChoiceField', 'TreeNodePositionField', 'MoveNodeForm') + +# Fields ###################################################################### + +class TreeNodeChoiceField(forms.ModelChoiceField): + """A ModelChoiceField for tree nodes.""" + def __init__(self, level_indicator=u'---', *args, **kwargs): + self.level_indicator = level_indicator + if kwargs.get('required', True) and not 'empty_label' in kwargs: + kwargs['empty_label'] = None + super(TreeNodeChoiceField, self).__init__(*args, **kwargs) + + def label_from_instance(self, obj): + """ + Creates labels which represent the tree level of each node when + generating option labels. + """ + return u'%s %s' % (self.level_indicator * getattr(obj, + obj._meta.level_attr), + smart_unicode(obj)) + +class TreeNodePositionField(forms.ChoiceField): + """A ChoiceField for specifying position relative to another node.""" + FIRST_CHILD = 'first-child' + LAST_CHILD = 'last-child' + LEFT = 'left' + RIGHT = 'right' + + DEFAULT_CHOICES = ( + (FIRST_CHILD, _('First child')), + (LAST_CHILD, _('Last child')), + (LEFT, _('Left sibling')), + (RIGHT, _('Right sibling')), + ) + + def __init__(self, *args, **kwargs): + if 'choices' not in kwargs: + kwargs['choices'] = self.DEFAULT_CHOICES + super(TreeNodePositionField, self).__init__(*args, **kwargs) + +# Forms ####################################################################### + +class MoveNodeForm(forms.Form): + """ + A form which allows the user to move a given node from one location + in its tree to another, with optional restriction of the nodes which + are valid target nodes for the move. + """ + target = TreeNodeChoiceField(queryset=None) + position = TreeNodePositionField() + + def __init__(self, node, *args, **kwargs): + """ + The ``node`` to be moved must be provided. The following keyword + arguments are also accepted:: + + ``valid_targets`` + Specifies a ``QuerySet`` of valid targets for the move. If + not provided, valid targets will consist of everything other + node of the same type, apart from the node itself and any + descendants. + + For example, if you want to restrict the node to moving + within its own tree, pass a ``QuerySet`` containing + everything in the node's tree except itself and its + descendants (to prevent invalid moves) and the root node (as + a user could choose to make the node a sibling of the root + node). + + ``target_select_size`` + The size of the select element used for the target node. + Defaults to ``10``. + + ``position_choices`` + A tuple of allowed position choices and their descriptions. + Defaults to ``TreeNodePositionField.DEFAULT_CHOICES``. + + ``level_indicator`` + A string which will be used to represent a single tree level + in the target options. + """ + self.node = node + valid_targets = kwargs.pop('valid_targets', None) + target_select_size = kwargs.pop('target_select_size', 10) + position_choices = kwargs.pop('position_choices', None) + level_indicator = kwargs.pop('level_indicator', None) + super(MoveNodeForm, self).__init__(*args, **kwargs) + opts = node._meta + if valid_targets is None: + valid_targets = node._tree_manager.exclude(**{ + opts.tree_id_attr: getattr(node, opts.tree_id_attr), + '%s__gte' % opts.left_attr: getattr(node, opts.left_attr), + '%s__lte' % opts.right_attr: getattr(node, opts.right_attr), + }) + self.fields['target'].queryset = valid_targets + self.fields['target'].widget.attrs['size'] = target_select_size + if level_indicator: + self.fields['target'].level_indicator = level_indicator + if position_choices: + self.fields['position_choices'].choices = position_choices + + def save(self): + """ + Attempts to move the node using the selected target and + position. + + If an invalid move is attempted, the related error message will + be added to the form's non-field errors and the error will be + re-raised. Callers should attempt to catch ``InvalidNode`` to + redisplay the form with the error, should it occur. + """ + try: + self.node.move_to(self.cleaned_data['target'], + self.cleaned_data['position']) + return self.node + except InvalidMove, e: + self.errors[NON_FIELD_ERRORS] = ErrorList(e) + raise
new file mode 100644 --- /dev/null +++ b/apps/mptt/managers.py @@ -0,0 +1,727 @@ +""" +A custom manager for working with trees of objects. +""" +from django.db import connection, models, transaction +from django.utils.translation import ugettext as _ + +from agora.apps.mptt.exceptions import InvalidMove + +__all__ = ('TreeManager',) + +qn = connection.ops.quote_name + +COUNT_SUBQUERY = """( + SELECT COUNT(*) + FROM %(rel_table)s + WHERE %(mptt_fk)s = %(mptt_table)s.%(mptt_pk)s +)""" + +CUMULATIVE_COUNT_SUBQUERY = """( + SELECT COUNT(*) + FROM %(rel_table)s + WHERE %(mptt_fk)s IN + ( + SELECT m2.%(mptt_pk)s + FROM %(mptt_table)s m2 + WHERE m2.%(tree_id)s = %(mptt_table)s.%(tree_id)s + AND m2.%(left)s BETWEEN %(mptt_table)s.%(left)s + AND %(mptt_table)s.%(right)s + ) +)""" + +class TreeManager(models.Manager): + """ + A manager for working with trees of objects. + """ + def __init__(self, parent_attr, left_attr, right_attr, tree_id_attr, + level_attr): + """ + Tree attributes for the model being managed are held as + attributes of this manager for later use, since it will be using + them a **lot**. + """ + super(TreeManager, self).__init__() + self.parent_attr = parent_attr + self.left_attr = left_attr + self.right_attr = right_attr + self.tree_id_attr = tree_id_attr + self.level_attr = level_attr + + def add_related_count(self, queryset, rel_model, rel_field, count_attr, + cumulative=False): + """ + Adds a related item count to a given ``QuerySet`` using its + ``extra`` method, for a ``Model`` class which has a relation to + this ``Manager``'s ``Model`` class. + + Arguments: + + ``rel_model`` + A ``Model`` class which has a relation to this `Manager``'s + ``Model`` class. + + ``rel_field`` + The name of the field in ``rel_model`` which holds the + relation. + + ``count_attr`` + The name of an attribute which should be added to each item in + this ``QuerySet``, containing a count of how many instances + of ``rel_model`` are related to it through ``rel_field``. + + ``cumulative`` + If ``True``, the count will be for each item and all of its + descendants, otherwise it will be for each item itself. + """ + opts = self.model._meta + if cumulative: + subquery = CUMULATIVE_COUNT_SUBQUERY % { + 'rel_table': qn(rel_model._meta.db_table), + 'mptt_fk': qn(rel_model._meta.get_field(rel_field).column), + 'mptt_table': qn(opts.db_table), + 'mptt_pk': qn(opts.pk.column), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + 'left': qn(opts.get_field(self.left_attr).column), + 'right': qn(opts.get_field(self.right_attr).column), + } + else: + subquery = COUNT_SUBQUERY % { + 'rel_table': qn(rel_model._meta.db_table), + 'mptt_fk': qn(rel_model._meta.get_field(rel_field).column), + 'mptt_table': qn(opts.db_table), + 'mptt_pk': qn(opts.pk.column), + } + return queryset.extra(select={count_attr: subquery}) + + def get_query_set(self): + """ + Returns a ``QuerySet`` which contains all tree items, ordered in + such a way that that root nodes appear in tree id order and + their subtrees appear in depth-first order. + """ + return super(TreeManager, self).get_query_set().order_by( + self.tree_id_attr, self.left_attr) + + def insert_node(self, node, target, position='last-child', + commit=False): + """ + Sets up the tree state for ``node`` (which has not yet been + inserted into in the database) so it will be positioned relative + to a given ``target`` node as specified by ``position`` (when + appropriate) it is inserted, with any neccessary space already + having been made for it. + + A ``target`` of ``None`` indicates that ``node`` should be + the last root node. + + If ``commit`` is ``True``, ``node``'s ``save()`` method will be + called before it is returned. + """ + if node.pk: + raise ValueError(_('Cannot insert a node which has already been saved.')) + + if target is None: + setattr(node, self.left_attr, 1) + setattr(node, self.right_attr, 2) + setattr(node, self.level_attr, 0) + setattr(node, self.tree_id_attr, self._get_next_tree_id()) + setattr(node, self.parent_attr, None) + elif target.is_root_node() and position in ['left', 'right']: + target_tree_id = getattr(target, self.tree_id_attr) + if position == 'left': + tree_id = target_tree_id + space_target = target_tree_id - 1 + else: + tree_id = target_tree_id + 1 + space_target = target_tree_id + + self._create_tree_space(space_target) + + setattr(node, self.left_attr, 1) + setattr(node, self.right_attr, 2) + setattr(node, self.level_attr, 0) + setattr(node, self.tree_id_attr, tree_id) + setattr(node, self.parent_attr, None) + else: + setattr(node, self.left_attr, 0) + setattr(node, self.level_attr, 0) + + space_target, level, left, parent = \ + self._calculate_inter_tree_move_values(node, target, position) + tree_id = getattr(parent, self.tree_id_attr) + + self._create_space(2, space_target, tree_id) + + setattr(node, self.left_attr, -left) + setattr(node, self.right_attr, -left + 1) + setattr(node, self.level_attr, -level) + setattr(node, self.tree_id_attr, tree_id) + setattr(node, self.parent_attr, parent) + + if commit: + node.save() + return node + + def move_node(self, node, target, position='last-child'): + """ + Moves ``node`` relative to a given ``target`` node as specified + by ``position`` (when appropriate), by examining both nodes and + calling the appropriate method to perform the move. + + A ``target`` of ``None`` indicates that ``node`` should be + turned into a root node. + + Valid values for ``position`` are ``'first-child'``, + ``'last-child'``, ``'left'`` or ``'right'``. + + ``node`` will be modified to reflect its new tree state in the + database. + + This method explicitly checks for ``node`` being made a sibling + of a root node, as this is a special case due to our use of tree + ids to order root nodes. + """ + if target is None: + if node.is_child_node(): + self._make_child_root_node(node) + elif target.is_root_node() and position in ['left', 'right']: + self._make_sibling_of_root_node(node, target, position) + else: + if node.is_root_node(): + self._move_root_node(node, target, position) + else: + self._move_child_node(node, target, position) + transaction.commit_unless_managed() + + def root_node(self, tree_id): + """ + Returns the root node of the tree with the given id. + """ + return self.get(**{ + self.tree_id_attr: tree_id, + '%s__isnull' % self.parent_attr: True, + }) + + def root_nodes(self): + """ + Creates a ``QuerySet`` containing root nodes. + """ + return self.filter(**{'%s__isnull' % self.parent_attr: True}) + + def _calculate_inter_tree_move_values(self, node, target, position): + """ + Calculates values required when moving ``node`` relative to + ``target`` as specified by ``position``. + """ + left = getattr(node, self.left_attr) + level = getattr(node, self.level_attr) + target_left = getattr(target, self.left_attr) + target_right = getattr(target, self.right_attr) + target_level = getattr(target, self.level_attr) + + if position == 'last-child' or position == 'first-child': + if position == 'last-child': + space_target = target_right - 1 + else: + space_target = target_left + level_change = level - target_level - 1 + parent = target + elif position == 'left' or position == 'right': + if position == 'left': + space_target = target_left - 1 + else: + space_target = target_right + level_change = level - target_level + parent = getattr(target, self.parent_attr) + else: + raise ValueError(_('An invalid position was given: %s.') % position) + + left_right_change = left - space_target - 1 + return space_target, level_change, left_right_change, parent + + def _close_gap(self, size, target, tree_id): + """ + Closes a gap of a certain ``size`` after the given ``target`` + point in the tree identified by ``tree_id``. + """ + self._manage_space(-size, target, tree_id) + + def _create_space(self, size, target, tree_id): + """ + Creates a space of a certain ``size`` after the given ``target`` + point in the tree identified by ``tree_id``. + """ + self._manage_space(size, target, tree_id) + + def _create_tree_space(self, target_tree_id): + """ + Creates space for a new tree by incrementing all tree ids + greater than ``target_tree_id``. + """ + opts = self.model._meta + cursor = connection.cursor() + cursor.execute(""" + UPDATE %(table)s + SET %(tree_id)s = %(tree_id)s + 1 + WHERE %(tree_id)s > %%s""" % { + 'table': qn(opts.db_table), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + }, [target_tree_id]) + + def _get_next_tree_id(self): + """ + Determines the next largest unused tree id for the tree managed + by this manager. + """ + opts = self.model._meta + cursor = connection.cursor() + cursor.execute('SELECT MAX(%s) FROM %s' % ( + qn(opts.get_field(self.tree_id_attr).column), + qn(opts.db_table))) + row = cursor.fetchone() + return row[0] and (row[0] + 1) or 1 + + def _inter_tree_move_and_close_gap(self, node, level_change, + left_right_change, new_tree_id, parent_pk=None): + """ + Removes ``node`` from its current tree, with the given set of + changes being applied to ``node`` and its descendants, closing + the gap left by moving ``node`` as it does so. + + If ``parent_pk`` is ``None``, this indicates that ``node`` is + being moved to a brand new tree as its root node, and will thus + have its parent field set to ``NULL``. Otherwise, ``node`` will + have ``parent_pk`` set for its parent field. + """ + opts = self.model._meta + inter_tree_move_query = """ + UPDATE %(table)s + SET %(level)s = CASE + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %(level)s - %%s + ELSE %(level)s END, + %(tree_id)s = CASE + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %%s + ELSE %(tree_id)s END, + %(left)s = CASE + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %(left)s - %%s + WHEN %(left)s > %%s + THEN %(left)s - %%s + ELSE %(left)s END, + %(right)s = CASE + WHEN %(right)s >= %%s AND %(right)s <= %%s + THEN %(right)s - %%s + WHEN %(right)s > %%s + THEN %(right)s - %%s + ELSE %(right)s END, + %(parent)s = CASE + WHEN %(pk)s = %%s + THEN %(new_parent)s + ELSE %(parent)s END + WHERE %(tree_id)s = %%s""" % { + 'table': qn(opts.db_table), + 'level': qn(opts.get_field(self.level_attr).column), + 'left': qn(opts.get_field(self.left_attr).column), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + 'right': qn(opts.get_field(self.right_attr).column), + 'parent': qn(opts.get_field(self.parent_attr).column), + 'pk': qn(opts.pk.column), + 'new_parent': parent_pk is None and 'NULL' or '%s', + } + + left = getattr(node, self.left_attr) + right = getattr(node, self.right_attr) + gap_size = right - left + 1 + gap_target_left = left - 1 + params = [ + left, right, level_change, + left, right, new_tree_id, + left, right, left_right_change, + gap_target_left, gap_size, + left, right, left_right_change, + gap_target_left, gap_size, + node.pk, + getattr(node, self.tree_id_attr) + ] + if parent_pk is not None: + params.insert(-1, parent_pk) + cursor = connection.cursor() + cursor.execute(inter_tree_move_query, params) + + def _make_child_root_node(self, node, new_tree_id=None): + """ + Removes ``node`` from its tree, making it the root node of a new + tree. + + If ``new_tree_id`` is not specified a new tree id will be + generated. + + ``node`` will be modified to reflect its new tree state in the + database. + """ + left = getattr(node, self.left_attr) + right = getattr(node, self.right_attr) + level = getattr(node, self.level_attr) + tree_id = getattr(node, self.tree_id_attr) + if not new_tree_id: + new_tree_id = self._get_next_tree_id() + left_right_change = left - 1 + + self._inter_tree_move_and_close_gap(node, level, left_right_change, + new_tree_id) + + # Update the node to be consistent with the updated + # tree in the database. + setattr(node, self.left_attr, left - left_right_change) + setattr(node, self.right_attr, right - left_right_change) + setattr(node, self.level_attr, 0) + setattr(node, self.tree_id_attr, new_tree_id) + setattr(node, self.parent_attr, None) + + def _make_sibling_of_root_node(self, node, target, position): + """ + Moves ``node``, making it a sibling of the given ``target`` root + node as specified by ``position``. + + ``node`` will be modified to reflect its new tree state in the + database. + + Since we use tree ids to reduce the number of rows affected by + tree mangement during insertion and deletion, root nodes are not + true siblings; thus, making an item a sibling of a root node is + a special case which involves shuffling tree ids around. + """ + if node == target: + raise InvalidMove(_('A node may not be made a sibling of itself.')) + + opts = self.model._meta + tree_id = getattr(node, self.tree_id_attr) + target_tree_id = getattr(target, self.tree_id_attr) + + if node.is_child_node(): + if position == 'left': + space_target = target_tree_id - 1 + new_tree_id = target_tree_id + elif position == 'right': + space_target = target_tree_id + new_tree_id = target_tree_id + 1 + else: + raise ValueError(_('An invalid position was given: %s.') % position) + + self._create_tree_space(space_target) + if tree_id > space_target: + # The node's tree id has been incremented in the + # database - this change must be reflected in the node + # object for the method call below to operate on the + # correct tree. + setattr(node, self.tree_id_attr, tree_id + 1) + self._make_child_root_node(node, new_tree_id) + else: + if position == 'left': + if target_tree_id > tree_id: + left_sibling = target.get_previous_sibling() + if node == left_sibling: + return + new_tree_id = getattr(left_sibling, self.tree_id_attr) + lower_bound, upper_bound = tree_id, new_tree_id + shift = -1 + else: + new_tree_id = target_tree_id + lower_bound, upper_bound = new_tree_id, tree_id + shift = 1 + elif position == 'right': + if target_tree_id > tree_id: + new_tree_id = target_tree_id + lower_bound, upper_bound = tree_id, target_tree_id + shift = -1 + else: + right_sibling = target.get_next_sibling() + if node == right_sibling: + return + new_tree_id = getattr(right_sibling, self.tree_id_attr) + lower_bound, upper_bound = new_tree_id, tree_id + shift = 1 + else: + raise ValueError(_('An invalid position was given: %s.') % position) + + root_sibling_query = """ + UPDATE %(table)s + SET %(tree_id)s = CASE + WHEN %(tree_id)s = %%s + THEN %%s + ELSE %(tree_id)s + %%s END + WHERE %(tree_id)s >= %%s AND %(tree_id)s <= %%s""" % { + 'table': qn(opts.db_table), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + } + cursor = connection.cursor() + cursor.execute(root_sibling_query, [tree_id, new_tree_id, shift, + lower_bound, upper_bound]) + setattr(node, self.tree_id_attr, new_tree_id) + + def _manage_space(self, size, target, tree_id): + """ + Manages spaces in the tree identified by ``tree_id`` by changing + the values of the left and right columns by ``size`` after the + given ``target`` point. + """ + opts = self.model._meta + space_query = """ + UPDATE %(table)s + SET %(left)s = CASE + WHEN %(left)s > %%s + THEN %(left)s + %%s + ELSE %(left)s END, + %(right)s = CASE + WHEN %(right)s > %%s + THEN %(right)s + %%s + ELSE %(right)s END + WHERE %(tree_id)s = %%s + AND (%(left)s > %%s OR %(right)s > %%s)""" % { + 'table': qn(opts.db_table), + 'left': qn(opts.get_field(self.left_attr).column), + 'right': qn(opts.get_field(self.right_attr).column), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + } + cursor = connection.cursor() + cursor.execute(space_query, [target, size, target, size, tree_id, + target, target]) + + def _move_child_node(self, node, target, position): + """ + Calls the appropriate method to move child node ``node`` + relative to the given ``target`` node as specified by + ``position``. + """ + tree_id = getattr(node, self.tree_id_attr) + target_tree_id = getattr(target, self.tree_id_attr) + + if (getattr(node, self.tree_id_attr) == + getattr(target, self.tree_id_attr)): + self._move_child_within_tree(node, target, position) + else: + self._move_child_to_new_tree(node, target, position) + + def _move_child_to_new_tree(self, node, target, position): + """ + Moves child node ``node`` to a different tree, inserting it + relative to the given ``target`` node in the new tree as + specified by ``position``. + + ``node`` will be modified to reflect its new tree state in the + database. + """ + left = getattr(node, self.left_attr) + right = getattr(node, self.right_attr) + level = getattr(node, self.level_attr) + target_left = getattr(target, self.left_attr) + target_right = getattr(target, self.right_attr) + target_level = getattr(target, self.level_attr) + tree_id = getattr(node, self.tree_id_attr) + new_tree_id = getattr(target, self.tree_id_attr) + + space_target, level_change, left_right_change, parent = \ + self._calculate_inter_tree_move_values(node, target, position) + + tree_width = right - left + 1 + + # Make space for the subtree which will be moved + self._create_space(tree_width, space_target, new_tree_id) + # Move the subtree + self._inter_tree_move_and_close_gap(node, level_change, + left_right_change, new_tree_id, parent.pk) + + # Update the node to be consistent with the updated + # tree in the database. + setattr(node, self.left_attr, left - left_right_change) + setattr(node, self.right_attr, right - left_right_change) + setattr(node, self.level_attr, level - level_change) + setattr(node, self.tree_id_attr, new_tree_id) + setattr(node, self.parent_attr, parent) + + def _move_child_within_tree(self, node, target, position): + """ + Moves child node ``node`` within its current tree relative to + the given ``target`` node as specified by ``position``. + + ``node`` will be modified to reflect its new tree state in the + database. + """ + left = getattr(node, self.left_attr) + right = getattr(node, self.right_attr) + level = getattr(node, self.level_attr) + width = right - left + 1 + tree_id = getattr(node, self.tree_id_attr) + target_left = getattr(target, self.left_attr) + target_right = getattr(target, self.right_attr) + target_level = getattr(target, self.level_attr) + + if position == 'last-child' or position == 'first-child': + if node == target: + raise InvalidMove(_('A node may not be made a child of itself.')) + elif left < target_left < right: + raise InvalidMove(_('A node may not be made a child of any of its descendants.')) + if position == 'last-child': + if target_right > right: + new_left = target_right - width + new_right = target_right - 1 + else: + new_left = target_right + new_right = target_right + width - 1 + else: + if target_left > left: + new_left = target_left - width + 1 + new_right = target_left + else: + new_left = target_left + 1 + new_right = target_left + width + level_change = level - target_level - 1 + parent = target + elif position == 'left' or position == 'right': + if node == target: + raise InvalidMove(_('A node may not be made a sibling of itself.')) + elif left < target_left < right: + raise InvalidMove(_('A node may not be made a sibling of any of its descendants.')) + if position == 'left': + if target_left > left: + new_left = target_left - width + new_right = target_left - 1 + else: + new_left = target_left + new_right = target_left + width - 1 + else: + if target_right > right: + new_left = target_right - width + 1 + new_right = target_right + else: + new_left = target_right + 1 + new_right = target_right + width + level_change = level - target_level + parent = getattr(target, self.parent_attr) + else: + raise ValueError(_('An invalid position was given: %s.') % position) + + left_boundary = min(left, new_left) + right_boundary = max(right, new_right) + left_right_change = new_left - left + gap_size = width + if left_right_change > 0: + gap_size = -gap_size + + opts = self.model._meta + # The level update must come before the left update to keep + # MySQL happy - left seems to refer to the updated value + # immediately after its update has been specified in the query + # with MySQL, but not with SQLite or Postgres. + move_subtree_query = """ + UPDATE %(table)s + SET %(level)s = CASE + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %(level)s - %%s + ELSE %(level)s END, + %(left)s = CASE + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %(left)s + %%s + WHEN %(left)s >= %%s AND %(left)s <= %%s + THEN %(left)s + %%s + ELSE %(left)s END, + %(right)s = CASE + WHEN %(right)s >= %%s AND %(right)s <= %%s + THEN %(right)s + %%s + WHEN %(right)s >= %%s AND %(right)s <= %%s + THEN %(right)s + %%s + ELSE %(right)s END, + %(parent)s = CASE + WHEN %(pk)s = %%s + THEN %%s + ELSE %(parent)s END + WHERE %(tree_id)s = %%s""" % { + 'table': qn(opts.db_table), + 'level': qn(opts.get_field(self.level_attr).column), + 'left': qn(opts.get_field(self.left_attr).column), + 'right': qn(opts.get_field(self.right_attr).column), + 'parent': qn(opts.get_field(self.parent_attr).column), + 'pk': qn(opts.pk.column), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + } + + cursor = connection.cursor() + cursor.execute(move_subtree_query, [ + left, right, level_change, + left, right, left_right_change, + left_boundary, right_boundary, gap_size, + left, right, left_right_change, + left_boundary, right_boundary, gap_size, + node.pk, parent.pk, + tree_id]) + + # Update the node to be consistent with the updated + # tree in the database. + setattr(node, self.left_attr, new_left) + setattr(node, self.right_attr, new_right) + setattr(node, self.level_attr, level - level_change) + setattr(node, self.parent_attr, parent) + + def _move_root_node(self, node, target, position): + """ + Moves root node``node`` to a different tree, inserting it + relative to the given ``target`` node as specified by + ``position``. + + ``node`` will be modified to reflect its new tree state in the + database. + """ + left = getattr(node, self.left_attr) + right = getattr(node, self.right_attr) + level = getattr(node, self.level_attr) + tree_id = getattr(node, self.tree_id_attr) + new_tree_id = getattr(target, self.tree_id_attr) + width = right - left + 1 + + if node == target: + raise InvalidMove(_('A node may not be made a child of itself.')) + elif tree_id == new_tree_id: + raise InvalidMove(_('A node may not be made a child of any of its descendants.')) + + space_target, level_change, left_right_change, parent = \ + self._calculate_inter_tree_move_values(node, target, position) + + # Create space for the tree which will be inserted + self._create_space(width, space_target, new_tree_id) + + # Move the root node, making it a child node + opts = self.model._meta + move_tree_query = """ + UPDATE %(table)s + SET %(level)s = %(level)s - %%s, + %(left)s = %(left)s - %%s, + %(right)s = %(right)s - %%s, + %(tree_id)s = %%s, + %(parent)s = CASE + WHEN %(pk)s = %%s + THEN %%s + ELSE %(parent)s END + WHERE %(left)s >= %%s AND %(left)s <= %%s + AND %(tree_id)s = %%s""" % { + 'table': qn(opts.db_table), + 'level': qn(opts.get_field(self.level_attr).column), + 'left': qn(opts.get_field(self.left_attr).column), + 'right': qn(opts.get_field(self.right_attr).column), + 'tree_id': qn(opts.get_field(self.tree_id_attr).column), + 'parent': qn(opts.get_field(self.parent_attr).column), + 'pk': qn(opts.pk.column), + } + cursor = connection.cursor() + cursor.execute(move_tree_query, [level_change, left_right_change, + left_right_change, new_tree_id, node.pk, parent.pk, left, right, + tree_id]) + + # Update the former root node to be consistent with the updated + # tree in the database. + setattr(node, self.left_attr, left - left_right_change) + setattr(node, self.right_attr, right - left_right_change) + setattr(node, self.level_attr, level - level_change) + setattr(node, self.tree_id_attr, new_tree_id) + setattr(node, self.parent_attr, parent)
new file mode 100644 --- /dev/null +++ b/apps/mptt/models.py @@ -0,0 +1,186 @@ +""" +New instance methods for Django models which are set up for Modified +Preorder Tree Traversal. +""" + +def get_ancestors(self, ascending=False): + """ + Creates a ``QuerySet`` containing the ancestors of this model + instance. + + This defaults to being in descending order (root ancestor first, + immediate parent last); passing ``True`` for the ``ascending`` + argument will reverse the ordering (immediate parent first, root + ancestor last). + """ + if self.is_root_node(): + return self._tree_manager.none() + + opts = self._meta + return self._default_manager.filter(**{ + '%s__lt' % opts.left_attr: getattr(self, opts.left_attr), + '%s__gt' % opts.right_attr: getattr(self, opts.right_attr), + opts.tree_id_attr: getattr(self, opts.tree_id_attr), + }).order_by('%s%s' % ({True: '-', False: ''}[ascending], opts.left_attr)) + +def get_children(self): + """ + Creates a ``QuerySet`` containing the immediate children of this + model instance, in tree order. + + The benefit of using this method over the reverse relation + provided by the ORM to the instance's children is that a + database query can be avoided in the case where the instance is + a leaf node (it has no children). + """ + if self.is_leaf_node(): + return self._tree_manager.none() + + return self._tree_manager.filter(**{ + self._meta.parent_attr: self, + }) + +def get_descendants(self, include_self=False): + """ + Creates a ``QuerySet`` containing descendants of this model + instance, in tree order. + + If ``include_self`` is ``True``, the ``QuerySet`` will also + include this model instance. + """ + if not include_self and self.is_leaf_node(): + return self._tree_manager.none() + + opts = self._meta + filters = {opts.tree_id_attr: getattr(self, opts.tree_id_attr)} + if include_self: + filters['%s__range' % opts.left_attr] = (getattr(self, opts.left_attr), + getattr(self, opts.right_attr)) + else: + filters['%s__gt' % opts.left_attr] = getattr(self, opts.left_attr) + filters['%s__lt' % opts.left_attr] = getattr(self, opts.right_attr) + return self._tree_manager.filter(**filters) + +def get_descendant_count(self): + """ + Returns the number of descendants this model instance has. + """ + return (getattr(self, self._meta.right_attr) - + getattr(self, self._meta.left_attr) - 1) / 2 + +def get_next_sibling(self): + """ + Returns this model instance's next sibling in the tree, or + ``None`` if it doesn't have a next sibling. + """ + opts = self._meta + if self.is_root_node(): + filters = { + '%s__isnull' % opts.parent_attr: True, + '%s__gt' % opts.tree_id_attr: getattr(self, opts.tree_id_attr), + } + else: + filters = { + opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr), + '%s__gt' % opts.left_attr: getattr(self, opts.right_attr), + } + + sibling = None + try: + sibling = self._tree_manager.filter(**filters)[0] + except IndexError: + pass + return sibling + +def get_previous_sibling(self): + """ + Returns this model instance's previous sibling in the tree, or + ``None`` if it doesn't have a previous sibling. + """ + opts = self._meta + if self.is_root_node(): + filters = { + '%s__isnull' % opts.parent_attr: True, + '%s__lt' % opts.tree_id_attr: getattr(self, opts.tree_id_attr), + } + order_by = '-%s' % opts.tree_id_attr + else: + filters = { + opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr), + '%s__lt' % opts.right_attr: getattr(self, opts.left_attr), + } + order_by = '-%s' % opts.right_attr + + sibling = None + try: + sibling = self._tree_manager.filter(**filters).order_by(order_by)[0] + except IndexError: + pass + return sibling + +def get_root(self): + """ + Returns the root node of this model instance's tree. + """ + if self.is_root_node(): + return self + + opts = self._meta + return self._default_manager.get(**{ + opts.tree_id_attr: getattr(self, opts.tree_id_attr), + '%s__isnull' % opts.parent_attr: True, + }) + +def get_siblings(self, include_self=False): + """ + Creates a ``QuerySet`` containing siblings of this model + instance. Root nodes are considered to be siblings of other root + nodes. + + If ``include_self`` is ``True``, the ``QuerySet`` will also + include this model instance. + """ + opts = self._meta + if self.is_root_node(): + filters = {'%s__isnull' % opts.parent_attr: True} + else: + filters = {opts.parent_attr: getattr(self, '%s_id' % opts.parent_attr)} + queryset = self._tree_manager.filter(**filters) + if not include_self: + queryset = queryset.exclude(pk=self.pk) + return queryset + +def insert_at(self, target, position='first-child', commit=False): + """ + Convenience method for calling ``TreeManager.insert_node`` with this + model instance. + """ + self._tree_manager.insert_node(self, target, position, commit) + +def is_child_node(self): + """ + Returns ``True`` if this model instance is a child node, ``False`` + otherwise. + """ + return not self.is_root_node() + +def is_leaf_node(self): + """ + Returns ``True`` if this model instance is a leaf node (it has no + children), ``False`` otherwise. + """ + return not self.get_descendant_count() + +def is_root_node(self): + """ + Returns ``True`` if this model instance is a root node, + ``False`` otherwise. + """ + return getattr(self, '%s_id' % self._meta.parent_attr) is None + +def move_to(self, target, position='first-child'): + """ + Convenience method for calling ``TreeManager.move_node`` with this + model instance. + """ + self._tree_manager.move_node(self, target, position)
new file mode 100644 --- /dev/null +++ b/apps/mptt/signals.py @@ -0,0 +1,127 @@ +""" +Signal receiving functions which handle Modified Preorder Tree Traversal +related logic when model instances are about to be saved or deleted. +""" +import operator + +from django.db.models.query import Q + +__all__ = ('pre_save',) + +def _insertion_target_filters(node, order_insertion_by): + """ + Creates a filter which matches suitable right siblings for ``node``, + where insertion should maintain ordering according to the list of + fields in ``order_insertion_by``. + + For example, given an ``order_insertion_by`` of + ``['field1', 'field2', 'field3']``, the resulting filter should + correspond to the following SQL:: + + field1 > %s + OR (field1 = %s AND field2 > %s) + OR (field1 = %s AND field2 = %s AND field3 > %s) + + """ + fields = [] + filters = [] + for field in order_insertion_by: + value = getattr(node, field) + filters.append(reduce(operator.and_, [Q(**{f: v}) for f, v in fields] + + [Q(**{'%s__gt' % field: value})])) + fields.append((field, value)) + return reduce(operator.or_, filters) + +def _get_ordered_insertion_target(node, parent): + """ + Attempts to retrieve a suitable right sibling for ``node`` + underneath ``parent`` (which may be ``None`` in the case of root + nodes) so that ordering by the fields specified by the node's class' + ``order_insertion_by`` option is maintained. + + Returns ``None`` if no suitable sibling can be found. + """ + right_sibling = None + # Optimisation - if the parent doesn't have descendants, + # the node will always be its last child. + if parent is None or parent.get_descendant_count() > 0: + opts = node._meta + order_by = opts.order_insertion_by[:] + filters = _insertion_target_filters(node, order_by) + if parent: + filters = filters & Q(**{opts.parent_attr: parent}) + # Fall back on tree ordering if multiple child nodes have + # the same values. + order_by.append(opts.left_attr) + else: + filters = filters & Q(**{'%s__isnull' % opts.parent_attr: True}) + # Fall back on tree id ordering if multiple root nodes have + # the same values. + order_by.append(opts.tree_id_attr) + try: + right_sibling = \ + node._default_manager.filter(filters).order_by(*order_by)[0] + except IndexError: + # No suitable right sibling could be found + pass + return right_sibling + +def pre_save(instance, **kwargs): + """ + If this is a new node, sets tree fields up before it is inserted + into the database, making room in the tree structure as neccessary, + defaulting to making the new node the last child of its parent. + + It the node's left and right edge indicators already been set, we + take this as indication that the node has already been set up for + insertion, so its tree fields are left untouched. + + If this is an existing node and its parent has been changed, + performs reparenting in the tree structure, defaulting to making the + node the last child of its new parent. + + In either case, if the node's class has its ``order_insertion_by`` + tree option set, the node will be inserted or moved to the + appropriate position to maintain ordering by the specified field. + """ + if kwargs.get('raw'): + return + + opts = instance._meta + parent = getattr(instance, opts.parent_attr) + if not instance.pk: + if (getattr(instance, opts.left_attr) and + getattr(instance, opts.right_attr)): + # This node has already been set up for insertion. + return + + if opts.order_insertion_by: + right_sibling = _get_ordered_insertion_target(instance, parent) + if right_sibling: + instance.insert_at(right_sibling, 'left') + return + + # Default insertion + instance.insert_at(parent, position='last-child') + else: + # TODO Is it possible to track the original parent so we + # don't have to look it up again on each save after the + # first? + old_parent = getattr(instance._default_manager.get(pk=instance.pk), + opts.parent_attr) + if parent != old_parent: + setattr(instance, opts.parent_attr, old_parent) + try: + if opts.order_insertion_by: + right_sibling = _get_ordered_insertion_target(instance, + parent) + if right_sibling: + instance.move_to(right_sibling, 'left') + return + + # Default movement + instance.move_to(parent, position='last-child') + finally: + # Make sure the instance's new parent is always + # restored on the way out in case of errors. + setattr(instance, opts.parent_attr, parent)
new file mode 100644 --- /dev/null +++ b/apps/mptt/templatetags/mptt_tags.py @@ -0,0 +1,197 @@ +""" +Template tags for working with lists of model instances which represent +trees. +""" +from django import template +from django.db.models import get_model +from django.db.models.fields import FieldDoesNotExist +from django.utils.encoding import force_unicode +from django.utils.translation import ugettext as _ + +from agora.apps.mptt.utils import tree_item_iterator, drilldown_tree_for_node + +register = template.Library() + +class FullTreeForModelNode(template.Node): + def __init__(self, model, context_var): + self.model = model + self.context_var = context_var + + def render(self, context): + cls = get_model(*self.model.split('.')) + if cls is None: + raise template.TemplateSyntaxError(_('full_tree_for_model tag was given an invalid model: %s') % self.model) + context[self.context_var] = cls._tree_manager.all() + return '' + +class DrilldownTreeForNodeNode(template.Node): + def __init__(self, node, context_var, foreign_key=None, count_attr=None, + cumulative=False): + self.node = template.Variable(node) + self.context_var = context_var + self.foreign_key = foreign_key + self.count_attr = count_attr + self.cumulative = cumulative + + def render(self, context): + # Let any VariableDoesNotExist raised bubble up + args = [self.node.resolve(context)] + + if self.foreign_key is not None: + app_label, model_name, fk_attr = self.foreign_key.split('.') + cls = get_model(app_label, model_name) + if cls is None: + raise template.TemplateSyntaxError(_('drilldown_tree_for_node tag was given an invalid model: %s') % '.'.join([app_label, model_name])) + try: + cls._meta.get_field(fk_attr) + except FieldDoesNotExist: + raise template.TemplateSyntaxError(_('drilldown_tree_for_node tag was given an invalid model field: %s') % fk_attr) + args.extend([cls, fk_attr, self.count_attr, self.cumulative]) + + context[self.context_var] = drilldown_tree_for_node(*args) + return '' + +def do_full_tree_for_model(parser, token): + """ + Populates a template variable with a ``QuerySet`` containing the + full tree for a given model. + + Usage:: + + {% full_tree_for_model [model] as [varname] %} + + The model is specified in ``[appname].[modelname]`` format. + + Example:: + + {% full_tree_for_model tests.Genre as genres %} + + """ + bits = token.contents.split() + if len(bits) != 4: + raise template.TemplateSyntaxError(_('%s tag requires three arguments') % bits[0]) + if bits[2] != 'as': + raise template.TemplateSyntaxError(_("second argument to %s tag must be 'as'") % bits[0]) + return FullTreeForModelNode(bits[1], bits[3]) + +def do_drilldown_tree_for_node(parser, token): + """ + Populates a template variable with the drilldown tree for a given + node, optionally counting the number of items associated with its + children. + + A drilldown tree consists of a node's ancestors, itself and its + immediate children. For example, a drilldown tree for a book + category "Personal Finance" might look something like:: + + Books + Business, Finance & Law + Personal Finance + Budgeting (220) + Financial Planning (670) + + Usage:: + + {% drilldown_tree_for_node [node] as [varname] %} + + Extended usage:: + + {% drilldown_tree_for_node [node] as [varname] count [foreign_key] in [count_attr] %} + {% drilldown_tree_for_node [node] as [varname] cumulative count [foreign_key] in [count_attr] %} + + The foreign key is specified in ``[appname].[modelname].[fieldname]`` + format, where ``fieldname`` is the name of a field in the specified + model which relates it to the given node's model. + + When this form is used, a ``count_attr`` attribute on each child of + the given node in the drilldown tree will contain a count of the + number of items associated with it through the given foreign key. + + If cumulative is also specified, this count will be for items + related to the child node and all of its descendants. + + Examples:: + + {% drilldown_tree_for_node genre as drilldown %} + {% drilldown_tree_for_node genre as drilldown count tests.Game.genre in game_count %} + {% drilldown_tree_for_node genre as drilldown cumulative count tests.Game.genre in game_count %} + + """ + bits = token.contents.split() + len_bits = len(bits) + if len_bits not in (4, 8, 9): + raise TemplateSyntaxError(_('%s tag requires either three, seven or eight arguments') % bits[0]) + if bits[2] != 'as': + raise TemplateSyntaxError(_("second argument to %s tag must be 'as'") % bits[0]) + if len_bits == 8: + if bits[4] != 'count': + raise TemplateSyntaxError(_("if seven arguments are given, fourth argument to %s tag must be 'with'") % bits[0]) + if bits[6] != 'in': + raise TemplateSyntaxError(_("if seven arguments are given, sixth argument to %s tag must be 'in'") % bits[0]) + return DrilldownTreeForNodeNode(bits[1], bits[3], bits[5], bits[7]) + elif len_bits == 9: + if bits[4] != 'cumulative': + raise TemplateSyntaxError(_("if eight arguments are given, fourth argument to %s tag must be 'cumulative'") % bits[0]) + if bits[5] != 'count': + raise TemplateSyntaxError(_("if eight arguments are given, fifth argument to %s tag must be 'count'") % bits[0]) + if bits[7] != 'in': + raise TemplateSyntaxError(_("if eight arguments are given, seventh argument to %s tag must be 'in'") % bits[0]) + return DrilldownTreeForNodeNode(bits[1], bits[3], bits[6], bits[8], cumulative=True) + else: + return DrilldownTreeForNodeNode(bits[1], bits[3]) + +def tree_info(items, features=None): + """ + Given a list of tree items, produces doubles of a tree item and a + ``dict`` containing information about the tree structure around the + item, with the following contents: + + new_level + ``True`` if the current item is the start of a new level in + the tree, ``False`` otherwise. + + closed_levels + A list of levels which end after the current item. This will + be an empty list if the next item is at the same level as the + current item. + + Using this filter with unpacking in a ``{% for %}`` tag, you should + have enough information about the tree structure to create a + hierarchical representation of the tree. + + Example:: + + {% for genre,structure in genres|tree_info %} + {% if tree.new_level %}<ul><li>{% else %}</li><li>{% endif %} + {{ genre.name }} + {% for level in tree.closed_levels %}</li></ul>{% endfor %} + {% endfor %} + + """ + kwargs = {} + if features: + feature_names = features.split(',') + if 'ancestors' in feature_names: + kwargs['ancestors'] = True + return tree_item_iterator(items, **kwargs) + +def tree_path(items, separator=' :: '): + """ + Creates a tree path represented by a list of ``items`` by joining + the items with a ``separator``. + + Each path item will be coerced to unicode, so a list of model + instances may be given if required. + + Example:: + + {{ some_list|tree_path }} + {{ some_node.get_ancestors|tree_path:" > " }} + + """ + return separator.join([force_unicode(i) for i in items]) + +register.tag('full_tree_for_model', do_full_tree_for_model) +register.tag('drilldown_tree_for_node', do_drilldown_tree_for_node) +register.filter('tree_info', tree_info) +register.filter('tree_path', tree_path)
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/doctests.py @@ -0,0 +1,1246 @@ +r""" +>>> from datetime import date +>>> from mptt.exceptions import InvalidMove +>>> from mptt.tests.models import Genre, Insert, MultiOrder, Node, OrderedInsertion, Tree + +>>> def print_tree_details(nodes): +... opts = nodes[0]._meta +... print '\n'.join(['%s %s %s %s %s %s' % \ +... (n.pk, getattr(n, '%s_id' % opts.parent_attr) or '-', +... getattr(n, opts.tree_id_attr), getattr(n, opts.level_attr), +... getattr(n, opts.left_attr), getattr(n, opts.right_attr)) \ +... for n in nodes]) + +>>> import mptt +>>> mptt.register(Genre) +Traceback (most recent call last): + ... +AlreadyRegistered: The model Genre has already been registered. + +# Creation #################################################################### +>>> action = Genre.objects.create(name='Action') +>>> platformer = Genre.objects.create(name='Platformer', parent=action) +>>> platformer_2d = Genre.objects.create(name='2D Platformer', parent=platformer) +>>> platformer = Genre.objects.get(pk=platformer.pk) +>>> platformer_3d = Genre.objects.create(name='3D Platformer', parent=platformer) +>>> platformer = Genre.objects.get(pk=platformer.pk) +>>> platformer_4d = Genre.objects.create(name='4D Platformer', parent=platformer) +>>> rpg = Genre.objects.create(name='Role-playing Game') +>>> arpg = Genre.objects.create(name='Action RPG', parent=rpg) +>>> rpg = Genre.objects.get(pk=rpg.pk) +>>> trpg = Genre.objects.create(name='Tactical RPG', parent=rpg) +>>> print_tree_details(Genre.tree.all()) +1 - 1 0 1 10 +2 1 1 1 2 9 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 2 1 2 7 8 +6 - 2 0 1 6 +7 6 2 1 2 3 +8 6 2 1 4 5 + +# Utilities ################################################################### +>>> from mptt.utils import previous_current_next, tree_item_iterator, drilldown_tree_for_node + +>>> for p,c,n in previous_current_next(Genre.tree.all()): +... print (p,c,n) +(None, <Genre: Action>, <Genre: Platformer>) +(<Genre: Action>, <Genre: Platformer>, <Genre: 2D Platformer>) +(<Genre: Platformer>, <Genre: 2D Platformer>, <Genre: 3D Platformer>) +(<Genre: 2D Platformer>, <Genre: 3D Platformer>, <Genre: 4D Platformer>) +(<Genre: 3D Platformer>, <Genre: 4D Platformer>, <Genre: Role-playing Game>) +(<Genre: 4D Platformer>, <Genre: Role-playing Game>, <Genre: Action RPG>) +(<Genre: Role-playing Game>, <Genre: Action RPG>, <Genre: Tactical RPG>) +(<Genre: Action RPG>, <Genre: Tactical RPG>, None) + +>>> for i,s in tree_item_iterator(Genre.tree.all()): +... print (i, s['new_level'], s['closed_levels']) +(<Genre: Action>, True, []) +(<Genre: Platformer>, True, []) +(<Genre: 2D Platformer>, True, []) +(<Genre: 3D Platformer>, False, []) +(<Genre: 4D Platformer>, False, [2, 1]) +(<Genre: Role-playing Game>, False, []) +(<Genre: Action RPG>, True, []) +(<Genre: Tactical RPG>, False, [1, 0]) + +>>> for i,s in tree_item_iterator(Genre.tree.all(), ancestors=True): +... print (i, s['new_level'], s['ancestors'], s['closed_levels']) +(<Genre: Action>, True, [], []) +(<Genre: Platformer>, True, [u'Action'], []) +(<Genre: 2D Platformer>, True, [u'Action', u'Platformer'], []) +(<Genre: 3D Platformer>, False, [u'Action', u'Platformer'], []) +(<Genre: 4D Platformer>, False, [u'Action', u'Platformer'], [2, 1]) +(<Genre: Role-playing Game>, False, [], []) +(<Genre: Action RPG>, True, [u'Role-playing Game'], []) +(<Genre: Tactical RPG>, False, [u'Role-playing Game'], [1, 0]) + +>>> action = Genre.objects.get(pk=action.pk) +>>> [item.name for item in drilldown_tree_for_node(action)] +[u'Action', u'Platformer'] + +>>> platformer = Genre.objects.get(pk=platformer.pk) +>>> [item.name for item in drilldown_tree_for_node(platformer)] +[u'Action', u'Platformer', u'2D Platformer', u'3D Platformer', u'4D Platformer'] + +>>> platformer_3d = Genre.objects.get(pk=platformer_3d.pk) +>>> [item.name for item in drilldown_tree_for_node(platformer_3d)] +[u'Action', u'Platformer', u'3D Platformer'] + +# Forms ####################################################################### +>>> from mptt.forms import TreeNodeChoiceField, MoveNodeForm + +>>> f = TreeNodeChoiceField(queryset=Genre.tree.all()) +>>> print(f.widget.render("test", None)) +<select name="test"> +<option value="1"> Action</option> +<option value="2">--- Platformer</option> +<option value="3">------ 2D Platformer</option> +<option value="4">------ 3D Platformer</option> +<option value="5">------ 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="7">--- Action RPG</option> +<option value="8">--- Tactical RPG</option> +</select> + +>>> f = TreeNodeChoiceField(queryset=Genre.tree.all(), required=False) +>>> print(f.widget.render("test", None)) +<select name="test"> +<option value="" selected="selected">---------</option> +<option value="1"> Action</option> +<option value="2">--- Platformer</option> +<option value="3">------ 2D Platformer</option> +<option value="4">------ 3D Platformer</option> +<option value="5">------ 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="7">--- Action RPG</option> +<option value="8">--- Tactical RPG</option> +</select> + +>>> f = TreeNodeChoiceField(queryset=Genre.tree.all(), empty_label=u'None of the below') +>>> print(f.widget.render("test", None)) +<select name="test"> +<option value="" selected="selected">None of the below</option> +<option value="1"> Action</option> +<option value="2">--- Platformer</option> +<option value="3">------ 2D Platformer</option> +<option value="4">------ 3D Platformer</option> +<option value="5">------ 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="7">--- Action RPG</option> +<option value="8">--- Tactical RPG</option> +</select> + +>>> f = TreeNodeChoiceField(queryset=Genre.tree.all(), required=False, empty_label=u'None of the below') +>>> print(f.widget.render("test", None)) +<select name="test"> +<option value="" selected="selected">None of the below</option> +<option value="1"> Action</option> +<option value="2">--- Platformer</option> +<option value="3">------ 2D Platformer</option> +<option value="4">------ 3D Platformer</option> +<option value="5">------ 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="7">--- Action RPG</option> +<option value="8">--- Tactical RPG</option> +</select> + +>>> f = TreeNodeChoiceField(queryset=Genre.tree.all(), level_indicator=u'+--') +>>> print(f.widget.render("test", None)) +<select name="test"> +<option value="1"> Action</option> +<option value="2">+-- Platformer</option> +<option value="3">+--+-- 2D Platformer</option> +<option value="4">+--+-- 3D Platformer</option> +<option value="5">+--+-- 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="7">+-- Action RPG</option> +<option value="8">+-- Tactical RPG</option> +</select> + +>>> form = MoveNodeForm(Genre.objects.get(pk=7)) +>>> print(form) +<tr><th><label for="id_target">Target:</label></th><td><select id="id_target" name="target" size="10"> +<option value="1"> Action</option> +<option value="2">--- Platformer</option> +<option value="3">------ 2D Platformer</option> +<option value="4">------ 3D Platformer</option> +<option value="5">------ 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="8">--- Tactical RPG</option> +</select></td></tr> +<tr><th><label for="id_position">Position:</label></th><td><select name="position" id="id_position"> +<option value="first-child">First child</option> +<option value="last-child">Last child</option> +<option value="left">Left sibling</option> +<option value="right">Right sibling</option> +</select></td></tr> + +>>> form = MoveNodeForm(Genre.objects.get(pk=7), level_indicator=u'+--', target_select_size=5) +>>> print(form) +<tr><th><label for="id_target">Target:</label></th><td><select id="id_target" name="target" size="5"> +<option value="1"> Action</option> +<option value="2">+-- Platformer</option> +<option value="3">+--+-- 2D Platformer</option> +<option value="4">+--+-- 3D Platformer</option> +<option value="5">+--+-- 4D Platformer</option> +<option value="6"> Role-playing Game</option> +<option value="8">+-- Tactical RPG</option> +</select></td></tr> +<tr><th><label for="id_position">Position:</label></th><td><select name="position" id="id_position"> +<option value="first-child">First child</option> +<option value="last-child">Last child</option> +<option value="left">Left sibling</option> +<option value="right">Right sibling</option> +</select></td></tr> + +# TreeManager Methods ######################################################### + +>>> Genre.tree.root_node(action.tree_id) +<Genre: Action> +>>> Genre.tree.root_node(rpg.tree_id) +<Genre: Role-playing Game> +>>> Genre.tree.root_node(3) +Traceback (most recent call last): + ... +DoesNotExist: Genre matching query does not exist. + +>>> [g.name for g in Genre.tree.root_nodes()] +[u'Action', u'Role-playing Game'] + +# Model Instance Methods ###################################################### +>>> action = Genre.objects.get(pk=action.pk) +>>> [g.name for g in action.get_ancestors()] +[] +>>> [g.name for g in action.get_ancestors(ascending=True)] +[] +>>> [g.name for g in action.get_children()] +[u'Platformer'] +>>> [g.name for g in action.get_descendants()] +[u'Platformer', u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> [g.name for g in action.get_descendants(include_self=True)] +[u'Action', u'Platformer', u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> action.get_descendant_count() +4 +>>> action.get_previous_sibling() +>>> action.get_next_sibling() +<Genre: Role-playing Game> +>>> action.get_root() +<Genre: Action> +>>> [g.name for g in action.get_siblings()] +[u'Role-playing Game'] +>>> [g.name for g in action.get_siblings(include_self=True)] +[u'Action', u'Role-playing Game'] +>>> action.is_root_node() +True +>>> action.is_child_node() +False +>>> action.is_leaf_node() +False + +>>> platformer = Genre.objects.get(pk=platformer.pk) +>>> [g.name for g in platformer.get_ancestors()] +[u'Action'] +>>> [g.name for g in platformer.get_ancestors(ascending=True)] +[u'Action'] +>>> [g.name for g in platformer.get_children()] +[u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> [g.name for g in platformer.get_descendants()] +[u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> [g.name for g in platformer.get_descendants(include_self=True)] +[u'Platformer', u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> platformer.get_descendant_count() +3 +>>> platformer.get_previous_sibling() +>>> platformer.get_next_sibling() +>>> platformer.get_root() +<Genre: Action> +>>> [g.name for g in platformer.get_siblings()] +[] +>>> [g.name for g in platformer.get_siblings(include_self=True)] +[u'Platformer'] +>>> platformer.is_root_node() +False +>>> platformer.is_child_node() +True +>>> platformer.is_leaf_node() +False + +>>> platformer_3d = Genre.objects.get(pk=platformer_3d.pk) +>>> [g.name for g in platformer_3d.get_ancestors()] +[u'Action', u'Platformer'] +>>> [g.name for g in platformer_3d.get_ancestors(ascending=True)] +[u'Platformer', u'Action'] +>>> [g.name for g in platformer_3d.get_children()] +[] +>>> [g.name for g in platformer_3d.get_descendants()] +[] +>>> [g.name for g in platformer_3d.get_descendants(include_self=True)] +[u'3D Platformer'] +>>> platformer_3d.get_descendant_count() +0 +>>> platformer_3d.get_previous_sibling() +<Genre: 2D Platformer> +>>> platformer_3d.get_next_sibling() +<Genre: 4D Platformer> +>>> platformer_3d.get_root() +<Genre: Action> +>>> [g.name for g in platformer_3d.get_siblings()] +[u'2D Platformer', u'4D Platformer'] +>>> [g.name for g in platformer_3d.get_siblings(include_self=True)] +[u'2D Platformer', u'3D Platformer', u'4D Platformer'] +>>> platformer_3d.is_root_node() +False +>>> platformer_3d.is_child_node() +True +>>> platformer_3d.is_leaf_node() +True + +# The move_to method will be used in other tests to verify that it calls the +# TreeManager correctly. + +####################### +# Intra-Tree Movement # +####################### + +>>> root = Node.objects.create() +>>> c_1 = Node.objects.create(parent=root) +>>> c_1_1 = Node.objects.create(parent=c_1) +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> c_1_2 = Node.objects.create(parent=c_1) +>>> root = Node.objects.get(pk=root.pk) +>>> c_2 = Node.objects.create(parent=root) +>>> c_2_1 = Node.objects.create(parent=c_2) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> c_2_2 = Node.objects.create(parent=c_2) +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Validate exceptions are raised appropriately +>>> root = Node.objects.get(pk=root.pk) +>>> Node.tree.move_node(root, root, position='first-child') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a child of itself. +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> Node.tree.move_node(c_1, c_1_1, position='last-child') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a child of any of its descendants. +>>> Node.tree.move_node(root, root, position='right') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a sibling of itself. +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1, c_1_1, position='left') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a sibling of any of its descendants. +>>> Node.tree.move_node(c_1, c_2, position='cheese') +Traceback (most recent call last): + ... +ValueError: An invalid position was given: cheese. + +# Move up the tree using first-child +>>> c_2_2 = Node.objects.get(pk=c_2_2.pk) +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(c_2_2, c_1, 'first-child') +>>> print_tree_details([c_2_2]) +7 2 1 2 3 4 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 9 +7 2 1 2 3 4 +3 2 1 2 5 6 +4 2 1 2 7 8 +5 1 1 1 10 13 +6 5 1 2 11 12 + +# Undo the move using right +>>> c_2_1 = Node.objects.get(pk=c_2_1.pk) +>>> c_2_2.move_to(c_2_1, 'right') +>>> print_tree_details([c_2_2]) +7 5 1 2 11 12 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Move up the tree with descendants using first-child +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(c_2, c_1, 'first-child') +>>> print_tree_details([c_2]) +5 2 1 2 3 8 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 13 +5 2 1 2 3 8 +6 5 1 3 4 5 +7 5 1 3 6 7 +3 2 1 2 9 10 +4 2 1 2 11 12 + +# Undo the move using right +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(c_2, c_1, 'right') +>>> print_tree_details([c_2]) +5 1 1 1 8 13 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +COVERAGE | U1 | U> | D1 | D> +------------+----+----+----+---- +first-child | Y | Y | | +last-child | | | | +left | | | | +right | | | Y | Y + +# Move down the tree using first-child +>>> c_1_2 = Node.objects.get(pk=c_1_2.pk) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1_2, c_2, 'first-child') +>>> print_tree_details([c_1_2]) +4 5 1 2 7 8 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 5 +3 2 1 2 3 4 +5 1 1 1 6 13 +4 5 1 2 7 8 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Undo the move using last-child +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(c_1_2, c_1, 'last-child') +>>> print_tree_details([c_1_2]) +4 2 1 2 5 6 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Move down the tree with descendants using first-child +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1, c_2, 'first-child') +>>> print_tree_details([c_1]) +2 5 1 2 3 8 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +5 1 1 1 2 13 +2 5 1 2 3 8 +3 2 1 3 4 5 +4 2 1 3 6 7 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Undo the move using left +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1, c_2, 'left') +>>> print_tree_details([c_1]) +2 1 1 1 2 7 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +COVERAGE | U1 | U> | D1 | D> +------------+----+----+----+---- +first-child | Y | Y | Y | Y +last-child | Y | | | +left | | Y | | +right | | | Y | Y + +# Move up the tree using right +>>> c_2_2 = Node.objects.get(pk=c_2_2.pk) +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> Node.tree.move_node(c_2_2, c_1_1, 'right') +>>> print_tree_details([c_2_2]) +7 2 1 2 5 6 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 9 +3 2 1 2 3 4 +7 2 1 2 5 6 +4 2 1 2 7 8 +5 1 1 1 10 13 +6 5 1 2 11 12 + +# Undo the move using last-child +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_2_2, c_2, 'last-child') +>>> print_tree_details([c_2_2]) +7 5 1 2 11 12 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Move up the tree with descendants using right +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> Node.tree.move_node(c_2, c_1_1, 'right') +>>> print_tree_details([c_2]) +5 2 1 2 5 10 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 13 +3 2 1 2 3 4 +5 2 1 2 5 10 +6 5 1 3 6 7 +7 5 1 3 8 9 +4 2 1 2 11 12 + +# Undo the move using last-child +>>> root = Node.objects.get(pk=root.pk) +>>> Node.tree.move_node(c_2, root, 'last-child') +>>> print_tree_details([c_2]) +5 1 1 1 8 13 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +COVERAGE | U1 | U> | D1 | D> +------------+----+----+----+---- +first-child | Y | Y | Y | Y +last-child | Y | | Y | Y +left | | Y | | +right | Y | Y | Y | Y + +# Move down the tree with descendants using left +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> c_2_2 = Node.objects.get(pk=c_2_2.pk) +>>> Node.tree.move_node(c_1, c_2_2, 'left') +>>> print_tree_details([c_1]) +2 5 1 2 5 10 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +5 1 1 1 2 13 +6 5 1 2 3 4 +2 5 1 2 5 10 +3 2 1 3 6 7 +4 2 1 3 8 9 +7 5 1 2 11 12 + +# Undo the move using first-child +>>> root = Node.objects.get(pk=root.pk) +>>> Node.tree.move_node(c_1, root, 'first-child') +>>> print_tree_details([c_1]) +2 1 1 1 2 7 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +# Move down the tree using left +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> c_2_2 = Node.objects.get(pk=c_2_2.pk) +>>> Node.tree.move_node(c_1_1, c_2_2, 'left') +>>> print_tree_details([c_1_1]) +3 5 1 2 9 10 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 5 +4 2 1 2 3 4 +5 1 1 1 6 13 +6 5 1 2 7 8 +3 5 1 2 9 10 +7 5 1 2 11 12 + +# Undo the move using left +>>> c_1_2 = Node.objects.get(pk=c_1_2.pk) +>>> Node.tree.move_node(c_1_1, c_1_2, 'left') +>>> print_tree_details([c_1_1]) +3 2 1 2 3 4 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 + +COVERAGE | U1 | U> | D1 | D> +------------+----+----+----+---- +first-child | Y | Y | Y | Y +last-child | Y | Y | Y | Y +left | Y | Y | Y | Y +right | Y | Y | Y | Y + +I guess we're covered :) + +####################### +# Inter-Tree Movement # +####################### + +>>> new_root = Node.objects.create() +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +5 1 1 1 8 13 +6 5 1 2 9 10 +7 5 1 2 11 12 +8 - 2 0 1 2 + +# Moving child nodes between trees ############################################ + +# Move using default (last-child) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> c_2.move_to(new_root) +>>> print_tree_details([c_2]) +5 8 2 1 2 7 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 8 +2 1 1 1 2 7 +3 2 1 2 3 4 +4 2 1 2 5 6 +8 - 2 0 1 8 +5 8 2 1 2 7 +6 5 2 2 3 4 +7 5 2 2 5 6 + +# Move using left +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1_1, c_2, position='left') +>>> print_tree_details([c_1_1]) +3 8 2 1 2 3 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 6 +2 1 1 1 2 5 +4 2 1 2 3 4 +8 - 2 0 1 10 +3 8 2 1 2 3 +5 8 2 1 4 9 +6 5 2 2 5 6 +7 5 2 2 7 8 + +# Move using first-child +>>> c_1_2 = Node.objects.get(pk=c_1_2.pk) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> Node.tree.move_node(c_1_2, c_2, position='first-child') +>>> print_tree_details([c_1_2]) +4 5 2 2 5 6 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 4 +2 1 1 1 2 3 +8 - 2 0 1 12 +3 8 2 1 2 3 +5 8 2 1 4 11 +4 5 2 2 5 6 +6 5 2 2 7 8 +7 5 2 2 9 10 + +# Move using right +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(c_2, c_1, position='right') +>>> print_tree_details([c_2]) +5 1 1 1 4 11 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 12 +2 1 1 1 2 3 +5 1 1 1 4 11 +4 5 1 2 5 6 +6 5 1 2 7 8 +7 5 1 2 9 10 +8 - 2 0 1 4 +3 8 2 1 2 3 + +# Move using last-child +>>> c_1_1 = Node.objects.get(pk=c_1_1.pk) +>>> Node.tree.move_node(c_1_1, c_2, position='last-child') +>>> print_tree_details([c_1_1]) +3 5 1 2 11 12 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 14 +2 1 1 1 2 3 +5 1 1 1 4 13 +4 5 1 2 5 6 +6 5 1 2 7 8 +7 5 1 2 9 10 +3 5 1 2 11 12 +8 - 2 0 1 2 + +# Moving a root node into another tree as a child node ######################## + +# Validate exceptions are raised appropriately +>>> Node.tree.move_node(root, c_1, position='first-child') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a child of any of its descendants. +>>> Node.tree.move_node(new_root, c_1, position='cheese') +Traceback (most recent call last): + ... +ValueError: An invalid position was given: cheese. + +>>> new_root = Node.objects.get(pk=new_root.pk) +>>> c_2 = Node.objects.get(pk=c_2.pk) +>>> new_root.move_to(c_2, position='first-child') +>>> print_tree_details([new_root]) +8 5 1 2 5 6 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 16 +2 1 1 1 2 3 +5 1 1 1 4 15 +8 5 1 2 5 6 +4 5 1 2 7 8 +6 5 1 2 9 10 +7 5 1 2 11 12 +3 5 1 2 13 14 + +>>> new_root = Node.objects.create() +>>> root = Node.objects.get(pk=root.pk) +>>> Node.tree.move_node(new_root, root, position='last-child') +>>> print_tree_details([new_root]) +9 1 1 1 16 17 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 18 +2 1 1 1 2 3 +5 1 1 1 4 15 +8 5 1 2 5 6 +4 5 1 2 7 8 +6 5 1 2 9 10 +7 5 1 2 11 12 +3 5 1 2 13 14 +9 1 1 1 16 17 + +>>> new_root = Node.objects.create() +>>> c_2_1 = Node.objects.get(pk=c_2_1.pk) +>>> Node.tree.move_node(new_root, c_2_1, position='left') +>>> print_tree_details([new_root]) +10 5 1 2 9 10 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 20 +2 1 1 1 2 3 +5 1 1 1 4 17 +8 5 1 2 5 6 +4 5 1 2 7 8 +10 5 1 2 9 10 +6 5 1 2 11 12 +7 5 1 2 13 14 +3 5 1 2 15 16 +9 1 1 1 18 19 + +>>> new_root = Node.objects.create() +>>> c_1 = Node.objects.get(pk=c_1.pk) +>>> Node.tree.move_node(new_root, c_1, position='right') +>>> print_tree_details([new_root]) +11 1 1 1 4 5 +>>> print_tree_details(Node.tree.all()) +1 - 1 0 1 22 +2 1 1 1 2 3 +11 1 1 1 4 5 +5 1 1 1 6 19 +8 5 1 2 7 8 +4 5 1 2 9 10 +10 5 1 2 11 12 +6 5 1 2 13 14 +7 5 1 2 15 16 +3 5 1 2 17 18 +9 1 1 1 20 21 + +# Making nodes siblings of root nodes ######################################### + +# Validate exceptions are raised appropriately +>>> root = Node.objects.get(pk=root.pk) +>>> Node.tree.move_node(root, root, position='left') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a sibling of itself. +>>> Node.tree.move_node(root, root, position='right') +Traceback (most recent call last): + ... +InvalidMove: A node may not be made a sibling of itself. + +>>> r1 = Tree.objects.create() +>>> c1_1 = Tree.objects.create(parent=r1) +>>> c1_1_1 = Tree.objects.create(parent=c1_1) +>>> r2 = Tree.objects.create() +>>> c2_1 = Tree.objects.create(parent=r2) +>>> c2_1_1 = Tree.objects.create(parent=c2_1) +>>> r3 = Tree.objects.create() +>>> c3_1 = Tree.objects.create(parent=r3) +>>> c3_1_1 = Tree.objects.create(parent=c3_1) +>>> print_tree_details(Tree.tree.all()) +1 - 1 0 1 6 +2 1 1 1 2 5 +3 2 1 2 3 4 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +7 - 3 0 1 6 +8 7 3 1 2 5 +9 8 3 2 3 4 + +# Target < root node, left sibling +>>> r1 = Tree.objects.get(pk=r1.pk) +>>> r2 = Tree.objects.get(pk=r2.pk) +>>> r2.move_to(r1, 'left') +>>> print_tree_details([r2]) +4 - 1 0 1 6 +>>> print_tree_details(Tree.tree.all()) +4 - 1 0 1 6 +5 4 1 1 2 5 +6 5 1 2 3 4 +1 - 2 0 1 6 +2 1 2 1 2 5 +3 2 2 2 3 4 +7 - 3 0 1 6 +8 7 3 1 2 5 +9 8 3 2 3 4 + +# Target > root node, left sibling +>>> r3 = Tree.objects.get(pk=r3.pk) +>>> r2.move_to(r3, 'left') +>>> print_tree_details([r2]) +4 - 2 0 1 6 +>>> print_tree_details(Tree.tree.all()) +1 - 1 0 1 6 +2 1 1 1 2 5 +3 2 1 2 3 4 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +7 - 3 0 1 6 +8 7 3 1 2 5 +9 8 3 2 3 4 + +# Target < root node, right sibling +>>> r1 = Tree.objects.get(pk=r1.pk) +>>> r3 = Tree.objects.get(pk=r3.pk) +>>> r3.move_to(r1, 'right') +>>> print_tree_details([r3]) +7 - 2 0 1 6 +>>> print_tree_details(Tree.tree.all()) +1 - 1 0 1 6 +2 1 1 1 2 5 +3 2 1 2 3 4 +7 - 2 0 1 6 +8 7 2 1 2 5 +9 8 2 2 3 4 +4 - 3 0 1 6 +5 4 3 1 2 5 +6 5 3 2 3 4 + +# Target > root node, right sibling +>>> r1 = Tree.objects.get(pk=r1.pk) +>>> r2 = Tree.objects.get(pk=r2.pk) +>>> r1.move_to(r2, 'right') +>>> print_tree_details([r1]) +1 - 3 0 1 6 +>>> print_tree_details(Tree.tree.all()) +7 - 1 0 1 6 +8 7 1 1 2 5 +9 8 1 2 3 4 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +1 - 3 0 1 6 +2 1 3 1 2 5 +3 2 3 2 3 4 + +# No-op, root left sibling +>>> r2 = Tree.objects.get(pk=r2.pk) +>>> r2.move_to(r1, 'left') +>>> print_tree_details([r2]) +4 - 2 0 1 6 +>>> print_tree_details(Tree.tree.all()) +7 - 1 0 1 6 +8 7 1 1 2 5 +9 8 1 2 3 4 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +1 - 3 0 1 6 +2 1 3 1 2 5 +3 2 3 2 3 4 + +# No-op, root right sibling +>>> r1.move_to(r2, 'right') +>>> print_tree_details([r1]) +1 - 3 0 1 6 +>>> print_tree_details(Tree.tree.all()) +7 - 1 0 1 6 +8 7 1 1 2 5 +9 8 1 2 3 4 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +1 - 3 0 1 6 +2 1 3 1 2 5 +3 2 3 2 3 4 + +# Child node, left sibling +>>> c3_1 = Tree.objects.get(pk=c3_1.pk) +>>> c3_1.move_to(r1, 'left') +>>> print_tree_details([c3_1]) +8 - 3 0 1 4 +>>> print_tree_details(Tree.tree.all()) +7 - 1 0 1 2 +4 - 2 0 1 6 +5 4 2 1 2 5 +6 5 2 2 3 4 +8 - 3 0 1 4 +9 8 3 1 2 3 +1 - 4 0 1 6 +2 1 4 1 2 5 +3 2 4 2 3 4 + +# Child node, right sibling +>>> r3 = Tree.objects.get(pk=r3.pk) +>>> c1_1 = Tree.objects.get(pk=c1_1.pk) +>>> c1_1.move_to(r3, 'right') +>>> print_tree_details([c1_1]) +2 - 2 0 1 4 +>>> print_tree_details(Tree.tree.all()) +7 - 1 0 1 2 +2 - 2 0 1 4 +3 2 2 1 2 3 +4 - 3 0 1 6 +5 4 3 1 2 5 +6 5 3 2 3 4 +8 - 4 0 1 4 +9 8 4 1 2 3 +1 - 5 0 1 2 + +# Insertion of positioned nodes ############################################### +>>> r1 = Insert.objects.create() +>>> r2 = Insert.objects.create() +>>> r3 = Insert.objects.create() +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 2 +3 - 3 0 1 2 + +>>> r2 = Insert.objects.get(pk=r2.pk) +>>> c1 = Insert() +>>> c1 = Insert.tree.insert_node(c1, r2, commit=True) +>>> print_tree_details([c1]) +4 2 2 1 2 3 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 4 +4 2 2 1 2 3 +3 - 3 0 1 2 + +>>> c1.insert_at(r2) +Traceback (most recent call last): + ... +ValueError: Cannot insert a node which has already been saved. + +# First child +>>> r2 = Insert.objects.get(pk=r2.pk) +>>> c2 = Insert() +>>> c2 = Insert.tree.insert_node(c2, r2, position='first-child', commit=True) +>>> print_tree_details([c2]) +5 2 2 1 2 3 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 6 +5 2 2 1 2 3 +4 2 2 1 4 5 +3 - 3 0 1 2 + +# Left +>>> c1 = Insert.objects.get(pk=c1.pk) +>>> c3 = Insert() +>>> c3 = Insert.tree.insert_node(c3, c1, position='left', commit=True) +>>> print_tree_details([c3]) +6 2 2 1 4 5 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 8 +5 2 2 1 2 3 +6 2 2 1 4 5 +4 2 2 1 6 7 +3 - 3 0 1 2 + +# Right +>>> c4 = Insert() +>>> c4 = Insert.tree.insert_node(c4, c3, position='right', commit=True) +>>> print_tree_details([c4]) +7 2 2 1 6 7 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 10 +5 2 2 1 2 3 +6 2 2 1 4 5 +7 2 2 1 6 7 +4 2 2 1 8 9 +3 - 3 0 1 2 + +# Last child +>>> r2 = Insert.objects.get(pk=r2.pk) +>>> c5 = Insert() +>>> c5 = Insert.tree.insert_node(c5, r2, position='last-child', commit=True) +>>> print_tree_details([c5]) +8 2 2 1 10 11 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +2 - 2 0 1 12 +5 2 2 1 2 3 +6 2 2 1 4 5 +7 2 2 1 6 7 +4 2 2 1 8 9 +8 2 2 1 10 11 +3 - 3 0 1 2 + +# Left sibling of root +>>> r2 = Insert.objects.get(pk=r2.pk) +>>> r4 = Insert() +>>> r4 = Insert.tree.insert_node(r4, r2, position='left', commit=True) +>>> print_tree_details([r4]) +9 - 2 0 1 2 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +9 - 2 0 1 2 +2 - 3 0 1 12 +5 2 3 1 2 3 +6 2 3 1 4 5 +7 2 3 1 6 7 +4 2 3 1 8 9 +8 2 3 1 10 11 +3 - 4 0 1 2 + +# Right sibling of root +>>> r2 = Insert.objects.get(pk=r2.pk) +>>> r5 = Insert() +>>> r5 = Insert.tree.insert_node(r5, r2, position='right', commit=True) +>>> print_tree_details([r5]) +10 - 4 0 1 2 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +9 - 2 0 1 2 +2 - 3 0 1 12 +5 2 3 1 2 3 +6 2 3 1 4 5 +7 2 3 1 6 7 +4 2 3 1 8 9 +8 2 3 1 10 11 +10 - 4 0 1 2 +3 - 5 0 1 2 + +# Last root +>>> r6 = Insert() +>>> r6 = Insert.tree.insert_node(r6, None, commit=True) +>>> print_tree_details([r6]) +11 - 6 0 1 2 +>>> print_tree_details(Insert.tree.all()) +1 - 1 0 1 2 +9 - 2 0 1 2 +2 - 3 0 1 12 +5 2 3 1 2 3 +6 2 3 1 4 5 +7 2 3 1 6 7 +4 2 3 1 8 9 +8 2 3 1 10 11 +10 - 4 0 1 2 +3 - 5 0 1 2 +11 - 6 0 1 2 + +# order_insertion_by with single criterion #################################### +>>> r1 = OrderedInsertion.objects.create(name='games') + +# Root ordering +>>> r2 = OrderedInsertion.objects.create(name='food') +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +1 - 2 0 1 2 + +# Same name - insert after +>>> r3 = OrderedInsertion.objects.create(name='food') +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 2 +1 - 3 0 1 2 + +>>> c1 = OrderedInsertion.objects.create(name='zoo', parent=r3) +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 4 +4 3 2 1 2 3 +1 - 3 0 1 2 + +>>> r3 = OrderedInsertion.objects.get(pk=r3.pk) +>>> c2 = OrderedInsertion.objects.create(name='monkey', parent=r3) +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 6 +5 3 2 1 2 3 +4 3 2 1 4 5 +1 - 3 0 1 2 + +>>> r3 = OrderedInsertion.objects.get(pk=r3.pk) +>>> c3 = OrderedInsertion.objects.create(name='animal', parent=r3) +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 8 +6 3 2 1 2 3 +5 3 2 1 4 5 +4 3 2 1 6 7 +1 - 3 0 1 2 + +# order_insertion_by reparenting with single criterion ######################## + +# Root -> child +>>> r1 = OrderedInsertion.objects.get(pk=r1.pk) +>>> r3 = OrderedInsertion.objects.get(pk=r3.pk) +>>> r1.parent = r3 +>>> r1.save() +>>> print_tree_details(OrderedInsertion.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 10 +6 3 2 1 2 3 +1 3 2 1 4 5 +5 3 2 1 6 7 +4 3 2 1 8 9 + +# Child -> root +>>> c3 = OrderedInsertion.objects.get(pk=c3.pk) +>>> c3.parent = None +>>> c3.save() +>>> print_tree_details(OrderedInsertion.tree.all()) +6 - 1 0 1 2 +2 - 2 0 1 2 +3 - 3 0 1 8 +1 3 3 1 2 3 +5 3 3 1 4 5 +4 3 3 1 6 7 + +# Child -> child +>>> c1 = OrderedInsertion.objects.get(pk=c1.pk) +>>> c1.parent = c3 +>>> c1.save() +>>> print_tree_details(OrderedInsertion.tree.all()) +6 - 1 0 1 4 +4 6 1 1 2 3 +2 - 2 0 1 2 +3 - 3 0 1 6 +1 3 3 1 2 3 +5 3 3 1 4 5 +>>> c3 = OrderedInsertion.objects.get(pk=c3.pk) +>>> c2 = OrderedInsertion.objects.get(pk=c2.pk) +>>> c2.parent = c3 +>>> c2.save() +>>> print_tree_details(OrderedInsertion.tree.all()) +6 - 1 0 1 6 +5 6 1 1 2 3 +4 6 1 1 4 5 +2 - 2 0 1 2 +3 - 3 0 1 4 +1 3 3 1 2 3 + +# Insertion of positioned nodes, multiple ordering criteria ################### +>>> r1 = MultiOrder.objects.create(name='fff', size=20, date=date(2008, 1, 1)) + +# Root nodes - ordering by subsequent fields +>>> r2 = MultiOrder.objects.create(name='fff', size=10, date=date(2009, 1, 1)) +>>> print_tree_details(MultiOrder.tree.all()) +2 - 1 0 1 2 +1 - 2 0 1 2 + +>>> r3 = MultiOrder.objects.create(name='fff', size=20, date=date(2007, 1, 1)) +>>> print_tree_details(MultiOrder.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 2 +1 - 3 0 1 2 + +>>> r4 = MultiOrder.objects.create(name='fff', size=20, date=date(2008, 1, 1)) +>>> print_tree_details(MultiOrder.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 2 +1 - 3 0 1 2 +4 - 4 0 1 2 + +>>> r5 = MultiOrder.objects.create(name='fff', size=20, date=date(2007, 1, 1)) +>>> print_tree_details(MultiOrder.tree.all()) +2 - 1 0 1 2 +3 - 2 0 1 2 +5 - 3 0 1 2 +1 - 4 0 1 2 +4 - 5 0 1 2 + +>>> r6 = MultiOrder.objects.create(name='aaa', size=999, date=date(2010, 1, 1)) +>>> print_tree_details(MultiOrder.tree.all()) +6 - 1 0 1 2 +2 - 2 0 1 2 +3 - 3 0 1 2 +5 - 4 0 1 2 +1 - 5 0 1 2 +4 - 6 0 1 2 + +# Child nodes +>>> r1 = MultiOrder.objects.get(pk=r1.pk) +>>> c1 = MultiOrder.objects.create(parent=r1, name='hhh', size=10, date=date(2009, 1, 1)) +>>> print_tree_details(MultiOrder.tree.filter(tree_id=r1.tree_id)) +1 - 5 0 1 4 +7 1 5 1 2 3 + +>>> r1 = MultiOrder.objects.get(pk=r1.pk) +>>> c2 = MultiOrder.objects.create(parent=r1, name='hhh', size=20, date=date(2008, 1, 1)) +>>> print_tree_details(MultiOrder.tree.filter(tree_id=r1.tree_id)) +1 - 5 0 1 6 +7 1 5 1 2 3 +8 1 5 1 4 5 + +>>> r1 = MultiOrder.objects.get(pk=r1.pk) +>>> c3 = MultiOrder.objects.create(parent=r1, name='hhh', size=15, date=date(2008, 1, 1)) +>>> print_tree_details(MultiOrder.tree.filter(tree_id=r1.tree_id)) +1 - 5 0 1 8 +7 1 5 1 2 3 +9 1 5 1 4 5 +8 1 5 1 6 7 + +>>> r1 = MultiOrder.objects.get(pk=r1.pk) +>>> c4 = MultiOrder.objects.create(parent=r1, name='hhh', size=15, date=date(2008, 1, 1)) +>>> print_tree_details(MultiOrder.tree.filter(tree_id=r1.tree_id)) +1 - 5 0 1 10 +7 1 5 1 2 3 +9 1 5 1 4 5 +10 1 5 1 6 7 +8 1 5 1 8 9 +"""
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/fixtures/categories.json @@ -0,0 +1,122 @@ +[ + { + "pk": 1, + "model": "tests.category", + "fields": { + "rght": 20, + "name": "PC & Video Games", + "parent": null, + "level": 0, + "lft": 1, + "tree_id": 1 + } + }, + { + "pk": 2, + "model": "tests.category", + "fields": { + "rght": 7, + "name": "Nintendo Wii", + "parent": 1, + "level": 1, + "lft": 2, + "tree_id": 1 + } + }, + { + "pk": 3, + "model": "tests.category", + "fields": { + "rght": 4, + "name": "Games", + "parent": 2, + "level": 2, + "lft": 3, + "tree_id": 1 + } + }, + { + "pk": 4, + "model": "tests.category", + "fields": { + "rght": 6, + "name": "Hardware & Accessories", + "parent": 2, + "level": 2, + "lft": 5, + "tree_id": 1 + } + }, + { + "pk": 5, + "model": "tests.category", + "fields": { + "rght": 13, + "name": "Xbox 360", + "parent": 1, + "level": 1, + "lft": 8, + "tree_id": 1 + } + }, + { + "pk": 6, + "model": "tests.category", + "fields": { + "rght": 10, + "name": "Games", + "parent": 5, + "level": 2, + "lft": 9, + "tree_id": 1 + } + }, + { + "pk": 7, + "model": "tests.category", + "fields": { + "rght": 12, + "name": "Hardware & Accessories", + "parent": 5, + "level": 2, + "lft": 11, + "tree_id": 1 + } + }, + { + "pk": 8, + "model": "tests.category", + "fields": { + "rght": 19, + "name": "PlayStation 3", + "parent": 1, + "level": 1, + "lft": 14, + "tree_id": 1 + } + }, + { + "pk": 9, + "model": "tests.category", + "fields": { + "rght": 16, + "name": "Games", + "parent": 8, + "level": 2, + "lft": 15, + "tree_id": 1 + } + }, + { + "pk": 10, + "model": "tests.category", + "fields": { + "rght": 18, + "name": "Hardware & Accessories", + "parent": 8, + "level": 2, + "lft": 17, + "tree_id": 1 + } + } +]
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/fixtures/genres.json @@ -0,0 +1,134 @@ +[ + { + "pk": 1, + "model": "tests.genre", + "fields": { + "rght": 16, + "name": "Action", + "parent": null, + "level": 0, + "lft": 1, + "tree_id": 1 + } + }, + { + "pk": 2, + "model": "tests.genre", + "fields": { + "rght": 9, + "name": "Platformer", + "parent": 1, + "level": 1, + "lft": 2, + "tree_id": 1 + } + }, + { + "pk": 3, + "model": "tests.genre", + "fields": { + "rght": 4, + "name": "2D Platformer", + "parent": 2, + "level": 2, + "lft": 3, + "tree_id": 1 + } + }, + { + "pk": 4, + "model": "tests.genre", + "fields": { + "rght": 6, + "name": "3D Platformer", + "parent": 2, + "level": 2, + "lft": 5, + "tree_id": 1 + } + }, + { + "pk": 5, + "model": "tests.genre", + "fields": { + "rght": 8, + "name": "4D Platformer", + "parent": 2, + "level": 2, + "lft": 7, + "tree_id": 1 + } + }, + { + "pk": 6, + "model": "tests.genre", + "fields": { + "rght": 15, + "name": "Shootemup", + "parent": 1, + "level": 1, + "lft": 10, + "tree_id": 1 + } + }, + { + "pk": 7, + "model": "tests.genre", + "fields": { + "rght": 12, + "name": "Vertical Scrolling Shootemup", + "parent": 6, + "level": 2, + "lft": 11, + "tree_id": 1 + } + }, + { + "pk": 8, + "model": "tests.genre", + "fields": { + "rght": 14, + "name": "Horizontal Scrolling Shootemup", + "parent": 6, + "level": 2, + "lft": 13, + "tree_id": 1 + } + }, + { + "pk": 9, + "model": "tests.genre", + "fields": { + "rght": 6, + "name": "Role-playing Game", + "parent": null, + "level": 0, + "lft": 1, + "tree_id": 2 + } + }, + { + "pk": 10, + "model": "tests.genre", + "fields": { + "rght": 3, + "name": "Action RPG", + "parent": 9, + "level": 1, + "lft": 2, + "tree_id": 2 + } + }, + { + "pk": 11, + "model": "tests.genre", + "fields": { + "rght": 5, + "name": "Tactical RPG", + "parent": 9, + "level": 1, + "lft": 4, + "tree_id": 2 + } + } +]
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/models.py @@ -0,0 +1,54 @@ +from django.db import models + +import mptt + +class Category(models.Model): + name = models.CharField(max_length=50) + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + + def __unicode__(self): + return self.name + + def delete(self): + super(Category, self).delete() + +class Genre(models.Model): + name = models.CharField(max_length=50, unique=True) + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + + def __unicode__(self): + return self.name + +class Insert(models.Model): + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + +class MultiOrder(models.Model): + name = models.CharField(max_length=50) + size = models.PositiveIntegerField() + date = models.DateField() + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + + def __unicode__(self): + return self.name + +class Node(models.Model): + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + +class OrderedInsertion(models.Model): + name = models.CharField(max_length=50) + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + + def __unicode__(self): + return self.name + +class Tree(models.Model): + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + +mptt.register(Category) +mptt.register(Genre) +mptt.register(Insert) +mptt.register(MultiOrder, order_insertion_by=['name', 'size', 'date']) +mptt.register(Node, left_attr='does', right_attr='zis', level_attr='madness', + tree_id_attr='work') +mptt.register(OrderedInsertion, order_insertion_by=['name']) +mptt.register(Tree)
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/settings.py @@ -0,0 +1,27 @@ +import os + +DIRNAME = os.path.dirname(__file__) + +DEBUG = True + +DATABASE_ENGINE = 'sqlite3' +DATABASE_NAME = os.path.join(DIRNAME, 'mptt.db') + +#DATABASE_ENGINE = 'mysql' +#DATABASE_NAME = 'mptt_test' +#DATABASE_USER = 'root' +#DATABASE_PASSWORD = '' +#DATABASE_HOST = 'localhost' +#DATABASE_PORT = '3306' + +#DATABASE_ENGINE = 'postgresql_psycopg2' +#DATABASE_NAME = 'mptt_test' +#DATABASE_USER = 'postgres' +#DATABASE_PASSWORD = '' +#DATABASE_HOST = 'localhost' +#DATABASE_PORT = '5432' + +INSTALLED_APPS = ( + 'mptt', + 'mptt.tests', +)
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/testcases.py @@ -0,0 +1,309 @@ +import re + +from django.test import TestCase + +from mptt.exceptions import InvalidMove +from mptt.tests import doctests +from mptt.tests.models import Category, Genre + +def get_tree_details(nodes): + """Creates pertinent tree details for the given list of nodes.""" + opts = nodes[0]._meta + return '\n'.join(['%s %s %s %s %s %s' % + (n.pk, getattr(n, '%s_id' % opts.parent_attr) or '-', + getattr(n, opts.tree_id_attr), getattr(n, opts.level_attr), + getattr(n, opts.left_attr), getattr(n, opts.right_attr)) + for n in nodes]) + +leading_whitespace_re = re.compile(r'^\s+', re.MULTILINE) + +def tree_details(text): + """ + Trims leading whitespace from the given text specifying tree details + so triple-quoted strings can be used to provide tree details in a + readable format (says who?), to be compared with the result of using + the ``get_tree_details`` function. + """ + return leading_whitespace_re.sub('', text) + +# genres.json defines the following tree structure +# +# 1 - 1 0 1 16 action +# 2 1 1 1 2 9 +-- platformer +# 3 2 1 2 3 4 | |-- platformer_2d +# 4 2 1 2 5 6 | |-- platformer_3d +# 5 2 1 2 7 8 | +-- platformer_4d +# 6 1 1 1 10 15 +-- shmup +# 7 6 1 2 11 12 |-- shmup_vertical +# 8 6 1 2 13 14 +-- shmup_horizontal +# 9 - 2 0 1 6 rpg +# 10 9 2 1 2 3 |-- arpg +# 11 9 2 1 4 5 +-- trpg + +class ReparentingTestCase(TestCase): + """ + Test that trees are in the appropriate state after reparenting and + that reparented items have the correct tree attributes defined, + should they be required for use after a save. + """ + fixtures = ['genres.json'] + + def test_new_root_from_subtree(self): + shmup = Genre.objects.get(id=6) + shmup.parent = None + shmup.save() + self.assertEqual(get_tree_details([shmup]), '6 - 3 0 1 6') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 10 + 2 1 1 1 2 9 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 2 1 2 7 8 + 9 - 2 0 1 6 + 10 9 2 1 2 3 + 11 9 2 1 4 5 + 6 - 3 0 1 6 + 7 6 3 1 2 3 + 8 6 3 1 4 5""")) + + def test_new_root_from_leaf_with_siblings(self): + platformer_2d = Genre.objects.get(id=3) + platformer_2d.parent = None + platformer_2d.save() + self.assertEqual(get_tree_details([platformer_2d]), '3 - 3 0 1 2') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 14 + 2 1 1 1 2 7 + 4 2 1 2 3 4 + 5 2 1 2 5 6 + 6 1 1 1 8 13 + 7 6 1 2 9 10 + 8 6 1 2 11 12 + 9 - 2 0 1 6 + 10 9 2 1 2 3 + 11 9 2 1 4 5 + 3 - 3 0 1 2""")) + + def test_new_child_from_root(self): + action = Genre.objects.get(id=1) + rpg = Genre.objects.get(id=9) + action.parent = rpg + action.save() + self.assertEqual(get_tree_details([action]), '1 9 2 1 6 21') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""9 - 2 0 1 22 + 10 9 2 1 2 3 + 11 9 2 1 4 5 + 1 9 2 1 6 21 + 2 1 2 2 7 14 + 3 2 2 3 8 9 + 4 2 2 3 10 11 + 5 2 2 3 12 13 + 6 1 2 2 15 20 + 7 6 2 3 16 17 + 8 6 2 3 18 19""")) + + def test_move_leaf_to_other_tree(self): + shmup_horizontal = Genre.objects.get(id=8) + rpg = Genre.objects.get(id=9) + shmup_horizontal.parent = rpg + shmup_horizontal.save() + self.assertEqual(get_tree_details([shmup_horizontal]), '8 9 2 1 6 7') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 14 + 2 1 1 1 2 9 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 2 1 2 7 8 + 6 1 1 1 10 13 + 7 6 1 2 11 12 + 9 - 2 0 1 8 + 10 9 2 1 2 3 + 11 9 2 1 4 5 + 8 9 2 1 6 7""")) + + def test_move_subtree_to_other_tree(self): + shmup = Genre.objects.get(id=6) + trpg = Genre.objects.get(id=11) + shmup.parent = trpg + shmup.save() + self.assertEqual(get_tree_details([shmup]), '6 11 2 2 5 10') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 10 + 2 1 1 1 2 9 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 2 1 2 7 8 + 9 - 2 0 1 12 + 10 9 2 1 2 3 + 11 9 2 1 4 11 + 6 11 2 2 5 10 + 7 6 2 3 6 7 + 8 6 2 3 8 9""")) + + def test_move_child_up_level(self): + shmup_horizontal = Genre.objects.get(id=8) + action = Genre.objects.get(id=1) + shmup_horizontal.parent = action + shmup_horizontal.save() + self.assertEqual(get_tree_details([shmup_horizontal]), '8 1 1 1 14 15') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 16 + 2 1 1 1 2 9 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 2 1 2 7 8 + 6 1 1 1 10 13 + 7 6 1 2 11 12 + 8 1 1 1 14 15 + 9 - 2 0 1 6 + 10 9 2 1 2 3 + 11 9 2 1 4 5""")) + + def test_move_subtree_down_level(self): + shmup = Genre.objects.get(id=6) + platformer = Genre.objects.get(id=2) + shmup.parent = platformer + shmup.save() + self.assertEqual(get_tree_details([shmup]), '6 2 1 2 9 14') + self.assertEqual(get_tree_details(Genre.tree.all()), + tree_details("""1 - 1 0 1 16 + 2 1 1 1 2 15 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 2 1 2 7 8 + 6 2 1 2 9 14 + 7 6 1 3 10 11 + 8 6 1 3 12 13 + 9 - 2 0 1 6 + 10 9 2 1 2 3 + 11 9 2 1 4 5""")) + + def test_invalid_moves(self): + # A node may not be made a child of itself + action = Genre.objects.get(id=1) + action.parent = action + platformer = Genre.objects.get(id=2) + platformer.parent = platformer + self.assertRaises(InvalidMove, action.save) + self.assertRaises(InvalidMove, platformer.save) + + # A node may not be made a child of any of its descendants + platformer_4d = Genre.objects.get(id=5) + action.parent = platformer_4d + platformer.parent = platformer_4d + self.assertRaises(InvalidMove, action.save) + self.assertRaises(InvalidMove, platformer.save) + + # New parent is still set when an error occurs + self.assertEquals(action.parent, platformer_4d) + self.assertEquals(platformer.parent, platformer_4d) + +# categories.json defines the following tree structure: +# +# 1 - 1 0 1 20 games +# 2 1 1 1 2 7 +-- wii +# 3 2 1 2 3 4 | |-- wii_games +# 4 2 1 2 5 6 | +-- wii_hardware +# 5 1 1 1 8 13 +-- xbox360 +# 6 5 1 2 9 10 | |-- xbox360_games +# 7 5 1 2 11 12 | +-- xbox360_hardware +# 8 1 1 1 14 19 +-- ps3 +# 9 8 1 2 15 16 |-- ps3_games +# 10 8 1 2 17 18 +-- ps3_hardware + +class DeletionTestCase(TestCase): + """ + Tests that the tree structure is maintained appropriately in various + deletion scenrios. + """ + fixtures = ['categories.json'] + + def test_delete_root_node(self): + # Add a few other roots to verify that they aren't affected + Category(name='Preceding root').insert_at(Category.objects.get(id=1), + 'left', commit=True) + Category(name='Following root').insert_at(Category.objects.get(id=1), + 'right', commit=True) + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""11 - 1 0 1 2 + 1 - 2 0 1 20 + 2 1 2 1 2 7 + 3 2 2 2 3 4 + 4 2 2 2 5 6 + 5 1 2 1 8 13 + 6 5 2 2 9 10 + 7 5 2 2 11 12 + 8 1 2 1 14 19 + 9 8 2 2 15 16 + 10 8 2 2 17 18 + 12 - 3 0 1 2"""), + 'Setup for test produced unexpected result') + + Category.objects.get(id=1).delete() + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""11 - 1 0 1 2 + 12 - 3 0 1 2""")) + + def test_delete_last_node_with_siblings(self): + Category.objects.get(id=9).delete() + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""1 - 1 0 1 18 + 2 1 1 1 2 7 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 1 1 1 8 13 + 6 5 1 2 9 10 + 7 5 1 2 11 12 + 8 1 1 1 14 17 + 10 8 1 2 15 16""")) + + def test_delete_last_node_with_descendants(self): + Category.objects.get(id=8).delete() + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""1 - 1 0 1 14 + 2 1 1 1 2 7 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 1 1 1 8 13 + 6 5 1 2 9 10 + 7 5 1 2 11 12""")) + + def test_delete_node_with_siblings(self): + Category.objects.get(id=6).delete() + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""1 - 1 0 1 18 + 2 1 1 1 2 7 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 5 1 1 1 8 11 + 7 5 1 2 9 10 + 8 1 1 1 12 17 + 9 8 1 2 13 14 + 10 8 1 2 15 16""")) + + def test_delete_node_with_descendants_and_siblings(self): + """ + Regression test for Issue 23 - we used to use pre_delete, which + resulted in tree cleanup being performed for every node being + deleted, rather than just the node on which ``delete()`` was + called. + """ + Category.objects.get(id=5).delete() + self.assertEqual(get_tree_details(Category.tree.all()), + tree_details("""1 - 1 0 1 14 + 2 1 1 1 2 7 + 3 2 1 2 3 4 + 4 2 1 2 5 6 + 8 1 1 1 8 13 + 9 8 1 2 9 10 + 10 8 1 2 11 12""")) + +class IntraTreeMovementTestCase(TestCase): + pass + +class InterTreeMovementTestCase(TestCase): + pass + +class PositionedInsertionTestCase(TestCase): + pass
new file mode 100644 --- /dev/null +++ b/apps/mptt/tests/tests.py @@ -0,0 +1,11 @@ +import doctest +import unittest + +from mptt.tests import doctests +from mptt.tests import testcases + +def suite(): + s = unittest.TestSuite() + s.addTest(doctest.DocTestSuite(doctests)) + s.addTest(unittest.defaultTestLoader.loadTestsFromModule(testcases)) + return s
new file mode 100644 --- /dev/null +++ b/apps/mptt/utils.py @@ -0,0 +1,134 @@ +""" +Utilities for working with lists of model instances which represent +trees. +""" +import copy +import itertools + +__all__ = ('previous_current_next', 'tree_item_iterator', + 'drilldown_tree_for_node') + +def previous_current_next(items): + """ + From http://www.wordaligned.org/articles/zippy-triples-served-with-python + + Creates an iterator which returns (previous, current, next) triples, + with ``None`` filling in when there is no previous or next + available. + """ + extend = itertools.chain([None], items, [None]) + previous, current, next = itertools.tee(extend, 3) + try: + current.next() + next.next() + next.next() + except StopIteration: + pass + return itertools.izip(previous, current, next) + +def tree_item_iterator(items, ancestors=False): + """ + Given a list of tree items, iterates over the list, generating + two-tuples of the current tree item and a ``dict`` containing + information about the tree structure around the item, with the + following keys: + + ``'new_level'` + ``True`` if the current item is the start of a new level in + the tree, ``False`` otherwise. + + ``'closed_levels'`` + A list of levels which end after the current item. This will + be an empty list if the next item is at the same level as the + current item. + + If ``ancestors`` is ``True``, the following key will also be + available: + + ``'ancestors'`` + A list of unicode representations of the ancestors of the + current node, in descending order (root node first, immediate + parent last). + + For example: given the sample tree below, the contents of the + list which would be available under the ``'ancestors'`` key + are given on the right:: + + Books -> [] + Sci-fi -> [u'Books'] + Dystopian Futures -> [u'Books', u'Sci-fi'] + + """ + structure = {} + opts = None + for previous, current, next in previous_current_next(items): + if opts is None: + opts = current._meta + + current_level = getattr(current, opts.level_attr) + if previous: + structure['new_level'] = (getattr(previous, + opts.level_attr) < current_level) + if ancestors: + # If the previous node was the end of any number of + # levels, remove the appropriate number of ancestors + # from the list. + if structure['closed_levels']: + structure['ancestors'] = \ + structure['ancestors'][:-len(structure['closed_levels'])] + # If the current node is the start of a new level, add its + # parent to the ancestors list. + if structure['new_level']: + structure['ancestors'].append(unicode(previous)) + else: + structure['new_level'] = True + if ancestors: + # Set up the ancestors list on the first item + structure['ancestors'] = [] + + if next: + structure['closed_levels'] = range(current_level, + getattr(next, + opts.level_attr), -1) + else: + # All remaining levels need to be closed + structure['closed_levels'] = range(current_level, -1, -1) + + # Return a deep copy of the structure dict so this function can + # be used in situations where the iterator is consumed + # immediately. + yield current, copy.deepcopy(structure) + +def drilldown_tree_for_node(node, rel_cls=None, rel_field=None, count_attr=None, + cumulative=False): + """ + Creates a drilldown tree for the given node. A drilldown tree + consists of a node's ancestors, itself and its immediate children, + all in tree order. + + Optional arguments may be given to specify a ``Model`` class which + is related to the node's class, for the purpose of adding related + item counts to the node's children: + + ``rel_cls`` + A ``Model`` class which has a relation to the node's class. + + ``rel_field`` + The name of the field in ``rel_cls`` which holds the relation + to the node's class. + + ``count_attr`` + The name of an attribute which should be added to each child in + the drilldown tree, containing a count of how many instances + of ``rel_cls`` are related through ``rel_field``. + + ``cumulative`` + If ``True``, the count will be for each child and all of its + descendants, otherwise it will be for each child itself. + """ + if rel_cls and rel_field and count_attr: + children = node._tree_manager.add_related_count( + node.get_children(), rel_cls, rel_field, count_attr, cumulative) + else: + children = node.get_children() + return itertools.chain(node.get_ancestors(), [node], children)
new file mode 100644 --- /dev/null +++ b/apps/snippet/forms.py @@ -0,0 +1,109 @@ +from django import forms +from django.conf import settings +from django.utils.translation import ugettext_lazy as _ +from agora.apps.snippet.models import Snippet +from agora.apps.snippet.highlight import LEXER_LIST_ALL, LEXER_LIST, LEXER_DEFAULT +import datetime + +#=============================================================================== +# Snippet Form and Handling +#=============================================================================== + +EXPIRE_CHOICES = ( + (3600, _(u'In one hour')), + (3600*24*7, _(u'In one week')), + (3600*24*30, _(u'In one month')), + (3600*24*30*12*100, _(u'Save forever')), # 100 years, I call it forever ;) +) + +EXPIRE_DEFAULT = 3600*24*30 + +class SnippetForm(forms.ModelForm): + + lexer = forms.ChoiceField( + choices=LEXER_LIST, + initial=LEXER_DEFAULT, + label=_(u'Lexer'), + ) + + expire_options = forms.ChoiceField( + choices=EXPIRE_CHOICES, + initial=EXPIRE_DEFAULT, + label=_(u'Expires'), + ) + + def __init__(self, request, *args, **kwargs): + super(SnippetForm, self).__init__(*args, **kwargs) + self.request = request + + try: + if self.request.session['userprefs'].get('display_all_lexer', False): + self.fields['lexer'].choices = LEXER_LIST_ALL + except KeyError: + pass + + try: + self.fields['author'].initial = self.request.session['userprefs'].get('default_name', '') + except KeyError: + pass + + def save(self, parent=None, *args, **kwargs): + + # Set parent snippet + if parent: + self.instance.parent = parent + + # Add expire datestamp + self.instance.expires = datetime.datetime.now() + \ + datetime.timedelta(seconds=int(self.cleaned_data['expire_options'])) + + # Save snippet in the db + super(SnippetForm, self).save(*args, **kwargs) + + # Add the snippet to the user session list + if self.request.session.get('snippet_list', False): + if len(self.request.session['snippet_list']) >= getattr(settings, 'MAX_SNIPPETS_PER_USER', 10): + self.request.session['snippet_list'].pop(0) + self.request.session['snippet_list'] += [self.instance.pk] + else: + self.request.session['snippet_list'] = [self.instance.pk] + + return self.request, self.instance + + class Meta: + model = Snippet + fields = ( + 'title', + 'content', + 'author', + 'lexer', + ) + + +#=============================================================================== +# User Settings +#=============================================================================== + +USERPREFS_FONT_CHOICES = [(None, _(u'Default'))] + [ + (i, i) for i in sorted(( + 'Monaco', + 'Bitstream Vera Sans Mono', + 'Courier New', + 'Consolas', + )) +] + +USERPREFS_SIZES = [(None, _(u'Default'))] + [(i, '%dpx' % i) for i in range(5, 25)] + +class UserSettingsForm(forms.Form): + + default_name = forms.CharField(label=_(u'Default Name'), required=False) + display_all_lexer = forms.BooleanField( + label=_(u'Display all lexer'), + required=False, + widget=forms.CheckboxInput, + help_text=_(u'This also enables the super secret \'guess lexer\' function.'), + ) + font_family = forms.ChoiceField(label=_(u'Font Family'), required=False, choices=USERPREFS_FONT_CHOICES) + font_size = forms.ChoiceField(label=_(u'Font Size'), required=False, choices=USERPREFS_SIZES) + line_height = forms.ChoiceField(label=_(u'Line Height'), required=False, choices=USERPREFS_SIZES)
new file mode 100644 --- /dev/null +++ b/apps/snippet/highlight.py @@ -0,0 +1,34 @@ +from pygments.lexers import get_all_lexers, get_lexer_by_name, guess_lexer +from pygments.styles import get_all_styles +from pygments.formatters import HtmlFormatter +from pygments.util import ClassNotFound +from pygments import highlight + +LEXER_LIST_ALL = sorted([(i[1][0], i[0]) for i in get_all_lexers()]) +LEXER_LIST = ( + ('c', 'C'), + ('c++', 'C++'), + ('matlab', 'MATLAB'), + ('octave', 'Octave'), + ('perl', 'Perl'), + ('php', 'PHP'), + ('text', 'Text only'), +) +LEXER_DEFAULT = 'octave' + + +class NakedHtmlFormatter(HtmlFormatter): + def wrap(self, source, outfile): + return self._wrap_code(source) + def _wrap_code(self, source): + for i, t in source: + yield i, t + +def pygmentize(code_string, lexer_name='text'): + return highlight(code_string, get_lexer_by_name(lexer_name), NakedHtmlFormatter()) + +def guess_code_lexer(code_string, default_lexer='unknown'): + try: + return guess_lexer(code_string).name + except ClassNotFound: + return default_lexer
--- a/apps/snippet/models.py +++ b/apps/snippet/models.py @@ -1,18 +1,52 @@ +import datetime +import difflib +import random +import agora.apps.mptt as mptt from django.db import models -from django.contrib.auth.models import User +from django.db.models import permalink +from django.utils.translation import ugettext_lazy as _ +from agora.apps.snippet.highlight import LEXER_DEFAULT, pygmentize + +t = 'abcdefghijkmnopqrstuvwwxyzABCDEFGHIJKLOMNOPQRSTUVWXYZ1234567890' +def generate_secret_id(length=4): + return ''.join([random.choice(t) for i in range(length)]) class Snippet(models.Model): - code = models.TextField(max_length=32768) - name = models.CharField(max_length=256) - description = models.TextField(max_length=1024) - uploader = models.ForeignKey(User) - pub_date = models.DateTimeField('date uploaded') - mod_date = models.DateTimeField('date last modified') + secret_id = models.CharField(_(u'Secret ID'), max_length=4, blank=True) + title = models.CharField(_(u'Title'), max_length=120, blank=True) + author = models.CharField(_(u'Author'), max_length=30, blank=True) + content = models.TextField(_(u'Content'), ) + content_highlighted = models.TextField(_(u'Highlighted Content'), blank=True) + lexer = models.CharField(_(u'Lexer'), max_length=30, default=LEXER_DEFAULT) + published = models.DateTimeField(_(u'Published'), blank=True) + expires = models.DateTimeField(_(u'Expires'), blank=True, help_text='asdf') + parent = models.ForeignKey('self', null=True, blank=True, related_name='children') + + class Meta: + ordering = ('-published',) + + def get_linecount(self): + return len(self.content.splitlines()) + + def content_splitted(self): + return self.content_highlighted.splitlines() + + def save(self, *args, **kwargs): + if not self.pk: + self.published = datetime.datetime.now() + self.secret_id = generate_secret_id() + self.content_highlighted = pygmentize(self.content, self.lexer) + super(Snippet, self).save(*args, **kwargs) + + @permalink + def get_absolute_url(self): + return ('snippet_details', (self.secret_id,)) def __unicode__(self): - if self.name: - return self.name - return self.id + return '%s' % self.secret_id + +mptt.register(Snippet, order_insertion_by=['content']) + class CodeLanguage(models.Model): name = models.CharField(max_length=64)
new file mode 100644 --- /dev/null +++ b/apps/snippet/templatetags/__init__.py @@ -0,0 +1,1 @@ +__version__ = '0.1'
new file mode 100644 --- /dev/null +++ b/apps/snippet/templatetags/snippet_tags.py @@ -0,0 +1,7 @@ +from django.template import Library + +register = Library() + +@register.filter +def in_list(value,arg): + return value in arg
new file mode 100644 --- /dev/null +++ b/apps/snippet/urls.py @@ -0,0 +1,31 @@ +from django.conf.urls.defaults import patterns, url +from django.conf import settings + +urlpatterns = patterns('agora.apps.snippet.views', + url(r'^$', + 'snippet_new', name='snippet_new'), + + url(r'^guess/$', + 'guess_lexer', name='snippet_guess_lexer'), + + url(r'^diff/$', + 'snippet_diff', name='snippet_diff'), + + url(r'^your-latest/$', + 'snippet_userlist', name='snippet_userlist'), + + url(r'^your-settings/$', + 'userprefs', name='snippet_userprefs'), + + url(r'^(?P<snippet_id>[a-zA-Z0-9]{4})/$', + 'snippet_details', name='snippet_details'), + + url(r'^(?P<snippet_id>[a-zA-Z0-9]{4})/delete/$', + 'snippet_delete', name='snippet_delete'), + + url(r'^(?P<snippet_id>[a-zA-Z0-9]{4})/raw/$', + 'snippet_details', + {'template_name': 'dpaste/snippet_details_raw.html', + 'is_raw': True}, + name='snippet_details_raw'), +)
--- a/apps/snippet/views.py +++ b/apps/snippet/views.py @@ -1,1 +1,169 @@ -# Create your views here. +from django.shortcuts import render_to_response, \ + get_object_or_404, get_list_or_404 +from django.template.context \ + import RequestContext +from django.http \ + import HttpResponseRedirect, HttpResponseBadRequest, \ + HttpResponse, HttpResponseForbidden +from django.conf import settings +from django.core.exceptions import ObjectDoesNotExist +from django.utils.translation import ugettext_lazy as _ +from agora.apps.snippet.forms import SnippetForm, UserSettingsForm +from agora.apps.snippet.models import Snippet +from agora.apps.snippet.highlight import pygmentize, guess_code_lexer +from django.core.urlresolvers import reverse +from django.utils import simplejson +import difflib + +def snippet_new(request, template_name='snippet/snippet_new.html'): + + if request.method == "POST": + snippet_form = SnippetForm(data=request.POST, request=request) + if snippet_form.is_valid(): + request, new_snippet = snippet_form.save() + return HttpResponseRedirect(new_snippet.get_absolute_url()) + else: + snippet_form = SnippetForm(request=request) + + template_context = { + 'snippet_form': snippet_form, + } + + return render_to_response( + template_name, + template_context, + RequestContext(request) + ) + + +def snippet_details(request, snippet_id, template_name='snippet/snippet_details.html', is_raw=False): + + snippet = get_object_or_404(Snippet, secret_id=snippet_id) + + tree = snippet.get_root() + tree = tree.get_descendants(include_self=True) + + new_snippet_initial = { + 'content': snippet.content, + 'lexer': snippet.lexer, + } + + if request.method == "POST": + snippet_form = SnippetForm(data=request.POST, request=request, initial=new_snippet_initial) + if snippet_form.is_valid(): + request, new_snippet = snippet_form.save(parent=snippet) + return HttpResponseRedirect(new_snippet.get_absolute_url()) + else: + snippet_form = SnippetForm(initial=new_snippet_initial, request=request) + + template_context = { + 'snippet_form': snippet_form, + 'snippet': snippet, + 'lines': range(snippet.get_linecount()), + 'tree': tree, + } + + response = render_to_response( + template_name, + template_context, + RequestContext(request) + ) + + if is_raw: + response['Content-Type'] = 'text/plain' + return response + else: + return response + +def snippet_delete(request, snippet_id): + snippet = get_object_or_404(Snippet, secret_id=snippet_id) + try: + snippet_list = request.session['snippet_list'] + except KeyError: + return HttpResponseForbidden('You have no recent snippet list, cookie error?') + if not snippet.pk in snippet_list: + return HttpResponseForbidden('That\'s not your snippet, sucka!') + snippet.delete() + return HttpResponseRedirect(reverse('snippet_new')) + +def snippet_userlist(request, template_name='snippet/snippet_list.html'): + + try: + snippet_list = get_list_or_404(Snippet, pk__in=request.session.get('snippet_list', None)) + except ValueError: + snippet_list = None + + template_context = { + 'snippets_max': getattr(settings, 'MAX_SNIPPETS_PER_USER', 10), + 'snippet_list': snippet_list, + } + + return render_to_response( + template_name, + template_context, + RequestContext(request) + ) + + +def userprefs(request, template_name='snippet/userprefs.html'): + + if request.method == 'POST': + settings_form = UserSettingsForm(request.POST, initial=request.session.get('userprefs', None)) + if settings_form.is_valid(): + request.session['userprefs'] = settings_form.cleaned_data + settings_saved = True + else: + settings_form = UserSettingsForm(initial=request.session.get('userprefs', None)) + settings_saved = False + + template_context = { + 'settings_form': settings_form, + 'settings_saved': settings_saved, + } + + return render_to_response( + template_name, + template_context, + RequestContext(request) + ) + +def snippet_diff(request, template_name='snippet/snippet_diff.html'): + + if request.GET.get('a').isdigit() and request.GET.get('b').isdigit(): + try: + fileA = Snippet.objects.get(pk=int(request.GET.get('a'))) + fileB = Snippet.objects.get(pk=int(request.GET.get('b'))) + except ObjectDoesNotExist: + return HttpResponseBadRequest(u'Selected file(s) does not exist.') + else: + return HttpResponseBadRequest(u'You must select two snippets.') + + if fileA.content != fileB.content: + d = difflib.unified_diff( + fileA.content.splitlines(), + fileB.content.splitlines(), + 'Original', + 'Current', + lineterm='' + ) + difftext = '\n'.join(d) + difftext = pygmentize(difftext, 'diff') + else: + difftext = _(u'No changes were made between this two files.') + + template_context = { + 'difftext': difftext, + 'fileA': fileA, + 'fileB': fileB, + } + + return render_to_response( + template_name, + template_context, + RequestContext(request) + ) + +def guess_lexer(request): + code_string = request.GET.get('codestring', False) + response = simplejson.dumps({'lexer': guess_code_lexer(code_string)}) + return HttpResponse(response)
--- a/settings.py +++ b/settings.py @@ -143,6 +143,7 @@ 'agora.apps.snippet', 'agora.apps.bundle', 'agora.apps.free_license', + 'agora.apps.mptt', ) LOGIN_REDIRECT_URL='/'
--- a/templates/base.djhtml +++ b/templates/base.djhtml @@ -43,7 +43,7 @@ </div> <ul id="nav-main"> <li id="nav-bundles"><a href="/bundles" class="first">Latest</a></li> - <li id="nav-snippets"><a href="/snippets">Snippets</a></li> + <li id="nav-snippets"><a href="/snippet">Snippets</a></li> <li id="nav-discuss"><a href="/discuss">Discussions</a></li> <li id="nav-about"><a href="/about">About</a></li> </ul>
new file mode 100644 --- /dev/null +++ b/templates/snippet/base.html @@ -0,0 +1,1 @@ +{% extends "base.djhtml" %}
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_details.html @@ -0,0 +1,173 @@ +{% extends "snippet/base.html" %} +{% load mptt_tags %} +{% load i18n %} + +{% block extrahead %} + {% if request.session.userprefs %} + <style type="text/css" media="all"> + .code{ + {# FIXME: Thats stupid #} + {% ifnotequal request.session.userprefs.font_family "None" %}font-family: {{ request.session.userprefs.font_family }} !important;{% endifnotequal %} + {% ifnotequal request.session.userprefs.font_size "None" %}font-size: {{ request.session.userprefs.font_size }}px !important;{% endifnotequal %} + {% ifnotequal request.session.userprefs.line_height "None" %}line-height: {{ request.session.userprefs.line_height }}px !important;{% endifnotequal %} + } + </style> + {% endif %} +{% endblock %} + +{% block title %}{% trans "Snippet" %} #{{ snippet.pk }}{% endblock %} +{% block headline %} + <h1> + {% trans "Snippet" %} #{{ snippet.pk }} + {% if snippet.parent_id %} + {% blocktrans with snippet.parent.get_absolute_url as parent_url and snippet.parent.id as parent_id %}(Copy of <a href="{{ parent_url }}">snippet #{{ parent_id }}</a>){% endblocktrans %} + {% endif %} + <span class="date">{{ snippet.published|date:_("DATETIME_FORMAT") }} ({% trans "UTC" %})</span> + </h1> +{% endblock %} +{% load snippet_tags %} + +{% block content %} +<div id="diff" style="display:none;">diff</div> + +<div class="whitebox"> + <div class="snippet-options"> + <abbr title="{% trans "Time to life" %}">TTL:</abbr> {{ snippet.expires|timeuntil }} + — + {% if snippet.pk|in_list:request.session.snippet_list %} + <a onclick="return confirm('{% trans "Really delete this snippet?" %}')" href="{% url snippet_delete snippet.secret_id %}">Delete now!</a> + — + {% endif %} + <a id="toggleWordwrap" href="#">{% trans "Wordwrap" %}</a> + </div> + <h2> + {% if snippet.title %}{{ snippet.title }}{% else %} {% trans "Snippet" %} #{{ snippet.id}}{% endif %} + <span>{% if snippet.author %}{% blocktrans with snippet.author as author %}by {{ author }}{% endblocktrans %}{% endif %}</span> + </h2> + + <div class="container"> + <div class="snippet"> + <table> + <tr> + <th><pre class="code">{% for l in lines %}<a href="#l{{ forloop.counter }}" id="l{{ forloop.counter }}">{{ forloop.counter }}</a>{% endfor %}</pre></th> + <td><pre class="code">{% for line in snippet.content_splitted %}<div class="line" id="l{{ forloop.counter }}">{% if line %}{{ line|safe }}{% else %} {% endif %}</div>{% endfor %}</pre></td> + </tr> + </table> + </div> + </div> + + <h2>{% trans "Write an answer" %} →</h2> + <div class="container" style="display: none;"> + {% include "snippet/snippet_form.html" %} + </div> +</div> +{% endblock %} + + + +{% block sidebar %} + <h2>{% trans "History" %}</h2> + + <form method="get" id="diffform" action="{% url snippet_diff %}"> + <div class="tree"> + {% for tree_item,structure in tree|tree_info %} + {% if structure.new_level %}<ul><li>{% else %}</li><li>{% endif %} + <div> + <span class="diff"> + <input type="radio" name="a" value="{{ tree_item.id }}" {% ifequal tree_item.id snippet.parent_id %}checked="checked"{% endifequal %}/> + <input type="radio" name="b" value="{{ tree_item.id }}" {% ifequal snippet tree_item %}checked="checked"{% endifequal %}/> + </span> + {% ifequal snippet tree_item %} + <strong>{% trans "Snippet" %} #{{ tree_item.id }}</strong> + {% else %} + <a href="{{ tree_item.get_absolute_url }}">{% trans "Snippet" %} #{{ tree_item.id }}</a> + {% endifequal %} + </div> + {% for level in structure.closed_levels %}</li></ul>{% endfor %} + {% endfor %} + <div class="submit"> + <input type="submit" value="{% trans "Compare" %}"/> + </div> + </div> + </form> + + <h2>{% trans "Options" %}</h2> + <p><a href="{% url snippet_details_raw snippet.secret_id %}">{% trans "View raw" %}</a></p> +{% endblock %} + +{% block script_footer %} +<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.2.6/jquery.min.js"></script> +<script src="http://ajax.googleapis.com/ajax/libs/jqueryui/1.5.2/jquery-ui.min.js"></script> +<script type="text/javascript"> +jQuery(document).ready(function(){ + + curLine = document.location.hash; + if(curLine.substring(0,2) == '#l'){ + $('div.snippet div.line'+curLine).addClass('marked'); + } + + $("div.accordion").accordion({ + autoHeight: false, + header: 'h2', + animation: 'bounceslide', + duration: 2000, + }); + + /** + * Diff Ajax Call + */ + $("form#diffform").submit(function() { + $.get("{% url snippet_diff %}", { + a: $("input[name=a]:checked").val(), + b: $("input[name=b]:checked").val() + }, function(data){ + $('#diff').html(data).slideDown('fast'); + }); + return false; + }); + + /** + * Wordwrap + */ + $('#toggleWordwrap').toggle( + function(){ + $('div.snippet pre.code').css('white-space', 'pre-wrap'); + return false; + }, + function(){ + $('div.snippet pre.code').css('white-space', 'pre'); + return false; + } + ); + + /** + * Line Highlighting + */ + $('div.snippet th a').each(function(i){ + $(this).click(function(){ + var j = $(this).text(); + $('div.snippet div.line.marked').removeClass('marked'); + $('div.snippet div.line#l'+j).toggleClass('marked'); + }); + }); + + {% if request.session.userprefs.display_all_lexer %} + /** + * Lexer Guessing + */ + $('#guess_lexer_btn').click(function(){ + $.getJSON('{% url snippet_guess_lexer %}', + {'codestring': $('#id_content').val()}, + function(data){ + if(data.lexer == "unknown"){ + $('#guess_lexer_btn').css('color', 'red'); + }else{ + $('#id_lexer').val(data.lexer); + $('#guess_lexer_btn').css('color', 'inherit'); + } + }); + }); + {% endif %} +}); +</script> +{% endblock %}
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_details_raw.html @@ -0,0 +1,1 @@ +{{ snippet.content|safe }} \ No newline at end of file
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_diff.html @@ -0,0 +1,13 @@ +{% load i18n %} + +<h2> + <span style="float:right;">(<a href="#" onclick="$('#diff').slideUp('fast'); return false;">{% trans "Close" %}</a>)</span> + {% blocktrans with fileA.get_absolute_url as filea_url and fileB.get_absolute_url as fileb_url and fileA.id as filea_id and fileB.id as fileb_id %} + Diff between + <a href="{{ filea_url }}">Snippet #{{ filea_id }}</a> + and + <a href="{{ fileb_url }}">Snippet #{{ fileb_id }}</a> + {% endblocktrans %} +</h2> + +<pre class="code">{{ difftext|safe }}</pre>
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_form.html @@ -0,0 +1,19 @@ +{% load i18n %} +<form method="post" action="." class="snippetform"> +{% csrf_token %} +<ol> + {% for field in snippet_form %} + <li> + {{ field.errors }} + {{ field.label_tag }} + {{ field }} + {% if request.session.userprefs.display_all_lexer %} + {% ifequal field.name "lexer" %} + <input type="button" value="{% trans "Guess lexer" %}" id="guess_lexer_btn"/> + {% endifequal %} + {% endif %} + </li> + {% endfor %} + <li class="submit"><input type="submit" value="{% trans "Paste it" %}"/></li> +</ol> +</form>
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_list.html @@ -0,0 +1,26 @@ +{% extends "snippet/base.html" %} +{% load i18n %} + +{% block title %}{% trans "Snippet" %} #{{ snippet.pk }}{% endblock %} +{% block headline %} +<h1>{% blocktrans %}Your latest {{ snippets_max }} snippets{% endblocktrans %}</h1> +{% endblock %} + +{% block content %} + {% if snippet_list %} + {% for snippet in snippet_list %} + <h2> + <a href="{{ snippet.get_absolute_url }}">{% trans "Snippet" %} #{{ snippet.pk }}</a> + ~ {{ snippet.published|date:_("DATETIME_FORMAT") }} + </h2> + <p style="color: #555; margin: 8px 0 20px 0;">{{ snippet.content|truncatewords:40 }}</p> + {% endfor %} + {% else %} + <p>{% trans "No snippets available." %}</p> + {% endif %} + + + <div class="hint"> + {% trans "DATA_STORED_IN_A_COOKIE_HINT" %} + </div> +{% endblock %}
new file mode 100644 --- /dev/null +++ b/templates/snippet/snippet_new.html @@ -0,0 +1,39 @@ +{% extends "snippet/base.html" %} +{% load i18n %} + +{% block title %}{% trans "New snippet" %}{% endblock %} +{% block headline %}<h1>{% trans "Paste a new snippet" %}</h1>{% endblock %} + +{% block content %} + <h2>{% trans "New snippet" %}</h2> + {% include "snippet/snippet_form.html" %} +{% endblock %} + + +{% block sidebar %} + <h2>{% trans "DPASTE_HOMEPAGE_TITLE" %}</h2> + <p>{% trans "DPASTE_HOMEPAGE_DESCRIPTION" %}</p> +{% endblock %} + + +{% block script_footer %} +<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.2.6/jquery.min.js"></script> +<script type="text/javascript"> +jQuery(document).ready(function(){ + {% if request.session.userprefs.display_all_lexer %} + $('#guess_lexer_btn').click(function(){ + $.getJSON('{% url snippet_guess_lexer %}', + {'codestring': $('#id_content').val()}, + function(data){ + if(data.lexer == "unknown"){ + $('#guess_lexer_btn').css('color', 'red'); + }else{ + $('#id_lexer').val(data.lexer); + $('#guess_lexer_btn').css('color', 'inherit'); + } + }); + }); + {% endif %} +}); +</script> +{% endblock %}
new file mode 100644 --- /dev/null +++ b/templates/snippet/userprefs.html @@ -0,0 +1,27 @@ +{% extends "snippet/base.html" %} +{% load i18n %} + +{% block headline %} + <h1>{% trans "User Settings" %}</h1> +{% endblock %} + +{% block content %} + {% if settings_saved %} + <div class="success"> + {% trans "USER_PREFS_SAVED_SUCCESSFULLY" %} + </div> + {% endif %} + + <h2>{% trans "User Settings" %}</h2> + + <form class="snippetform" method="post" action="."> + <ol> + {{ settings_form.as_ul }} + <li class="submit"><input type="submit" value="{% trans "Save settings" %}"/></li> + </ol> + </form> + + <div class="hint"> + {% trans "DATA_STORED_IN_A_COOKIE_HINT" %} + </div> +{% endblock %}