将任意长度的位置[4、1、2]的列表转换为嵌套列表的索引 [英] Convert list of positions [4, 1, 2] of arbitrary length to an index for a nested list
问题描述
假设此列表
nestedList = ["a", "b", [1, 2, 3], "c",[4, 5, 6, [100, 200, 300]], "d"]
我有一个函数，该函数返回任意深度的嵌套列表的位置列表. 示例:
I have a function that returns a position list for a nested list of arbitrary depth. Examples:
[2, 1] -> "2"
[5] -> "d"
[4, 3, 2] -> "300"
您可以看到，一开始不清楚嵌套的层数是多少.
As you can see it is not clear in the beginning how many levels of nesting there are.
其他问题 对于列表修改，我想使用[:]或[4:]或[0:1]表示法.
Additional Problem For list modifications I want to use the [:] or [4:] or [0:1] notations.
对于人类来说，这非常容易做到:只需添加所需数量的索引位置即可.
For a human its very easy to do: simply add as many index position as you need to.
nestedList[2][1]
nestedList[5]
nestedList[4][3][2]
nestedList[4][1:] = NewItem + nestedList[4][1:] #insert item
nestedList[2][1] = [] #remove item
但是，由于我不得不将字符串附加在一起并在以后进行评估，因此这种方法无法奏效.废话很明显:)
However this approach does not lead anywhere since I had to append strings together and eval them later. Obvious nonsense :)
处理具有未知数量索引位置的嵌套列表并仍具有像普通列表一样的功能(读取，修改，插入，删除)的最佳方法是什么
What is the best way to handle a nested list with an unknown number of index positions and still have the functionality to handle it like a normal list (read, modify, insert, remove)
我希望对此有一个答案.
I hope there is an answer to that.
P.S.该列表必须保持嵌套.扁平化不是一种选择.
P.S. the list must remain nested. Flattening is not an option.
推荐答案
我终于有一些时间来解决这个问题.我被带走了.它很长，但是我还是要粘贴它.我添加了set_item，insert，delete，find和find_left方法，以及一些私有方法，以允许破坏光标抽象的低级操作.我还添加了move_cursor方法，该方法为超出范围或指向非顶级对象的索引元组抛出IndexError.
I finally had some time to fiddle around with this. I got a little carried away. It's long, but I'm pasting it anyway. I added set_item, insert, delete, find, and find_left methods, as well as some private methods to allow low-level manipulation that breaks the cursor abstraction. I also added a move_cursor method that throws an IndexError for index tuples that are out of range or point to a non-toplevel object.
基本上，应该保证，只要您仅使用公共函数，光标就始终指向顶级对象，并且所有插入和删除操作都在顶级进行.从这里开始，您应该可以安全地实现__getitem__，__setitem__，__delitem__等，甚至可以实现__getslice__，__setslice__.
Basically, it (should) be guaranteed that as long as you use public functions only, the cursor always points to a top-level object, and insertions and deletions all happen at the top level. From here, you should be able to safely implement __getitem__, __setitem__, __delitem__, etc, and maybe even __getslice__, __setslice__.
但是，有一些皱纹.游标始终指向顶级对象的限制使其非常容易遍历嵌套列表，就好像它是平面列表一样.但这也意味着光标不能指向较低级别的对象，因此单独使用insert不会发生某些类型的插入.例如，假设您有三个列表:
However, there are a couple of wrinkles. The restriction that the cursor always points to a toplevel object makes it very easy to iterate over the nested list as though it were a flat list. But it also means that the cursor can't point at lower-level objects, and hence some kinds of insertions can't happen using insert alone. For example, say you have three lists:
>>> l1 = [1, 2, 3, 4]
>>> l2 = [5, 6, 7, 8]
>>> l3 = [l1, l2]
>>> l3
[[1, 2, 3, 4], [5, 6, 7, 8]]
现在将这个嵌套结构放入NLI中，移至5，然后尝试插入.
Now put this nested structure in a NLI, move to 5, and try to insert.
>>> nli = NestedListIter(l3)
>>> nli.find(5)
>>> nli.insert(9)
>>> nli.nested_list
[[1, 2, 3, 4], [9, 5, 6, 7, 8]]
如您所见，您可以在l2中插入一些内容，但不能轻松地在l3中插入一些内容.实际上，现在要做的是，您必须使用一个私有函数，该函数以一种不愉快的方式破坏了光标的抽象:
As you can see, you can insert something into l2, but you can't easily insert something into l3. In fact, to do so right now, you have to use a private function, which breaks the cursor abstraction in an unpleasant way:
>>> 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方法的方法，但是它们涉及的复杂性比我现在所关心的要复杂.
There are surely ways to implement a safe public insert_between_branches method, but they involve more complication than I care to bother with right now.
当尝试在4之后插入值时，出现另一个问题.如您所见，您可以在5之前的l2中插入一个值，但是如果将光标移至4和insert，您会很快意识到您不能在l1内.
Another problem appears when one tries to insert a value after 4. As you've seen, you can insert a value into l2 before 5, but if you move the cursor to 4 and insert, you'll quickly realize that you can't insert something after 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实际上是left_insert，因此可以使用right_insert方法部分纠正此问题(而该方法又将无法在l1的开头插入).
From the perspective of flat access, inserting after 4 and inserting before 5 are the same thing, but from the perspective of the nested list, they are different. Since insert is effectively a left_insert, this problem could be partially rectified with a right_insert method (which would, in turn, be unable to insert at the beginning of l1).
可以通过允许光标指向较低级别的对象来更一般地解决这些问题，但这会使平面访问更加复杂.简而言之，任何纠正这些问题的尝试都将导致更大的复杂性，无论是在接口的平面还是嵌套的一侧.
These problems could probably be dealt with more generally by allowing the cursor to point to lower-level objects, but that would make flat access more complicated. In short, any attempt to rectify these problems will lead to greater complexity, either on the flat or the nested side of the interface.
(That is actually why I still prefer the simple enumerate_nested method! A proper tree structure with values at all nodes (and not just top-level nodes) might also be simpler and better. But this was fun to code nonetheless.)
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()
这篇关于将任意长度的位置[4、1、2]的列表转换为嵌套列表的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
