Mercurial > repos > lsong10 > psiclass

comparison PsiCLASS-1.0.2/BitTable.hpp @ 0:903fc43d6227 draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author lsong10
date Fri, 26 Mar 2021 16:52:45 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:903fc43d6227
1 /**
2 Use an 64bit integer to represent bit table.
3
4 Li Song
5 July 24, 2012
6
7 - Modified again from May 27, 2017.
8 */
9
10
11 #ifndef _BIT_TABLE_HEADER
12 #define _BIT_TABLE_HEADER
13
14 #include <stdio.h>
15
16 typedef unsigned long long int UINT64 ;
17 #define UNIT_SIZE (sizeof( UINT64 ) * 8 )
18 #define UNIT_MASK ((UINT64)63)
19
20 class BitTable
21 {
22 private:
23 UINT64 *tab ; // The bits
24 int size ; // The size of the table
25 int asize ; // The size of the array (size/64).
26 public:
27 BitTable() // Intialize a bit table.
28 {
29 //tab = new UINT64[1] ;
30 //size = UNIT_SIZE ;
31 tab = NULL ;
32 size = 0 ;
33 }
34
35 BitTable( int s ) // Initalize a bit table with size s.
36 {
37 if ( s == 0 )
38 s = UNIT_SIZE ;
39
40 if ( s & UNIT_MASK )
41 {
42 asize = s / UNIT_SIZE + 1 ;
43 tab = new UINT64[ asize ] ;
44 }
45 else
46 {
47 asize = s / UNIT_SIZE ;
48 tab = new UINT64[ asize ] ;
49 }
50
51 size = s ;
52 Reset() ;
53 }
54
55 ~BitTable()
56 {
57 //printf( "hi %d\n", size ) ;
58 //printf( "%s\n", __func__ ) ;
59 //if ( tab != NULL )
60 // delete [] tab ;
61 //size = -1 ;
62
63 // Manually release the memory.
64 }
65
66 void Init( int s ) // Initialize a bit table with size s.
67 {
68 if ( tab != NULL )
69 delete [] tab ;
70
71 if ( s == 0 )
72 s = UNIT_SIZE ;
73
74 if ( s & UNIT_MASK )
75 {
76 asize = s / UNIT_SIZE + 1 ;
77 tab = new UINT64[ asize ] ;
78 }
79 else
80 {
81 asize = s / UNIT_SIZE ;
82 tab = new UINT64[ asize ] ;
83 }
84
85 size = s ;
86 Reset() ;
87 }
88
89 void Release()
90 {
91 if ( tab != NULL )
92 delete[] tab ;
93 tab = NULL ;
94 }
95
96 void Reset() // Make every value 0.
97 {
98 for ( int i = 0 ; i < asize ; ++i )
99 tab[i] = 0 ;
100 }
101
102 void Set( int i ) // Set the ith bit.
103 {
104 int ind, offset ;
105 ind = i / UNIT_SIZE ;
106 offset = i & UNIT_MASK ;
107 //printf( "%d,%d %d,%d: %llx", 311 / UNIT_SIZE, 311 & UNIT_MASK, 279 / UNIT_SIZE, 279 & UNIT_MASK, tab[ind] ) ;
108 tab[ind] |= ( (UINT64)1 << offset ) ;
109 //printf( " %llx %d\n", tab[ind], UNIT_SIZE ) ;
110 }
111
112 void Unset( int i ) // Unset the ith bit
113 {
114 int ind, offset ;
115 ind = i / UNIT_SIZE ;
116 offset = i & UNIT_MASK ;
117
118 tab[ind] &= ( (UINT64)-1 ^ ( (UINT64)1 << offset ) ) ;
119 }
120
121 void Flip( int i ) // Flip the ith bit. Same as xor 1.
122 {
123 int ind, offset ;
124 ind = i / UNIT_SIZE ;
125 offset = i & UNIT_MASK ;
126
127 tab[ind] ^= ( (UINT64)1 << offset ) ;
128 }
129
130 bool Test( unsigned int i ) const // Test the ith bit.
131 {
132 if ( i >= (unsigned int)size )
133 return false ;
134
135 unsigned int ind, offset ;
136 ind = i / UNIT_SIZE ;
137 offset = i & UNIT_MASK ;
138
139 if ( tab[ind] & ( (UINT64)1 << offset ) )
140 return true ;
141 else
142 return false ;
143 }
144
145 void Not() // Not all the bits.
146 {
147 int i ;
148 for ( i = 0 ; i < asize ; ++i )
149 {
150 tab[i] = ~tab[i] ;
151 }
152 }
153
154 void And( const BitTable &in ) // Do the "and" on each bits.
155 {
156 if ( asize != in.asize )
157 return ;
158 int i ;
159 for ( i = 0 ; i < asize ; ++i )
160 tab[i] &= in.tab[i] ;
161 }
162
163 void Or( const BitTable &in ) // Do the "or" on each bits.
164 {
165 if ( asize != in.asize )
166 return ;
167 int i ;
168 for ( i = 0 ; i < asize ; ++i )
169 tab[i] |= in.tab[i] ;
170 }
171
172 void Xor( const BitTable &in )
173 {
174 if ( asize != in.asize )
175 return ;
176 int i ;
177 for ( i = 0 ; i < asize ; ++i )
178 tab[i] ^= in.tab[i] ;
179 }
180
181 // Unset all the bits outside [s,e]
182 void MaskRegionOutside( unsigned int s, unsigned int e )
183 {
184 int i ;
185 // mask out [0, s-1].
186 int ind, offset ;
187 if ( s > 0 )
188 {
189 ind = (s - 1) / UNIT_SIZE ;
190 offset = ( s - 1 ) & UNIT_MASK ;
191 for ( i = 0 ; i <= ind - 1 ; ++i )
192 tab[i] = 0 ;
193 if ( offset + 1 >= 64 )
194 tab[i] = 0 ;
195 else
196 tab[i] = ( tab[i] >> (UINT64)( offset + 1 ) ) << (UINT64)( offset + 1 ) ;
197 }
198
199 // mask out [e+1, size-1]
200 if ( e < ( (unsigned int)size - 1 ) )
201 {
202 ind = ( e + 1 ) / UNIT_SIZE ;
203 offset = ( e + 1 ) & UNIT_MASK ;
204 for ( i = ind + 1 ; i < asize ; ++i )
205 tab[i] = 0 ;
206
207 if ( UNIT_SIZE - offset >= 64 )
208 tab[ind] = 0 ;
209 else
210 tab[ind] = ( tab[ind] << (UINT64)( UNIT_SIZE - offset ) ) >> (UINT64)( UNIT_SIZE - offset ) ;
211 }
212 }
213
214 // Given further information about the position of first and last 1's
215 void MaskRegionOutsideInRange( int s, int e, int first, int last )
216 {
217 int i ;
218 int start, to ;
219 start = first / UNIT_SIZE ;
220 to = last / UNIT_SIZE ;
221 // mask out [0, s-1].
222 int ind, offset ;
223 if ( s > 0 )
224 {
225 ind = (s - 1) / UNIT_SIZE ;
226 offset = ( s - 1 ) & UNIT_MASK ;
227 for ( i = start ; i <= ind - 1 ; ++i )
228 tab[i] = 0 ;
229 if ( offset + 1 >= 64 )
230 tab[i] = 0 ;
231 else
232 tab[i] = ( tab[i] >> (UINT64)( offset + 1 ) ) << (UINT64)( offset + 1 ) ;
233 }
234
235 // mask out [e+1, size-1]
236 if ( e < size - 1 )
237 {
238 ind = ( e + 1 ) / UNIT_SIZE ;
239 offset = ( e + 1 ) & UNIT_MASK ;
240 for ( i = ind + 1 ; i <= to ; ++i )
241 tab[i] = 0 ;
242
243 if ( UNIT_SIZE - offset >= 64 )
244 tab[ind] = 0 ;
245 else
246 tab[ind] = ( tab[ind] << (UINT64)( UNIT_SIZE - offset ) ) >> (UINT64)( UNIT_SIZE - offset ) ;
247 }
248 }
249 void ShiftOneLeft()
250 {
251 int i ;
252 UINT64 carry = 0 ;
253 UINT64 lastTabMask ;
254 if ( ( size & UNIT_MASK ) == 0 )
255 lastTabMask = (UINT64)(-1) ;
256 else
257 lastTabMask = ( 1 << ( size & UNIT_MASK ) ) - 1 ;
258
259 for ( i = 0 ; i < asize - 1 ; ++i )
260 {
261 UINT64 tmp = ( tab[i] >> ( UNIT_SIZE - 1 ) ) & 1 ;
262 tab[i] = ( tab[i] << 1 ) | carry ;
263 carry = tmp ;
264 }
265 tab[i] = ( ( tab[i] << 1 ) | carry ) & lastTabMask ;
266 }
267
268 void ShiftOneRight()
269 {
270 int i ;
271 UINT64 carry = ( tab[ asize - 1 ] & 1 ) ;
272 tab[ asize - 1 ] >>= 1 ;
273 for ( i = asize - 2 ; i >= 0 ; --i )
274 {
275 UINT64 tmp = ( tab[i] & 1 ) ;
276 tab[i] = ( tab[i] >> 1 ) | ( carry << ( UNIT_SIZE - 1 ) ) ;
277 carry = tmp ;
278 }
279 }
280
281 bool IsAllZero()
282 {
283 int i ;
284 for ( i = 0 ; i < asize ; ++i )
285 if ( tab[i] != 0 )
286 return false ;
287 return true ;
288 }
289
290 int Count() const // Count how many 1.
291 {
292 if ( size <= 0 )
293 return 0 ;
294 UINT64 k ;
295 int i, ret = 0 ;
296 for ( i = 0 ; i < asize - 1 ; ++i )
297 {
298 k = tab[i] ;
299 while ( k )
300 //for ( j = 0 ; j < UNIT_SIZE ; ++j )
301 {
302 if ( k & 1 )
303 ++ret ;
304 //printf( "### %d %d %d %d\n", ret, asize, size, k ) ;
305 k /= 2 ;
306 }
307 }
308 //printf( "(%d) ", ret ) ;
309 k = tab[ asize - 1 ] ;
310 for ( i = 0 ; i <= (int)( ( size - 1 ) & UNIT_MASK ) ; ++i )
311 {
312 if ( k & 1 )
313 ++ret ;
314 k /= 2 ;
315 }
316 //for ( i = 0 ; i < asize ; ++i )
317 // printf( "%llu ", tab[i] ) ;
318 //printf( "(%d)\n", ret ) ;
319 return ret ;
320 }
321
322 void GetOnesIndices( std::vector<int> &indices )
323 {
324 if ( size <= 0 )
325 return ;
326 UINT64 k ;
327 int i ;
328 int ind = 0 ;
329 for ( i = 0 ; i < asize - 1 ; ++i )
330 {
331 k = tab[i] ;
332 ind = i * UNIT_SIZE ;
333 while ( k )
334 //for ( j = 0 ; j < UNIT_SIZE ; ++j )
335 {
336 if ( k & 1 )
337 indices.push_back( ind ) ;
338 //printf( "### %d %d %d %d\n", ret, asize, size, k ) ;
339 k /= 2 ;
340 ++ind ;
341 }
342 }
343 //printf( "(%d) ", ret ) ;
344 k = tab[ asize - 1 ] ;
345 ind = i * UNIT_SIZE ;
346 for ( i = 0 ; i <= (int)( ( size - 1 ) & UNIT_MASK ) ; ++i )
347 {
348 if ( k & 1ull )
349 indices.push_back( ind ) ;
350 k /= 2ull ;
351 ++ind ;
352 }
353 }
354
355 bool IsEqual( const BitTable &in ) const// Test wether two bit tables equal.
356 {
357 int i ;
358 if ( in.size != size )
359 return false ;
360 //printf( "== %d %d\n", in.size, size ) ;
361 //if ( size & UNIT_MASK )
362 // k = size / UNIT_SIZE + 1 ;
363 //else
364 // k = size / UNIT_SIZE ;
365
366 for ( i = 0 ; i < asize ; ++i )
367 if ( tab[i] != in.tab[i] )
368 return false ;
369 return true ;
370 }
371
372 // Return the location of the first difference. -1 if the same.
373 int GetFirstDifference( const BitTable &in ) const
374 {
375 int as = asize < in.asize ? asize : in.asize ;
376 //int s = size < in.size ? size : in.size ;
377 int i, j ;
378
379 for ( i = 0 ; i < as ; ++i )
380 {
381 if ( tab[i] != in.tab[i] )
382 {
383 UINT64 k1 = tab[i] ;
384 UINT64 k2 = in.tab[i] ;
385 for ( j = 0 ; j < (int)UNIT_SIZE ; ++j )
386 {
387 if ( ( k1 & 1 ) != ( k2 & 1 ) )
388 {
389 return j + UNIT_SIZE * i ;
390 }
391 k1 >>= 1 ;
392 k2 >>= 1 ;
393 }
394 }
395 }
396
397 for ( ; i < asize ; ++i )
398 {
399 if ( tab[i] != 0 )
400 {
401 UINT64 k = tab[i] ;
402 for ( j = 0 ; j < (int)UNIT_SIZE ; ++j )
403 {
404 if ( k & 1 )
405 return j + UNIT_SIZE * i ;
406 k >>= 1 ;
407 }
408 }
409 }
410
411 for ( ; i < in.asize ; ++i )
412 {
413 if ( in.tab[i] != 0 )
414 {
415 UINT64 k = in.tab[i] ;
416 for ( j = 0 ; j < (int)UNIT_SIZE ; ++j )
417 {
418 if ( k & 1 )
419 return j + UNIT_SIZE * i ;
420 k >>= 1 ;
421 }
422 }
423 }
424 return -1 ;
425 }
426
427 void Duplicate( BitTable &in )
428 {
429 if ( tab != NULL )
430 delete [] tab ;
431 int i ;
432 size = in.size ;
433 asize = in.asize ;
434 tab = new UINT64[ asize ] ;
435 for ( i = 0 ; i < asize ; ++i )
436 tab[i] = in.tab[i] ;
437 }
438
439 /*void SetBulk( int ind, uint64_t val )
440 {
441 tab[ind] = val ;
442 }*/
443
444 void Assign( BitTable &in )
445 {
446 int i ;
447 for ( i = 0 ; i < asize ; ++i )
448 tab[i] = in.tab[i] ;
449 }
450
451 void Nullify()
452 {
453 tab = NULL ;
454 }
455
456 int GetSize()
457 {
458 return size ;
459 }
460
461 void Print()
462 {
463 int i ;
464 for ( i = 0 ; i < asize; ++i )
465 printf( "%llu ", tab[i] ) ;
466 printf( "\n" ) ;
467 }
468 } ;
469
470
471 #endif