← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/intset.py

  • Committer: Martin Pool
  • Date: 2005-07-17 17:53:39 UTC
  • mfrom: (909.1.5)
  • Revision ID: mbp@sourcefrog.net-20050717175339-9433d3dc4d9d3b5c
- Add IntSet class

- Start converting weave calculation to use it

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
class IntSet(Exception):
 
23
    """Faster set-like class storing only whole numbers.
 
24
 
 
25
    Despite the name this stores long integers happily, but negative
 
26
    values are not allowed.
 
27
 
 
28
    >>> a = IntSet([0, 2, 5])
 
29
    >>> bool(a)
 
30
    True
 
31
    >>> 2 in a
 
32
    True
 
33
    >>> 4 in a
 
34
    False
 
35
    >>> a.add(4)
 
36
    >>> 4 in a
 
37
    True
 
38
 
 
39
    >>> b = IntSet()
 
40
    >>> not b
 
41
    True
 
42
    >>> b.add(10)
 
43
    >>> 10 in a
 
44
    False
 
45
    >>> a.update(b)
 
46
    >>> 10 in a
 
47
    True
 
48
    >>> a.update(range(5))
 
49
    >>> 3 in a
 
50
    True
 
51
 
 
52
    Being a set, duplicates are ignored:
 
53
    >>> a = IntSet()
 
54
    >>> a.add(10)
 
55
    >>> a.add(10)
 
56
    >>> 10 in a
 
57
    True
 
58
    >>> list(a)
 
59
    [10]
 
60
    
 
61
    """
 
62
    # __slots__ = ['_val']
 
63
 
 
64
    def __init__(self, values=None):
 
65
        """Create a new intset.
 
66
 
 
67
        values
 
68
            If specified, an initial collection of values.
 
69
        """
 
70
        self._val = 0
 
71
        if values != None:
 
72
            self.update(values)
 
73
 
 
74
 
 
75
    def __nonzero__(self):
 
76
        """IntSets are false if empty, otherwise True.
 
77
 
 
78
        >>> bool(IntSet())
 
79
        False
 
80
        
 
81
        >>> bool(IntSet([0]))
 
82
        True
 
83
        """
 
84
        return bool(self._val)
 
85
 
 
86
 
 
87
    def __eq__(self, other):
 
88
        """Comparison."""
 
89
        if isinstance(other, IntSet):
 
90
            return self._val == other._val
 
91
        else:
 
92
            return False
 
93
 
 
94
 
 
95
    def __ne__(self, other):
 
96
        return not self.__eq__(other)
 
97
 
 
98
 
 
99
    def __contains__(self, i):
 
100
        assert i >= 0
 
101
        return self._val & (1L << i)
 
102
 
 
103
 
 
104
    def __iter__(self):
 
105
        """Return contents of set.
 
106
 
 
107
        >>> list(IntSet())
 
108
        []
 
109
        >>> list(IntSet([0, 1, 5, 7]))
 
110
        [0, 1, 5, 7]
 
111
        """
 
112
        v = self._val
 
113
        o = 0
 
114
        # XXX: This is a bit slow
 
115
        while v:
 
116
            if v & 1:
 
117
                yield o
 
118
            v = v >> 1
 
119
            o = o + 1
 
120
 
 
121
        
 
122
    def update(self, to_add):
 
123
        """Add all the values from the sequence or intset to_add"""
 
124
        if isinstance(to_add, IntSet):
 
125
            self._val |= to_add._val
 
126
        else:
 
127
            for i in to_add:
 
128
                assert i >= 0
 
129
                self._val |= (1L << i)
 
130
 
 
131
 
 
132
    def add(self, to_add):
 
133
        assert 0 <= to_add
 
134
        self._val |= (1L << to_add)
 
135
 
 
136
 
 
137
    def remove(self, to_remove):
 
138
        """Remove one value from the set.
 
139
 
 
140
        Raises KeyError if the value is not present.
 
141
 
 
142
        >>> a = IntSet([10])
 
143
        >>> a.remove(9)
 
144
        Traceback (most recent call last):
 
145
          File "/usr/lib/python2.4/doctest.py", line 1243, in __run
 
146
            compileflags, 1) in test.globs
 
147
          File "<doctest __main__.IntSet.remove[1]>", line 1, in ?
 
148
            a.remove(9)
 
149
        KeyError: 9
 
150
        >>> a.remove(10)
 
151
        >>> not a
 
152
        True
 
153
        """
 
154
        assert 0 <= to_remove
 
155
        m = 1L << to_remove
 
156
        if not self._val & m:
 
157
            raise KeyError(to_remove)
 
158
        self._val ^= m
 
159
        
 
160
        
 
161
            
 
162
    
 
163
 
 
164
if __name__ == '__main__':
 
165
    import doctest
 
166
    doctest.testmod()
 
167