# Ordered Sets

pataphor pataphor at gmail.com
Thu Mar 26 11:29:43 CET 2009

```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/

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

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]

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))
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)