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