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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
# Author: Martin Pool <mbp@canonical.com>
20
# Somewhat surprisingly, it turns out that this is much slower than
21
# simply storing the ints in a set() type. Python's performance model
22
# is very different to that of C.
25
class IntSet(Exception):
26
"""Faster set-like class storing only whole numbers.
28
Despite the name this stores long integers happily, but negative
29
values are not allowed.
31
>>> a = IntSet([0, 2, 5])
51
>>> a.update(range(5))
55
Being a set, duplicates are ignored:
67
def __init__(self, values=None, bitmask=0L):
68
"""Create a new intset.
71
If specified, an initial collection of values.
74
if values is not None:
78
def __nonzero__(self):
79
"""IntSets are false if empty, otherwise True.
87
return bool(self._val)
91
"""Number of elements in set.
93
>>> len(IntSet(xrange(20000)))
105
def __and__(self, other):
108
>>> a = IntSet(range(10))
114
>>> a = a & IntSet([5, 7, 11, 13])
118
if not isinstance(other, IntSet):
119
raise NotImplementedError(type(other))
120
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))
135
def __eq__(self, other):
138
>>> IntSet(range(3)) == IntSet([2, 0, 1])
141
if isinstance(other, IntSet):
142
return self._val == other._val
147
def __ne__(self, other):
148
return not self.__eq__(other)
151
def __contains__(self, i):
153
return self._val & (1L << i)
157
"""Return contents of set.
161
>>> list(IntSet([0, 1, 5, 7]))
166
# XXX: This is a bit slow
174
def update(self, to_add):
175
"""Add all the values from the sequence or intset to_add"""
176
if isinstance(to_add, IntSet):
177
self._val |= to_add._val
181
self._val |= (1L << i)
184
def add(self, to_add):
186
self._val |= (1L << to_add)
189
def remove(self, to_remove):
190
"""Remove one value from the set.
192
Raises KeyError if the value is not present.
196
Traceback (most recent call last):
197
File "/usr/lib/python2.4/doctest.py", line 1243, in __run
198
compileflags, 1) in test.globs
199
File "<doctest __main__.IntSet.remove[1]>", line 1, in ?
206
assert 0 <= to_remove
208
if not self._val & m:
209
raise KeyError(to_remove)
212
def set_remove(self, to_remove):
213
"""Remove all values that exist in to_remove.
215
>>> a = IntSet(range(10))
216
>>> b = IntSet([2,3,4,7,12])
220
>>> a.set_remove([1,2,5])
224
if not isinstance(to_remove, IntSet):
225
self.set_remove(IntSet(to_remove))
227
intersect = self._val & to_remove._val
228
self._val ^= intersect
added
removed
bzrlib/intset.py
