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 cls = self.__class__ 88 obj = cls.__new__(cls) 89 obj.items = self.items.copy() 90 return obj 91 92 def __copy__(self): 93 """Make a (shallow) copy of the set. 94 """ 95 96 return self._clone() 97 98 def copy(self): 99 """Make a (shallow) copy of the set. 100 """ 101 102 return self._clone() 103 104 def union_update(self, other): 105 """Update the set, adding any elements from other which are not 106 already in the set. 107 """ 108 109 if not isinstance(other, Set): 110 raise ValueError('other must be a Set instance') 111 if self is other: 112 return 113 for item in other.items: 114 self.add(item) 115 116 def intersection_update(self, other): 117 """Update the set, removing any elements from other which are not 118 in both sets. 119 """ 120 121 if not isinstance(other, Set): 122 raise ValueError('other must be a Set instance') 123 if self is other: 124 return 125 # we make a copy of the list so that we can remove items from 126 # the list without breaking the iterator. 127 for item in list(self.items): 128 if item not in other.items: 129 del self.items[item] 130 131 def difference_update(self, other): 132 """Update the set, removing any elements from other which are in 133 the set. 134 """ 135 136 if not isinstance(other, Set): 137 raise ValueError('other must be a Set instance') 138 if self is other: 139 self.items.clear() 140 else: 141 for item in other.items: 142 self.discard(item) 143 144 def union(self, other): 145 """Return a new set which is the union of ``self`` and ``other``. 146 147 Returns the same Set type as this set. 148 """ 149 150 obj = self._clone() 151 obj.union_update(other) 152 return obj 153 154 def intersection(self, other): 155 """Return a new set which is the intersection of ``self`` and 156 ``other``. 157 158 Returns the same Set type as this set. 159 """ 160 161 obj = self._clone() 162 obj.intersection_update(other) 163 return obj 164 165 def difference(self, other): 166 """Return a new set which ``self`` - ``other``, i.e. the items 167 in ``self`` which are not also in ``other``. 168 169 Returns the same Set type as this set. 170 """ 171 172 obj = self._clone() 173 obj.difference_update(other) 174 return obj 175 176 def __or__(self, other): 177 return self.union(other) 178 179 def __and__(self, other): 180 return self.intersection(other) 181 182 def __add__(self, other): 183 return self.union(other) 184 185 def __sub__(self, other): 186 return self.difference(other) 187 188 def __ior__(self, other): 189 self.union_update(other) 190 return self 191 192 def __iand__(self, other): 193 self.intersection_update(other) 194 return self 195 196 def __iadd__(self, other): 197 self.union_update(other) 198 return self 199 200 def __isub__(self, other): 201 self.difference_update(other) 202 return self 203 204 def update(self, other): 205 """Update the set, adding any elements from other which are not 206 already in the set. 207 208 *other*, the collection of items with which to update the set, which 209 may be any iterable type. 210 """ 211 212 for item in other: 213 self.add(item) 214 215 def clear(self): 216 """Make the set empty.""" 217 self.items.clear() 218 219 def __eq__(self, other): 220 if odict == dict: 221 return self.items == other.items 222 else: 223 # We don't want an ordered comparison. 224 if len(self.items) != len(other.items): 225 return False 226 return all(elt in other.items for elt in self.items) 227 228 def __ne__(self, other): 229 return not self.__eq__(other) 230 231 def __len__(self): 232 return len(self.items) 233 234 def __iter__(self): 235 return iter(self.items) 236 237 def __getitem__(self, i): 238 if isinstance(i, slice): 239 return list(itertools.islice(self.items, i.start, i.stop, i.step)) 240 else: 241 return next(itertools.islice(self.items, i, i + 1)) 242 243 def __delitem__(self, i): 244 if isinstance(i, slice): 245 for elt in list(self[i]): 246 del self.items[elt] 247 else: 248 del self.items[self[i]] 249 250 def issubset(self, other): 251 """Is this set a subset of *other*? 252 253 Returns a ``bool``. 254 """ 255 256 if not isinstance(other, Set): 257 raise ValueError('other must be a Set instance') 258 for item in self.items: 259 if item not in other.items: 260 return False 261 return True 262 263 def issuperset(self, other): 264 """Is this set a superset of *other*? 265 266 Returns a ``bool``. 267 """ 268 269 if not isinstance(other, Set): 270 raise ValueError('other must be a Set instance') 271 for item in other.items: 272 if item not in self.items: 273 return False 274 return True 275