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_iterabl e_list(list):
"""just like a list except it iterates gracefully under
mutation"""
def __init__(self, object):
list.__init__(s elf, 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__(se lf, i, j):
self.__delitem_ _(slice(i, j))
def __setslice__(se lf, i, j, object):
self.__setitem_ _(slice(i, j), object)
def __delitem__(sel f, 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.repea t(-1))
# inform each iterator of the changes to the list
for it in self._mutations :
self._mutations[it].append(mutatio ns)
else:
for it in self._mutations :
self._mutations[it].append(((index , -1),))
def __setitem__(sel f, 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.repea t(-1))
for it in self._mutations :
self._mutations[it].append(mutatio ns)
# 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(sel f, 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(obje ct)
list.remove(sel f, object)
for it in self._mutations :
self._mutations[it].append(((index , -1),))
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_iterabl e_list(list):
"""just like a list except it iterates gracefully under
mutation"""
def __init__(self, object):
list.__init__(s elf, 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__(se lf, i, j):
self.__delitem_ _(slice(i, j))
def __setslice__(se lf, i, j, object):
self.__setitem_ _(slice(i, j), object)
def __delitem__(sel f, 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.repea t(-1))
# inform each iterator of the changes to the list
for it in self._mutations :
self._mutations[it].append(mutatio ns)
else:
for it in self._mutations :
self._mutations[it].append(((index , -1),))
def __setitem__(sel f, 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.repea t(-1))
for it in self._mutations :
self._mutations[it].append(mutatio ns)
# 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(sel f, 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(obje ct)
list.remove(sel f, object)
for it in self._mutations :
self._mutations[it].append(((index , -1),))
Comment