1 # Originally from http://code.activestate.com/recipes/576694/
4 from collections
.abc
import MutableSet
7 class OrderedSet(MutableSet
):
9 def __init__(self
, iterable
=None):
11 end
+= [None, end
, end
] # sentinel node for doubly linked list
12 self
.map = {} # key --> [key, prev, next]
13 if iterable
is not None:
19 def __contains__(self
, key
):
20 return key
in self
.map
27 curr
[2] = end
[1] = self
.map[key
] = [key
, curr
, end
]
29 def discard(self
, key
):
31 key
, prev
, next
= self
.map.pop(key
)
38 while curr
is not end
:
44 return '%s()' % (self
.__class
__.__name
__,)
45 return '%s(%r)' % (self
.__class
__.__name
__, list(self
))
47 if __name__
== '__main__':
48 s
= OrderedSet('abracadaba')
49 t
= OrderedSet('simsalabim')