1 | #ifndef PS_BITMAP_HXX |
---|
2 | #define PS_BITMAP_HXX |
---|
3 | |
---|
4 | #ifndef __MAP__ |
---|
5 | #include <map> |
---|
6 | #endif |
---|
7 | #ifndef PS_BITSET_HXX |
---|
8 | #include "ps_bitset.hxx" |
---|
9 | #endif |
---|
10 | |
---|
11 | // ############################################################ |
---|
12 | // # PS_BitMap |
---|
13 | // ############################################################ |
---|
14 | class PS_BitMap { |
---|
15 | protected: |
---|
16 | |
---|
17 | PS_BitSet **data; // array of pointers to PS_BitSet |
---|
18 | bool bias; // preset for bitmap |
---|
19 | long max_row; // max used row index |
---|
20 | long capacity; // number of allocated rows (and columns) |
---|
21 | |
---|
22 | virtual bool do_reserve( const long _capacity, const bool _init_sets ); |
---|
23 | |
---|
24 | PS_BitMap( const PS_BitMap& ); |
---|
25 | PS_BitMap(); |
---|
26 | PS_BitMap( const bool _bias, const long _max_row, const long _capacity ) { |
---|
27 | bias = _bias; |
---|
28 | max_row = _max_row; |
---|
29 | capacity = _capacity; |
---|
30 | } |
---|
31 | |
---|
32 | public: |
---|
33 | |
---|
34 | virtual long getTrueIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ); |
---|
35 | virtual long getFalseIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ); |
---|
36 | virtual long getCountOfTrues(); |
---|
37 | |
---|
38 | virtual bool get( const long _row, const long _col ); |
---|
39 | virtual bool set( const long _row, const long _col, const bool _value ); |
---|
40 | // triangle_ - functions reverse _row and _col if _row is greater than _col |
---|
41 | // the resulting map is only triangular |
---|
42 | bool triangle_get( const long _row, const long _col ); |
---|
43 | bool triangle_set( const long _row, const long _col, const bool _value ); |
---|
44 | |
---|
45 | virtual void invert(); |
---|
46 | virtual void x_or( const PS_BitMap *_other_map ); |
---|
47 | |
---|
48 | virtual void print(); |
---|
49 | virtual void printGNUplot( const char *_title, char *_buffer, PS_FileBuffer *_file ); |
---|
50 | virtual bool save( PS_FileBuffer *_file ); |
---|
51 | virtual bool load( PS_FileBuffer *_file ); |
---|
52 | |
---|
53 | bool copy( const PS_BitMap *_other_bitmap ); |
---|
54 | virtual bool reserve( const long _capacity ); |
---|
55 | |
---|
56 | explicit PS_BitMap( const bool _bias, const long _capacity ) : bias(_bias), max_row(0), capacity(_capacity) { |
---|
57 | data = (PS_BitSet **)malloc(capacity * sizeof(PS_BitSet*)); |
---|
58 | // printf( "PS_BitMap(%p) data = malloc(%lu) = %p\n", this, capacity*sizeof(PS_BitSet*), data ); |
---|
59 | for (long i = 0; i < capacity; ++i) { // init requested bitsets |
---|
60 | data[i] = new PS_BitSet( bias, capacity ); // init field |
---|
61 | // printf( "PS_BitMap(%p) data[%li] = %p\n", this, i, data[i] ); |
---|
62 | if (data[i] == 0) { |
---|
63 | printf( "PS_BitMap( %s,%li ) : error while init. data[%li]\n", bias ? "true" : "false", capacity, i ); |
---|
64 | exit( 1 ); |
---|
65 | } |
---|
66 | } |
---|
67 | } |
---|
68 | |
---|
69 | explicit PS_BitMap( PS_FileBuffer *_file ) : bias(false), max_row(0), capacity(0) { |
---|
70 | data = 0; |
---|
71 | load( _file ); |
---|
72 | } |
---|
73 | |
---|
74 | virtual ~PS_BitMap() { |
---|
75 | for (long i = 0; i < capacity; ++i) { |
---|
76 | // printf( "~PS_BitMap(%p) delete data[%li] (%p) : ", this, i, data[i] ); |
---|
77 | if (data[i]) delete data[i]; |
---|
78 | } |
---|
79 | // printf( "~PS_BitMap(%p) free( data(%p) (%li) )\n : ", this, data, capacity*sizeof(PS_BitSet*) ); |
---|
80 | if (data) free( data ); |
---|
81 | } |
---|
82 | }; |
---|
83 | |
---|
84 | |
---|
85 | // ############################################################ |
---|
86 | // # PS_BitMap_Fast |
---|
87 | // ############################################################ |
---|
88 | // No checks are made to assure that given row/col indices |
---|
89 | // point to an allocated byte. Make sure you reserve the needed |
---|
90 | // space either at creation time or before accessing the bits. |
---|
91 | // |
---|
92 | class PS_BitMap_Fast : public PS_BitMap { |
---|
93 | private: |
---|
94 | |
---|
95 | bool copy( const PS_BitSet *_other_bitset ); // declared but not implemented |
---|
96 | virtual bool do_reserve( const long _capacity, const bool _init_sets ); |
---|
97 | |
---|
98 | PS_BitMap_Fast( const PS_BitMap_Fast& ); |
---|
99 | PS_BitMap_Fast(); |
---|
100 | |
---|
101 | public: |
---|
102 | |
---|
103 | virtual bool get( const long _row, const long _col ); |
---|
104 | virtual bool set( const long _row, const long _col, const bool _value ); |
---|
105 | virtual void setTrue( const long _row, const long _col ); |
---|
106 | virtual void setFalse( const long _row, const long _col ); |
---|
107 | |
---|
108 | virtual bool load( PS_FileBuffer *_file ); |
---|
109 | |
---|
110 | bool copy( const PS_BitMap_Fast *_other_bitmap ); |
---|
111 | virtual bool reserve( const long _capacity ); |
---|
112 | |
---|
113 | explicit PS_BitMap_Fast( const bool _bias, const long _capacity ) : PS_BitMap(_bias,0,_capacity) { |
---|
114 | data = (PS_BitSet **)malloc(capacity * sizeof(PS_BitSet*)); |
---|
115 | // printf( "PS_BitMap_Fast(%p) data = malloc(%lu) = %p\n", this, capacity*sizeof(PS_BitSet*), data ); |
---|
116 | for (long i = 0; i < capacity; ++i) { // init requested bitsets |
---|
117 | data[i] = new PS_BitSet_Fast( bias, capacity ); // init field |
---|
118 | // printf( "PS_BitMap_Fast(%p) data[%li] = %p\n", this, i, data[i] ); |
---|
119 | if (data[i] == 0) { |
---|
120 | printf( "PS_BitMap_Fast( %s,%li ) : error while init. data[%li]\n", bias ? "true" : "false", capacity, i ); |
---|
121 | exit( 1 ); |
---|
122 | } |
---|
123 | } |
---|
124 | } |
---|
125 | }; |
---|
126 | |
---|
127 | |
---|
128 | // ############################################################ |
---|
129 | // # PS_BitMap_Counted |
---|
130 | // ############################################################ |
---|
131 | // PS_BitMap_Counted is ALWAYS triangular. |
---|
132 | // This means that the max column index in a row is the row number. |
---|
133 | // The resulting bitmap is the lower left half |
---|
134 | // 012 |
---|
135 | // 0 . |
---|
136 | // 1 .. |
---|
137 | // 2 ... |
---|
138 | // Therefore the row index must be higher or equal than the column index |
---|
139 | // when you call set/get-functions, which do not check given row,col. |
---|
140 | // If you cannot assure this use the triangleSet/Get-functions. |
---|
141 | // |
---|
142 | // count_true_per_index counts TRUEs in a row + the TRUEs in the |
---|
143 | // column of the same index. |
---|
144 | // Only set() automatically updates count_true_per_index. |
---|
145 | // |
---|
146 | class PS_BitMap_Counted : public PS_BitMap { |
---|
147 | private: |
---|
148 | |
---|
149 | long *count_true_per_index; |
---|
150 | |
---|
151 | bool copy( const PS_BitSet *_other_bitset ); // declared but not implemented because PS_BitSet has no count_true_per_index array |
---|
152 | virtual bool do_reserve( const long _capacity, const bool _init_sets ); |
---|
153 | |
---|
154 | PS_BitMap_Counted( const PS_BitMap_Counted& ); |
---|
155 | PS_BitMap_Counted(); |
---|
156 | |
---|
157 | public: |
---|
158 | |
---|
159 | void recalcCounters(); |
---|
160 | long getCountFor( const long _index ) { return count_true_per_index[ _index ]; } |
---|
161 | |
---|
162 | virtual long getTrueIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ); |
---|
163 | virtual long getFalseIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ); |
---|
164 | long getTrueIndicesForRow( const long _row, PS_BitSet::IndexSet &_index_set ); |
---|
165 | long getFalseIndicesForRow( const long _row, PS_BitSet::IndexSet &_index_set ); |
---|
166 | virtual long getCountOfTrues(); |
---|
167 | |
---|
168 | virtual bool get( const long _row, const long _col ); |
---|
169 | virtual bool set( const long _row, const long _col, const bool _value ); |
---|
170 | virtual void setTrue( const long _row, const long _col ); |
---|
171 | virtual void setFalse( const long _row, const long _col ); |
---|
172 | |
---|
173 | virtual void print(); |
---|
174 | virtual void printGNUplot( const char *_title, char *_buffer, PS_FileBuffer *_file ); |
---|
175 | virtual bool load( PS_FileBuffer *_file ); |
---|
176 | |
---|
177 | virtual bool copy( const PS_BitMap_Counted *_other_bitmap ); |
---|
178 | virtual bool reserve( const long _capacity ); |
---|
179 | |
---|
180 | explicit PS_BitMap_Counted( PS_FileBuffer *_file ) : PS_BitMap(false,0,0) { |
---|
181 | data = 0; |
---|
182 | count_true_per_index = 0; |
---|
183 | load( _file ); |
---|
184 | } |
---|
185 | |
---|
186 | explicit PS_BitMap_Counted( const bool _bias, const long _capacity ) : PS_BitMap(_bias,0,_capacity) { |
---|
187 | data = (PS_BitSet **)malloc(capacity * sizeof(PS_BitSet*)); |
---|
188 | // printf( "PS_BitMap_Counted(%p) data = malloc(%lu) = %p\n", this, capacity*sizeof(PS_BitSet*), data ); |
---|
189 | for (long i = 0; i < capacity; ++i) { // init requested bitsets |
---|
190 | data[i] = new PS_BitSet_Fast( bias, capacity ); // init field |
---|
191 | // printf( "PS_BitMap_Counted(%p) data[%li] = %p\n", this, i, data[i] ); |
---|
192 | if (data[i] == 0) { |
---|
193 | printf( "PS_BitMap_Counted( %s,%li ) : error while init. data[%li]\n", bias ? "true" : "false", capacity, i ); |
---|
194 | exit( 1 ); |
---|
195 | } |
---|
196 | } |
---|
197 | // alloc memory for counters |
---|
198 | count_true_per_index = (long *)malloc( capacity * sizeof(long) ); |
---|
199 | // printf( "PS_BitMap_Counted(%p) count_true_per_index = malloc(%lu) = %p\n", this, capacity*sizeof(long), count_true_per_index ); |
---|
200 | |
---|
201 | // preset memory of counters |
---|
202 | memset( count_true_per_index, (bias) ? capacity : 0, capacity * sizeof(long) ); |
---|
203 | } |
---|
204 | |
---|
205 | virtual ~PS_BitMap_Counted() { |
---|
206 | // printf( "~PS_BitMap_Counted(%p) free(count_true_per_index) %p (%li)\n", this, count_true_per_index, capacity*sizeof(long) ); |
---|
207 | if (count_true_per_index) free( count_true_per_index ); |
---|
208 | } |
---|
209 | }; |
---|
210 | |
---|
211 | |
---|
212 | long PS_BitMap::getTrueIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ) { |
---|
213 | // get trues in the row |
---|
214 | data[ _index ]->getTrueIndices( _index_set, _index ); |
---|
215 | // scan column _index in the remaining rows |
---|
216 | for (long row = _index+1; row <= max_row; ++row) { |
---|
217 | if (data[ row ]->Get( _index )) _index_set.insert( row ); |
---|
218 | } |
---|
219 | return _index_set.size(); |
---|
220 | } |
---|
221 | |
---|
222 | |
---|
223 | long PS_BitMap::getFalseIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ) { |
---|
224 | // get falses in the row |
---|
225 | data[ _index ]->getFalseIndices( _index_set, _index ); |
---|
226 | // scan column _index in the remaining rows |
---|
227 | for (long row = _index+1; row <= max_row; ++row) { |
---|
228 | if (!(data[ row ]->Get( _index ))) _index_set.insert( row ); |
---|
229 | } |
---|
230 | return _index_set.size(); |
---|
231 | } |
---|
232 | |
---|
233 | |
---|
234 | long PS_BitMap::getCountOfTrues() { |
---|
235 | long count = 0; |
---|
236 | // sum up trues in the rows |
---|
237 | for (long row = 0; row <= max_row; ++row) { |
---|
238 | count += data[ row ]->getCountOfTrues(); |
---|
239 | } |
---|
240 | return count; |
---|
241 | } |
---|
242 | |
---|
243 | |
---|
244 | bool PS_BitMap::set( const long _row, const long _col, const bool _value ) { |
---|
245 | reserve( _row+1 ); |
---|
246 | if (_row > max_row) max_row = _row; |
---|
247 | return data[_row]->Set( _col, _value ); |
---|
248 | } |
---|
249 | |
---|
250 | |
---|
251 | bool PS_BitMap::get( const long _row, const long _col ) { |
---|
252 | reserve( _row+1 ); |
---|
253 | return data[_row]->Get( _col ); |
---|
254 | } |
---|
255 | |
---|
256 | |
---|
257 | bool PS_BitMap::triangle_set( const long _row, const long _col, const bool _value ) { |
---|
258 | if (_row > _col) { |
---|
259 | return set( _col,_row,_value ); |
---|
260 | } else { |
---|
261 | return set( _row,_col,_value ); |
---|
262 | } |
---|
263 | } |
---|
264 | |
---|
265 | |
---|
266 | bool PS_BitMap::triangle_get( const long _row, const long _col ) { |
---|
267 | if (_row > _col) { |
---|
268 | return get( _col,_row ); |
---|
269 | } else { |
---|
270 | return get( _row,_col ); |
---|
271 | } |
---|
272 | } |
---|
273 | |
---|
274 | |
---|
275 | bool PS_BitMap::copy( const PS_BitMap *_other_bitmap ) { |
---|
276 | bias = _other_bitmap->bias; |
---|
277 | if (!do_reserve( _other_bitmap->capacity, false )) return false; |
---|
278 | for (long i = 0; i < capacity; ++i) { |
---|
279 | if (!data[i]) data[i] = new PS_BitSet( bias, _other_bitmap->data[i]->capacity ); |
---|
280 | if (!data[i]->copy( _other_bitmap->data[i] )) return false; |
---|
281 | } |
---|
282 | max_row = _other_bitmap->max_row; |
---|
283 | return true; |
---|
284 | } |
---|
285 | |
---|
286 | |
---|
287 | bool PS_BitMap::reserve( const long _capacity ) { |
---|
288 | return do_reserve( _capacity, true ); |
---|
289 | } |
---|
290 | bool PS_BitMap::do_reserve( const long _capacity, const bool _init_sets ) { |
---|
291 | PS_BitSet **new_data; |
---|
292 | long new_capacity_bytes = _capacity * sizeof(PS_BitSet*); |
---|
293 | long old_capacity_bytes = capacity * sizeof(PS_BitSet*); |
---|
294 | if (_capacity <= capacity) return true; // smaller or same size requested ? |
---|
295 | new_data = (PS_BitSet **)malloc( new_capacity_bytes ); // get new memory for pointer array |
---|
296 | if (new_data == 0) return false; |
---|
297 | if (capacity > 0) memcpy( new_data,data,old_capacity_bytes );// copy old pointers |
---|
298 | if (data) free( data ); // free old memory |
---|
299 | data = new_data; |
---|
300 | if (_init_sets) { |
---|
301 | for (long i = capacity; i < _capacity; ++i) { // init new requested bitsets |
---|
302 | data[i] = new PS_BitSet( bias,1 ); // init field |
---|
303 | if (data[i] == 0) return false; // check success |
---|
304 | } |
---|
305 | } |
---|
306 | capacity = _capacity; // store new capacity |
---|
307 | return true; |
---|
308 | } |
---|
309 | |
---|
310 | |
---|
311 | void PS_BitMap::invert() { |
---|
312 | for (long i = 0; i <= max_row; ++i) { |
---|
313 | data[i]->invert(); |
---|
314 | } |
---|
315 | } |
---|
316 | |
---|
317 | |
---|
318 | void PS_BitMap::x_or( const PS_BitMap *_other_map ) { |
---|
319 | for (long i = 0; i <= max_row; ++i) { |
---|
320 | data[i]->x_or( _other_map->data[i] ); |
---|
321 | } |
---|
322 | } |
---|
323 | |
---|
324 | |
---|
325 | void PS_BitMap::print() { |
---|
326 | printf( "PS_BitMap : bias(%1i) max_row(%6li) capacity(%6li)\n", bias, max_row, capacity ); |
---|
327 | for (long i = 0; i < capacity; ++i) { |
---|
328 | printf( "[%5li] ",i); |
---|
329 | data[i]->print( true, i ); |
---|
330 | } |
---|
331 | } |
---|
332 | |
---|
333 | |
---|
334 | void PS_BitMap::printGNUplot( const char *_title, char *_buffer, PS_FileBuffer *_file ) { |
---|
335 | // write title |
---|
336 | long size; |
---|
337 | size = sprintf( _buffer, "# %s\n#PS_BitMap : bias(%1i) max_row(%li) capacity(%li)\n#col row\n", _title, bias, max_row, capacity ); |
---|
338 | _file->put( _buffer, size ); |
---|
339 | |
---|
340 | // write indices of trues per row |
---|
341 | PS_BitSet::IndexSet trues; |
---|
342 | for ( long row = 0; |
---|
343 | row < capacity; |
---|
344 | ++row ) { |
---|
345 | data[ row ]->getTrueIndices( trues ); |
---|
346 | for ( PS_BitSet::IndexSet::iterator col = trues.begin(); |
---|
347 | col != trues.end(); |
---|
348 | ++col ) { |
---|
349 | size = sprintf( _buffer, "%li %li\n", *col, row ); |
---|
350 | _file->put( _buffer, size ); |
---|
351 | } |
---|
352 | } |
---|
353 | |
---|
354 | _file->flush(); |
---|
355 | } |
---|
356 | |
---|
357 | |
---|
358 | bool PS_BitMap::save( PS_FileBuffer *_file ) { |
---|
359 | if (_file->isReadonly()) return false; |
---|
360 | // save max_row |
---|
361 | _file->put_long( max_row ); |
---|
362 | // save bias |
---|
363 | _file->put_char( (bias) ? '1' : '0' ); |
---|
364 | // save bitsets |
---|
365 | for (long i = 0; i <= max_row; ++i) { |
---|
366 | data[i]->save( _file ); |
---|
367 | } |
---|
368 | return true; |
---|
369 | } |
---|
370 | |
---|
371 | |
---|
372 | bool PS_BitMap::load( PS_FileBuffer *_file ) { |
---|
373 | if (!_file->isReadonly()) return false; |
---|
374 | // load max_row |
---|
375 | _file->get_long( max_row ); |
---|
376 | // load bias |
---|
377 | bias = (_file->get_char() == '1'); |
---|
378 | // initialize bitmap |
---|
379 | // printf( "PS_BitMap::load(%p) max_row (%li) bias(%1i)\n", this, max_row, bias ); |
---|
380 | if (!do_reserve( max_row+1, false )) return false; |
---|
381 | for (long i = 0; i <= max_row; ++i) { |
---|
382 | if (data[i]) { |
---|
383 | // printf( "PS_BitMap::load(%p) delete data[%li] = %p\n", this, i, data[i] ); |
---|
384 | delete data[i]; |
---|
385 | } |
---|
386 | // printf( "PS_BitMap::load(%p) load data[%li] = ", this,i ); |
---|
387 | data[i] = new PS_BitSet( _file ); |
---|
388 | // printf( "%p\n", data[i] ); |
---|
389 | } |
---|
390 | return true; |
---|
391 | } |
---|
392 | |
---|
393 | |
---|
394 | inline bool PS_BitMap_Fast::set( const long _row, const long _col, const bool _value ) { |
---|
395 | if (_row > max_row) max_row = _row; |
---|
396 | return data[_row]->Set( _col, _value ); |
---|
397 | } |
---|
398 | |
---|
399 | |
---|
400 | inline bool PS_BitMap_Fast::get( const long _row, const long _col ) { |
---|
401 | if (_row > max_row) max_row = _row; |
---|
402 | return data[_row]->Get( _col ); |
---|
403 | } |
---|
404 | |
---|
405 | |
---|
406 | inline void PS_BitMap_Fast::setTrue( const long _row, const long _col ) { |
---|
407 | if (_row > max_row) max_row = _row; |
---|
408 | data[_row]->setTrue( _col ); |
---|
409 | } |
---|
410 | |
---|
411 | |
---|
412 | inline void PS_BitMap_Fast::setFalse( const long _row, const long _col ) { |
---|
413 | if (_row > max_row) max_row = _row; |
---|
414 | data[_row]->setFalse( _col ); |
---|
415 | } |
---|
416 | |
---|
417 | |
---|
418 | bool PS_BitMap_Fast::load( PS_FileBuffer *_file ) { |
---|
419 | if (!_file->isReadonly()) return false; |
---|
420 | // load max_row |
---|
421 | _file->get_long( max_row ); |
---|
422 | // load bias |
---|
423 | bias = (_file->get_char() == '1'); |
---|
424 | // initialize bitmap |
---|
425 | // printf( "PS_BitMap_Fast::load(%p) max_row (%li) bias(%1i)\n", this, max_row, bias ); |
---|
426 | if (!do_reserve( max_row+1, false )) return false; |
---|
427 | for (long i = 0; i <= max_row; ++i) { |
---|
428 | if (data[i]) { |
---|
429 | // printf( "PS_BitMap_Fast::load(%p) delete data[%li] = %p\n", this, i, data[i] ); |
---|
430 | delete data[i]; |
---|
431 | } |
---|
432 | data[i] = new PS_BitSet_Fast( _file ); |
---|
433 | // printf( "PS_BitMap_Fast::load(%p) data[%li] = %p\n", this, i, data[i] ); |
---|
434 | } |
---|
435 | return true; |
---|
436 | } |
---|
437 | |
---|
438 | bool PS_BitMap_Fast::copy( const PS_BitMap_Fast *_other_bitmap ) { |
---|
439 | bias = _other_bitmap->bias; |
---|
440 | if (!do_reserve( _other_bitmap->capacity, false )) return false; |
---|
441 | for (long i = 0; i < capacity; ++i) { |
---|
442 | if (!data[i]) data[i] = new PS_BitSet_Fast( bias, _other_bitmap->data[i]->capacity ); |
---|
443 | if (!data[i]->copy( _other_bitmap->data[i] )) return false; |
---|
444 | } |
---|
445 | max_row = _other_bitmap->max_row; |
---|
446 | return true; |
---|
447 | } |
---|
448 | |
---|
449 | bool PS_BitMap_Fast::reserve( const long _capacity ) { |
---|
450 | return do_reserve( _capacity, true ); |
---|
451 | } |
---|
452 | bool PS_BitMap_Fast::do_reserve( const long _capacity, const bool _init_sets ) { |
---|
453 | if (_capacity <= capacity) return true; // smaller or same size requested ? |
---|
454 | PS_BitSet **new_data; |
---|
455 | long new_capacity_bytes = _capacity * sizeof(PS_BitSet*); |
---|
456 | long old_capacity_bytes = capacity * sizeof(PS_BitSet*); |
---|
457 | new_data = (PS_BitSet **)malloc( new_capacity_bytes ); // get new memory for pointer array |
---|
458 | if (new_data == 0) return false; |
---|
459 | if (capacity > 0) memcpy( new_data,data,old_capacity_bytes );// copy old pointers |
---|
460 | if (data) free( data ); // free old memory |
---|
461 | data = new_data; |
---|
462 | if (_init_sets) { |
---|
463 | for (long i = capacity; i < _capacity; ++i) { // init new requested bitsets |
---|
464 | data[i] = new PS_BitSet_Fast( bias,1 ); // init field |
---|
465 | if (data[i] == 0) return false; // check success |
---|
466 | } |
---|
467 | } |
---|
468 | capacity = _capacity; // store new capacity |
---|
469 | return true; |
---|
470 | } |
---|
471 | |
---|
472 | |
---|
473 | long PS_BitMap_Counted::getTrueIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ) { |
---|
474 | // get total number of trues |
---|
475 | unsigned long total_count_trues = count_true_per_index[ _index ]; |
---|
476 | // get trues in the row |
---|
477 | data[ _index ]->getTrueIndices( _index_set, _index ); |
---|
478 | // scan column _index in the remaining rows until all trues are found |
---|
479 | for (long row = _index+1; |
---|
480 | ((row <= max_row) && (_index_set.size() < total_count_trues)); |
---|
481 | ++row) { |
---|
482 | if (data[ row ]->Get( _index )) _index_set.insert( row ); |
---|
483 | } |
---|
484 | return _index_set.size(); |
---|
485 | } |
---|
486 | |
---|
487 | |
---|
488 | long PS_BitMap_Counted::getFalseIndicesFor( const long _index, PS_BitSet::IndexSet &_index_set ) { |
---|
489 | // get total number of falses |
---|
490 | unsigned long total_count_falses = capacity - count_true_per_index[ _index ]; |
---|
491 | // get falses in the row |
---|
492 | data[ _index ]->getFalseIndices( _index_set, _index ); |
---|
493 | // scan column _index in the remaining rows until all falses are found |
---|
494 | for (long row = _index+1; |
---|
495 | ((row <= max_row) && (_index_set.size() < total_count_falses)); |
---|
496 | ++row) { |
---|
497 | if (!(data[ row ]->Get( _index ))) _index_set.insert( row ); |
---|
498 | } |
---|
499 | return _index_set.size(); |
---|
500 | } |
---|
501 | |
---|
502 | |
---|
503 | long PS_BitMap_Counted::getTrueIndicesForRow( const long _row, PS_BitSet::IndexSet &_index_set ) { |
---|
504 | // get trues in the row |
---|
505 | data[ _row ]->getTrueIndices( _index_set, _row ); |
---|
506 | return _index_set.size(); |
---|
507 | } |
---|
508 | |
---|
509 | |
---|
510 | long PS_BitMap_Counted::getFalseIndicesForRow( const long _row, PS_BitSet::IndexSet &_index_set ) { |
---|
511 | // get falses in the row |
---|
512 | data[ _row ]->getFalseIndices( _index_set, _row ); |
---|
513 | return _index_set.size(); |
---|
514 | } |
---|
515 | |
---|
516 | |
---|
517 | long PS_BitMap_Counted::getCountOfTrues() { |
---|
518 | long count = 0; |
---|
519 | // sum up trues in the rows |
---|
520 | for (long row = 0; row <= max_row; ++row) { |
---|
521 | count += data[ row ]->getCountOfTrues( row ); |
---|
522 | } |
---|
523 | return count; |
---|
524 | } |
---|
525 | |
---|
526 | |
---|
527 | bool PS_BitMap_Counted::set( const long _row, const long _col, const bool _value ) { |
---|
528 | if (_col > _row) printf( "PS_BitMap_Counted::set( %li,%li,%1i ) not allowed\n", _row, _col, _value ); |
---|
529 | if (_row > max_row) max_row = _row; |
---|
530 | bool previous_value = data[_row]->Set( _col, _value ); |
---|
531 | if (_value && !previous_value) { |
---|
532 | ++count_true_per_index[ _row ]; |
---|
533 | ++count_true_per_index[ _col ]; |
---|
534 | } else if (!_value && previous_value) { |
---|
535 | --count_true_per_index[ _row ]; |
---|
536 | --count_true_per_index[ _col ]; |
---|
537 | } |
---|
538 | return previous_value; |
---|
539 | } |
---|
540 | |
---|
541 | |
---|
542 | inline bool PS_BitMap_Counted::get( const long _row, const long _col ) { |
---|
543 | if (_col > _row) printf( "PS_BitMap_Counted::get( %li,%li ) not allowed\n", _row, _col ); |
---|
544 | if (_row > max_row) max_row = _row; |
---|
545 | return data[_row]->Get( _col ); |
---|
546 | } |
---|
547 | |
---|
548 | |
---|
549 | inline void PS_BitMap_Counted::setTrue( const long _row, const long _col ) { |
---|
550 | if (_col > _row) printf( "PS_BitMap_Counted::setTrue( %li,%li ) not allowed\n", _row, _col ); |
---|
551 | if (_row > max_row) max_row = _row; |
---|
552 | data[_row]->setTrue( _col ); |
---|
553 | } |
---|
554 | |
---|
555 | |
---|
556 | inline void PS_BitMap_Counted::setFalse( const long _row, const long _col ) { |
---|
557 | if (_col > _row) printf( "PS_BitMap_Counted::setFalse( %li,%li ) not allowed\n", _row, _col ); |
---|
558 | if (_row > max_row) max_row = _row; |
---|
559 | data[_row]->setFalse( _col ); |
---|
560 | } |
---|
561 | |
---|
562 | |
---|
563 | bool PS_BitMap_Counted::load( PS_FileBuffer *_file ) { |
---|
564 | if (!_file->isReadonly()) return false; |
---|
565 | // load max_row |
---|
566 | _file->get_long( max_row ); |
---|
567 | // load bias |
---|
568 | bias = (_file->get_char() == '1'); |
---|
569 | // initialize bitmap |
---|
570 | // printf( "PS_BitMap_Counted::load(%p) max_row (%li) bias(%1i)\n", this, max_row, bias ); |
---|
571 | if (!do_reserve( max_row+1, false )) return false; |
---|
572 | for (long i = 0; i <= max_row; ++i) { |
---|
573 | if (data[i]) { |
---|
574 | // printf( "PS_BitMap_Counted::load(%p) delete data[%li] = %p\n", this, i, data[i] ); |
---|
575 | delete data[i]; |
---|
576 | } |
---|
577 | data[i] = new PS_BitSet_Fast( _file, i ); |
---|
578 | // printf( "PS_BitMap_Counted::load(%p) data[%li] = %p capacity(%li)\n", this, i, data[i], data[i]->capacity ); |
---|
579 | } |
---|
580 | recalcCounters(); |
---|
581 | return true; |
---|
582 | } |
---|
583 | |
---|
584 | |
---|
585 | bool PS_BitMap_Counted::copy( const PS_BitMap_Counted *_other_bitmap ) { |
---|
586 | bias = _other_bitmap->bias; |
---|
587 | if (!do_reserve( _other_bitmap->capacity, false )) return false; |
---|
588 | memcpy( count_true_per_index, _other_bitmap->count_true_per_index, (capacity * sizeof(long)) ); |
---|
589 | for (long i = 0; i < capacity; ++i) { |
---|
590 | if (!data[i]) data[i] = new PS_BitSet_Fast( bias, _other_bitmap->data[i]->capacity ); |
---|
591 | if (!data[i]->copy( _other_bitmap->data[i] )) return false; |
---|
592 | } |
---|
593 | max_row = _other_bitmap->max_row; |
---|
594 | return true; |
---|
595 | } |
---|
596 | |
---|
597 | |
---|
598 | bool PS_BitMap_Counted::reserve( const long _capacity ) { |
---|
599 | return do_reserve( _capacity, true ); |
---|
600 | } |
---|
601 | bool PS_BitMap_Counted::do_reserve( const long _capacity, const bool _init_sets ) { |
---|
602 | PS_BitSet **new_data; |
---|
603 | long *new_counts; |
---|
604 | if (_capacity <= capacity) return true; // smaller or same size requested ? |
---|
605 | long new_data_bytes = _capacity * sizeof(PS_BitSet*); |
---|
606 | long old_data_bytes = capacity * sizeof(PS_BitSet*); |
---|
607 | long new_counts_bytes = _capacity * sizeof(long); |
---|
608 | long old_counts_bytes = capacity * sizeof(long); |
---|
609 | // |
---|
610 | // allocate new memory |
---|
611 | // |
---|
612 | new_data = (PS_BitSet **)malloc( new_data_bytes ); |
---|
613 | new_counts = (long *)malloc( new_counts_bytes ); |
---|
614 | // printf( "PS_BitMap_Counted::reserve(%p) new_data = malloc(%li) = %p\n", this, new_data_bytes, new_data ); |
---|
615 | // printf( "PS_BitMap_Counted::reserve(%p) new_counts = malloc(%li) = %p\n", this, new_counts_bytes, new_counts ); |
---|
616 | // |
---|
617 | // test is we got the memory we wanted |
---|
618 | // |
---|
619 | if (!new_data || !new_counts) { |
---|
620 | // failed to allocate all memory so give up the parts we got |
---|
621 | if (new_data) free( new_data ); |
---|
622 | if (new_counts) free( new_counts ); |
---|
623 | return false; |
---|
624 | } |
---|
625 | // |
---|
626 | // initialize new data-array |
---|
627 | // |
---|
628 | if (capacity > 0) memcpy( new_data,data,old_data_bytes ); // copy old pointers |
---|
629 | if (data) free( data ); // free old memory |
---|
630 | data = new_data; |
---|
631 | // printf( "PS_BitMap_Counted::reserve( %li )\n", _capacity ); |
---|
632 | if (_init_sets) { |
---|
633 | for (long i = capacity; i < _capacity; ++i) { // init new requested bitsets |
---|
634 | data[i] = new PS_BitSet_Fast( bias,i+1 ); // init field |
---|
635 | // printf( "PS_BitMap_Counted::reserve(%p) data[%li] = %p\n", this, i, data[i] ); |
---|
636 | if (data[i] == 0) return false; // check success |
---|
637 | } |
---|
638 | } |
---|
639 | // |
---|
640 | // initialize new counts-arrays |
---|
641 | // |
---|
642 | if (capacity > 0) memcpy( new_counts, count_true_per_index, old_counts_bytes ); |
---|
643 | memset( new_counts+old_counts_bytes, 0, new_counts_bytes-old_counts_bytes ); |
---|
644 | if (count_true_per_index) free( count_true_per_index ); |
---|
645 | count_true_per_index = new_counts; |
---|
646 | |
---|
647 | capacity = _capacity; // store new capacity |
---|
648 | return true; |
---|
649 | } |
---|
650 | |
---|
651 | |
---|
652 | void PS_BitMap_Counted::print() { |
---|
653 | printf( "PS_BitMap_Counted : bias(%1i) max_row(%6li) capacity(%6li)\n", bias, max_row, capacity ); |
---|
654 | for (long i = 0; i < capacity; ++i) { |
---|
655 | printf( "[%5li] %6li ", i, count_true_per_index[i] ); |
---|
656 | data[i]->print( false ); |
---|
657 | } |
---|
658 | } |
---|
659 | |
---|
660 | |
---|
661 | void PS_BitMap_Counted::printGNUplot( const char *_title, char *_buffer, PS_FileBuffer *_file ) { |
---|
662 | // write title and header of bitmap |
---|
663 | long size; |
---|
664 | size = sprintf( _buffer, "# %s\n#PS_BitMap_Counted : bias(%1i) max_row(%li) capacity(%li)\n#col row - index of a true\n", _title, bias, max_row, capacity ); |
---|
665 | _file->put( _buffer, size ); |
---|
666 | |
---|
667 | // write indices of trues per row |
---|
668 | PS_BitSet::IndexSet trues; |
---|
669 | for ( long row = 0; |
---|
670 | row < capacity; |
---|
671 | ++row ) { |
---|
672 | data[ row ]->getTrueIndices( trues ); |
---|
673 | for ( PS_BitSet::IndexSet::iterator col = trues.begin(); |
---|
674 | col != trues.end(); |
---|
675 | ++col ) { |
---|
676 | size = sprintf( _buffer, "%li %li\n", *col, row ); |
---|
677 | _file->put( _buffer, size ); |
---|
678 | } |
---|
679 | } |
---|
680 | |
---|
681 | // write dataset seperator and header of counters |
---|
682 | size = sprintf( _buffer, "\n\n# speciesID count (of trues)\n" ); |
---|
683 | _file->put( _buffer, size ); |
---|
684 | |
---|
685 | // write counters per species |
---|
686 | map<long,long> species_per_count; |
---|
687 | for ( long row = 0; |
---|
688 | row < capacity; |
---|
689 | ++row ) { |
---|
690 | size = sprintf( _buffer, "%li %li\n", row, count_true_per_index[ row ] ); |
---|
691 | _file->put( _buffer, size ); |
---|
692 | ++species_per_count[ count_true_per_index[ row ] ]; |
---|
693 | } |
---|
694 | |
---|
695 | // write dataset seperator and header of counters |
---|
696 | size = sprintf( _buffer, "\n\n# count (of trues) count (of species)\n" ); |
---|
697 | _file->put( _buffer, size ); |
---|
698 | for ( map<long,long>::iterator count = species_per_count.begin(); |
---|
699 | count != species_per_count.end(); |
---|
700 | ++count ) { |
---|
701 | size = sprintf( _buffer, "%li %li\n", count->first, count->second ); |
---|
702 | _file->put( _buffer, size ); |
---|
703 | } |
---|
704 | |
---|
705 | _file->flush(); |
---|
706 | } |
---|
707 | |
---|
708 | |
---|
709 | void PS_BitMap_Counted::recalcCounters() { |
---|
710 | printf( "PS_BitMap_Counted::recalcCounters()\n" ); |
---|
711 | memset( count_true_per_index, 0, capacity * sizeof(long) ); |
---|
712 | for (long row = 0; row <= max_row; ++row) { |
---|
713 | PS_BitSet *row_data = data[row]; |
---|
714 | if (row_data->getMaxUsedIndex() > row) printf( "row %4li 0..%li ??\n", row, row_data->getMaxUsedIndex() ); |
---|
715 | for (long col = 0; col <= row_data->getMaxUsedIndex(); ++col) { |
---|
716 | if (row_data->Get(col)) { |
---|
717 | ++count_true_per_index[ col ]; |
---|
718 | if (row != col) ++count_true_per_index[ row ]; // dont count diagonal trues twice |
---|
719 | } |
---|
720 | } |
---|
721 | } |
---|
722 | } |
---|
723 | |
---|
724 | #else |
---|
725 | #error ps_bitmap.hxx included twice |
---|
726 | #endif |
---|