Create Proper Hierarchical Data for TreeView?

[bentraje]

Hi,

All the examples I found so far for TreeView uses the "objects" in C4D such as the objects and materials.

I needed to create a TreeView that would represent directories and subdirectories (much the same way with the Content Browser) .

I can access the directories properly using this code based on this thread

import os

def list_files(startpath):
    for root, dirs, files in os.walk(startpath):
     
        level = root.replace(startpath, '').count(os.sep)
        indent = ' ' * 4 * (level)
        print('{}{}/'.format(indent, os.path.basename(root)))
        subindent = ' ' * 4 * (level + 1)

Result:
    folder1/
        sec_folder1_A/
            ter_folder1_A/
        sec_folder1_B/
    folder2/
        subfolder2_A/

My problem, for now, is creating Proper Hierarchical Data for Tree View so that I can execute GetFirst, GetDown, GetNext function properly (although I have recreate those functions, for another thread problem maybe haha).

1) What would be the proper format? list or dictionary? It seems like either are insufficient.

Dictionary:
dir_dict = {
    'folder1': {'sec_folder1_A':'ter_folder1_A',
                'sec_folder1_B': 'None' },
    'folder2': {'sec_folder2_A': 'None'}       
}

List: 
dir_list = [
        [folder1,
                [ [sec_folder1_A, [ter_folder1_A]],
                sec_folder1_B
                ],
        [folder2, 
                [subfolder2_A]
        ]

]

2) Even if its List or Dictionary, I'm actually at lost how to populate it as hierarchical data. Do you have any tips?

Thank you for looking at my problem

Regards,
Ben

[zipit]

Hi,

1. Technically the dict (i.e. a hash map) solution would be better due to the constant access time, but that will hardly be of any real consequence in your case. But if you are going for an unoptimised graph representation (i.e. do not use something like an adjacency matrix or an inverted index) - which is the right choice here IMHO, I do not really see the point of handling the "raw data". Why not write some node type with which you can both represent and access/modify your graph?
2. Well, TreeviewFunctions is the interface between the TreeViewCustomGui and whatever is representing the data of your graph. You have to implement the graph traversal methods you mentioned. Using a dict or an inverted index this can get a bit messy. For an adjacency matrix things would be a bit more straight forward, but the easiest solution is probably implementing your own type, since you have only to return the corresponding attribute of your custom node type then.

Cheers,
zipit

[bentraje]

Hi @zipit

Thanks for the response. Just a heads up, I'm still a novice Python user so forgive me if I'm asking the obvious below.

1 ==================
RE: do not use something like an adjacency matrix or an inverted index
I haven't encountered both but what you should I use other than those two? I didn't know there were "types" of dictionary.

RE:Why not write some node type with which you can both represent and access/modify your graph?
I don't know how to write a node type. That's also the first time I have heard of it.
This is what you are referring to right?
https://developers.maxon.net/docs/Cinema4DPythonSDK/html/modules/c4d.plugins/BaseData/NodeData/index.html

2 ==================

Since creating node type is out of my league. I guess using dict will be the way to go. Need to read up on inverted index and adjacency matrix. Basically, both can help me "crawl" on my hierarchical data right? Such as performing GetNext, GetDown functions.

[zipit]

Hi,

