0
\$\begingroup\$

The data structure I am working with is a list of lists that is created by parsing a file. The depth of the list can vary. The list can have n Strings before its child-value begins.

My current example of this list of list looks something (this is already slightly formatted for better readability, also there can be different structures before and after it):

[['archive', 'Structures', [[
['set', 'Control', [['attribute', "'speed'", []], ['attribute', "'angle'", []], ['attribute', "'field'", []], ['attribute', "'cycle'", []], ['attribute', "'speed2'", []], ['attribute', "'field2'", []]]]
['part', 'Stage', [['attribute', "'Connection'", []], ['function', "StageOpen", []], ['attribute', "Resistance", []]]]
['archive', 'Field', [['attribute', "'Cycles'", []], ['attribute', "'Connection'", []], ['value', "'Field (Integer)'", []], ['attribute', "Poles", []], ['attribute', "'Inertia'", []], ['attribute', "'Magnet'", []]]]
['set', 'Load', [['value', "'testval'", []], ['attribute', "'coef'", []], ['attribute', "'inertia'", []]]]
]]

What I want to do is to search for a pair like ('set', 'Control') or ('set', 'Load') and get the list that is in the same record. For set/control that would be:

[['attribute', "'speed'", []], ['attribute', "'angle'", []], ['attribute', "'field'", []], ['attribute', "'cycle'", []], ['attribute', "'speed2'", []], ['attribute', "'field2'", []]]]

From what I can see until now my program works, however I am not satisfied with it. I don't do recursions often and it's probably obvious that there is quite a potential for improvement:

class ParsedReader():
    def __init__(self,parsed):
        self.parsed=parsed
        self.foundItem=[]

    def reset(self):
        self.foundItem=[]

    @staticmethod
    def compareFun(item,combo):
        return all(elem in combo for elem in item)
        
    def getChildrenByCombo(self, combo, depth=0, chain=None):
        if chain is None:
            chain=self.parsed

        for item in chain:
            if isinstance(item,str) or item == []:
                continue
            elif isinstance(item,list):
                if self.compareFun(combo,item):
                    self.foundItem=item[self.getIndexOfClass(item,list)]
                    return item[self.getIndexOfClass(item,list)]                                   
            self.getChildrenByCombo(combo, depth+1, item)            

        return self.foundItem


    @staticmethod
    def getIndexOfClass(liste,klasse):
        for cnt,obj in enumerate(liste):
            if isinstance(obj,klasse):
                return cnt
        return -1

This is called by:

preader = ParsedReader(parsed)
sub_parts=preader.getChildrenByCombo(["set","control"])
#Do something
sreader.reset()

I am well aware recursions shouldn't use global variables, the exiting of the function is not clean, and so forth. However, it works. Yet, before I keep patching unnecessary things I'd be happy to receive a proper feedback on how this is to be done instead.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

It looks like you're trying to make a tree structure. Normally a tree structure is nicely represented with a 'node' class which can contain multiple children nodes:

from typing import NamedTuple, Tuple, List


class Node(NamedTuple):
    key: Tuple[str]
    children: List["Node"]

Now, the example you included was a little unclear (and in fact not valid python without adding some commas) . It looks like sometimes you have elements of the form ['string', 'other string', ... , [...]]; And sometimes you have elements like [[...], [...], [...], ...]. The former can be matched nicely with tuple unpacking, the second one will need to be handled separately. Let's add a parser to our 'Node' class for that:

@classmethod
def from_iterable(cls, iterable):
    if all(isinstance(item, list) for item in iterable):
        return cls(tuple(), children=[cls.from_iterable(item) for item in iterable])
    *key, payload = iterable
    return cls(key=tuple(key), children=[cls.from_iterable(item) for item in payload])

Now we need to navigate our tree structure, depth first seems fine here:

def walk(self):
    yield self
    yield from chain.from_iterable(child.walk() for child in self.children)  # chain comes from the 'itertools' module

And now search:

def search(self, key):
    for node in self.walk():
        if node.key == key:
            return node

This gives us what you initially asked for:

example = [
    [
        'archive', 'Structures', 
        [
            [
                ['set', 'Control', 
                 [
                     ['attribute', "'speed'", []],
                     ['attribute', "'angle'", []], 
                     ['attribute', "'field'", []], 
                     ['attribute', "'cycle'", []], 
                     ['attribute', "'speed2'", []],
                     ['attribute', "'field2'", []]
                 ]
                ]
                ,
                ['part', 'Stage', 
                 [
                     ['attribute', "'Connection'", []],
                     ['function', "StageOpen", []],
                     ['attribute', "Resistance", []]
                 ]
                ],
                ['archive', 'Field', 
                 [
                     ['attribute', "'Cycles'", []],
                     ['attribute', "'Connection'", []],
                     ['value', "'Field (Integer)'", []],
                     ['attribute', "Poles", []], 
                     ['attribute', "'Inertia'", []], 
                     ['attribute', "'Magnet'", []]
                 ]
                ],
                ['set', 'Load', 
                 [
                     ['value', "'testval'", []],
                     ['attribute', "'coef'", []],
                     ['attribute', "'inertia'", []]
                 ]
                ]
            ]
        ]
    ]
]

Followed by:

>>> Node.from_iterable(example).search(('set', 'Load'))
Node(key=('set', 'Load'), children=[Node(key=('value', "'testval'"), children=[]), Node(key=('attribute', "'coef'"), children=[]), Node(key=('attribute', "'inertia'"), children=[])])

The algorithmic complexity here isn't great. Worst case we'll need to navigate the entire tree to get a key. We can speed this up by caching the results of 'search' (the cache decorator from functools would be handy here). We can also pre-emptively compute an index (which takes a bit more ram in return for speed).

>>> root = Node.from_iterable(example)
>>> index = {node.key: node for node in root.walk()}
>>> index[('set', 'Load')]
Node(key=('set', 'Load'), children=[Node(key=('value', "'testval'"), children=[]), Node(key=('attribute', "'coef'"), children=[]), Node(key=('attribute', "'inertia'"), children=[])])
\$\endgroup\$
1
  • \$\begingroup\$ I'm always getting a '_collections._tuplegetter' object is not iterable when calling search(('set', 'Load')). Same for {node.key: node for node in root.walk()}. It seems the error appears if the 3rd value has something in the list. Difficult however to debug \$\endgroup\$
    – Qohelet
    Dec 21, 2022 at 13:42

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.