mutable list iterators - a proposal

[Jess Austin]

hi,

I like the way that Python does lists, and I love the way it does
iterators.  But I've decided I don't like what it does with iterators
of lists.  Lists are supposed to be mutable sequences, but try to use
an iterator of a list that you're mutating and watch it all fall to
pieces.  That is, if you change the length of a section of the list
through which the iterator has already passed, it will lose track of
where it is.  I think this should be fixed for 2.4.  I'm not sure if
this is a bug or a PEP, so I'd like to hear from others on this
newsgroup.

I've coded the following Python implementation of how I think lists
should work.  It looks a little odd, and I'm sure that a C
implementation could be quite a bit more efficient (at least I hope
that is the case), and it wouldn't leak iterators like this one does. 
But I think I've thought of, and dealt with, all of the weird cases. 
These include: adding before the last yielded item, subtracting before
the next item to be yielded, adding between the last-yielded and
next-yielded items, subtracting the next-yielded item, etc.  I think
that this subclass does the right thing in each of these cases.  I'm
curious to see if others agree, and whether they think something like
this should be in the next version of Python.  This code should work
with 2.3.

I hope this isn't in conflict with any previous irrevocable
pronouncements.  b-)

Hope you like it,
Jess



import itertools

class mutable_iterable_list(list):
    """just like a list except it iterates gracefully under
mutation"""
    def __init__(self, object):
        list.__init__(self, object)
        # set up a way for other methods to communicate with iterators
        self._mutations = {}
        self._iterator_keys = itertools.count()
    def __iter__(self):
        # get a unique name for this iterator and 'register' it
        key = self._iterator_keys.next()
        self._mutations[key] = []
        i = 0
        try:
            while True:
                # calculate the cumulative effect of all changes to
the list
                # since the last yield statement
                for mutation in self._mutations[key]:
                    delta = 0
                    # we must use nesting to accomodate slice deletion
-
                    # if we didn't accumulate in delta, i and j could
pass
                    # each other in the night
                    # otherwise a list of (j, d)'s would do
                    for j, d in mutation:
                        if j < i:
                            delta += d
                    i += delta
                self._mutations[key] = []
                yield self[i]
                i += 1
        except IndexError:
            pass
        del self._mutations[key]   # this iterator needs no further
updates
    # avoid calling list.__delslice__ and list.__setslice__
    def __delslice__(self, i, j):
        self.__delitem__(slice(i, j))
    def __setslice__(self, i, j, object):
        self.__setitem__(slice(i, j), object)
    def __delitem__(self, index):
        list.__delitem__(self, index)
        if type(index) is slice:
            # range() can't handle None as an argument
            start = index.start or 0
            if index.stop is None:
                stop = len(self)
            else:
                stop = index.stop
            step = index.step or 1
            # record the implicit deletion at each point where it
occurs
            mutations = zip(range(start, stop, step),
itertools.repeat(-1))
            # inform each iterator of the changes to the list
            for it in self._mutations:
                self._mutations[it].append(mutations)
        else:
            for it in self._mutations:
                self._mutations[it].append(((index, -1),))
    def __setitem__(self, index, object):
        list.__setitem__(self, index, object)
        # otherwise __setitem__ has no effect on iterators
        if type(index) is slice and index.step is None:
            start = index.start or 0
            if index.stop is None:
                stop = len(self)
            else:
                stop = index.stop
            mutations = zip(range(start, stop), itertools.repeat(-1))
            for it in self._mutations:
                self._mutations[it].append(mutations)
                # record the insertion at the beginning of the slice -
this is
                # added separately so that if i was pointing to part
of the
                # affected slice, it will go back to the beginning of
the added
                # sequence
                self._mutations[it].append(((start, len(object)),))
    def insert(self, index, object):
        list.insert(self, index, object)
        for it in self._mutations:
            self._mutations[it].append(((index, 1),))
    def pop(self, index):
        r = list.pop(self, index)
        for it in self._mutations:
            self._mutations[it].append(((index, -1),))
        return r
    def remove(self, object):
        index = self.index(object)
        list.remove(self, object)
        for it in self._mutations:
            self._mutations[it].append(((index, -1),))