将任意长度的位置列表 [4, 1, 2] 转换为嵌套列表的索引

Question

假设这个列表

nestedList = ["a", "b", [1, 2, 3], "c",[4, 5, 6, [100, 200, 300]], "d"]

我有一个函数，它返回任意深度的嵌套列表的位置列表。 示例：

[2, 1] -> "2"
[5] -> "d"
[4, 3, 2] -> "300"

正如您所看到的，一开始并不清楚有多少层嵌套。

其他问题 对于列表修改，我想使用 [:] 或 [4:] 或 [0:1] 符号。

对于人类来说，这很容易做到：只需添加所需数量的索引位置即可。

nestedList[2][1]
nestedList[5]
nestedList[4][3][2]
nestedList[4][1:] = NewItem + nestedList[4][1:] #insert item
nestedList[2][1] = [] #remove item

然而，这种方法不会产生任何结果，因为我必须将字符串附加在一起并稍后对其进行评估。明显的废话:)

处理具有未知数量索引位置的嵌套列表并且仍然具有像普通列表一样处理它的功能（读取、修改、插入、删除）的最佳方法是什么

我希望有一个答案。

PS 列表必须保持嵌套。扁平化不是一种选择。

Answer 1

第一部分很简单。

>>> reduce(lambda x, y: x[y], [4, 3, 2], nestedList)
300

第二部分需要更多的努力，但仍然是可行的。暗示：

>>> a = [1, 2, 3]
>>> a[slice(1, None)] = [4, 5]
>>> a
[1, 4, 5]

Answer 2

我终于有时间摆弄这个了。我有点得意忘形了。虽然很长，不过我还是贴一下吧。我添加了 set_item、insert、delete、find 和 find_left 方法，如下以及一些允许破坏游标抽象的低级操作的私有方法。我还添加了一个 move_cursor 方法，对于超出范围或指向非顶级对象的索引元组抛出 IndexError 。

基本上，（应该）保证只要你只使用公共函数，光标总是指向顶级对象，并且插入和删除都发生在顶级。从这里，您应该能够安全地实现 __getitem__、__setitem__、__delitem__ 等，甚至可能 __getslice__ ，__setslice__。

然而，还有一些问题。光标始终指向顶级对象的限制使得迭代嵌套列表变得非常容易，就好像它是一个平面列表一样。但这也意味着光标无法指向较低级别的对象，因此单独使用 insert 无法进行某些类型的插入。例如，假设您有三个列表：

>>> l1 = [1, 2, 3, 4]
>>> l2 = [5, 6, 7, 8]
>>> l3 = [l1, l2]
>>> l3
[[1, 2, 3, 4], [5, 6, 7, 8]]

现在将此嵌套结构放入 NLI 中，移至 5，然后尝试插入。

>>> nli = NestedListIter(l3)
>>> nli.find(5)
>>> nli.insert(9)
>>> nli.nested_list
[[1, 2, 3, 4], [9, 5, 6, 7, 8]]

正如您所看到的，您可以将某些内容插入到 l2 中，但无法轻松地将某些内容插入到 l3 中。事实上，现在要做到这一点，您必须使用私有函数，这会以一种令人不快的方式破坏游标抽象：

>>> nli._insert_at(nli.stack[:-1], 10)
>>> nli.nested_list
[[1, 2, 3, 4], 10, [9, 5, 6, 7, 8]]
>>> nli.get_item()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "nestedlistiterator.py", line 130, in get_item
    return self._get_item_at(self.stack)
  File "nestedlistiterator.py", line 39, in _get_item_at
    item = item[i]
TypeError: 'int' object is unsubscriptable

肯定有方法可以实现安全的公共 insert_ Between_branches 方法，但它们涉及更多比我现在关心的复杂性。

当尝试在 4 之后插入值时，会出现另一个问题。如您所见，您可以在 5 之前将值插入到 l2 中，但如果将光标移动到 4 并 insert，您很快就会意识到您无法在 l1 内的 4 之后插入内容。

>>> nli.go_to_head()
>>> nli.find(4)
>>> nli.insert(11)
>>> nli.nested_list
[[1, 2, 3, 11, 4], 10, [9, 5, 6, 7, 8]]

从平面访问的角度来看，在4之后插入和在5之前插入是同一件事，但是从嵌套列表的角度来看，它们是不同的。由于 insert 实际上是 left_insert，因此可以使用 right_insert 方法部分纠正此问题（反过来，该方法将无法插入到l1) 的开头。

这些问题可能可以通过允许光标指向较低级别的对象来更普遍地处理，但这将使平面访问更加复杂。简而言之，任何纠正这些问题的尝试都会导致更大的复杂性，无论是在界面的平面还是嵌套方面。

（这实际上就是为什么我仍然更喜欢简单的 enumerate_nested方法！一个正确的树结构，所有节点都有值（而不仅仅是顶级节点）也可能更简单、更好，但是编码仍然很有趣。）

import collections

