仅通过"left()"和"right()"命令手动在嵌套列表中导航？

Question

虽然我用的是Python，但我觉得抽象的概念对我和其他人来说更有趣。如果你愿意的话，可以用伪代码来说明 :)

我有一个包含我某个类的项目的列表。这里我们用字符串和数字来举例，其实不太重要。这个列表可以嵌套到任意深度。（它实际上不是一个普通的列表，而是基于列表的一个容器类。）

例子： [1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6]

注意，两个['a', 'b', 'c']实际上是同一个容器。如果你改变了一个，另一个也会跟着改变。容器和项目都可以被编辑，可以插入项目，最重要的是，容器可以被多次使用。为了避免重复，不能把这个列表展开（我觉得！），因为那样你就失去了在一个容器中插入项目的能力，而这个项目会自动出现在所有其他容器中。

问题：对于前端（只是用Python的“cmd”模块的命令行），我想用一个光标来浏览这个结构，光标始终指向当前项目，这样就可以读取或编辑。光标可以左右移动（从用户的角度来看），并且应该表现得像这个列表不是嵌套的，而是一个平坦的列表。

对人类来说，这个操作非常简单。你只需要假装在上面的列表中，子列表不存在，直接从左到右移动就可以了。

例如，如果你在上面列表中的“3”位置，向右移动，你会得到下一个项目'a'，然后是'b'，'c'，接着是"4"等等。或者如果你从"300"向右移动，你会得到下一个"5"。

向后移动也是一样： 如果你从"6"向左移动，下一个是'c'。如果你从"5"向左移动，下一个是"300"。

那么，原则上我该怎么做呢？我这里有一个方法，但它是错误的，而问题已经这么长了，我担心大多数人不会看完 :(. 我可以稍后再发。

附言： 即使很难抵挡：这个问题的答案不是“你为什么想这样做，为什么要这样组织数据，为什么不先[展开列表|我想象中的其他东西]呢？”问题正是我在这里描述的内容，别无其他。数据的结构正是因为这个问题的性质而如此。

Answer 1

基本上，我会基于递归来构建自己的解决方案。我会在容器类中添加以下内容：

1. cursor_position - 这个属性用来存储当前高亮元素的索引（或者是包含高亮元素的元素的索引，或者更深层次的递归索引）。
2. repr_with_cursor - 这个方法应该返回容器内容的可打印版本，并且已经高亮显示当前选中的项目。
3. mov_right - 当光标向右移动时调用这个方法。它会返回光标在元素中的新索引，如果光标移动到当前容器的“外面”，则返回None（比如你移动过了容器中的最后一个元素）。
4. mov_left - 同样的功能，但向左移动。

递归的工作方式是，对于每个方法，根据高亮元素的类型，应该有两种不同的行为：

• 如果光标在一个容器上，它应该调用“指向”的容器的方法。
• 如果光标在一个非容器上，它应该执行“真实的操作”。

编辑 我有半个小时的空闲时间，所以我简单写了一个示例类来实现我的想法。这个类并不完整（例如，当到达最大容器的任一端时处理得不好，并且每个类的实例只能在最大序列中使用一次），但它足够演示这个概念。我在这里重申一下：这是一个概念验证代码，绝对不能直接使用！

#!/usr/bin/env python
# -*- coding: utf-8  -*-

class C(list):

    def __init__(self, *args):
        self.cursor_position = None
        super(C, self).__init__(*args)

    def _pointed(self):
        '''Return currently pointed item'''
        if self.cursor_position == None:
            return None
        return self[self.cursor_position]

    def _recursable(self):
        '''Return True if pointed item is a container [C class]'''
        return (type(self._pointed()) == C)

    def init_pointer(self, end):
        '''
        Recursively set the pointers of containers in a way to point to the
        first non-container item of the nested hierarchy.
        '''
        assert end in ('left', 'right')
        val = 0 if end == 'left' else len(self)-1
        self.cursor_position = val
        if self._recursable():
            self.pointed._init_pointer(end)

    def repr_with_cursor(self):
        '''
        Return a representation of the container with highlighted item.
        '''
        composite = '['
        for i, elem in enumerate(self):
            if type(elem) == C:
                composite += elem.repr_with_cursor()
            else:
                if i != self.cursor_position:
                    composite += str(elem)
                else:
                    composite += '**' + str(elem) + '**'
            if i != len(self)-1:
                composite += ', '
        composite += ']'
        return composite

    def mov_right(self):
        '''
        Move pointer to the right.
        '''
        if self._recursable():
            if self._pointed().mov_right() == -1:
                if self.cursor_position != len(self)-1:
                    self.cursor_position += 1
        else:
            if self.cursor_position != len(self)-1:
                self.cursor_position += 1
                if self._recursable():
                    self._pointed().init_pointer('left')
            else:
                self.cursor_position = None
                return -1

    def mov_left(self):
        '''
        Move pointer to the left.
        '''
        if self._recursable():
            if self._pointed().mov_left() == -1:
                if self.cursor_position != 0:
                    self.cursor_position -= 1
        else:
            if self.cursor_position != 0:
                self.cursor_position -= 1
                if self._recursable():
                    self._pointed().init_pointer('right')
            else:
                self.cursor_position = None
                return -1

一个简单的测试脚本：

# Create the nested structure
LevelOne = C(('I say',))
LevelTwo = C(('Hello', 'Bye', 'Ciao'))
LevelOne.append(LevelTwo)
LevelOne.append('!')
LevelOne.init_pointer('left')
# The container's content can be seen as both a regualar list or a
# special container.
print(LevelOne)
print(LevelOne.repr_with_cursor())
print('---')
# Showcase the effect of moving the cursor to right
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_right()
print('---')
# Showcase the effect of moving the cursor to left
LevelOne.init_pointer('right')
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_left()

它的输出是：

['I say', ['Hello', 'Bye', 'Ciao'], '!']
[**I say**, [Hello, Bye, Ciao], !]
---
[**I say**, [Hello, Bye, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, Bye, Ciao], **!**]
---
[I say, [Hello, Bye, Ciao], **!**]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[**I say**, [Hello, Bye, Ciao], !]

有趣的问题！今天我最喜欢的操作系统问题！ :)

