Convertir la lista de posiciones de longitud arbitraria en un índice para una lista anidada

Asumiendo esta lista

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

Tengo una función que devuelve una lista de posiciones para una lista anidada de profundidad arbitraria. Ejemplos :

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

Como puede ver, al principio no está claro cuántos niveles de anidación hay.

Problema adicional Para las modificaciones de la lista, quiero usar las notaciones [:] o [4:] o [0: 1].

Para un ser humano es muy fácil de hacer: simplemente agregue tantas posiciones de índice como sea necesario.

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

Sin embargo, este enfoque no lleva a ninguna parte, ya que tuve que agregar cadenas y evaluarlas más tarde. Sin sentido obvio 🙂

¿Cuál es la mejor manera de manejar una lista anidada con un número desconocido de posiciones de índice y aún así tener la funcionalidad para manejarlo como una lista normal (leer, modificar, insertar, eliminar)?

Espero que haya una respuesta a eso.

PD la lista debe permanecer anidada. El aplanamiento no es una opción.

Finalmente tuve algo de tiempo para juguetear con esto. Me deje llevar un poquito. Es largo, pero lo estoy pegando de todos modos. find_left métodos set_item , insert , delete , find y find_left , así como algunos métodos privados para permitir la manipulación de bajo nivel que rompe la abstracción del cursor. También agregué un método move_cursor que lanza un IndexError para tuplas de índice que están fuera de rango o apuntan a un objeto que no es de nivel superior.

Básicamente, se debe (debería) garantizar que, siempre que use funciones públicas solamente, el cursor siempre apunta a un objeto de nivel superior, y las inserciones y eliminaciones ocurren en el nivel superior. Desde aquí, debería poder implementar de forma segura __getitem__ , __setitem__ , __delitem__ , etc., y tal vez incluso __getslice__ , __setslice__ .

Sin embargo, hay un par de arrugas. La restricción de que el cursor siempre apunta a un objeto de nivel superior hace que sea muy fácil recorrer la lista anidada como si fuera una lista plana. Pero también significa que el cursor no puede apuntar a objetos de nivel inferior y, por lo tanto, algunos tipos de inserciones no pueden suceder usando solo insert . Por ejemplo, digamos que tienes tres listas:

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

Ahora ponga esta estructura anidada en un NLI, muévase a 5 e intente insertarlo.

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

Como puede ver, puede insertar algo en l2 , pero no puede insertar fácilmente algo en l3 . De hecho, para hacerlo ahora mismo, tiene que usar una función privada, que rompe la abstracción del cursor de una manera desagradable:

 >>> 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 "", line 1, in  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 

Seguramente hay maneras de implementar un método de insert_between_branches público seguro, pero implican más complicaciones de las que me importa preocuparme ahora.

Otro problema aparece cuando uno intenta insertar un valor después de 4 . Como ha visto, puede insertar un valor en l2 antes de 5 , pero si mueve el cursor a 4 e insert , rápidamente se dará cuenta de que no puede insertar algo después de 4 dentro de 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]] 

Desde la perspectiva del acceso plano, la inserción después de 4 y la inserción antes de 5 son la misma cosa, pero desde la perspectiva de la lista anidada, son diferentes. Dado que insert es efectivamente un left_insert , este problema podría ser parcialmente right_insert con un método right_insert (que, a su vez, sería incapaz de insertar al principio de l1).

Estos problemas probablemente podrían tratarse de manera más general al permitir que el cursor apunte a objetos de nivel inferior, pero eso haría que el acceso plano sea más complicado. En resumen, cualquier bash de rectificar estos problemas dará lugar a una mayor complejidad, ya sea en el plano o en el lado nested de la interfaz.

(En realidad, esa es la razón por la que prefiero el método enumerate_nested simple. Una estructura de árbol adecuada con valores en todos los nodos (y no solo en los nodos de nivel superior) también podría ser más simple y mejor.

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

La primera parte es bastante fácil.

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

La segunda parte requiere mucho más esfuerzo, pero aún es factible. Insinuación:

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