scons/scons-1.2.0/engine/SCons/compat/_scons_sets15.py

   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
  17 import string
  18
  19 class Set:
  20     """The set class. It can contain mutable objects."""
  21
  22     def __init__(self, seq = None):
  23         """The constructor. It can take any object giving an iterator as an optional
  24         argument to populate the new set."""
  25         self.elems = []
  26         if seq:
  27             for elem in seq:
  28                 if elem not in self.elems:
  29                     hash(elem)
  30                     self.elems.append(elem)
  31
  32     def __str__(self):
  33         return "set([%s])" % string.join(map(str, self.elems), ", ")
  34
  35
  36     def copy(self):
  37         """Shallow copy of a set object."""
  38         return Set(self.elems)
  39
  40     def __contains__(self, elem):
  41         return elem in self.elems
  42
  43     def __len__(self):
  44         return len(self.elems)
  45
  46     def __getitem__(self, index):
  47         # Added so that Python 1.5 can iterate over the elements.
  48         # The cookbook recipe's author didn't like this because there
  49         # really isn't any order in a set object, but this is necessary
  50         # to make the class work well enough for our purposes.
  51         return self.elems[index]
  52
  53     def items(self):
  54         """Returns a list of the elements in the set."""
  55         return self.elems
  56
  57     def add(self, elem):
  58         """Add one element to the set."""
  59         if elem not in self.elems:
  60             hash(elem)
  61             self.elems.append(elem)
  62
  63     def remove(self, elem):
  64         """Remove an element from the set. Return an error if elem is not in the set."""
  65         try:
  66             self.elems.remove(elem)
  67         except ValueError:
  68             raise LookupError, "Object %s is not a member of the set." % str(elem)
  69
  70     def discard(self, elem):
  71         """Remove an element from the set. Do nothing if elem is not in the set."""
  72         try:
  73             self.elems.remove(elem)
  74         except ValueError:
  75             pass
  76
  77     def sort(self, func=cmp):
  78         self.elems.sort(func)
  79
  80     #Define an iterator for a set.
  81     def __iter__(self):
  82         return iter(self.elems)
  83
  84     #The basic binary operations with sets.
  85     def __or__(self, other):
  86         """Union of two sets."""
  87         ret = self.copy()
  88         for elem in other.elems:
  89             if elem not in ret:
  90                 ret.elems.append(elem)
  91         return ret
  92
  93     def __sub__(self, other):
  94         """Difference of two sets."""
  95         ret = self.copy()
  96         for elem in other.elems:
  97             ret.discard(elem)
  98         return ret
  99
 100     def __and__(self, other):
 101         """Intersection of two sets."""
 102         ret = Set()
 103         for elem in self.elems:
 104             if elem in other.elems:
 105                 ret.elems.append(elem)
 106         return ret
 107
 108     def __add__(self, other):
 109         """Symmetric difference of two sets."""
 110         ret = Set()
 111         temp = other.copy()
 112         for elem in self.elems:
 113             if elem in temp.elems:
 114                 temp.elems.remove(elem)
 115             else:
 116                 ret.elems.append(elem)
 117         #Add remaining elements.
 118         for elem in temp.elems:
 119                 ret.elems.append(elem)
 120         return ret
 121
 122     def __mul__(self, other):
 123         """Cartesian product of two sets."""
 124         ret = Set()
 125         for elemself in self.elems:
 126             x = map(lambda other, s=elemself: (s, other), other.elems)
 127             ret.elems.extend(x)
 128         return ret
 129
 130     #Some of the binary comparisons.
 131     def __lt__(self, other):
 132         """Returns 1 if the lhs set is contained but not equal to the rhs set."""
 133         if len(self.elems) < len(other.elems):
 134             temp = other.copy()
 135             for elem in self.elems:
 136                 if elem in temp.elems:
 137                     temp.remove(elem)
 138                 else:
 139                     return 0
 140             return len(temp.elems) == 0
 141         else:
 142             return 0
 143
 144     def __le__(self, other):
 145         """Returns 1 if the lhs set is contained in the rhs set."""
 146         if len(self.elems) <= len(other.elems):
 147             ret = 1
 148             for elem in self.elems:
 149                 if elem not in other.elems:
 150                     ret = 0
 151                     break
 152             return ret
 153         else:
 154             return 0
 155
 156     def __eq__(self, other):
 157         """Returns 1 if the sets are equal."""
 158         if len(self.elems) != len(other.elems):
 159             return 0
 160         else:
 161             return len(self - other) == 0
 162
 163     def __cmp__(self, other):
 164         """Returns 1 if the sets are equal."""
 165         if self.__lt__(other):
 166             return -1
 167         elif other.__lt__(self):
 168             return 1
 169         else:
 170             return 0