Return all items within path, inc siblings at each level traversed

Question

I'm not even sure how to describe this, but I'll have a go in the hope that someone here can understand and help. I have a number of lists that consist of paths to nodes that could appear in a navigation structure, e.g.:

['nav1']
['nav1','subnav1']
['nav1','subnav2']
['nav2']
['nav3']
['nav3','subnav1']
['nav3','subnav2']
['nav3','subnav3']
['nav3','subnav3','subsubnav1'] **
['nav3','subnav3','subsubnav1','subsubsubnav']
['nav4']
['nav5']
['nav5','subnav1']
['nav5','subnav1','subsubnav1']
['nav5','subnav2']
['nav5','subnav3']

Supposing I have selected the node indicated by ** in this navigation, I would also like to return all nodes that are parents and siblings of this node. (Like Windows Explorer tree menu).

So using the selected example I would return:

['nav1']
['nav2']
['nav3']
['nav3','subnav1']
['nav3','subnav2']
['nav3','subnav3']
['nav3','subnav3','subsubitem1']
['nav3','subnav3','subsubitem1','subsubsub']
['nav4']
['nav5']

I'd like to achieve this in the most efficient pythonic way. I've had a few attempts myself, but haven't really succeeded. This is the closest I've come, but unfortunately it doesn't return the siblings.

#model_path is the current selected node e.g ** as illustrated above
#always show 1st level nodes
if len(node_path) == 1:
    return True
#always show final level nodes
if model_path == node_path[:-1]:
    return True
#show all items in tree from root to model
if len(node_path) > 1:
    return self._find_sublist(node_path, model_path) >= 0
#show siblings at each level traversed
#????

# find_sublist credit to this post by nosklo:
# http://stackoverflow.com/a/2251638/1844977
def _find_sublist(self, sub, bigger):
    if not bigger:
        return -1
    if not sub:
        return 0
    first, rest = sub[0], sub[1:]
    pos = 0
    try:
        while True:
            pos = bigger.index(first, pos) + 1
            if not rest or bigger[pos:pos+len(rest)] == rest:
                return pos
    except ValueError:
        return -1

I'd really appreciate some help here as I'm struggling to find a solution. A solution, I should add, that would work when there are an unlimited number of levels.

I apologise if this question isn't clear, or if it's a duplicate (I fear it maybe), but the fact that I don't really know the correct terminology for what I'm asking doesn't help my search.

Incidentally I'm restricted to Python 2.4.

Johntyb · Accepted Answer

Thanks to mVChr's answer I was able to return exactly what I wanted using the following:

FULL_NAV = [
    ['nav1'],
    ['nav1', 'subnav1'],
    ['nav1', 'subnav2'],
    ['nav2'],
    ['nav3'],
    ['nav3', 'subnav1'],
    ['nav3', 'subnav2'],
    ['nav3', 'subnav3'],
    ['nav3', 'subnav3', 'subsubnav1'],
    ['nav3', 'subnav3', 'subsubnav1', 'subsubsubnav'],
    ['nav4'],
    ['nav5'],
    ['nav5', 'subnav1'],
    ['nav5', 'subnav1', 'subsubnav1'],
    ['nav5', 'subnav2'],
    ['nav5', 'subnav3']
]


def get_required_nav(node_path, full_nav):
    return_list = []

    for comparison_node in full_nav:
        cn_len = len(comparison_node)
        np_len = len(node_path)
        if cn_len <= np_len:
            if comparison_node[:cn_len - 1] == node_path[:cn_len - 1]:
                return_list.append(comparison_node)
        else:
            if comparison_node[:-1] == node_path:
                return_list.append(comparison_node)
    return return_list

if __name__ == '__main__':
        from pprint import pprint
        pprint(get_required_nav(
            ['nav3', 'subnav3'], FULL_NAV))


# Output of above example:
# [['nav1'],
#  ['nav2'],
#  ['nav3'],
#  ['nav3', 'subnav1'],
#  ['nav3', 'subnav2'],
#  ['nav3', 'subnav3'],
#  ['nav3', 'subnav3', 'subsubnav1'],
#  ['nav4'],
#  ['nav5']]

Return all items within path, inc siblings at each level traversed

Answers (2)

Related Questions