class NestedListIter(object):
    '''A mutable container that enables flat traversal of a nested tree of 
    lists. nested_list should contain only a list-like mutable sequence. 
    To preserve a clear demarcation between 'leaves' and 'branches', empty 
    sequences are not allowed as toplevel objects.'''
    def __init__(self, nested_list):
        if not nested_list:
            raise ValueError, 'nested_list must be a non-empty sequence'
        self.nested_list = nested_list # at some point, vet this to make sure
        self.go_to_head()              # it contains no empty sequences

    def _is_sequence(self, item=None):
        '''Private method to test whether an item is a non-string sequence.
        If item is None, test current item.'''
        if item is None:
            item = self._get_item_at(self.stack)
        return isinstance(item, collections.Sequence) and not isinstance(item, basestring)

    def _is_in_range(self, index_tuple=None):
        '''Private method to test whether an index is in range. 
        If index is None, test current index.'''
        if index_tuple is None:
            index_tuple = self.stack
        if any(x < 0 for x in index_tuple):
            return False
        try:
            self._get_item_at(index_tuple)
        except IndexError:
            return False
        else:
            return True

    def _get_item_at(self, index_tuple):
        '''Private method to get item at an arbitrary index, with no bounds checking.'''
        item = self.nested_list
        for i in index_tuple:
            item = item[i]
        return item

    def _set_item_at(self, index_tuple, value):
        '''Private method to set item at an arbitrary index, with no bounds checking.
        Throws a ValueError if value is an empty non-string sequence.'''
        if self._is_sequence(value) and not value:
            raise ValueError, "Cannot set an empty list!"
        containing_list = self._get_item_at(index_tuple[:-1])
        containing_list[index_tuple[-1]] = value

    def _insert_at(self, index_tuple, value):
        '''Private method to insert item at an arbitrary index, with no bounds checking.
        Throws a ValueError if value is an empty non-string sequence.'''
        if self._is_sequence(value) and not value:
            raise ValueError, "Cannot insert an empty list!"
        containing_list = self._get_item_at(index_tuple[:-1])
        containing_list.insert(index_tuple[-1], value)

    def _delete_at(self, index_tuple):
        '''Private method to delete item at an arbitrary index, with no bounds checking.
        Recursively deletes a resulting branch of empty lists.'''
        containing_list = self._get_item_at(index_tuple[:-1])
        del containing_list[index_tuple[-1]]
        if not self._get_item_at(index_tuple[:-1]):
            self._delete_at(index_tuple[:-1])

    def _increment_stack(self):
        '''Private method that tires to increment the top value of the stack.
        Returns True on success, False on failure (empty stack).'''
        try:
            self.stack[-1] += 1
        except IndexError:
            return False
        else: 
            return True

    def _decrement_stack(self):
        '''Private method that tries to decrement the top value of the stack.
        Returns True on success, False on failure (empty stack).'''
        try:
            self.stack[-1] -= 1
        except IndexError:
            return False
        else:
            return True

    def go_to_head(self):
        '''Move the cursor to the head of the nested list.'''
        self.stack = []
        while self._is_sequence():
            self.stack.append(0)

    def go_to_tail(self):
        self.stack = []
        '''Move the cursor to the tail of the nested list.'''
        while self._is_sequence():
            self.stack.append(len(self.get_item()) - 1)

    def right(self):
        '''Move cursor one step right in the nested list.'''
        while self._increment_stack() and not self._is_in_range():
            self.stack.pop()
        if not self.stack:
            self.go_to_tail()
            return False
        while self._is_sequence():
            self.stack.append(0)
        return True

    def left(self):
        '''Move cursor one step left in the nested list.'''
        while self._decrement_stack() and not self._is_in_range():
            self.stack.pop()
        if not self.stack:
            self.go_to_head()
            return False
        while self._is_sequence():
            self.stack.append(len(self.get_item()) - 1)
        return True

    def move_cursor(self, index_tuple):
        '''Move cursor to the location indicated by index_tuple.
        Raises an error if index_tuple is out of range or doesn't correspond
        to a toplevel object.'''
        item = self._get_item_at(index_tuple)
        if self._is_sequence(item):
            raise IndexError, 'index_tuple must point to a toplevel object'

    def get_item(self):
        '''Get the item at the cursor location.'''
        return self._get_item_at(self.stack)

    def set_item(self, value):
        '''Set the item a the cursor locaiton.'''
        return self._set_item_at(self.stack, value)

    def insert(self, value):
        '''Insert an item at the cursor location. If value is a sequence, 
        cursor moves to the first toplevel object in value after insertion. 
        Otherwise, cursor does not move.'''
        temp_stack = self.stack[:]
        self.left()
        self._insert_at(temp_stack, value)
        self.right()

    def delete(self):
        '''Deete an item at the cursor location. Cursor does not move.'''
        temp_stack = self.stack[:]
        self.left()
        self._delete_at(temp_stack)
        self.right()

    def iterate(self):
        '''Iterate over the values in nested_list in sequence'''
        self.go_to_head()
        yield self.get_item()
        while self.right():
            yield self.get_item()

    def iterate_left(self):
        '''Iterate over the values in nested_list in reverse.'''
        self.go_to_tail()
        yield self.get_item()
        while self.left():
            yield self.get_item()

    def find(self, value):
        '''Search for value in nested_list; move cursor to first location of value.'''
        for i in self.iterate():
            if i == value:
                break

    def find_left(self, value):
        '''Search for value backwards in nested_list; move cursor to last location of value.'''
        for i in self.iterate_left():
            if i == value:
                break

def _NLI_Test():
    l = [1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6]
    nli = NestedListIter(l)
    print nli.nested_list
    for i in nli.iterate():
        print i,
    print
    for i in nli.iterate_left():
        print i,
    print

    nli.go_to_head()
    for i in range(5):
        nli.right()
    nli.insert('cow')
    nli.insert(['c', ['o', 'w']])
    print nli.nested_list
    nli.find('cow')
    print nli.get_item()
    nli.delete()
    print nli.nested_list
    nli.find('c')
    nli.delete()
    print nli.nested_list
    nli.find_left('w')
    nli.delete()
    nli.find('o')
    nli.delete()
    print nli.nested_list
    print nli.nested_list == l
    nli.find(100)
    nli.set_item(100.1)
    print nli.nested_list

if __name__ == '__main__':
    _NLI_Test()