Checking several strings against a n-depth list of lists and returning one if its values

Question

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.

Answer 1

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=[])])