lib/dnspython/dns/set.py

   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 class 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