1# Copyright (C) 2003-2007, 2009-2011 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
18
19class Set(object):
20
21    """A simple set class.
22
23    Sets are not in Python until 2.3, and rdata are not immutable so
24    we cannot use sets.Set anyway.  This class implements subset of
25    the 2.3 Set interface using a list as the container.
26
27    @ivar items: A list of the items which are in the set
28    @type items: list"""
29
30    __slots__ = ['items']
31
32    def __init__(self, items=None):
33        """Initialize the set.
34
35        @param items: the initial set of items
36        @type items: any iterable or None
37        """
38
39        self.items = []
40        if items is not None:
41            for item in items:
42                self.add(item)
43
44    def __repr__(self):
45        return "dns.simpleset.Set(%s)" % repr(self.items)
46
47    def add(self, item):
48        """Add an item to the set."""
49        if item not in self.items:
50            self.items.append(item)
51
52    def remove(self, item):
53        """Remove an item from the set."""
54        self.items.remove(item)
55
56    def discard(self, item):
57        """Remove an item from the set if present."""
58        try:
59            self.items.remove(item)
60        except ValueError:
61            pass
62
63    def _clone(self):
64        """Make a (shallow) copy of the set.
65
66        There is a 'clone protocol' that subclasses of this class
67        should use.  To make a copy, first call your super's _clone()
68        method, and use the object returned as the new instance.  Then
69        make shallow copies of the attributes defined in the subclass.
70
71        This protocol allows us to write the set algorithms that
72        return new instances (e.g. union) once, and keep using them in
73        subclasses.
74        """
75
76        cls = self.__class__
77        obj = cls.__new__(cls)
78        obj.items = list(self.items)
79        return obj
80
81    def __copy__(self):
82        """Make a (shallow) copy of the set."""
83        return self._clone()
84
85    def copy(self):
86        """Make a (shallow) copy of the set."""
87        return self._clone()
88
89    def union_update(self, other):
90        """Update the set, adding any elements from other which are not
91        already in the set.
92        @param other: the collection of items with which to update the set
93        @type other: Set object
94        """
95        if not isinstance(other, Set):
96            raise ValueError('other must be a Set instance')
97        if self is other:
98            return
99        for item in other.items:
100            self.add(item)
101
102    def intersection_update(self, other):
103        """Update the set, removing any elements from other which are not
104        in both sets.
105        @param other: the collection of items with which to update the set
106        @type other: Set object
107        """
108        if not isinstance(other, Set):
109            raise ValueError('other must be a Set instance')
110        if self is other:
111            return
112        # we make a copy of the list so that we can remove items from
113        # the list without breaking the iterator.
114        for item in list(self.items):
115            if item not in other.items:
116                self.items.remove(item)
117
118    def difference_update(self, other):
119        """Update the set, removing any elements from other which are in
120        the set.
121        @param other: the collection of items with which to update the set
122        @type other: Set object
123        """
124        if not isinstance(other, Set):
125            raise ValueError('other must be a Set instance')
126        if self is other:
127            self.items = []
128        else:
129            for item in other.items:
130                self.discard(item)
131
132    def union(self, other):
133        """Return a new set which is the union of I{self} and I{other}.
134
135        @param other: the other set
136        @type other: Set object
137        @rtype: the same type as I{self}
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 I{self} and I{other}.
146
147        @param other: the other set
148        @type other: Set object
149        @rtype: the same type as I{self}
150        """
151
152        obj = self._clone()
153        obj.intersection_update(other)
154        return obj
155
156    def difference(self, other):
157        """Return a new set which I{self} - I{other}, i.e. the items
158        in I{self} which are not also in I{other}.
159
160        @param other: the other set
161        @type other: Set object
162        @rtype: the same type as I{self}
163        """
164
165        obj = self._clone()
166        obj.difference_update(other)
167        return obj
168
169    def __or__(self, other):
170        return self.union(other)
171
172    def __and__(self, other):
173        return self.intersection(other)
174
175    def __add__(self, other):
176        return self.union(other)
177
178    def __sub__(self, other):
179        return self.difference(other)
180
181    def __ior__(self, other):
182        self.union_update(other)
183        return self
184
185    def __iand__(self, other):
186        self.intersection_update(other)
187        return self
188
189    def __iadd__(self, other):
190        self.union_update(other)
191        return self
192
193    def __isub__(self, other):
194        self.difference_update(other)
195        return self
196
197    def update(self, other):
198        """Update the set, adding any elements from other which are not
199        already in the set.
200        @param other: the collection of items with which to update the set
201        @type other: any iterable type"""
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 I{self} a subset of I{other}?
237
238        @rtype: 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 I{self} a superset of I{other}?
250
251        @rtype: 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