/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/intset.py

  • Committer: Vincent Ladeuil
  • Date: 2010-01-25 15:55:48 UTC
  • mto: (4985.1.4 add-attr-cleanup)
  • mto: This revision was merged to the branch mainline in revision 4988.
  • Revision ID: v.ladeuil+lp@free.fr-20100125155548-0l352pujvt5bzl5e
Deploy addAttrCleanup on the whole test suite.

Several use case worth mentioning:

- setting a module or any other object attribute is the majority
by far. In some cases the setting itself is deferred but most of
the time we want to set at the same time we add the cleanup.

- there multiple occurrences of protecting hooks or ui factory
which are now useless (the test framework takes care of that now),

- there was some lambda uses that can now be avoided.

That first cleanup already simplifies things a lot.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/intset.py
 
1
# Copyright (C) 2005 Canonical Ltd
 
2
#
 
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.
 
7
#
 
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.
 
12
#
 
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
 
16
 
 
17
# Author: Martin Pool <mbp@canonical.com>
 
18
 
 
19
 
 
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.
 
23
 
 
24
 
 
25
class IntSet(Exception):
 
26
    """Faster set-like class storing only whole numbers.
 
27
 
 
28
    Despite the name this stores long integers happily, but negative
 
29
    values are not allowed.
 
30
 
 
31
    >>> a = IntSet([0, 2, 5])
 
32
    >>> bool(a)
 
33
    True
 
34
    >>> 2 in a
 
35
    True
 
36
    >>> 4 in a
 
37
    False
 
38
    >>> a.add(4)
 
39
    >>> 4 in a
 
40
    True
 
41
 
 
42
    >>> b = IntSet()
 
43
    >>> not b
 
44
    True
 
45
    >>> b.add(10)
 
46
    >>> 10 in a
 
47
    False
 
48
    >>> a.update(b)
 
49
    >>> 10 in a
 
50
    True
 
51
    >>> a.update(range(5))
 
52
    >>> 3 in a
 
53
    True
 
54
 
 
55
    Being a set, duplicates are ignored:
 
56
    >>> a = IntSet()
 
57
    >>> a.add(10)
 
58
    >>> a.add(10)
 
59
    >>> 10 in a
 
60
    True
 
61
    >>> list(a)
 
62
    [10]
 
63
 
 
64
    """
 
65
    __slots__ = ['_val']
 
66
 
 
67
    def __init__(self, values=None, bitmask=0L):
 
68
        """Create a new intset.
 
69
 
 
70
        values
 
71
            If specified, an initial collection of values.
 
72
        """
 
73
        self._val = bitmask
 
74
        if values is not None:
 
75
            self.update(values)
 
76
 
 
77
 
 
78
    def __nonzero__(self):
 
79
        """IntSets are false if empty, otherwise True.
 
80
 
 
81
        >>> bool(IntSet())
 
82
        False
 
83
 
 
84
        >>> bool(IntSet([0]))
 
85
        True
 
86
        """
 
87
        return bool(self._val)
 
88
 
 
89
 
 
90
    def __len__(self):
 
91
        """Number of elements in set.
 
92
 
 
93
        >>> len(IntSet(xrange(20000)))
 
94
        20000
 
95
        """
 
96
        v = self._val
 
97
        c = 0
 
98
        while v:
 
99
            if v & 1:
 
100
                c += 1
 
101
            v = v >> 1
 
102
        return c
 
103
 
 
104
 
 
105
    def __and__(self, other):
 
106
        """Set intersection.
 
107
 
 
108
        >>> a = IntSet(range(10))
 
109
        >>> len(a)
 
110
        10
 
111
        >>> b = a & a
 
112
        >>> b == a
 
113
        True
 
114
        >>> a = a & IntSet([5, 7, 11, 13])
 
115
        >>> list(a)
 
116
        [5, 7]
 
117
        """
 
118
        if not isinstance(other, IntSet):
 
119
            raise NotImplementedError(type(other))
 
120
        return IntSet(bitmask=(self._val & other._val))
 
121
 
 
122
 
 
123
    def __or__(self, other):
 
124
        """Set union.
 
125
 
 
126
        >>> a = IntSet(range(10)) | IntSet([5, 15, 25])
 
127
        >>> len(a)
 
128
        12
 
129
        """
 
130
        if not isinstance(other, IntSet):
 
131
            raise NotImplementedError(type(other))
 
132
        return IntSet(bitmask=(self._val | other._val))
 
133
 
 
134
 
 
135
    def __eq__(self, other):
 
136
        """Comparison.
 
137
 
 
138
        >>> IntSet(range(3)) == IntSet([2, 0, 1])
 
139
        True
 
140
        """
 
141
        if isinstance(other, IntSet):
 
142
            return self._val == other._val
 
143
        else:
 
144
            return False
 
145
 
 
146
 
 
147
    def __ne__(self, other):
 
148
        return not self.__eq__(other)
 
149
 
 
150
 
 
151
    def __contains__(self, i):
 
152
        return self._val & (1L << i)
 
153
 
 
154
 
 
155
    def __iter__(self):
 
156
        """Return contents of set.
 
157
 
 
158
        >>> list(IntSet())
 
159
        []
 
160
        >>> list(IntSet([0, 1, 5, 7]))
 
161
        [0, 1, 5, 7]
 
162
        """
 
163
        v = self._val
 
164
        o = 0
 
165
        # XXX: This is a bit slow
 
166
        while v:
 
167
            if v & 1:
 
168
                yield o
 
169
            v = v >> 1
 
170
            o = o + 1
 
171
 
 
172
 
 
173
    def update(self, to_add):
 
174
        """Add all the values from the sequence or intset to_add"""
 
175
        if isinstance(to_add, IntSet):
 
176
            self._val |= to_add._val
 
177
        else:
 
178
            for i in to_add:
 
179
                self._val |= (1L << i)
 
180
 
 
181
 
 
182
    def add(self, to_add):
 
183
        self._val |= (1L << to_add)
 
184
 
 
185
 
 
186
    def remove(self, to_remove):
 
187
        """Remove one value from the set.
 
188
 
 
189
        Raises KeyError if the value is not present.
 
190
 
 
191
        >>> a = IntSet([10])
 
192
        >>> a.remove(9)
 
193
        Traceback (most recent call last):
 
194
          File "/usr/lib/python2.4/doctest.py", line 1243, in __run
 
195
            compileflags, 1) in test.globs
 
196
          File "<doctest __main__.IntSet.remove[1]>", line 1, in ?
 
197
            a.remove(9)
 
198
        KeyError: 9
 
199
        >>> a.remove(10)
 
200
        >>> not a
 
201
        True
 
202
        """
 
203
        m = 1L << to_remove
 
204
        if not self._val & m:
 
205
            raise KeyError(to_remove)
 
206
        self._val ^= m
 
207
 
 
208
    def set_remove(self, to_remove):
 
209
        """Remove all values that exist in to_remove.
 
210
 
 
211
        >>> a = IntSet(range(10))
 
212
        >>> b = IntSet([2,3,4,7,12])
 
213
        >>> a.set_remove(b)
 
214
        >>> list(a)
 
215
        [0, 1, 5, 6, 8, 9]
 
216
        >>> a.set_remove([1,2,5])
 
217
        >>> list(a)
 
218
        [0, 6, 8, 9]
 
219
        """
 
220
        if not isinstance(to_remove, IntSet):
 
221
            self.set_remove(IntSet(to_remove))
 
222
            return
 
223
        intersect = self._val & to_remove._val
 
224
        self._val ^= intersect
 
225