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