1. These are both just concepts to store and access graphs (i.e. also a tree). An adjacency matrix is just a square matrix for n nodes, where you describe the relation between two nodes in each cell. An inverted index flattens any edge relation of a graph to a list by inverting the edge relation (i.e. if you have the node a with some kind of relation to b,c, d, the inverted index would be b: a, c: a, d: a). There are fancier concepts to do this, but they are not really needed here, since a file tree is so small. In fact I would not use any optimisation here as stated in my previous post.
2. Don't sell yourself short. I think you overestimate the difficulty of the problem. You have just to write a class that can somehow represent a graph (or a trie in your case). Below is a minimal example. The advantage of this approach is that is easy to understand and work with, the disadvantage is it is slow (doesn't matter here) and expressing more than one relation can be difficult (doesn't matter here either):

class Node(object):
    """A very simple node type for a tree/trie graph.
    """
    def __init__(self, **kwargs):
        """The constructor for ``Node``.

        Args:
            **kwargs: Any non-graph related attributes of the node.
        """
        # You might want to encapsulate your attributes in properties, so
        # that you can validate / process them, I took the lazy route.
        if "name" not in kwargs:
            kwargs["name"] = "Node"
        self.__dict__.update(kwargs)
        self.parent = None
        self.children = []
        self.prev = None
        self.next = None
        self.down = None

    def __repr__(self):
        """The representation is: class, name, memory location.
        """
        msg = "<{} named {} at {}>"
        hid = "0x{:0>16X}".format(id(self))
        return msg.format(self.__class__.__name__, self.name, hid)

    def add(self, nodes):
        """Adds one or multiple nodes to the instance as children.

        Args:
            nodes (list[Node] or Node): The nodes to add.
        
        Raises:
            TypeError: When nodes contains non-Node elements.
        """
        nodes = [nodes] if not isinstance(nodes, list) else nodes
        # last child of the instance, needed for linked list logic
        prev = self.children[-1] if self.children else None

        for node in nodes:
            if not isinstance(node, Node):
                raise TypeError(node)

            node.parent = self
            node.prev = prev
            if prev is not None:
                prev.next = node
            else:
                self.down = node

            self.children.append(node)
            prev = node

    def pretty_print(self, indent=0):
        """Pretty print the instance and its descendants.
        
        Args:
            indent (int, optional): Private.
        """
        tab="\t" * indent
        a = self.prev.name if self.prev else None
        b = self.next.name if self.next else None
        c = self.down.name if self.down else None
        msg = "{tab}{node} (prev: {prev}, next: {next}, down: {down})"
        print msg.format(tab=tab, node=self, prev=a, next=b, down=c)
        for child in self.children:
            child.pretty_print(indent+1)

def build_example_tree():
    """
    """
    root = Node(name="root")
    node_0 = Node(name="node_0")
    node_00 = Node(name="node_00")
    node_01 = Node(name="node_01")
    node_02 = Node(name="node_02")
    node_1 = Node(name="node_1")
    node_10 = Node(name="node_10")

    root.add(nodes=[node_0, node_1])
    node_0.add(nodes=[node_00, node_01, node_02])
    node_1.add(nodes=node_10)
    return root

root = build_example_tree()
root.pretty_print()

Cheers,
zipit

[bentraje]

@zipit

Thanks for the response and the sample code. I appreciate it a lot.
So I guess, when you mentioned "Node Type", it's not necessarily specific to Cinema4D but a general concept.

So now, I just need to repopulate the Node Class with the directories.
Will keep you updated on the progress.

This should keep me busy for the weekend.

Thanks again!

[bentraje]

@zipit

DISCLAIMER: If you think, the question below merits a separate thread, let me know, and I'll create another thread.

Thanks again for the reply. The code still not completed yet.
I populated the class with the directories but I'm having a problem with "parenting" the nodes.
Specifically, I'm having problem accessing the Node class by its name attribute.

This is the snippet of the problem:

            current_index = folder_path_list.index(folder)
            parent_folder = folder_path_list[current_index-1]


            parent_node = #PROBLEM #get_class_node_base_on_its_name 

            new_node = Node(name=folder)
            parent_node.add(nodes=new_node)

You can check the whole code below:

import os

start_path = '.'

# written by zipit

class Node(object):
    """A very simple node type for a tree/trie graph.
    """
    baseId = 90000
    dct = {}


    def __init__(self, **kwargs):
        """The constructor for ``Node``.

        Args:
            **kwargs: Any non-graph related attributes of the node.
        """
        # You might want to encapsulate your attributes in properties, so
        # that you can validate / process them, I took the lazy route.
        if "name" not in kwargs:
            kwargs["name"] = "Node"
        self.__dict__.update(kwargs)
        self.parent = None
        self.children = []
        self.prev = None
        self.next = None
        self.down = None

    def __repr__(self):
        """The representation is: class, name, memory location.
        """
        msg = "<{} named {} at {}>"
        hid = "0x{:0>16X}".format(id(self))
        return msg.format(self.__class__.__name__, self.name, hid)

    def add(self, nodes):
        """Adds one or multiple nodes to the instance as children.

        Args:
            nodes (list[Node] or Node): The nodes to add.
        
        Raises:
            TypeError: When nodes contains non-Node elements.
        """
        nodes = [nodes] if not isinstance(nodes, list) else nodes
        # last child of the instance, needed for linked list logic
        prev = self.children[-1] if self.children else None

        for node in nodes:
            if not isinstance(node, Node):
                raise TypeError(node)

            node.parent = self
            node.prev = prev
            if prev is not None:
                prev.next = node
            else:
                self.down = node

            self.children.append(node)
            prev = node

    def pretty_print(self, indent=0):
        """Pretty print the instance and its descendants.
        
        Args:
            indent (int, optional): Private.
        """
        tab="\t" * indent
        a = self.prev.name if self.prev else None
        b = self.next.name if self.next else None
        c = self.down.name if self.down else None
        msg = "{tab}{node} (prev: {prev}, next: {next}, down: {down})"
        print (msg.format(tab=tab, node=self, prev=a, next=b, down=c))
        for child in self.children:
            child.pretty_print(indent+1)

created_dir = []
root_node = Node(name="images")

for root, dirs, files in os.walk(start_path):
    

    root_normalized = root.replace(start_path, '')

    for dir in dirs:
        folder_path = os.path.join(root_normalized, dir)
        folder_path_list = folder_path.split(os.sep)
        folder_path_list = list(filter(None, folder_path_list)) # Remove empty strings


        for folder in folder_path_list:

            # Images node is already created before this loop. It is set as the root node
            if folder == "images":
                continue
            
            # Prevent creation of node if it was already created beforehand
            if folder in created_dir: 
                continue

            current_index = folder_path_list.index(folder)
            parent_folder = folder_path_list[current_index-1]

            parent_node = #get_class_node_base_on_its_name 

            new_node = Node(name=folder)
            parent_node.add(nodes=new_node)

            created_dir.append(folder) 
      
root_node.pretty_print() 

The directory is still as above:

images/
    folder1/
        sec_folder1_A/
            ter_folder1_A/
        sec_folder1_B/
    folder2/
        subfolder2_A/

[zipit]

Hi,

I am not quite sure what your actual question is. However, I think that you somehow missed the point of writing a node type. The advantage of it is that you can encapsulate any logic into your nodes and can operate on local and small scale. When you write some external functions which operate more or less non-object oriented and on the scale of the whole graph, you could also use a builtin data structure like a dictionary and ignore the whole OO-stuff. I do not want to start a discussion about functional vs. OO programming, use whatever you are comfortable with, but if you want to benefit from some custom node type, you have to implement a custom node type ;)

