3
# Copyright (C) 2005 Canonical Ltd
5
# This program is free software; you can redistribute it and/or modify
6
# it under the terms of the GNU General Public License as published by
7
# the Free Software Foundation; either version 2 of the License, or
8
# (at your option) any later version.
10
# This program is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
# GNU General Public License for more details.
15
# You should have received a copy of the GNU General Public License
16
# along with this program; if not, write to the Free Software
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
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=0L):
70
"""Create a new intset.
73
If specified, an initial collection of values.
80
def __nonzero__(self):
81
"""IntSets are false if empty, otherwise True.
89
return bool(self._val)
93
"""Number of elements in set.
95
>>> len(IntSet(xrange(20000)))
107
def __and__(self, other):
110
>>> a = IntSet(range(10))
116
>>> a = a & IntSet([5, 7, 11, 13])
120
if not isinstance(other, IntSet):
121
raise NotImplementedError(type(other))
122
return IntSet(bitmask=(self._val & other._val))
125
def __or__(self, other):
128
>>> a = IntSet(range(10)) | IntSet([5, 15, 25])
132
if not isinstance(other, IntSet):
133
raise NotImplementedError(type(other))
134
return IntSet(bitmask=(self._val | other._val))
137
def __eq__(self, other):
140
>>> IntSet(range(3)) == IntSet([2, 0, 1])
143
if isinstance(other, IntSet):
144
return self._val == other._val
149
def __ne__(self, other):
150
return not self.__eq__(other)
153
def __contains__(self, i):
155
return self._val & (1L << i)
159
"""Return contents of set.
163
>>> list(IntSet([0, 1, 5, 7]))
168
# XXX: This is a bit slow
176
def update(self, to_add):
177
"""Add all the values from the sequence or intset to_add"""
178
if isinstance(to_add, IntSet):
179
self._val |= to_add._val
183
self._val |= (1L << i)
186
def add(self, to_add):
188
self._val |= (1L << to_add)
191
def remove(self, to_remove):
192
"""Remove one value from the set.
194
Raises KeyError if the value is not present.
198
Traceback (most recent call last):
199
File "/usr/lib/python2.4/doctest.py", line 1243, in __run
200
compileflags, 1) in test.globs
201
File "<doctest __main__.IntSet.remove[1]>", line 1, in ?
208
assert 0 <= to_remove
210
if not self._val & m:
211
raise KeyError(to_remove)
218
if __name__ == '__main__':
added
removed
bzrlib/intset.py
