src/soc/decoder/orderedset.py

   1 # Originally from http://code.activestate.com/recipes/576694/
   2 # cut down to minimum
   3
   4 import collections
   5
   6 class OrderedSet(collections.MutableSet):
   7
   8     def __init__(self, iterable=None):
   9         self.end = end = []
  10         end += [None, end, end]         # sentinel node for doubly linked list
  11         self.map = {}                   # key --> [key, prev, next]
  12         if iterable is not None:
  13             self |= iterable
  14
  15     def __len__(self):
  16         return len(self.map)
  17
  18     def __contains__(self, key):
  19         return key in self.map
  20
  21     def add(self, key):
  22         if key in self.map:
  23             return
  24         end = self.end
  25         curr = end[1]
  26         curr[2] = end[1] = self.map[key] = [key, curr, end]
  27
  28     def discard(self, key):
  29         if key in self.map:
  30             key, prev, next = self.map.pop(key)
  31             prev[2] = next
  32             next[1] = prev
  33
  34     def __iter__(self):
  35         end = self.end
  36         curr = end[2]
  37         while curr is not end:
  38             yield curr[0]
  39             curr = curr[2]
  40
  41     def __repr__(self):
  42         if not self:
  43             return '%s()' % (self.__class__.__name__,)
  44         return '%s(%r)' % (self.__class__.__name__, list(self))
  45
  46 if __name__ == '__main__':
  47     s = OrderedSet('abracadaba')
  48     t = OrderedSet('simsalabim')
  49     print(s | t)
  50     print(s & t)
  51     print(s - t)