Raymond Hettinger wrote:
Right. Here's a link to a weakref version (though I think the
previous __del__ version also does the trick):
http://code.activestate.com/recipes/576696/
Interesting. But how about this one? Does it also have the reference
problem? By the way collections.MutableSet needs python >= 2.6
P.
import collections
class OrderedSet(collections.MutableSet):
'Set that remembers the order elements were added'
# Big-O running times for all methods are the same as for regular sets.
def __init__(self, iterable=None):
self.__map = {} # key --> [prev,key,next]
if iterable is not None:
self |= iterable
def __len__(self):
return len(self.__map)
def __contains__(self, key):
return key in self.__map
def add(self, key):
if not self.__map:
self.start = key
self.__map = {key: [key,key,key]}
elif key not in self.__map:
a,b,c = self.__map[self.start]
self.__map[a][2] = key
self.__map[b][0] = key
self.__map[key] = [a,key,b]
def discard(self, key):
if key in self.__map:
a,b,c = self.__map.pop(key)
if self.__map:
self.__map[a][2] = c
self.__map[c][0] = a
if b == self.start:
self.start = c
def __iter__(self):
if self.__map:
a,b,c = self.__map[self.start]
while c is not self.start:
yield b
a,b,c = self.__map[c]
yield b
def __reversed__(self):
if self.__map:
a,b,c = self.__map[self.start]
while a is not self.start:
yield a
a,b,c = self.__map[a]
yield a
def pop(self, last=True):
if not self:
raise KeyError('set is empty')
key = next(reversed(self)) if last else next(iter(self))
self.discard(key)
return key
def __repr__(self):
if not self:
return '%s()' % (self.__class__.__name__,)
return '%s(%r)' % (self.__class__.__name__, list(self))
def __eq__(self, other):
if isinstance(other, OrderedSet):
return len(self) == len(other) and list(self) == list(other)
return not self.isdisjoint(other)
def test():
D = OrderedSet('abcd')
R = OrderedSet()
for x in list(D):
print(D,R)
R.add(D.pop(last = False))
print(D,R)
if __name__ == '__main__':
test()
--
http://mail.python.org/mailman/listinfo/python-list
