src/openpower/decoder/orderedset.py

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