1
\$\begingroup\$

Given the models below:

class Structure(Model):
    ...

class StructureComponent(Model):
    ...
    structure = ForeignKey(Structure)
    parent_component = ForeignKey('self', null=True, ...)

Developer should synchronize with the database a list of trees:

The sample of request data:

{
    'trees': [
        {
            'id': 1,
            'name': 'root1',
            'children': [
                {            
                    'id': null, # new child component, should be created as a child of component with id 1
                    'name': 'root1.1',
                    'children': [],
                },
            ],
        },
        {
            'id': null, # new root component, should be created
            'name': 'root2',
            'children': [],
        },
        # other components that are in the database but not listed here (in the request payload) should be deleted
    ],
}

And this is the serializer to process the payload and sync with the database.

class StructureComponentTreeListSerializer(serializers.Serializer):
    trees = StructureComponentTreeSerializer(many=True)

    def __init__(self, *args, **kwargs):
        super(StructureComponentTreeListSerializer, self).__init__(*args, **kwargs)

        self.structure = self.context['structure']
        self.component_type = self.context['component_type']

        # create filtered queryset for further use
        self.filtered_queryset = (
            StructureComponent
            .objects
            .filter(
                structure=self.structure,
                type=self.component_type,
            )
        )

        # queue to traverse trees using BST algorithm
        self.queue = deque()

        # list of components that should be updated(keys are levels in tree)
        self.updates = defaultdict(list)
        # list of components that should be created(keys are levels in tree)
        self.creates = defaultdict(list)

        # collect ids of final components and remove the rest
        self.exclude_pks = []

    def save(self, validated_data):
        trees = validated_data['trees']

        # queue root nodes
        for idx, tree in enumerate(trees):
            # assign unique id for getting matched as a parent in child nodes
            tree['_uuid'] = uuid.uuid4().hex
            # idx will be used to set the order_by field
            self.queue.append([tree, idx, 0, None])

        self.traverse(*self.queue.popleft())

    def traverse(self, node, order_by, level=0, parent=None):
        """
        BST traverse
        :param node: dictionary with information about component
                     id: None or int
                     name: str
                     _uuid: unique id
        :param order_by: the number used in ordering
        :param level: current level of tree
        :param parent: dictionary containing id of the parent component if any
        """
        entity = StructureComponent(
            pk=node.get('id'),
            name=node.get('name', ''),
            structure=self.structure,
            type=self.component_type,
            order_by=order_by,
        )
        entity._uuid = node.get('_uuid')
        if parent:
            entity.parent_component_id = parent.get('id')

        if node.get('id'):
            # append to updates list because we have the id
            self.updates[level].append(entity)
            # collect pks of remaining components
            self.exclude_pks.append(entity.pk)
        else:
            # append to creates list because we don't have the id
            self.creates[level].append(entity)

        if level + 1 < self.max_depth:
            # we don't care about nodes below max_depth level
            for idx, child in enumerate(node.get('children', [])):
                # queue children and assign unique id for getting matched as a parent in child nodes
                child['_uuid'] = uuid.uuid4().hex
                # idx will be used to set the order_by field
                self.queue.append([child, idx, level + 1, node])

        if len(self.queue):
            # get the next from queue(keeping it there) to detect level change
            _, _, next_level, _ = self.queue[0]

            if next_level != level:
                # sync db if we are moving down on level
                # before that we should have all primary keys of parents to be able to connect with children
                self.sync_db(level)

            # traverse over next from queue
            self.traverse(*self.queue.popleft())

        else:
            # we still have non synchronized items(lowest levels of trees) so we should sync them too
            self.sync_db(level)
            # now we have all pks to exclude so we can delete components that are not exist in final trees
            self.clean_db()

    def sync_db(self, level):
        # update name and order_by fields based on level
        self.filtered_queryset.bulk_update((cmp for cmp in self.updates[level]), ['name', 'order_by'])

        # create new components
        components = StructureComponent.objects.bulk_create(self.creates[level])

        for cmp, node in zip(components, self.creates[level]):
            # collect pks of remaining components
            self.exclude_pks.append(cmp.pk)
            for args in self.queue:
                # update parents in queue which are created during last sync
                if args[-1].get('_uuid') == node._uuid:
                    # attach pk of newly created parent to child
                    args[-1]['id'] = cmp.pk

    def clean_db(self):
        """
        Remove all components except final ones
        that are collected in exclude_pks attribute.
        """
        self.filtered_queryset.exclude(pk__in=self.exclude_pks).delete()

This serializer is a bit complicated compared with others in the project. And colleague asked if the author can make it more readable and even optimal if it's possible.

Another case which will help you to understand it better:

{
    'trees': [
        {
            'id': 2,
            'name': 'root2',
            'children': [],
        },
    ],
}

The client will send this data as a second payload and the root component in the previous payload should be removed.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

My suggestion is to broke the dict in smaller pieces something like:

node_root1_1 = { 'id': None, 'name': 'root1.1', 'children' : [] }
node_root1 = { 'id': 1, 'name': 'root1', 'children' : [ node_root1_1 ] }
node_root2 = { 'id': None, 'name': 'root2', 'children' : [] }

'trees': [ node_root1, 
           node_root2 ]

Bear in mind that work with this types of structs, nested dicts, lists and other types sometimes can be tricky and depends on the reader, hope you get the idea.

\$\endgroup\$
1
  • \$\begingroup\$ Sorry, but I didn't get it. \$\endgroup\$ Feb 20, 2020 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.