pythonrecursionhierarchy

How to transform a list of objects into a objects hierarchy?


I have SQLlite database which contain this table:table In this table we can see rows which describe a specific tasks. Nesting of tasks is implemented using root_task_id cells. For example: task with id: 1, is root task for task with id: 19, and task with id: 19 is root task for task with id: 20. And that means: task with id: 20 is subtask of task with id: 19, and task with id: 19 is subtask of task with id: 1. When i get this data from database to Python program I want to create hierarchy of this tasks by using objects of Task class:

class Task:
     def __init__(self, task_id, root_task_id, task_name, task_text, task_is_executed, subtasks = []):
        self.id = task_id
        self.root_task_id = root_task_id
        self.name = task_name
        self.text = task_text
        if task_is_executed == 0:
            self.is_executed = "No executed"
        else:
            self.is_executed = "EXECUTED"
        self.subtasks = subtasks

Hierarchy of this tasks must be implemented by using subtasks property of Task class objects. In short I need to pack tasks as subtasks according to hierarchy implemented by root_task_id cells of SQL table.

I wrote this code, but that has some mistake, which I cannot detect:

def wrap_up_task_recursive(task: Task, tasks: list[Task], depth = 0):
    for root_task in tasks:
        print(f"root_task with id: {root_task.id}, is root? for task with id: {task.id}, that has root task with id: {task.root_task_id}?")
        print(depth)
        if task.root_task_id == root_task.id:
            print("Yes")
            root_task.subtasks.append(task)
            break
        else:
            if len(root_task.subtasks) != 0:
                wrap_up_task_recursive(task=task, tasks=root_task.subtasks, depth=depth + 1)


def convertTasksToUserFrandlyFormat2(all_tasks: list[Task]) -> list[Task]:
    root_tasks: list[Task] = []
    root_tasks_indexes: list[int] = []
    for index, task in enumerate(all_tasks):
        if task.root_task_id == None:
            root_tasks.append(task)
            root_tasks_indexes.append(index)
    root_tasks_indexes.sort(reverse=True)
    print(f"Root tasks indexes: {root_tasks_indexes}")
    for index in root_tasks_indexes:
        all_tasks.pop(index)
    print(f"**********root_tasks**********")
    for rt in root_tasks:
        print(f"id: {rt.id}")
        print(f"root_id: {rt.root_task_id}")
        print(f"sub: {len(rt.subtasks)}")
    print(f"**********Subtasks**********")
    for t in all_tasks:
        print(f"id: {t.id}")
        print(f"root_id: {t.root_task_id}")
        print(f"sub: {len(rt.subtasks)}")
    
    for task in all_tasks:
        wrap_up_task_recursive(task=task, tasks=root_tasks)
    return root_tasks

def indentation(depth: int) -> str:
    resultStr = ""
    for _ in range(depth):
        resultStr += "  "
    return resultStr

def recursiveReading(task: Task, depth = 0):
    print(f"{indentation(depth)} id = {task.id}")
    print(task.subtasks)
    print(len(task.subtasks))

def readTasksToUserFrandlyFormat(all_tasks: list[Task]):
    for task in all_tasks:
        recursiveReading(task)


