Implement closure-tree to improve performance.

[TimurKady]

Hello!
I want to share the experience of using the module. Today I see many of its advantages and two main disadvantages. One of them I want to discuss. This is control over the order of elements.

Description of the problem.
The module does not have a transparent and understandable mechanism for ordering elements in the tree. In practice, the most common are two modes: alphabetical sorting and strict order set by the user. The logic dictates that the tn_priority field provided by the default form should do this. If it is set to 0 for all elements, then they must be ordered alphabetically. If it is specified, then the field value determines the order.

But alas, this is not the case.

Another method of establishing a coercive order of elements, which is intuitively prompted by experience, is also not suitable. This is an attempt to import data with the tn_order field set.

It would be nice if you made it easier to manage the order of items in tree.

PS. The main trouble is that with all my attachment to this module, without a mechanism for intelligible order management, I have to refuse to use it. And it just tears my soul to shreds :-(

[fabiocaccamo]

@Timurkhan thank you for reporting your experience with this library.

The ordering problem was really hard to solve because the objective was to sort an N levels data structure which is stored in a flat data-structure (just 1 db table) and at the same time each object must respect the order of its ancestors.

I understand that the solution is not very transparent but it solves the problem well, if you have any idea on how to obtain the same result in a better way feel free to share it.

The tn_order field is used internally for the final ordering, its value is calculated based on the tn_priority value.

Please try to import your data using the tn_priority instead of tn_order and I think that it will work correctly (let me know).

[TimurKady]

I will think about how to solve the problem.
What is obvious now (as a statement of the task) is that the tn_priority parameter must be abandoned. At least its purpose should be to set the position of the element in the list of children of the node.
At one time (until I found your library) I had some developments. I will try to present something.

I've tried all the options. First, I assigned the tn_priority a order number in the list of node . Secondly, I tried to duplicate the id in the same field. Nothing helped. All the time, sorting occurs in the reverse order of id.

[TimurKady]

I have a quick idea. It doesn't require a lot of code change.

1. If the user needs an alphabetical ordering, then we leave the decision to him. Let's enter a CharField field, will create an index (db_index=True) in it, will indicate this field as a sorting field in the Meta class.

2. We must change the type of the tn_order field to BinaryField. We store the Materialized Path to the tree node in it. We allocate two bytes (word or 65536 child nodes) for the binary representation of tn_priority of each node along the path. We must create an index. We don't change anything in the Meta class.

In this case, sorting will occur correctly when the ordinal number of the node in the children of this node is specified in the tn_priority field.

This will slow down the already not very fast insertion of the node, but I think it will be also useful for issuing the Materialized Path without traversing the tree.

[fabiocaccamo]

This doesn't seem to be more a more transparent solution :)

Anyway, before the current implementation, I stored the ordering string in a db field, but it could become very long in case of deep structures, especially if the pk is a UUIDField, and there is not real need to store it, so I decided to compute the ordering string just in memory and use it to calculate the final order using integer field.

I agree with the fact that tn_order and tn_priority field could be merged into a single field, that would surely reduce confusion.

[TimurKady]

Yes: of course! The combined field must in any case unambiguously specify the order of the element in the list of the node's children.

[fabiocaccamo]

@Timurkhan have you any update on this?

[TimurKady]

Befor NY I will sent u vertion. Now in testing

[TimurKady]

Hi Fabio!
After testing various ideas, we settled on this variation, with which we use your module:

    def __get_node_order_str(self):

        return '.'.join(
            '{0:04d}'.format(item)
            for item in self.get_breadcrumbs(attr='tn_priority')
        )

    def save(self, *args, **kwargs):
        def sort_key(obj):
            return obj.tn_priority

        super().save(*args, **kwargs)
        siblings = sorted(self.get_siblings(), key=sort_key)
        index = 1
        for leaf in siblings:
            if leaf.tn_priority >= self.tn_priority:
                leaf.tn_priority = self.tn_priority + index
                leaf.save()
                index += 1

It doesn't seem to work badly. The main thing is that it allows you to explicitly specify the order of the entries in the tree.
Perhaps you will not like this solution, or seem too straightforward. But... :-)

[fabiocaccamo]

@Timurkhan thank you for the feedback, I will test it and let you know!

[TimurKady]

Hi @fabiocaccamo!
Below is the more correct code. Also, it doesn't slow down the code working and use less no more 3 requests

    def __get_node_order_str(self):

        return '.'.join(
            '{0:04d}'.format(item)
            for item in self.get_breadcrumbs(attr='tn_priority')
        )

    def save(self, force_insert=False, force_update=False, *args, **kwargs):

        def sort_key(obj):
            return obj.tn_priority

        def order_list(obj_list):
            index = 0
            for obj in obj_list:
                obj.tn_priority = index
                index += 1
            self._meta.model.objects.bulk_update(obj_list, ['tn_priority'])

        try:
            parent = self.tn_parent
        except:
            parent = None

        if parent:
            new_siblings = sorted(self.tn_parent.get_children(), key=sort_key)
        else:
            roots = self._meta.model.get_roots()
            new_siblings = sorted(roots, key=sort_key)

        if self.pk and not force_insert:
            try:
                old = self._meta.model.objects.get(pk=self.pk)
                old_siblings = sorted(old.get_siblings(), key=sort_key)
            except:
                old = None

            if self in new_siblings:
                new_siblings.remove(self)
            new_siblings.insert(self.tn_priority, self)

            if old and (old.tn_parent != self.tn_parent):
                order_list(old_siblings)
                order_list(new_siblings)

            if old and (old.tn_priority != self.tn_priority):
                order_list(new_siblings)

        else:
            new_siblings.insert(self.tn_priority, self)
            super().save(*args, **kwargs)
            if len(new_siblings):
                order_list(new_siblings)

        self._meta.model.update_tree()

[fabiocaccamo]

Hello @TimurKady, thank you for the update, the code seems pretty clear, I will test it as soon as possible.

[TimurKady]

Tnx!
If interested, I can also offer update for TreeNodeForm. It is a widget for the "tn_parent" field (signal2 tree based).