Welcome, guest | Sign In | My Account | Store | Cart
import collections

class OrderedSet(collections.MutableSet):
    
    KEY, PREV, NEXT = range(3)

    def __init__(self, iterable=None):
        self.end = end = [] 
        end += [None, end, end]         # sentinel node for doubly linked list
        self.map = {}                   # key --> [key, prev, 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 key not in self.map:
            end = self.end
            curr = end[self.PREV]
            curr[self.NEXT] = end[self.PREV] = self.map[key] = [key, curr, end]

    def discard(self, key):
        if key in self.map:        
            key, prev, next = self.map.pop(key)
            prev[self.NEXT] = next
            next[self.PREV] = prev

    def __iter__(self):
        end = self.end
        curr = end[self.NEXT]
        while curr is not end:
            yield curr[self.KEY]
            curr = curr[self.NEXT]

    def __reversed__(self):
        end = self.end
        curr = end[self.PREV]
        while curr is not end:
            yield curr[self.KEY]
            curr = curr[self.PREV]

    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 set(self) == set(other)

    def __del__(self):
        self.clear()                    # remove circular references


if __name__ == '__main__':
    print(OrderedSet('abracadaba'))
    print(OrderedSet('simsalabim'))
    x = OrderedSet('abracadaba')
    # doesn't raise "Exception TypeError: TypeError('list indices must be integers, not NoneType',) in ignored"

Diff to Previous Revision

--- revision 1 2011-03-24 10:55:46
+++ revision 2 2011-08-12 14:15:20
@@ -1,8 +1,8 @@
 import collections
 
-KEY, PREV, NEXT = range(3)
-
 class OrderedSet(collections.MutableSet):
+    
+    KEY, PREV, NEXT = range(3)
 
     def __init__(self, iterable=None):
         self.end = end = [] 
@@ -20,28 +20,28 @@
     def add(self, key):
         if key not in self.map:
             end = self.end
-            curr = end[PREV]
-            curr[NEXT] = end[PREV] = self.map[key] = [key, curr, end]
+            curr = end[self.PREV]
+            curr[self.NEXT] = end[self.PREV] = self.map[key] = [key, curr, end]
 
     def discard(self, key):
         if key in self.map:        
             key, prev, next = self.map.pop(key)
-            prev[NEXT] = next
-            next[PREV] = prev
+            prev[self.NEXT] = next
+            next[self.PREV] = prev
 
     def __iter__(self):
         end = self.end
-        curr = end[NEXT]
+        curr = end[self.NEXT]
         while curr is not end:
-            yield curr[KEY]
-            curr = curr[NEXT]
+            yield curr[self.KEY]
+            curr = curr[self.NEXT]
 
     def __reversed__(self):
         end = self.end
-        curr = end[PREV]
+        curr = end[self.PREV]
         while curr is not end:
-            yield curr[KEY]
-            curr = curr[PREV]
+            yield curr[self.KEY]
+            curr = curr[self.PREV]
 
     def pop(self, last=True):
         if not self:
@@ -63,7 +63,9 @@
     def __del__(self):
         self.clear()                    # remove circular references
 
-            
+
 if __name__ == '__main__':
     print(OrderedSet('abracadaba'))
     print(OrderedSet('simsalabim'))
+    x = OrderedSet('abracadaba')
+    # doesn't raise "Exception TypeError: TypeError('list indices must be integers, not NoneType',) in ignored"

History