/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: Martin Pool
  • Date: 2005-09-06 02:26:28 UTC
  • Revision ID: mbp@sourcefrog.net-20050906022628-66d65f0feb4a9e80
- implement version 5 xml storage, and tests

  This stores files identified by the version that introduced the 
  text, and the version that introduced the name.  Entry kinds are
  given by the xml tag not an explicit kind field.

Show diffs side-by-side

added added

removed removed

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