python - Convert list of positions [4, 1, 2] of arbitrary length to an index for a nested list -

assuming list

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

i have function returns position list nested list of arbitrary depth. examples:

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

as can see not clear in beginning how many levels of nesting there are.

additional problem list modifications want use [:] or [4:] or [0:1] notations.

for human easy do: add many index position 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 approach not lead anywhere since had append strings , eval them later. obvious nonsense :)

what best way handle nested list unknown number of index positions , still have functionality handle normal list (read, modify, insert, remove)

i hope there answer that.

p.s. list must remain nested. flattening not option.

i had time fiddle around this. got little carried away. it's long, i'm pasting anyway. added set_item, insert, delete, find, , find_left methods, private methods allow low-level manipulation breaks cursor abstraction. added move_cursor method throws indexerror index tuples out of range or point non-toplevel object.

basically, (should) guaranteed long use public functions only, cursor points top-level object, , insertions , deletions happen @ top level. here, should able safely implement __getitem__, __setitem__, __delitem__, etc, , maybe __getslice__, __setslice__.

however, there couple of wrinkles. restriction cursor points toplevel object makes easy iterate on nested list though flat list. means cursor can't point @ lower-level objects, , hence kinds of insertions can't happen using insert alone. example, have 3 lists:

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

now put nested structure in nli, move 5, , try insert.

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

as can see, can insert l2, can't insert l3. in fact, right now, have use private function, breaks cursor abstraction in 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 unsubscriptable 

there surely ways implement safe public insert_between_branches method, involve more complication care bother right now.

another problem appears when 1 tries insert value after 4. you've seen, can insert value l2 before 5, if move cursor 4 , insert, you'll realize can't insert 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]] 

from perspective of flat access, inserting after 4 , inserting before 5 same thing, perspective of nested list, different. since insert left_insert, problem partially rectified right_insert method (which would, in turn, unable insert @ beginning of l1).

these problems dealt more allowing cursor point lower-level objects, make flat access more complicated. in short, attempt rectify these problems lead greater complexity, either on flat or nested side of interface.

(that why still prefer simple enumerate_nested method! proper tree structure values @ nodes (and not top-level nodes) might simpler , better. fun code nonetheless.)

import collections  class nestedlistiter(object):     '''a mutable container enables flat traversal of nested tree of      lists. nested_list should contain list-like mutable sequence.      preserve clear demarcation between 'leaves' , 'branches', empty      sequences not allowed toplevel objects.'''     def __init__(self, nested_list):         if not nested_list:             raise valueerror, 'nested_list must non-empty sequence'         self.nested_list = nested_list # @ point, vet make sure         self.go_to_head()              # contains no empty sequences      def _is_sequence(self, item=none):         '''private method test whether item non-string sequence.         if item none, test current item.'''         if item none:             item = self._get_item_at(self.stack)         return isinstance(item, collections.sequence) , not isinstance(item, basestring)      def _is_in_range(self, index_tuple=none):         '''private method test whether index in range.          if index none, test current index.'''         if index_tuple none:             index_tuple = self.stack         if any(x < 0 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 item @ arbitrary index, no bounds checking.'''         item = self.nested_list         in index_tuple:             item = item[i]         return item      def _set_item_at(self, index_tuple, value):         '''private method set item @ arbitrary index, no bounds checking.         throws valueerror if value empty non-string sequence.'''         if self._is_sequence(value) , not value:             raise valueerror, "cannot set 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 insert item @ arbitrary index, no bounds checking.         throws valueerror if value empty non-string sequence.'''         if self._is_sequence(value) , not value:             raise valueerror, "cannot insert 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 delete item @ arbitrary index, no bounds checking.         recursively deletes 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 tires increment top value of 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 tries decrement top value of 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 cursor head of nested list.'''         self.stack = []         while self._is_sequence():             self.stack.append(0)      def go_to_tail(self):         self.stack = []         '''move cursor tail of nested list.'''         while self._is_sequence():             self.stack.append(len(self.get_item()) - 1)      def right(self):         '''move cursor 1 step right in nested list.'''         while self._increment_stack() , 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 1 step left in nested list.'''         while self._decrement_stack() , 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 location indicated index_tuple.         raises error if index_tuple out of range or doesn't correspond         toplevel object.'''         item = self._get_item_at(index_tuple)         if self._is_sequence(item):             raise indexerror, 'index_tuple must point toplevel object'      def get_item(self):         '''get item @ cursor location.'''         return self._get_item_at(self.stack)      def set_item(self, value):         '''set item cursor locaiton.'''         return self._set_item_at(self.stack, value)      def insert(self, value):         '''insert item @ cursor location. if value sequence,          cursor moves first toplevel object in value after insertion.          otherwise, cursor not move.'''         temp_stack = self.stack[:]         self.left()         self._insert_at(temp_stack, value)         self.right()      def delete(self):         '''deete item @ cursor location. cursor not move.'''         temp_stack = self.stack[:]         self.left()         self._delete_at(temp_stack)         self.right()      def iterate(self):         '''iterate on 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 on 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 value in nested_list; move cursor first location of value.'''         in self.iterate():             if == value:                 break      def find_left(self, value):         '''search value backwards in nested_list; move cursor last location of value.'''         in self.iterate_left():             if == 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     in nli.iterate():         print i,     print     in nli.iterate_left():         print i,     print      nli.go_to_head()     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()