Below you will find an example for how I would go about what you are probably trying to do. Please note that this is example code and not by any means something that should be used ;)

Cheers,
zipit

import os

class BaseNode(object):
    """The base node type.
    """

    def __init__(self, **kwargs):
        """The constructor for BaseNode.

        Args:
            **kwargs: Any non-graph related attributes of the node.
        """
        # You might want to encapsulate your attributes in properties, so
        # that you can validate / process them, I took the lazy route.
        if "name" not in kwargs:
            kwargs["name"] = "Node"
        self.__dict__.update(kwargs)
        self.children = []
        self.up = None
        self.down = None
        self.prev = None
        self.next = None

    def __iter__(self):
        """Yields all nodes attached to the node.

        Yields:
            BaseNode: A node attached to this node.
        """
        for child in self.children:
            yield child

    def __repr__(self):
        """The string representation of the node.
        """
        msg = "<{} named {} at {}>"
        hid = "0x{:0>16X}".format(id(self))
        return msg.format(self.__class__.__name__, self.name, hid)

    def _link_nodes(self):
        """Builds the links between the children of the instance and the instance.
        """
        prev = None
        for node in self:
            node.up = self
            node.prev = prev
            if prev is not None:
                prev.next = node
            prev = node
        self.down = self.children[0] if self.children else None


    def add(self, nodes):
        """Adds one or multiple nodes to the instance as children.

        Args:
            nodes (list[BaseNode] or BaseNode): The nodes to add.

        Raises:
            TypeError: When nodes contains non-BaseNode elements.
        """
        nodes = [nodes] if not isinstance(nodes, list) else nodes
        # last child of the instance, needed for linked list logic
        prev = self.children[-1] if self.children else None

        for node in nodes:
            if not isinstance(node, BaseNode):
                raise TypeError(node)
            self.children.append(node)
        self._link_nodes()

    def pretty_print(self, indent=0):
        """Pretty print the instance and its descendants.
        """
        tab = "\t" * indent
        a = self.prev.name if self.prev else None
        b = self.next.name if self.next else None
        c = self.down.name if self.down else None
        msg = "{tab}{node} (prev: {prev}, next: {next}, down: {down})"
        print(msg.format(tab=tab, node=self, prev=a, next=b, down=c))
        for child in self.children:
            child.pretty_print(indent+1)


