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 16"""A simple Set class.""" 17 18 19class Set(object): 20 21 """A simple set class. 22 23 Sets are not in Python until 2.3, and rdata are not immutable so 24 we cannot use sets.Set anyway. This class implements subset of 25 the 2.3 Set interface using a list as the container. 26 27 @ivar items: A list of the items which are in the set 28 @type items: list""" 29 30 __slots__ = ['items'] 31 32 def __init__(self, items=None): 33 """Initialize the set. 34 35 @param items: the initial set of items 36 @type items: any iterable or None 37 """ 38 39 self.items = [] 40 if items is not None: 41 for item in items: 42 self.add(item) 43 44 def __repr__(self): 45 return "dns.simpleset.Set(%s)" % repr(self.items) 46 47 def add(self, item): 48 """Add an item to the set.""" 49 if item not in self.items: 50 self.items.append(item) 51 52 def remove(self, item): 53 """Remove an item from the set.""" 54 self.items.remove(item) 55 56 def discard(self, item): 57 """Remove an item from the set if present.""" 58 try: 59 self.items.remove(item) 60 except ValueError: 61 pass 62 63 def _clone(self): 64 """Make a (shallow) copy of the set. 65 66 There is a 'clone protocol' that subclasses of this class 67 should use. To make a copy, first call your super's _clone() 68 method, and use the object returned as the new instance. Then 69 make shallow copies of the attributes defined in the subclass. 70 71 This protocol allows us to write the set algorithms that 72 return new instances (e.g. union) once, and keep using them in 73 subclasses. 74 """ 75 76 cls = self.__class__ 77 obj = cls.__new__(cls) 78 obj.items = list(self.items) 79 return obj 80 81 def __copy__(self): 82 """Make a (shallow) copy of the set.""" 83 return self._clone() 84 85 def copy(self): 86 """Make a (shallow) copy of the set.""" 87 return self._clone() 88 89 def union_update(self, other): 90 """Update the set, adding any elements from other which are not 91 already in the set. 92 @param other: the collection of items with which to update the set 93 @type other: Set object 94 """ 95 if not isinstance(other, Set): 96 raise ValueError('other must be a Set instance') 97 if self is other: 98 return 99 for item in other.items: 100 self.add(item) 101 102 def intersection_update(self, other): 103 """Update the set, removing any elements from other which are not 104 in both sets. 105 @param other: the collection of items with which to update the set 106 @type other: Set object 107 """ 108 if not isinstance(other, Set): 109 raise ValueError('other must be a Set instance') 110 if self is other: 111 return 112 # we make a copy of the list so that we can remove items from 113 # the list without breaking the iterator. 114 for item in list(self.items): 115 if item not in other.items: 116 self.items.remove(item) 117 118 def difference_update(self, other): 119 """Update the set, removing any elements from other which are in 120 the set. 121 @param other: the collection of items with which to update the set 122 @type other: Set object 123 """ 124 if not isinstance(other, Set): 125 raise ValueError('other must be a Set instance') 126 if self is other: 127 self.items = [] 128 else: 129 for item in other.items: 130 self.discard(item) 131 132 def union(self, other): 133 """Return a new set which is the union of I{self} and I{other}. 134 135 @param other: the other set 136 @type other: Set object 137 @rtype: the same type as I{self} 138 """ 139 140 obj = self._clone() 141 obj.union_update(other) 142 return obj 143 144 def intersection(self, other): 145 """Return a new set which is the intersection of I{self} and I{other}. 146 147 @param other: the other set 148 @type other: Set object 149 @rtype: the same type as I{self} 150 """ 151 152 obj = self._clone() 153 obj.intersection_update(other) 154 return obj 155 156 def difference(self, other): 157 """Return a new set which I{self} - I{other}, i.e. the items 158 in I{self} which are not also in I{other}. 159 160 @param other: the other set 161 @type other: Set object 162 @rtype: the same type as I{self} 163 """ 164 165 obj = self._clone() 166 obj.difference_update(other) 167 return obj 168 169 def __or__(self, other): 170 return self.union(other) 171 172 def __and__(self, other): 173 return self.intersection(other) 174 175 def __add__(self, other): 176 return self.union(other) 177 178 def __sub__(self, other): 179 return self.difference(other) 180 181 def __ior__(self, other): 182 self.union_update(other) 183 return self 184 185 def __iand__(self, other): 186 self.intersection_update(other) 187 return self 188 189 def __iadd__(self, other): 190 self.union_update(other) 191 return self 192 193 def __isub__(self, other): 194 self.difference_update(other) 195 return self 196 197 def update(self, other): 198 """Update the set, adding any elements from other which are not 199 already in the set. 200 @param other: the collection of items with which to update the set 201 @type other: any iterable type""" 202 for item in other: 203 self.add(item) 204 205 def clear(self): 206 """Make the set empty.""" 207 self.items = [] 208 209 def __eq__(self, other): 210 # Yes, this is inefficient but the sets we're dealing with are 211 # usually quite small, so it shouldn't hurt too much. 212 for item in self.items: 213 if item not in other.items: 214 return False 215 for item in other.items: 216 if item not in self.items: 217 return False 218 return True 219 220 def __ne__(self, other): 221 return not self.__eq__(other) 222 223 def __len__(self): 224 return len(self.items) 225 226 def __iter__(self): 227 return iter(self.items) 228 229 def __getitem__(self, i): 230 return self.items[i] 231 232 def __delitem__(self, i): 233 del self.items[i] 234 235 def issubset(self, other): 236 """Is I{self} a subset of I{other}? 237 238 @rtype: bool 239 """ 240 241 if not isinstance(other, Set): 242 raise ValueError('other must be a Set instance') 243 for item in self.items: 244 if item not in other.items: 245 return False 246 return True 247 248 def issuperset(self, other): 249 """Is I{self} a superset of I{other}? 250 251 @rtype: bool 252 """ 253 254 if not isinstance(other, Set): 255 raise ValueError('other must be a Set instance') 256 for item in other.items: 257 if item not in self.items: 258 return False 259 return True 260