1
# Copyright (C) 2005 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
19
# Author: Martin Pool <mbp@canonical.com>
22
# Somewhat surprisingly, it turns out that this is much slower than
23
# simply storing the ints in a set() type. Python's performance model
24
# is very different to that of C.
27
class IntSet(Exception):
28
"""Faster set-like class storing only whole numbers.
30
Despite the name this stores long integers happily, but negative
31
values are not allowed.
33
>>> a = IntSet([0, 2, 5])
53
>>> a.update(range(5))
57
Being a set, duplicates are ignored:
69
def __init__(self, values=None, bitmask=0):
70
"""Create a new intset.
73
If specified, an initial collection of values.
76
if values is not None:
80
"""IntSets are false if empty, otherwise True.
88
return bool(self._val)
90
__nonzero__ = __bool__
93
"""Number of elements in set.
95
>>> len(IntSet(xrange(20000)))
106
def __and__(self, other):
109
>>> a = IntSet(range(10))
115
>>> a = a & IntSet([5, 7, 11, 13])
119
if not isinstance(other, IntSet):
120
raise NotImplementedError(type(other))
121
return IntSet(bitmask=(self._val & other._val))
123
def __or__(self, other):
126
>>> a = IntSet(range(10)) | IntSet([5, 15, 25])
130
if not isinstance(other, IntSet):
131
raise NotImplementedError(type(other))
132
return IntSet(bitmask=(self._val | other._val))
134
def __eq__(self, other):
137
>>> IntSet(range(3)) == IntSet([2, 0, 1])
140
if isinstance(other, IntSet):
141
return self._val == other._val
145
def __ne__(self, other):
146
return not self.__eq__(other)
148
def __contains__(self, i):
149
return self._val & (1 << i)
152
"""Return contents of set.
156
>>> list(IntSet([0, 1, 5, 7]))
161
# XXX: This is a bit slow
168
def update(self, to_add):
169
"""Add all the values from the sequence or intset to_add"""
170
if isinstance(to_add, IntSet):
171
self._val |= to_add._val
174
self._val |= (1 << i)
176
def add(self, to_add):
177
self._val |= (1 << to_add)
179
def remove(self, to_remove):
180
"""Remove one value from the set.
182
Raises KeyError if the value is not present.
186
Traceback (most recent call last):
187
File "/usr/lib/python2.4/doctest.py", line 1243, in __run
188
compileflags, 1) in test.globs
189
File "<doctest __main__.IntSet.remove[1]>", line 1, in ?
197
if not self._val & m:
198
raise KeyError(to_remove)
201
def set_remove(self, to_remove):
202
"""Remove all values that exist in to_remove.
204
>>> a = IntSet(range(10))
205
>>> b = IntSet([2,3,4,7,12])
209
>>> a.set_remove([1,2,5])
213
if not isinstance(to_remove, IntSet):
214
self.set_remove(IntSet(to_remove))
216
intersect = self._val & to_remove._val
217
self._val ^= intersect
added
removed
breezy/intset.py
