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

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

我终于有一些时间来弄弄这个。我被带走了。很长，但是我还是要粘贴它。我说

set_item

，

insert

，

delete

，

find

，和

find_left

方法，以及一些私有方法，让低级别的 *** 作，打破了光标抽象。我还添加了一种

move_cursor

方法，该方法抛出

IndexError

for索引元组超出范围或指向非顶级对象。

基本上，应该（只要）保证，只要您仅使用公共函数，光标就始终指向顶级对象，并且所有插入和删除 *** 作都在顶级进行。从这里，你应该能够安全地实施

__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

。如您所见，您可以在

l2

before之前插入一个值

5

，但是如果将光标移至

4

and

insert

，则会很快意识到您不能在

4

inside之后插入任何内容

l1

。

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

实际上是a

left_insert

，所以可以使用一种

right_insert

方法（此方法将无法在l1的开头插入）部分纠正此问题。

通过允许光标指向较低级别的对象，可以更一般地解决这些问题，但这会使平面访问更加复杂。简而言之，纠正这些问题的任何尝试都将导致更大的复杂性，无论是在接口的平面还是嵌套的一侧。

（这实际上就是为什么我仍然偏爱简单

enumerate_nested

方法的原因！在所有节点（而不仅仅是顶层节点）都具有值的适当树形结构也可能会变得更简单，更好。但这仍然很有趣。）

import collectionsclass 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:     breakdef _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_listif __name__ == '__main__':    _NLI_Test()