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