source: trunk/essentials/dev-lang/python/Demo/classes/bitvec.py

Last change on this file was 3225, checked in by bird, 18 years ago

Python 2.5
File size: 10.2 KB
Line 
1#
2# this is a rather strict implementation of a bit vector class
3# it is accessed the same way as an array of python-ints, except
4# the value must be 0 or 1
5#
6
7import sys; rprt = sys.stderr.write #for debugging
8
9error = 'bitvec.error'
10
11
12def _check_value(value):
13 if type(value) != type(0) or not 0 <= value < 2:
14 raise error, 'bitvec() items must have int value 0 or 1'
15
16
17import math
18
19def _compute_len(param):
20 mant, l = math.frexp(float(param))
21 bitmask = 1L << l
22 if bitmask <= param:
23 raise 'FATAL', '(param, l) = %r' % ((param, l),)
24 while l:
25 bitmask = bitmask >> 1
26 if param & bitmask:
27 break
28 l = l - 1
29 return l
30
31
32def _check_key(len, key):
33 if type(key) != type(0):
34 raise TypeError, 'sequence subscript not int'
35 if key < 0:
36 key = key + len
37 if not 0 <= key < len:
38 raise IndexError, 'list index out of range'
39 return key
40
41def _check_slice(len, i, j):
42 #the type is ok, Python already checked that
43 i, j = max(i, 0), min(len, j)
44 if i > j:
45 i = j
46 return i, j
47
48
49class BitVec:
50
51 def __init__(self, *params):
52 self._data = 0L
53 self._len = 0
54 if not len(params):
55 pass
56 elif len(params) == 1:
57 param, = params
58 if type(param) == type([]):
59 value = 0L
60 bit_mask = 1L
61 for item in param:
62 # strict check
63 #_check_value(item)
64 if item:
65 value = value | bit_mask
66 bit_mask = bit_mask << 1
67 self._data = value
68 self._len = len(param)
69 elif type(param) == type(0L):
70 if param < 0:
71 raise error, 'bitvec() can\'t handle negative longs'
72 self._data = param
73 self._len = _compute_len(param)
74 else:
75 raise error, 'bitvec() requires array or long parameter'
76 elif len(params) == 2:
77 param, length = params
78 if type(param) == type(0L):
79 if param < 0:
80 raise error, \
81 'can\'t handle negative longs'
82 self._data = param
83 if type(length) != type(0):
84 raise error, 'bitvec()\'s 2nd parameter must be int'
85 computed_length = _compute_len(param)
86 if computed_length > length:
87 print 'warning: bitvec() value is longer than the length indicates, truncating value'
88 self._data = self._data & \
89 ((1L << length) - 1)
90 self._len = length
91 else:
92 raise error, 'bitvec() requires array or long parameter'
93 else:
94 raise error, 'bitvec() requires 0 -- 2 parameter(s)'
95
96
97 def append(self, item):
98 #_check_value(item)
99 #self[self._len:self._len] = [item]
100 self[self._len:self._len] = \
101 BitVec(long(not not item), 1)
102
103
104 def count(self, value):
105 #_check_value(value)
106 if value:
107 data = self._data
108 else:
109 data = (~self)._data
110 count = 0
111 while data:
112 data, count = data >> 1, count + (data & 1 != 0)
113 return count
114
115
116 def index(self, value):
117 #_check_value(value):
118 if value:
119 data = self._data
120 else:
121 data = (~self)._data
122 index = 0
123 if not data:
124 raise ValueError, 'list.index(x): x not in list'
125 while not (data & 1):
126 data, index = data >> 1, index + 1
127 return index
128
129
130 def insert(self, index, item):
131 #_check_value(item)
132 #self[index:index] = [item]
133 self[index:index] = BitVec(long(not not item), 1)
134
135
136 def remove(self, value):
137 del self[self.index(value)]
138
139
140 def reverse(self):
141 #ouch, this one is expensive!
142 #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]
143 data, result = self._data, 0L
144 for i in range(self._len):
145 if not data:
146 result = result << (self._len - i)
147 break
148 result, data = (result << 1) | (data & 1), data >> 1
149 self._data = result
150
151
152 def sort(self):
153 c = self.count(1)
154 self._data = ((1L << c) - 1) << (self._len - c)
155
156
157 def copy(self):
158 return BitVec(self._data, self._len)
159
160
161 def seq(self):
162 result = []
163 for i in self:
164 result.append(i)
165 return result
166
167
168 def __repr__(self):
169 ##rprt('<bitvec class instance object>.' + '__repr__()\n')
170 return 'bitvec(%r, %r)' % (self._data, self._len)
171
172 def __cmp__(self, other, *rest):
173 #rprt('%r.__cmp__%r\n' % (self, (other,) + rest))
174 if type(other) != type(self):
175 other = apply(bitvec, (other, ) + rest)
176 #expensive solution... recursive binary, with slicing
177 length = self._len
178 if length == 0 or other._len == 0:
179 return cmp(length, other._len)
180 if length != other._len:
181 min_length = min(length, other._len)
182 return cmp(self[:min_length], other[:min_length]) or \
183 cmp(self[min_length:], other[min_length:])
184 #the lengths are the same now...
185 if self._data == other._data:
186 return 0
187 if length == 1:
188 return cmp(self[0], other[0])
189 else:
190 length = length >> 1
191 return cmp(self[:length], other[:length]) or \
192 cmp(self[length:], other[length:])
193
194
195 def __len__(self):
196 #rprt('%r.__len__()\n' % (self,))
197 return self._len
198
199 def __getitem__(self, key):
200 #rprt('%r.__getitem__(%r)\n' % (self, key))
201 key = _check_key(self._len, key)
202 return self._data & (1L << key) != 0
203
204 def __setitem__(self, key, value):
205 #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value))
206 key = _check_key(self._len, key)
207 #_check_value(value)
208 if value:
209 self._data = self._data | (1L << key)
210 else:
211 self._data = self._data & ~(1L << key)
212
213 def __delitem__(self, key):
214 #rprt('%r.__delitem__(%r)\n' % (self, key))
215 key = _check_key(self._len, key)
216 #el cheapo solution...
217 self._data = self[:key]._data | self[key+1:]._data >> key
218 self._len = self._len - 1
219
220 def __getslice__(self, i, j):
221 #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j))
222 i, j = _check_slice(self._len, i, j)
223 if i >= j:
224 return BitVec(0L, 0)
225 if i:
226 ndata = self._data >> i
227 else:
228 ndata = self._data
229 nlength = j - i
230 if j != self._len:
231 #we'll have to invent faster variants here
232 #e.g. mod_2exp
233 ndata = ndata & ((1L << nlength) - 1)
234 return BitVec(ndata, nlength)
235
236 def __setslice__(self, i, j, sequence, *rest):
237 #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest))
238 i, j = _check_slice(self._len, i, j)
239 if type(sequence) != type(self):
240 sequence = apply(bitvec, (sequence, ) + rest)
241 #sequence is now of our own type
242 ls_part = self[:i]
243 ms_part = self[j:]
244 self._data = ls_part._data | \
245 ((sequence._data | \
246 (ms_part._data << sequence._len)) << ls_part._len)
247 self._len = self._len - j + i + sequence._len
248
249 def __delslice__(self, i, j):
250 #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j))
251 i, j = _check_slice(self._len, i, j)
252 if i == 0 and j == self._len:
253 self._data, self._len = 0L, 0
254 elif i < j:
255 self._data = self[:i]._data | (self[j:]._data >> i)
256 self._len = self._len - j + i
257
258 def __add__(self, other):
259 #rprt('%r.__add__(%r)\n' % (self, other))
260 retval = self.copy()
261 retval[self._len:self._len] = other
262 return retval
263
264 def __mul__(self, multiplier):
265 #rprt('%r.__mul__(%r)\n' % (self, multiplier))
266 if type(multiplier) != type(0):
267 raise TypeError, 'sequence subscript not int'
268 if multiplier <= 0:
269 return BitVec(0L, 0)
270 elif multiplier == 1:
271 return self.copy()
272 #handle special cases all 0 or all 1...
273 if self._data == 0L:
274 return BitVec(0L, self._len * multiplier)
275 elif (~self)._data == 0L:
276 return ~BitVec(0L, self._len * multiplier)
277 #otherwise el cheapo again...
278 retval = BitVec(0L, 0)
279 while multiplier:
280 retval, multiplier = retval + self, multiplier - 1
281 return retval
282
283 def __and__(self, otherseq, *rest):
284 #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest))
285 if type(otherseq) != type(self):
286 otherseq = apply(bitvec, (otherseq, ) + rest)
287 #sequence is now of our own type
288 return BitVec(self._data & otherseq._data, \
289 min(self._len, otherseq._len))
290
291
292 def __xor__(self, otherseq, *rest):
293 #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest))
294 if type(otherseq) != type(self):
295 otherseq = apply(bitvec, (otherseq, ) + rest)
296 #sequence is now of our own type
297 return BitVec(self._data ^ otherseq._data, \
298 max(self._len, otherseq._len))
299
300
301 def __or__(self, otherseq, *rest):
302 #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest))
303 if type(otherseq) != type(self):
304 otherseq = apply(bitvec, (otherseq, ) + rest)
305 #sequence is now of our own type
306 return BitVec(self._data | otherseq._data, \
307 max(self._len, otherseq._len))
308
309
310 def __invert__(self):
311 #rprt('%r.__invert__()\n' % (self,))
312 return BitVec(~self._data & ((1L << self._len) - 1), \
313 self._len)
314
315 def __coerce__(self, otherseq, *rest):
316 #needed for *some* of the arithmetic operations
317 #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest))
318 if type(otherseq) != type(self):
319 otherseq = apply(bitvec, (otherseq, ) + rest)
320 return self, otherseq
321
322 def __int__(self):
323 return int(self._data)
324
325 def __long__(self):
326 return long(self._data)
327
328 def __float__(self):
329 return float(self._data)
330
331
332bitvec = BitVec
Note: See TracBrowser for help on using the repository browser.