1# Copyright (C) Dnspython Contributors, see LICENSE for text of ISC license 2 3# Copyright (C) 2003-2017 Nominum, Inc. 4# 5# Permission to use, copy, modify, and distribute this software and its 6# documentation for any purpose with or without fee is hereby granted, 7# provided that the above copyright notice and this permission notice 8# appear in all copies. 9# 10# THE SOFTWARE IS PROVIDED "AS IS" AND NOMINUM DISCLAIMS ALL WARRANTIES 11# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL NOMINUM BE LIABLE FOR 13# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT 16# OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 18import itertools 19import sys 20 21if sys.version_info >= (3, 7): 22 odict = dict 23else: 24 from collections import OrderedDict as odict # pragma: no cover 25 26class Set: 27 28 """A simple set class. 29 30 This class was originally used to deal with sets being missing in 31 ancient versions of python, but dnspython will continue to use it 32 as these sets are based on lists and are thus indexable, and this 33 ability is widely used in dnspython applications. 34 """ 35 36 __slots__ = ['items'] 37 38 def __init__(self, items=None): 39 """Initialize the set. 40 41 *items*, an iterable or ``None``, the initial set of items. 42 """ 43 44 self.items = odict() 45 if items is not None: 46 for item in items: 47 self.add(item) 48 49 def __repr__(self): 50 return "dns.set.Set(%s)" % repr(list(self.items.keys())) 51 52 def add(self, item): 53 """Add an item to the set. 54 """ 55 56 if item not in self.items: 57 self.items[item] = None 58 59 def remove(self, item): 60 """Remove an item from the set. 61 """ 62 63 try: 64 del self.items[item] 65 except KeyError: 66 raise ValueError 67 68 def discard(self, item): 69 """Remove an item from the set if present. 70 """ 71 72 self.items.pop(item, None) 73 74 def _clone(self): 75 """Make a (shallow) copy of the set. 76 77 There is a 'clone protocol' that subclasses of this class 78 should use. To make a copy, first call your super's _clone() 79 method, and use the object returned as the new instance. Then 80 make shallow copies of the attributes defined in the subclass. 81 82 This protocol allows us to write the set algorithms that 83 return new instances (e.g. union) once, and keep using them in 84 subclasses. 85 """ 86 87 if hasattr(self, '_clone_class'): 88 cls = self._clone_class 89 else: 90 cls = self.__class__ 91 obj = cls.__new__(cls) 92 obj.items = odict() 93 obj.items.update(self.items) 94 return obj 95 96 def __copy__(self): 97 """Make a (shallow) copy of the set. 98 """ 99 100 return self._clone() 101 102 def copy(self): 103 """Make a (shallow) copy of the set. 104 """ 105 106 return self._clone() 107 108 def union_update(self, other): 109 """Update the set, adding any elements from other which are not 110 already in the set. 111 """ 112 113 if not isinstance(other, Set): 114 raise ValueError('other must be a Set instance') 115 if self is other: 116 return 117 for item in other.items: 118 self.add(item) 119 120 def intersection_update(self, other): 121 """Update the set, removing any elements from other which are not 122 in both sets. 123 """ 124 125 if not isinstance(other, Set): 126 raise ValueError('other must be a Set instance') 127 if self is other: 128 return 129 # we make a copy of the list so that we can remove items from 130 # the list without breaking the iterator. 131 for item in list(self.items): 132 if item not in other.items: 133 del self.items[item] 134 135 def difference_update(self, other): 136 """Update the set, removing any elements from other which are in 137 the set. 138 """ 139 140 if not isinstance(other, Set): 141 raise ValueError('other must be a Set instance') 142 if self is other: 143 self.items.clear() 144 else: 145 for item in other.items: 146 self.discard(item) 147 148 def union(self, other): 149 """Return a new set which is the union of ``self`` and ``other``. 150 151 Returns the same Set type as this set. 152 """ 153 154 obj = self._clone() 155 obj.union_update(other) 156 return obj 157 158 def intersection(self, other): 159 """Return a new set which is the intersection of ``self`` and 160 ``other``. 161 162 Returns the same Set type as this set. 163 """ 164 165 obj = self._clone() 166 obj.intersection_update(other) 167 return obj 168 169 def difference(self, other): 170 """Return a new set which ``self`` - ``other``, i.e. the items 171 in ``self`` which are not also in ``other``. 172 173 Returns the same Set type as this set. 174 """ 175 176 obj = self._clone() 177 obj.difference_update(other) 178 return obj 179 180 def __or__(self, other): 181 return self.union(other) 182 183 def __and__(self, other): 184 return self.intersection(other) 185 186 def __add__(self, other): 187 return self.union(other) 188 189 def __sub__(self, other): 190 return self.difference(other) 191 192 def __ior__(self, other): 193 self.union_update(other) 194 return self 195 196 def __iand__(self, other): 197 self.intersection_update(other) 198 return self 199 200 def __iadd__(self, other): 201 self.union_update(other) 202 return self 203 204 def __isub__(self, other): 205 self.difference_update(other) 206 return self 207 208 def update(self, other): 209 """Update the set, adding any elements from other which are not 210 already in the set. 211 212 *other*, the collection of items with which to update the set, which 213 may be any iterable type. 214 """ 215 216 for item in other: 217 self.add(item) 218 219 def clear(self): 220 """Make the set empty.""" 221 self.items.clear() 222 223 def __eq__(self, other): 224 if odict == dict: 225 return self.items == other.items 226 else: 227 # We don't want an ordered comparison. 228 if len(self.items) != len(other.items): 229 return False 230 return all(elt in other.items for elt in self.items) 231 232 def __ne__(self, other): 233 return not self.__eq__(other) 234 235 def __len__(self): 236 return len(self.items) 237 238 def __iter__(self): 239 return iter(self.items) 240 241 def __getitem__(self, i): 242 if isinstance(i, slice): 243 return list(itertools.islice(self.items, i.start, i.stop, i.step)) 244 else: 245 return next(itertools.islice(self.items, i, i + 1)) 246 247 def __delitem__(self, i): 248 if isinstance(i, slice): 249 for elt in list(self[i]): 250 del self.items[elt] 251 else: 252 del self.items[self[i]] 253 254 def issubset(self, other): 255 """Is this set a subset of *other*? 256 257 Returns a ``bool``. 258 """ 259 260 if not isinstance(other, Set): 261 raise ValueError('other must be a Set instance') 262 for item in self.items: 263 if item not in other.items: 264 return False 265 return True 266 267 def issuperset(self, other): 268 """Is this set a superset of *other*? 269 270 Returns a ``bool``. 271 """ 272 273 if not isinstance(other, Set): 274 raise ValueError('other must be a Set instance') 275 for item in other.items: 276 if item not in self.items: 277 return False 278 return True 279