source: python/trunk/Demo/classes/bitvec.py@ 1538

Last change on this file since 1538 was 2, checked in by Yuri Dario, 15 years ago

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