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