У меня наконец-то появилось время поиграться с этим. Я немного увлекся. Это долго, но я все равно вставляю это. Я добавил методы 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. Как вы уже видели, вы можете вставить значение в l2 до 5, но если переместить курсор на 4 и insert, вы быстро поймете, что не можете вставить что-то после 4 внутри 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).
Эти проблемы, вероятно, можно было бы разрешить в более общем плане, позволив курсору указывать на объекты более низкого уровня, но это усложнило бы плоский доступ. Короче говоря, любая попытка исправить эти проблемы приведет к большей сложности, как на плоской, так и на вложенной стороне интерфейса.
(Именно поэтому я все еще предпочитаю простой метод 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()