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
18class Set(object):
19
20    """A simple set class.
21
22    This class was originally used to deal with sets being missing in
23    ancient versions of python, but dnspython will continue to use it
24    as these sets are based on lists and are thus indexable, and this
25    ability is widely used in dnspython applications.
26    """
27
28    __slots__ = ['items']
29
30    def __init__(self, items=None):
31        """Initialize the set.
32
33        *items*, an iterable or ``None``, the initial set of items.
34        """
35
36        self.items = []
37        if items is not None:
38            for item in items:
39                self.add(item)
40
41    def __repr__(self):
42        return "dns.simpleset.Set(%s)" % repr(self.items)
43
44    def add(self, item):
45        """Add an item to the set.
46        """
47
48        if item not in self.items:
49            self.items.append(item)
50
51    def remove(self, item):
52        """Remove an item from the set.
53        """
54
55        self.items.remove(item)
56
57    def discard(self, item):
58        """Remove an item from the set if present.
59        """
60
61        try:
62            self.items.remove(item)
63        except ValueError:
64            pass
65
66    def _clone(self):
67        """Make a (shallow) copy of the set.
68
69        There is a 'clone protocol' that subclasses of this class
70        should use.  To make a copy, first call your super's _clone()
71        method, and use the object returned as the new instance.  Then
72        make shallow copies of the attributes defined in the subclass.
73
74        This protocol allows us to write the set algorithms that
75        return new instances (e.g. union) once, and keep using them in
76        subclasses.
77        """
78
79        cls = self.__class__
80        obj = cls.__new__(cls)
81        obj.items = list(self.items)
82        return obj
83
84    def __copy__(self):
85        """Make a (shallow) copy of the set.
86        """
87
88        return self._clone()
89
90    def copy(self):
91        """Make a (shallow) copy of the set.
92        """
93
94        return self._clone()
95
96    def union_update(self, other):
97        """Update the set, adding any elements from other which are not
98        already in the set.
99        """
100
101        if not isinstance(other, Set):
102            raise ValueError('other must be a Set instance')
103        if self is other:
104            return
105        for item in other.items:
106            self.add(item)
107
108    def intersection_update(self, other):
109        """Update the set, removing any elements from other which are not
110        in both sets.
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        # we make a copy of the list so that we can remove items from
118        # the list without breaking the iterator.
119        for item in list(self.items):
120            if item not in other.items:
121                self.items.remove(item)
122
123    def difference_update(self, other):
124        """Update the set, removing any elements from other which are in
125        the set.
126        """
127
128        if not isinstance(other, Set):
129            raise ValueError('other must be a Set instance')
130        if self is other:
131            self.items = []
132        else:
133            for item in other.items:
134                self.discard(item)
135
136    def union(self, other):
137        """Return a new set which is the union of ``self`` and ``other``.
138
139        Returns the same Set type as this set.
140        """
141
142        obj = self._clone()
143        obj.union_update(other)
144        return obj
145
146    def intersection(self, other):
147        """Return a new set which is the intersection of ``self`` and
148        ``other``.
149
150        Returns the same Set type as this set.
151        """
152
153        obj = self._clone()
154        obj.intersection_update(other)
155        return obj
156
157    def difference(self, other):
158        """Return a new set which ``self`` - ``other``, i.e. the items
159        in ``self`` which are not also in ``other``.
160
161        Returns the same Set type as this set.
162        """
163
164        obj = self._clone()
165        obj.difference_update(other)
166        return obj
167
168    def __or__(self, other):
169        return self.union(other)
170
171    def __and__(self, other):
172        return self.intersection(other)
173
174    def __add__(self, other):
175        return self.union(other)
176
177    def __sub__(self, other):
178        return self.difference(other)
179
180    def __ior__(self, other):
181        self.union_update(other)
182        return self
183
184    def __iand__(self, other):
185        self.intersection_update(other)
186        return self
187
188    def __iadd__(self, other):
189        self.union_update(other)
190        return self
191
192    def __isub__(self, other):
193        self.difference_update(other)
194        return self
195
196    def update(self, other):
197        """Update the set, adding any elements from other which are not
198        already in the set.
199
200        *other*, the collection of items with which to update the set, which
201        may be any iterable type.
202        """
203
204        for item in other:
205            self.add(item)
206
207    def clear(self):
208        """Make the set empty."""
209        self.items = []
210
211    def __eq__(self, other):
212        # Yes, this is inefficient but the sets we're dealing with are
213        # usually quite small, so it shouldn't hurt too much.
214        for item in self.items:
215            if item not in other.items:
216                return False
217        for item in other.items:
218            if item not in self.items:
219                return False
220        return True
221
222    def __ne__(self, other):
223        return not self.__eq__(other)
224
225    def __len__(self):
226        return len(self.items)
227
228    def __iter__(self):
229        return iter(self.items)
230
231    def __getitem__(self, i):
232        return self.items[i]
233
234    def __delitem__(self, i):
235        del self.items[i]
236
237    def issubset(self, other):
238        """Is this set a subset of *other*?
239
240        Returns a ``bool``.
241        """
242
243        if not isinstance(other, Set):
244            raise ValueError('other must be a Set instance')
245        for item in self.items:
246            if item not in other.items:
247                return False
248        return True
249
250    def issuperset(self, other):
251        """Is this set a superset 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 other.items:
259            if item not in self.items:
260                return False
261        return True
262