Ordered Sets

[pataphor]

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