Navigate manually with a cursor through nested lists by only providing "left()" and "right()" as commands?

Question

Eventhough I write in python I think the abstract concept is more interesting to me and others. So pseudocode please if you like :)

I have a list with items from one of my classes. Lets do it with strings and numbers here, it really doesn't matter. Its nested to any depth. (Its not really a list but a container class which is based on a list.)

Example: [1, 2, 3, ['a', 'b', 'c'] 4 ['d', 'e', [100, 200, 300]] 5, ['a', 'b', 'c'], 6]

Note that both ['a', 'b', 'c'] are really the same container. If you change one you change the other. The containers and items can be edited, items inserted and most important containers can be used multiple times. To avoid redundancy its not possible to flatten the list (I think!) because you loose the ability to insert items in one container and it automatically appears in all other containers.

The Problem: For the frontend (just commandline with the python "cmd" module) I want to navigate through this structure with a cursor which always points to the current item so it can be read or edited. The cursor can go left and right (users point of view) and should behave like the list is not a nested list but a flat one.

For a human this is super easy to do. You just pretend that in this list above the sublists don't exist and simply go from left to right and back.

For example if you are at the position of "3" in the list above and go right you get 'a' as next item, then 'b', 'c', and then "4" etc. Or if you go right from the "300" you get the "5" next.

And backwards: If you go left from "6" the next is 'c'. If you go left from "5" its "300".

So how do I do that in principle? I have one approach here but its wrong and the question is already so long that I fear most people will not read it :(. I can post it later.

P.S. Even if its hard to resist: The answer to this question is not "Why do you want to do this, why do you organize your data this way, why don't you [flatten the list| something out of my imagination] first? The problem is exactly what I've described here, nothing else. The data is structured by the nature of the problem this way.

Answer 1

One solution would be to store current index and/or depth information and use it to traverse the nested list. But that seems like a solution that would do a lot of complicated forking -- testing for ends of lists, and so on. Instead, I came up with a compromise. Instead of flattening the list of lists, I created a generator that creates a flat list of indices into the list of lists:

def enumerate_nested(nested, indices):
    for i, item in enumerate(nested):
        if isinstance(item, collections.Iterable) and not isinstance(item, basestring):
            for new_indices in enumerate_nested(item, indices + (i,)):
                yield new_indices
        else:
            yield indices + (i,)

Then a simple function that extracts an innermost item from the list of lists based on an index tuple:

def tuple_index(nested_list, index_tuple):
    for i in index_tuple:
        nested_list = nested_list[i]
    return nested_list

Now all you have to do is traverse the flat index list, in whatever way you like.

>>> indices = list(enumerate_nested(l, tuple()))
>>> print l
[1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6]
>>> for i in indices:
...     print tuple_index(l, i),
... 
1 2 3 a b c 4 d e 100 200 300 5 a b c 6

---

Since this answer was accepted for the stack-based solution that I posted on ideone in the comments, and since it's preferable not to use external pastebins for answer code, please note that this answer also contains my stack-based solution.

Answer 2

I'd let the cursor have a stack of the indices of the arrays.

Examples:

[1, 2, 3, ['a', 'b', 'c'], 4 ]

If the cursor is at the 1 (at index 0), the cursor's position is [0].

It the cursor is at the 2 (at index 1), the cursor's position is [1].

If the cursor is at the 'a' (at index 3 at the outmost level and index 0 at the second level), the cursor's position would be [3, 0].

If the cursor is at the 'b' (at index 3 at the outmost level and index 1 at the second level), the cursor's position would be [3, 1].

etc.

To move the cursor right, you just increase the rightmost index in the position. So when you go from 'b' to 'c' it will increase from [3, 1] to [3, 2]. If the index then becomes out of range, you pop the rightmost value from the index stack and increase the rightmost value. So if you go from 'c' to 4, you go from [3, 2] to [4].

When moving, if you encounter a position with a nested array, you enter it. So if you go right from 3 (at index [2]), you enter the first element in the array ['a','b','c'], which is at index [3, 0].

Moving left would just do the inverse of moving right.