1# Copyright (C) 2003-2017 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 16class Set(object): 17 18 """A simple set class. 19 20 This class was originally used to deal with sets being missing in 21 ancient versions of python, but dnspython will continue to use it 22 as these sets are based on lists and are thus indexable, and this 23 ability is widely used in dnspython applications. 24 """ 25 26 __slots__ = ['items'] 27 28 def __init__(self, items=None): 29 """Initialize the set. 30 31 *items*, an iterable or ``None``, the initial set of items. 32 """ 33 34 self.items = [] 35 if items is not None: 36 for item in items: 37 self.add(item) 38 39 def __repr__(self): 40 return "dns.simpleset.Set(%s)" % repr(self.items) 41 42 def add(self, item): 43 """Add an item to the set. 44 """ 45 46 if item not in self.items: 47 self.items.append(item) 48 49 def remove(self, item): 50 """Remove an item from the set. 51 """ 52 53 self.items.remove(item) 54 55 def discard(self, item): 56 """Remove an item from the set if present. 57 """ 58 59 try: 60 self.items.remove(item) 61 except ValueError: 62 pass 63 64 def _clone(self): 65 """Make a (shallow) copy of the set. 66 67 There is a 'clone protocol' that subclasses of this class 68 should use. To make a copy, first call your super's _clone() 69 method, and use the object returned as the new instance. Then 70 make shallow copies of the attributes defined in the subclass. 71 72 This protocol allows us to write the set algorithms that 73 return new instances (e.g. union) once, and keep using them in 74 subclasses. 75 """ 76 77 cls = self.__class__ 78 obj = cls.__new__(cls) 79 obj.items = list(self.items) 80 return obj 81 82 def __copy__(self): 83 """Make a (shallow) copy of the set. 84 """ 85 86 return self._clone() 87 88 def copy(self): 89 """Make a (shallow) copy of the set. 90 """ 91 92 return self._clone() 93 94 def union_update(self, other): 95 """Update the set, adding any elements from other which are not 96 already in the set. 97 """ 98 99 if not isinstance(other, Set): 100 raise ValueError('other must be a Set instance') 101 if self is other: 102 return 103 for item in other.items: 104 self.add(item) 105 106 def intersection_update(self, other): 107 """Update the set, removing any elements from other which are not 108 in both sets. 109 """ 110 111 if not isinstance(other, Set): 112 raise ValueError('other must be a Set instance') 113 if self is other: 114 return 115 # we make a copy of the list so that we can remove items from 116 # the list without breaking the iterator. 117 for item in list(self.items): 118 if item not in other.items: 119 self.items.remove(item) 120 121 def difference_update(self, other): 122 """Update the set, removing any elements from other which are in 123 the set. 124 """ 125 126 if not isinstance(other, Set): 127 raise ValueError('other must be a Set instance') 128 if self is other: 129 self.items = [] 130 else: 131 for item in other.items: 132 self.discard(item) 133 134 def union(self, other): 135 """Return a new set which is the union of ``self`` and ``other``. 136 137 Returns the same Set type as this set. 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 ``self`` and 146 ``other``. 147 148 Returns the same Set type as this set. 149 """ 150 151 obj = self._clone() 152 obj.intersection_update(other) 153 return obj 154 155 def difference(self, other): 156 """Return a new set which ``self`` - ``other``, i.e. the items 157 in ``self`` which are not also in ``other``. 158 159 Returns the same Set type as this set. 160 """ 161 162 obj = self._clone() 163 obj.difference_update(other) 164 return obj 165 166 def __or__(self, other): 167 return self.union(other) 168 169 def __and__(self, other): 170 return self.intersection(other) 171 172 def __add__(self, other): 173 return self.union(other) 174 175 def __sub__(self, other): 176 return self.difference(other) 177 178 def __ior__(self, other): 179 self.union_update(other) 180 return self 181 182 def __iand__(self, other): 183 self.intersection_update(other) 184 return self 185 186 def __iadd__(self, other): 187 self.union_update(other) 188 return self 189 190 def __isub__(self, other): 191 self.difference_update(other) 192 return self 193 194 def update(self, other): 195 """Update the set, adding any elements from other which are not 196 already in the set. 197 198 *other*, the collection of items with which to update the set, which 199 may be any iterable type. 200 """ 201 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 this set a subset of *other*? 237 238 Returns a ``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 this set a superset of *other*? 250 251 Returns a ``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