_scons_sets15.py.svn-base
上传用户:market2
上传日期:2018-11-18
资源大小:18786k
文件大小:5k
源码类别:

外挂编程

开发平台:

Windows_Unix

  1. #
  2. # A Set class that works all the way back to Python 1.5.  From:
  3. #
  4. #       Python Cookbook:  Yet another Set class for Python
  5. #       http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/106469
  6. #       Goncalo Rodriques
  7. #
  8. #       This is a pure Pythonic implementation of a set class.  The syntax
  9. #       and methods implemented are, for the most part, borrowed from
  10. #       PEP 218 by Greg Wilson.
  11. #
  12. # Note that this class violates the formal definition of a set() by adding
  13. # a __getitem__() method so we can iterate over a set's elements under
  14. # Python 1.5 and 2.1, which don't support __iter__() and iterator types.
  15. #
  16. import string
  17. class Set:
  18.     """The set class. It can contain mutable objects."""
  19.     def __init__(self, seq = None):
  20.         """The constructor. It can take any object giving an iterator as an optional
  21.         argument to populate the new set."""
  22.         self.elems = []
  23.         if seq:
  24.             for elem in seq:
  25.                 if elem not in self.elems:
  26.                     hash(elem)
  27.                     self.elems.append(elem)
  28.     def __str__(self):
  29.         return "set([%s])" % string.join(map(str, self.elems), ", ")
  30.     def copy(self):
  31.         """Shallow copy of a set object."""
  32.         return Set(self.elems)
  33.     def __contains__(self, elem):
  34.         return elem in self.elems
  35.     def __len__(self):
  36.         return len(self.elems)
  37.     def __getitem__(self, index):
  38.         # Added so that Python 1.5 can iterate over the elements.
  39.         # The cookbook recipe's author didn't like this because there
  40.         # really isn't any order in a set object, but this is necessary
  41.         # to make the class work well enough for our purposes.
  42.         return self.elems[index]
  43.     def items(self):
  44.         """Returns a list of the elements in the set."""
  45.         return self.elems
  46.     def add(self, elem):
  47.         """Add one element to the set."""
  48.         if elem not in self.elems:
  49.             hash(elem)
  50.             self.elems.append(elem)
  51.     def remove(self, elem):
  52.         """Remove an element from the set. Return an error if elem is not in the set."""
  53.         try:
  54.             self.elems.remove(elem)
  55.         except ValueError:
  56.             raise LookupError, "Object %s is not a member of the set." % str(elem)
  57.     def discard(self, elem):
  58.         """Remove an element from the set. Do nothing if elem is not in the set."""
  59.         try:
  60.             self.elems.remove(elem)
  61.         except ValueError:
  62.             pass
  63.     def sort(self, func=cmp):
  64.         self.elems.sort(func)
  65.     #Define an iterator for a set.
  66.     def __iter__(self):
  67.         return iter(self.elems)
  68.     #The basic binary operations with sets.
  69.     def __or__(self, other):
  70.         """Union of two sets."""
  71.         ret = self.copy()
  72.         for elem in other.elems:
  73.             if elem not in ret:
  74.                 ret.elems.append(elem)
  75.         return ret
  76.     def __sub__(self, other):
  77.         """Difference of two sets."""
  78.         ret = self.copy()
  79.         for elem in other.elems:
  80.             ret.discard(elem)
  81.         return ret
  82.     def __and__(self, other):
  83.         """Intersection of two sets."""
  84.         ret = Set()
  85.         for elem in self.elems:
  86.             if elem in other.elems:
  87.                 ret.elems.append(elem)
  88.         return ret
  89.     def __add__(self, other):
  90.         """Symmetric difference of two sets."""
  91.         ret = Set()
  92.         temp = other.copy()
  93.         for elem in self.elems:
  94.             if elem in temp.elems:
  95.                 temp.elems.remove(elem)
  96.             else:
  97.                 ret.elems.append(elem)
  98.         #Add remaining elements.
  99.         for elem in temp.elems:
  100.                 ret.elems.append(elem)
  101.         return ret
  102.     def __mul__(self, other):
  103.         """Cartesian product of two sets."""
  104.         ret = Set()
  105.         for elemself in self.elems:
  106.             x = map(lambda other, s=elemself: (s, other), other.elems)
  107.             ret.elems.extend(x)
  108.         return ret
  109.     #Some of the binary comparisons.
  110.     def __lt__(self, other):
  111.         """Returns 1 if the lhs set is contained but not equal to the rhs set."""
  112.         if len(self.elems) < len(other.elems):
  113.             temp = other.copy()
  114.             for elem in self.elems:
  115.                 if elem in temp.elems:
  116.                     temp.remove(elem)
  117.                 else:
  118.                     return 0
  119.             return len(temp.elems) == 0
  120.         else:
  121.             return 0
  122.     def __le__(self, other):
  123.         """Returns 1 if the lhs set is contained in the rhs set."""
  124.         if len(self.elems) <= len(other.elems):
  125.             ret = 1
  126.             for elem in self.elems:
  127.                 if elem not in other.elems:
  128.                     ret = 0
  129.                     break
  130.             return ret
  131.         else:
  132.             return 0
  133.     def __eq__(self, other):
  134.         """Returns 1 if the sets are equal."""
  135.         if len(self.elems) != len(other.elems):
  136.             return 0
  137.         else:
  138.             return len(self - other) == 0
  139.     def __cmp__(self, other):
  140.         """Returns 1 if the sets are equal."""
  141.         if self.__lt__(other):
  142.             return -1
  143.         elif other.__lt__(self):
  144.             return 1
  145.         else:
  146.             return 0