class PathNode(BaseNode):
    """The file-path specialization of a BaseNode.
    """

    def __init__(self, path, **kwargs):
        """The constructor of PathNode.

        Args:
            path (str): The file/folder path of the node.
            **kwargs: Any other non-graph related attributes to be attached to the node.
        """
        BaseNode.__init__(self, path=path)
        self._initialize_path_tree()

    def _initialize_path_tree(self):
        """Initializes a path tree with the path attribute of the instance.

        Recursively builds a PathNode tree for the folders and files that are descendants of the path attribute of the instance.
        """
        # Validate the path attribute.
        if not "path" in self.__dict__:
            msg = "The node hasn't been initialized with a 'path' attribute."
            raise AttributeError(msg)
        if not os.path.exists(self.path):
            msg = "The path '{path}' does not exist or cannot be accessed."
            raise OSError(msg.format(path=self.path))

        path = self.path
        root_path, element = os.path.split(path)
        # Node is a terminal node / file
        if os.path.isfile(path):
            name, extension = os.path.splitext(element)
            self.name = name
            self.extension = extension
            self.is_file = True
        # Node is a non-terminal node / a folder
        else:
            self.name = element
            self.extension = None
            self.is_file = False
            # Build the children
            paths = [os.path.join(path, item) for item in os.listdir(path)]
            for item in paths:
                self.add(PathNode(path=item))
        self.sort()

    def get(self, name, inclusive=False):
        """Yields all nodes which have a matching name attribute.
        
        Note:
            This your "get_class_node_base_on_its_name" method. I am not quite sure, what you are trying to accomplish with it, so there
            are multiple things one could do differently.
        
        Args:
            name (str): The name to match against.
        
        Yields:
            BaseNode: A node that is a descendant of the instance and which fulfills the criteria.
        """
        if self.name == name:
            yield self
        
        for item in self:
            for result in item.get(name=name):
                yield result

    def sort(self):
        """Sorts the children by folder/files, file types and names.
        """
        if not self.children:
            return
        key_lambda = lambda x: (x.is_file, x.extension, x.name)
        self.children = sorted(self.children, key=key_lambda)
        self._link_nodes()
        for node in self:
            node.sort()

    def pretty_print(self, indent=0):
        """Pretty print the directory structure attached to this node.
        """
        tab = "\t" * indent
        if self.is_file:
            msg = "{tab}{name}{ext}".format(tab=tab,
                                            name=self.name,
                                            ext=self.extension)
        else:
            msg = "{tab}[{name}]".format(tab=tab, name=self.name)

        print msg
        for child in self.children:
            child.pretty_print(indent+1)


def demo():
    """
    """
    path = os.path.dirname(__file__)
    root = PathNode(path=path)
    print "root:", root
    root.pretty_print()

    print "\nIterate the root node:"
    for node in root:
        print node

    print "\nGet node by name:"
    for item in root.get("plots"):
        print item

    print "\nGet node by name:"
    for item in root.get("todo"):
        print item

if __name__ == "__main__":
    demo()

root: <PathNode named misc at 0x000000000309C0C8>
[misc]
	[plots]
		plots_interpolation.py
		plots_projection.py
		plotters.py
	[scripts]
		svg_colors.py
	todo.md
	scribbles_1.py
	scribbles_2.py
	scribbles_3.py
	scribbles_4.py
	scribbles_5.py

Iterate the root node:
<PathNode named plots at 0x000000000309C208>
<PathNode named scripts at 0x000000000309C548>
<PathNode named todo at 0x000000000309C5C8>
<PathNode named scribbles_1 at 0x000000000309C308>
<PathNode named scribbles_2 at 0x000000000309C448>
<PathNode named scribbles_3 at 0x000000000309C488>
<PathNode named scribbles_4 at 0x000000000309C4C8>
<PathNode named scribbles_5 at 0x000000000309C508>

Get node by name:
<PathNode named plots at 0x000000000309C208>

Get node by name:
<PathNode named todo at 0x000000000309C5C8>
[Finished in 0.1s]

[m_adam]

Hi sorry for the delay I completely missed the topic, you can find valuable information about how TreeView is working on using customgui listview, then for more advice especially about TreeViewFunctions.GetDown usage Insert object in Treeview, and in No multiple selection in Treeview not working?, you can find a more versatile "node" object which can be used as a root, while previously I used a list as a root.

Cheers,
Maxime.

[bentraje]

Thank you for your response.

@zipit

With the previous help, I was able to represent the folder hierarchy in the treeview.
You can see it here (image)
Source file is here.

In summary, I didn't use your recent with the PathNode class but it helped me how to create the Get Parent Node function which was to store the nodes in a list, and compare the node name and the folder name.

===================================

The code is working now but may I ask about this line.
for item in self:

This is my first seeing a for loop for the self. I understand if it would be self.list_of_names or self.list_of_nodes
but iterating for the self itself? How is it even possible?

I couldn't see any self.append(item) in the code.

Please enlighten me sensei.

@m_adam

No worries. Thanks for the thread links. Will add them as reference.

Regards,
Ben

[zipit]

This works, because I did implement __iter__ in BaseNode, which will be called when you try to iterate an object. For the same reason also for node in root does work. You can learn more about operator overloading in Python here. In a pythonic context they are called spcieal methods, important methods or dunder methods, but practically it's just operator overloading if you are willing to be a bit fuzzy with the term operator.

Cheers,
zipit

[bentraje]

Thanks for the clarification.
Have a great day ahead!