/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-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
19
19
# Author: Martin Pool <mbp@canonical.com>
20
20
 
21
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
22
class IntSet(Exception):
28
23
    """Faster set-like class storing only whole numbers.
29
24
 
64
59
    [10]
65
60
    
66
61
    """
67
 
    __slots__ = ['_val']
 
62
    # __slots__ = ['_val']
68
63
 
69
 
    def __init__(self, values=None, bitmask=0L):
 
64
    def __init__(self, values=None):
70
65
        """Create a new intset.
71
66
 
72
67
        values
73
68
            If specified, an initial collection of values.
74
69
        """
75
 
        self._val = bitmask
 
70
        self._val = 0
76
71
        if values != None:
77
72
            self.update(values)
78
73
 
89
84
        return bool(self._val)
90
85
 
91
86
 
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
87
    def __eq__(self, other):
138
 
        """Comparison.
139
 
 
140
 
        >>> IntSet(range(3)) == IntSet([2, 0, 1])
141
 
        True
142
 
        """
 
88
        """Comparison."""
143
89
        if isinstance(other, IntSet):
144
90
            return self._val == other._val
145
91
        else: