set.py 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  1. # Copyright (C) 2003-2007, 2009-2011 Nominum, Inc.
  2. #
  3. # Permission to use, copy, modify, and distribute this software and its
  4. # documentation for any purpose with or without fee is hereby granted,
  5. # provided that the above copyright notice and this permission notice
  6. # appear in all copies.
  7. #
  8. # THE SOFTWARE IS PROVIDED "AS IS" AND NOMINUM DISCLAIMS ALL WARRANTIES
  9. # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10. # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL NOMINUM BE LIABLE FOR
  11. # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12. # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13. # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  14. # OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15. """A simple Set class."""
  16. class Set(object):
  17. """A simple set class.
  18. Sets are not in Python until 2.3, and rdata are not immutable so
  19. we cannot use sets.Set anyway. This class implements subset of
  20. the 2.3 Set interface using a list as the container.
  21. @ivar items: A list of the items which are in the set
  22. @type items: list"""
  23. __slots__ = ['items']
  24. def __init__(self, items=None):
  25. """Initialize the set.
  26. @param items: the initial set of items
  27. @type items: any iterable or None
  28. """
  29. self.items = []
  30. if items is not None:
  31. for item in items:
  32. self.add(item)
  33. def __repr__(self):
  34. return "dns.simpleset.Set(%s)" % repr(self.items)
  35. def add(self, item):
  36. """Add an item to the set."""
  37. if item not in self.items:
  38. self.items.append(item)
  39. def remove(self, item):
  40. """Remove an item from the set."""
  41. self.items.remove(item)
  42. def discard(self, item):
  43. """Remove an item from the set if present."""
  44. try:
  45. self.items.remove(item)
  46. except ValueError:
  47. pass
  48. def _clone(self):
  49. """Make a (shallow) copy of the set.
  50. There is a 'clone protocol' that subclasses of this class
  51. should use. To make a copy, first call your super's _clone()
  52. method, and use the object returned as the new instance. Then
  53. make shallow copies of the attributes defined in the subclass.
  54. This protocol allows us to write the set algorithms that
  55. return new instances (e.g. union) once, and keep using them in
  56. subclasses.
  57. """
  58. cls = self.__class__
  59. obj = cls.__new__(cls)
  60. obj.items = list(self.items)
  61. return obj
  62. def __copy__(self):
  63. """Make a (shallow) copy of the set."""
  64. return self._clone()
  65. def copy(self):
  66. """Make a (shallow) copy of the set."""
  67. return self._clone()
  68. def union_update(self, other):
  69. """Update the set, adding any elements from other which are not
  70. already in the set.
  71. @param other: the collection of items with which to update the set
  72. @type other: Set object
  73. """
  74. if not isinstance(other, Set):
  75. raise ValueError('other must be a Set instance')
  76. if self is other:
  77. return
  78. for item in other.items:
  79. self.add(item)
  80. def intersection_update(self, other):
  81. """Update the set, removing any elements from other which are not
  82. in both sets.
  83. @param other: the collection of items with which to update the set
  84. @type other: Set object
  85. """
  86. if not isinstance(other, Set):
  87. raise ValueError('other must be a Set instance')
  88. if self is other:
  89. return
  90. # we make a copy of the list so that we can remove items from
  91. # the list without breaking the iterator.
  92. for item in list(self.items):
  93. if item not in other.items:
  94. self.items.remove(item)
  95. def difference_update(self, other):
  96. """Update the set, removing any elements from other which are in
  97. the set.
  98. @param other: the collection of items with which to update the set
  99. @type other: Set object
  100. """
  101. if not isinstance(other, Set):
  102. raise ValueError('other must be a Set instance')
  103. if self is other:
  104. self.items = []
  105. else:
  106. for item in other.items:
  107. self.discard(item)
  108. def union(self, other):
  109. """Return a new set which is the union of I{self} and I{other}.
  110. @param other: the other set
  111. @type other: Set object
  112. @rtype: the same type as I{self}
  113. """
  114. obj = self._clone()
  115. obj.union_update(other)
  116. return obj
  117. def intersection(self, other):
  118. """Return a new set which is the intersection of I{self} and I{other}.
  119. @param other: the other set
  120. @type other: Set object
  121. @rtype: the same type as I{self}
  122. """
  123. obj = self._clone()
  124. obj.intersection_update(other)
  125. return obj
  126. def difference(self, other):
  127. """Return a new set which I{self} - I{other}, i.e. the items
  128. in I{self} which are not also in I{other}.
  129. @param other: the other set
  130. @type other: Set object
  131. @rtype: the same type as I{self}
  132. """
  133. obj = self._clone()
  134. obj.difference_update(other)
  135. return obj
  136. def __or__(self, other):
  137. return self.union(other)
  138. def __and__(self, other):
  139. return self.intersection(other)
  140. def __add__(self, other):
  141. return self.union(other)
  142. def __sub__(self, other):
  143. return self.difference(other)
  144. def __ior__(self, other):
  145. self.union_update(other)
  146. return self
  147. def __iand__(self, other):
  148. self.intersection_update(other)
  149. return self
  150. def __iadd__(self, other):
  151. self.union_update(other)
  152. return self
  153. def __isub__(self, other):
  154. self.difference_update(other)
  155. return self
  156. def update(self, other):
  157. """Update the set, adding any elements from other which are not
  158. already in the set.
  159. @param other: the collection of items with which to update the set
  160. @type other: any iterable type"""
  161. for item in other:
  162. self.add(item)
  163. def clear(self):
  164. """Make the set empty."""
  165. self.items = []
  166. def __eq__(self, other):
  167. # Yes, this is inefficient but the sets we're dealing with are
  168. # usually quite small, so it shouldn't hurt too much.
  169. for item in self.items:
  170. if item not in other.items:
  171. return False
  172. for item in other.items:
  173. if item not in self.items:
  174. return False
  175. return True
  176. def __ne__(self, other):
  177. return not self.__eq__(other)
  178. def __len__(self):
  179. return len(self.items)
  180. def __iter__(self):
  181. return iter(self.items)
  182. def __getitem__(self, i):
  183. return self.items[i]
  184. def __delitem__(self, i):
  185. del self.items[i]
  186. def issubset(self, other):
  187. """Is I{self} a subset of I{other}?
  188. @rtype: bool
  189. """
  190. if not isinstance(other, Set):
  191. raise ValueError('other must be a Set instance')
  192. for item in self.items:
  193. if item not in other.items:
  194. return False
  195. return True
  196. def issuperset(self, other):
  197. """Is I{self} a superset of I{other}?
  198. @rtype: bool
  199. """
  200. if not isinstance(other, Set):
  201. raise ValueError('other must be a Set instance')
  202. for item in other.items:
  203. if item not in self.items:
  204. return False
  205. return True