1 # Originally from http://code.activestate.com/recipes/576694/
6 class OrderedSet(collections
.MutableSet
):
8 def __init__(self
, iterable
=None):
10 end
+= [None, end
, end
] # sentinel node for doubly linked list
11 self
.map = {} # key --> [key, prev, next]
12 if iterable
is not None:
18 def __contains__(self
, key
):
19 return key
in self
.map
26 curr
[2] = end
[1] = self
.map[key
] = [key
, curr
, end
]
28 def discard(self
, key
):
30 key
, prev
, next
= self
.map.pop(key
)
37 while curr
is not end
:
43 return '%s()' % (self
.__class
__.__name
__,)
44 return '%s(%r)' % (self
.__class
__.__name
__, list(self
))
46 if __name__
== '__main__':
47 s
= OrderedSet('abracadaba')
48 t
= OrderedSet('simsalabim')