Answer 2

我会让光标有一个数组索引的堆栈。

举个例子：

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

如果光标在1的位置（索引为0），那么光标的位置就是[0]。

如果光标在2的位置（索引为1），那么光标的位置就是[1]。

如果光标在'a'的位置（最外层索引为3，第二层索引为0），那么光标的位置就是[3, 0]。

如果光标在'b'的位置（最外层索引为3，第二层索引为1），那么光标的位置就是[3, 1]。

等等。

要向右移动光标，只需要增加位置中最右边的索引值。所以当你从'b'移动到'c'时，位置会从[3, 1]变成[3, 2]。如果索引超出了范围，就把索引堆栈中最右边的值弹出，然后增加最右边的值。所以如果你从'c'移动到4，位置会从[3, 2]变成[4]。

在移动时，如果遇到一个嵌套的数组，就要进入这个数组。所以如果你从3（索引为[2]）向右移动，就会进入数组['a','b','c']的第一个元素，位置变为[3, 0]。

向左移动就只是向右移动的反向操作。

Answer 3

一种解决方案是存储当前的索引和/或深度信息，然后用它来遍历嵌套列表。但这样做似乎会涉及很多复杂的分支，比如要测试列表的结束等等。于是，我想出了一个折中的办法。与其把嵌套的列表压平，不如创建一个生成器，生成一个指向嵌套列表的平坦索引列表：

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,)

接着，我写了一个简单的函数，根据索引元组从嵌套列表中提取最里面的项目：

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

现在，你只需要以你喜欢的方式遍历这个平坦的索引列表就可以了。

>>> 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

---

由于这个答案被接受为我在ideone上评论中发布的基于栈的解决方案，并且为了避免使用外部的代码分享网站， 请注意 这个答案 也包含了我的基于栈的解决方案。