mutable list iterators - a proposal

[Jess Austin]

Sorry I didn't respond in a timely fashion; I've been out of town.

python at rcn.com (Raymond Hettinger) wrote in message news:<5d83790c.0403170242.759ac8d9 at posting.google.com>...
> List iterators likely won't change because
> * it does not encourage an error prone programming style
> * it is documented to perform as it currently does
> * there is likely existing code that relies on the current behavior
> * there are performance issues which changing it
> * there do not seem to be compelling, general use cases to warrant a
> change

These are all reasonable objections.

 
> Also, I'm not sure your proposal is self-consistent.  If I read it
> correctly, there is a strong notion of having the iterator remember
> the last item emitted even if its position changes.  However, with a
> combination of slice deletion and insertion, the notion of the last
> item emitted becomes muddy:
> 
> lyst = range(10)
> it = iter(lyst)
> for i in xrange(5):
>    it.next()
> lyst[3:7] = [20]
> print it.next()          # Should this print 20 or 7 ?

In this case my class returns a 20.  My thinking on this was that if a
slice containing the "normal" next item is replaced by a slice, the
iterator should go to the beginning of the replacement slice, EXCEPT
in the case where the new slice is the same length as the old slice,
in which case the iterator should stay where it is.  The exception is
for backwards compatibility with current uses.


> Py2.4 adds a new type, collections.deque(), that can reasonably be
> made to do what your asking (workable because there is no slicing,
> just appending or popping from either end and setitem value
> mutations):
> 
> >>> from collections import deque
> >>> d = deque('abcdefg')
> >>> it = iter(d)
> >>> it.next()
>  'a'
> >>> it.next()
>  'b'
> >>> d.extend('hijk')
> >>> d.appendleft('z')
> >>> d.appendleft('y')
> >>> list(it)   # this picks up right where it left off
>  ['c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
> >>> d
> deque(['y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
> 'k'])

This looks great.  It would indeed work for the class I had in mind. 
Frankly, the fact that the iterator for deque works *correctly* seems
to beg the question, "why doesn't the iterator for list work
correctly?"  I know, see above for the reasons.  The current list
iteration stills seems ugly, and I know it's jarring to new users
because I've been jarred by it, have forgotten it, and then been
jarred again.  As for performance, I think that it could be coded so
that all performance penalties would be within the iterator, and there
only after the list has been changed.  There follows a revision of the
code I posted originally, which attempts to demonstrate that.

cheers,
Jess


import itertools

class muterable_list(list):
    """just like a list except it iterates gracefully under
mutation"""
    Insertion = object()
    Deletion = object()
    def __init__(self, object_):
        list.__init__(self, object_)
        self._mutations = []
        self._iterators = {}
        self._iterators_keys = itertools.count()
    def __iter__(self):
        key = self._iterators_keys.next()
        self._iterators[key] = []
        i = 0
        try:
            while True:
                for position, direction in self._iterators[key]:
                    if isinstance(position, int):
                        if position < i:
                            if direction is self.Deletion:
                                i += -1
                            else:
                                i += 1
                    elif direction is self.Deletion: # slice deletion
                        start, stop, step = position.indices(i)
                        i += (start - stop)/step
                    elif position.start < i:         # slice insertion
                        i += position.stop - position.start
                self._iterators[key] = []
                yield self[i]
                i += 1
                for iterator in self._iterators:
                    self._iterators[iterator].extend(self._mutations)
                self._mutations = []
        except IndexError:
            del self._iterators[key]
    def __delslice__(self, i, j):
        list.__delslice__(self, i, j)
        if self._iterators:
            self._mutations.append((slice(i, j), self.Deletion))
    def __setslice__(self, i, j, object_):
        list.__setslice__(self, i, j, object_)
        if self._iterators:
            length = len(object_)
            if length != (j - i):
                self._mutations.append((slice(i, j), self.Deletion))
                self._mutations.append((slice(i, i + length),
                                        self.Insertion))
    def __delitem__(self, index):
        list.__delitem__(self, index)
        if self._iterators:
            self._mutations.append((index, self.Deletion))
    def __setitem__(self, index, object_):
        list.__setitem__(self, index, object_)
        if self._iterators:
            length = len(object_)
            if (isinstance(index, slice) and (index.step == 1 or
                index.step is None) and length != (index.start - 
                index.stop)):
                self._mutations.append((index, self.Deletion))
                self._mutations.append((slice(index.start,
                                              index.start+length),
                                        self.Insertion))
    def insert(self, index, object_):
        list.insert(self, index, object_)
        if self._iterators:
            self._mutations.append((index, self.Insertion))
    def pop(self, index):
        r = list.pop(self, index)
        if self._iterators:
            self._mutations.append((index, self.Deletion))
        return r
    def remove(self, object_):
        if self._iterators:
            mutation = self.index(object_), self.Deletion
            list.remove(self, object_)
            self._mutations.append(mutation)
        else:
            list.remove(self, object_)