task1 = Task(task_id=1, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task2 = Task(task_id=14, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task3 = Task(task_id=15, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task4 = Task(task_id=16, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task5 = Task(task_id=17, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task6 = Task(task_id=18, root_task_id=None, task_name="New task", task_text="This is new task", task_is_executed=0)
task7 = Task(task_id=19, root_task_id=1, task_name="New task", task_text="This is new task", task_is_executed=0)
task8 = Task(task_id=20, root_task_id=19, task_name="New task", task_text="This is new task", task_is_executed=0)
all_tasks = [task1, task2, task3, task4, task5, task6, task7, task8]
h_all_tasks = convertTasksToUserFrandlyFormat2(all_tasks)
readTasksToUserFrandlyFormat(h_all_tasks)

Console output:

Root tasks indexes: [5, 4, 3, 2, 1, 0]
**********root_tasks**********
id: 1
root_id: None
sub: 0
id: 14
root_id: None
sub: 0
id: 15
root_id: None
sub: 0
id: 16
root_id: None
sub: 0
id: 17
root_id: None
sub: 0
id: 18
root_id: None
sub: 0
**********Subtasks**********
id: 19
root_id: 1
sub: 0
id: 20
root_id: 19
sub: 0
root_task with id: 1, is root? for task with id: 19, that has root task with id: 1?
0
Yes
root_task with id: 1, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
root_task with id: 14, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
root_task with id: 15, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
root_task with id: 16, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
root_task with id: 17, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
root_task with id: 18, is root? for task with id: 20, that has root task with id: 19?
0
root_task with id: 19, is root? for task with id: 20, that has root task with id: 19?
1
Yes
 id = 1
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7
 id = 14
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7
 id = 15
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7
 id = 16
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7
 id = 17
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7
 id = 18
[<myTaskManager.Task object at 0x000001BCA396E750>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>, <myTaskManager.Task object at 0x000001BCA396E780>]
7

Solution

  • Surprisingly, all my code is working correctly, except for the line:

    def __init__(self, task_id, root_task_id, task_name, task_text, task_is_executed, subtasks = []):
    

    In this line of code I have constructor with Default Parameter: subtasks = [] which is causing the problem that all objects of Task class have the same subtasks list (reference to the same memory cell). What causes the confusion when you use a “mutable” object as a default value; The reason is simple: the constructor keeps using the same Default Parameter object, in each call. Anyone who wants to understand it in more detail, I strongly recommend reading this post which @Michael Butscher advised me in comments.

    What do I need to do to make my code work as expected? To do this you only need to change two lines of code: replace subtasks = [] Default Parameter in constructor to subtasks = None and then replace self.subtasks = subtasks to self.subtasks = [] inside init function. This is how it should be:

    class Task:
         def __init__(self, task_id, root_task_id, task_name, task_text, task_is_executed, subtasks = None):
            self.id = task_id
            self.root_task_id = root_task_id
            self.name = task_name
            self.text = task_text
            if task_is_executed == 0:
                self.is_executed = "No executed"
            else:
                self.is_executed = "EXECUTED"
            if subtasks == None:
                self.subtasks = []
            else:
                self.subtasks = subtasks
    

    Also I am attaching the complete code for pack tasks as subtasks according to hierarchy implemented by root_task_id cells of SQL table:

    class Task:
         def __init__(self, task_id, root_task_id, task_name, task_text, task_is_executed, subtasks = None):
            self.id = task_id
            self.root_task_id = root_task_id
            self.name = task_name
            self.text = task_text
            if task_is_executed == 0:
                self.is_executed = "No executed"
            else:
                self.is_executed = "EXECUTED"
            if subtasks == None:
                self.subtasks = []
            else:
                self.subtasks = subtasks
    
    def wrap_up_task_recursive(task: Task, tasks: list[Task], depth = 0):
        for root_task in tasks:
            print(f"root_task with id: {root_task.id}, is root? for task with id: {task.id}, that has root task with id: {task.root_task_id}?")
            print(depth)
            if task.root_task_id == root_task.id:
                print("Yes")
                root_task.subtasks.append(task)
                break
            else:
                if len(root_task.subtasks) != 0:
                    wrap_up_task_recursive(task=task, tasks=root_task.subtasks, depth=depth + 1)
                
    def convertTasksToUserFrandlyFormat2(all_tasks: list[Task]) -> list[Task]:
        root_tasks: list[Task] = []
        root_tasks_indexes: list[int] = []
        for index, task in enumerate(all_tasks):
            if task.root_task_id == None:
                root_tasks.append(task)
                root_tasks_indexes.append(index)
        root_tasks_indexes.sort(reverse=True)
        print(f"Root tasks indexes: {root_tasks_indexes}")
        for index in root_tasks_indexes:
            all_tasks.pop(index)
        print(f"**********root_tasks**********")
        for rt in root_tasks:
            print(f"id: {rt.id}")
            print(f"root_id: {rt.root_task_id}")
            print(f"sub: {len(rt.subtasks)}")
        print(f"**********Subtasks**********")
        for t in all_tasks:
            print(f"id: {t.id}")
            print(f"root_id: {t.root_task_id}")
            print(f"sub: {len(rt.subtasks)}")
        
        for task in all_tasks:
            wrap_up_task_recursive(task=task, tasks=root_tasks)
        return root_tasks
    
    def indentation(depth: int) -> str:
        resultStr = ""
        for _ in range(depth):
            resultStr += "|__"
        return resultStr
    
    def recursiveReading(task: Task, depth = 0):
        print(f"{indentation(depth)} id = {task.id}")
        
        if len(task.subtasks) != 0:
            for subtask in task.subtasks:
                recursiveReading(subtask, depth + 1)
        
    
    def readTasksToUserFrandlyFormat(all_tasks: list[Task]):
        print("********Task hierarchy********")
        for task in all_tasks:
            recursiveReading(task)
    
    
    task1 = Task(task_id=1, root_task_id=None, task_name="New Task", task_text="This is new task", task_is_executed=0)
    task2 = Task(task_id=2, root_task_id=1, task_name="New Task", task_text="This is new task", task_is_executed=0)
    task3 = Task(task_id=3, root_task_id=None, task_name="New Task", task_text="This is new task", task_is_executed=0)
    task4 = Task(task_id=4, root_task_id=2, task_name="New Task", task_text="This is new task", task_is_executed=0)
    task5 = Task(task_id=5, root_task_id=4, task_name="New Task", task_text="This is new task", task_is_executed=0)
    
    listOfTasks = [task1, task2, task3, task4, task5]
    listOfTasksWithHierarchy = convertTasksToUserFrandlyFormat2(listOfTasks) # Here list of packed tasks as subtasks according to hierarchy implemented by root_task_id cells of SQL table.
    readTasksToUserFrandlyFormat(listOfTasksWithHierarchy)
    

    Console output:

    Root tasks indexes: [2, 0]
    **********root_tasks**********
    id: 1
    root_id: None
    sub: 0
    id: 3
    root_id: None
    sub: 0
    **********Subtasks**********
    id: 2
    root_id: 1
    sub: 0
    id: 4
    root_id: 2
    sub: 0
    id: 5
    root_id: 4
    sub: 0
    root_task with id: 1, is root? for task with id: 2, that has root task with id: 1?
    0
    Yes
    root_task with id: 1, is root? for task with id: 4, that has root task with id: 2?
    0
    root_task with id: 2, is root? for task with id: 4, that has root task with id: 2?
    1
    Yes
    root_task with id: 3, is root? for task with id: 4, that has root task with id: 2?
    0
    root_task with id: 1, is root? for task with id: 5, that has root task with id: 4?
    0
    root_task with id: 2, is root? for task with id: 5, that has root task with id: 4?
    1
    root_task with id: 4, is root? for task with id: 5, that has root task with id: 4?
    2
    Yes
    root_task with id: 3, is root? for task with id: 5, that has root task with id: 4?
    0
    ********Task hierarchy********
     id = 1
    |__ id = 2
    |__|__ id = 4
    |__|__|__ id = 5
     id = 3