ARB
ps_bitset.hxx
Go to the documentation of this file.
1 #ifndef PS_BITSET_HXX
2 #define PS_BITSET_HXX
3 
4 #ifndef __SET__
5 #include <set>
6 #endif
7 #ifndef PS_FILEBUFFER_HXX
8 #include "ps_filebuffer.hxx"
9 #endif
10 
11 class PS_BitSet : virtual Noncopyable {
12 protected:
13  unsigned char *data;
14 
15  bool bias; // preset value for newly allocated memory
16  long max_index; // max. used index
17  long capacity; // number of allocated bits
18 
19  PS_BitSet(const bool _bias, const long _max_index, const long _capacity)
20  : data(NULp),
21  bias(_bias),
22  max_index(_max_index),
23  capacity(_capacity)
24  {}
25 
26 public:
27  typedef set<long> IndexSet;
28 
29  long getTrueIndices(IndexSet &_index_set, const long _fill_index);
30  long getFalseIndices(IndexSet &_index_set, const long _fill_index);
31  long getCountOfTrues(const long _fill_index = -1);
32 
33  long getMaxUsedIndex() const { return max_index; }
34  long getCapacity() const { return capacity; }
35 
36  virtual bool Get(const long _index);
37  virtual bool Set(const long _index, const bool _value);
38 
39  virtual void setTrue(const long _index);
40  virtual void setFalse(const long _index);
41 
42  void invert();
43  void x_or(const PS_BitSet *_other_set);
44 
45  void print(FILE *out, const bool _header, const long _fill_index);
46  bool save(PS_FileBuffer *_file);
47  bool load(PS_FileBuffer *_file, const long _fill_index);
48 
49  bool copy(const PS_BitSet *_other_bitset);
50  virtual bool reserve(const long _capacity);
51 
52  explicit PS_BitSet(const bool _bias, const long _capacity) : bias(_bias), max_index(-1), capacity(0) {
53  data = NULp;
54  reserve(_capacity);
55  }
56 
57  explicit PS_BitSet(PS_FileBuffer *_file, const long _fill_index = -1) : bias(false), max_index(-1), capacity(0) {
58  data = NULp;
59  load(_file, _fill_index);
60  }
61 
62  virtual ~PS_BitSet() {
63  if (data) free(data);
64  }
65 };
66 
67 // ############################################################
68 // # PS_BitSet_Fast
69 // ############################################################
70 class PS_BitSet_Fast FINAL_TYPE : public PS_BitSet {
71 private:
72 
73  PS_BitSet_Fast(const PS_BitSet_Fast&);
74  PS_BitSet_Fast();
75 
76 public:
77 
78  bool Get(const long _index) OVERRIDE;
79  bool Set(const long _index, const bool _value) OVERRIDE;
80 
81  void setTrue(const long _index) OVERRIDE;
82  void setFalse(const long _index) OVERRIDE;
83 
84  bool reserve(const long _capacity) OVERRIDE;
85 
86  explicit PS_BitSet_Fast(PS_FileBuffer *_file, const long _fill_index = -1) : PS_BitSet(false, -1, 0) {
87  data = NULp;
88  load(_file, _fill_index);
89  }
90 
91  explicit PS_BitSet_Fast(bool _bias, long _capacity) : PS_BitSet(_bias, _capacity) {
92  // we just altered member functions so we don't do anything here
93  // but call correct base class constructor to prevent
94  // the call of PS_BitSet() without parameters
95  }
96 };
97 
98 
99 long PS_BitSet::getFalseIndices(PS_BitSet::IndexSet &_index_set, const long _fill_index = -1) {
100  _index_set.clear();
101  // get indices of falses from bitset up to max_index
102  long index = 0;
103  long byte_index = 0;
104  while (index<=max_index) {
105  unsigned char byte = data[byte_index++]; // get a data byte
106  for (int i = 0; i<8 && index<=max_index; ++i) {
107  if (!(byte&1)) _index_set.insert(index);
108  ++index;
109  byte >>= 1;
110  }
111  }
112  ps_assert(index == max_index+1);
113  // append indices [max_index+1 .. _fill_index] if bias is set to false
114  if (!bias) {
115  for (; (index <= _fill_index); ++index) {
116  _index_set.insert(index);
117  }
118  }
119  return _index_set.size();
120 }
121 
122 
123 long PS_BitSet::getTrueIndices(PS_BitSet::IndexSet &_index_set, const long _fill_index = -1) {
124  _index_set.clear();
125  // get indices of trues from bitset up to max_index
126  long index = 0;
127  long byte_index = 0;
128  while (index<=max_index) {
129  unsigned char byte = data[byte_index++]; // get a data byte
130  for (int i = 0; i<8 && index<=max_index; ++i) {
131  if (byte&1) _index_set.insert(index);
132  ++index;
133  byte >>= 1;
134  }
135  }
136  ps_assert(index == max_index+1);
137  // append indices [max_index+1 .. _max_index] if bias is set to true
138  if (bias) {
139  for (; (index <= _fill_index); ++index) {
140  _index_set.insert(index);
141  }
142  }
143  return _index_set.size();
144 }
145 
146 
147 long PS_BitSet::getCountOfTrues(const long _fill_index) {
148  long count = 0;
149  // get indices of trues from bitset up to max_index
150  long index = 0;
151  long byte_index = 0;
152  while (index<=max_index) {
153  unsigned char byte = data[byte_index++]; // get a data byte
154  for (int i = 0; i<8 && index<=max_index; ++i) {
155  if (byte&1) ++count;
156  ++index;
157  byte >>= 1;
158  }
159  }
160  ps_assert(index == max_index+1);
161  // append indices [max_index+1 .. _max_index] if bias is set to true
162  if (bias && (_fill_index > max_index)) {
163  count += _fill_index-max_index + 1;
164  }
165  return count;
166 }
167 
168 
169 bool PS_BitSet::Set(const long _index, const bool _value) {
170  ps_assert(_index >= 0);
171  reserve(_index);
172  bool previous_value = (((data[_index/8] >> (_index % 8)) & 1) == 1);
173  if (_value) {
174  data[_index/8] |= 1 << (_index % 8);
175  }
176  else {
177  data[_index/8] &= ~(1 << (_index % 8));
178  }
179  if (_index > max_index) max_index = _index;
180  return previous_value;
181 }
182 
183 
184 void PS_BitSet::setTrue(const long _index) {
185  ps_assert(_index >= 0);
186  reserve(_index);
187  data[_index/8] &= 1 << (_index % 8);
188  if (_index > max_index) max_index = _index;
189 }
190 
191 
192 void PS_BitSet::setFalse(const long _index) {
193  ps_assert(_index >= 0);
194  reserve(_index);
195  data[_index/8] &= ~(1 << (_index % 8));
196  if (_index > max_index) max_index = _index;
197 }
198 
199 
200 bool PS_BitSet::Get(const long _index) {
201  ps_assert(_index >= 0);
202  reserve(_index);
203  return ((data[_index/8] >> (_index % 8)) & 1) == 1;
204 }
205 
206 
207 bool PS_BitSet::copy(const PS_BitSet *_other_bitset) {
208  bias = _other_bitset->bias;
209  if (!reserve(_other_bitset->capacity)) return false;
210  memcpy(data, _other_bitset->data, (capacity>>3));
211  max_index = _other_bitset->max_index;
212  return true;
213 }
214 
215 
216 bool PS_BitSet::reserve(const long _capacity) {
217  unsigned char *new_data;
218  long new_capacity_bytes = (_capacity/8)+1;
219  long old_capacity_bytes = (capacity/8)+1;
220  if (capacity > 0) {
221  if (new_capacity_bytes <= old_capacity_bytes) return true; // smaller or same size requested ?
222  }
223  new_capacity_bytes = ((new_capacity_bytes / 32)+1)*32; // adjust requested size to bigger chunks
224  new_data = (unsigned char *)malloc(new_capacity_bytes); // get new memory
225  if (!new_data) return false;
226  memset(new_data, bias ? 0xFF : 0, new_capacity_bytes); // set memory to bias value
227  if (capacity > 0) memcpy(new_data, data, old_capacity_bytes); // copy old values
228  if (data) free(data); // free old memory
229  data = new_data; // store new pointer
230  capacity = new_capacity_bytes*8; // store new capacity
231  return true;
232 }
233 
234 
236  for (long i = 0; i < capacity/8; ++i) {
237  data[i] = ~data[i];
238  }
239 }
240 
241 
242 void PS_BitSet::x_or(const PS_BitSet *_other_set) {
243  for (long i = 0; i < capacity/8; ++i) {
244  data[i] ^= _other_set->data[i];
245  }
246 }
247 
248 
249 void PS_BitSet::print(FILE *out, const bool _header = true, const long _fill_index = -1) {
250  if (_header) fprintf(out, "PS_BitSet: bias(%1i) max_index(%6li) capacity(%6li) ", bias, max_index, capacity);
251  for (long i = 0; i <= max_index; ++i) {
252  fputc(Get(i) ? '+' : '_', out);
253  }
254  for (long i = max_index+1; i <= _fill_index; ++i) {
255  fputc('.', out);
256  }
257  fprintf(out, " %li\n", max_index);
258 }
259 
260 
262  if (_file->isReadonly()) return false;
263  // save max_index
264  _file->put_long(max_index);
265  // save bias
266  _file->put_char((bias) ? '1' : '0');
267  // save bitset
268  long bytes = (max_index / 8)+1;
269  long i = 0;
270  while ((bytes-i) >= PS_FileBuffer::BUFFER_SIZE) {
271  _file->put(&(data[i]), PS_FileBuffer::BUFFER_SIZE);
273  }
274  _file->put(&(data[i]), (bytes-i));
275  return true;
276 }
277 
278 
279 bool PS_BitSet::load(PS_FileBuffer *_file, const long _fill_index = -1) {
280  // load max_index
281  _file->get_long(max_index);
282  // load bias
283  bias = (_file->get_char() == '1');
284  // initialize bitset
285  capacity = 0;
286  if (!reserve((max_index > _fill_index) ? max_index : _fill_index)) return false;
287  // load bitset
288  long bytes = (max_index / 8)+1;
289  long i = 0;
290  while ((bytes-i) >= PS_FileBuffer::BUFFER_SIZE) {
291  _file->get(&(data[i]), PS_FileBuffer::BUFFER_SIZE);
293  }
294  _file->get(&(data[i]), (bytes-i));
295  return true;
296 }
297 
298 
299 bool PS_BitSet_Fast::Get(const long _index) {
300  if (_index >= capacity) {
301  printf("PS_BitSet_Fast::get( %li ) exceeds capacity %li\n", _index, capacity);
302  ps_assert(0);
303  return false;
304  }
305  if (_index > max_index) max_index = _index;
306  return ((data[_index/8] >> (_index % 8)) & 1) == 1;
307 }
308 
309 
310 bool PS_BitSet_Fast::Set(const long _index, const bool _value) {
311  if (_index >= capacity) {
312  printf("PS_BitSet_Fast::set( %li,%1i ) exceeds capacity %li\n", _index, _value, capacity);
313  ps_assert(0);
314  return false;
315  }
316  bool previous_value = (((data[_index/8] >> (_index % 8)) & 1) == 1);
317  if (_value) {
318  data[_index/8] |= 1 << (_index % 8);
319  }
320  else {
321  data[_index/8] &= ~(1 << (_index % 8));
322  }
323  if (_index > max_index) max_index = _index;
324  return previous_value;
325 }
326 
327 
328 void PS_BitSet_Fast::setTrue(const long _index) {
329  if (_index >= capacity) {
330  printf("PS_BitSet_Fast::setTrue( %li ) exceeds capacity %li\n", _index, capacity);
331  ps_assert(0);
332  return;
333  }
334  data[_index/8] |= 1 << (_index % 8);
335  if (_index > max_index) max_index = _index;
336 }
337 
338 
339 void PS_BitSet_Fast::setFalse(const long _index) {
340  if (_index >= capacity) printf("PS_BitSet_Fast::setFalse( %li ) exceeds capacity %li\n", _index, capacity);
341  data[_index/8] &= ~(1 << (_index % 8));
342  if (_index > max_index) max_index = _index;
343 }
344 
345 
346 // as i assume that a user of the _FAST variant knows how much
347 // data will be stored in the set we don't adjust the given
348 // capacity to bigger chunks as PS_BitSet::reserve does
349 bool PS_BitSet_Fast::reserve(const long _capacity) {
350  unsigned char *new_data;
351  long new_capacity_bytes = (_capacity/8)+1;
352  long old_capacity_bytes = (capacity/8)+1;
353  if (capacity > 0) {
354  if (new_capacity_bytes <= old_capacity_bytes) return true; // smaller or same size requested ?
355  }
356  new_data = (unsigned char *)malloc(new_capacity_bytes); // get new memory
357  if (!new_data) return false;
358  memset(new_data, bias ? 0xFF : 0, new_capacity_bytes); // set memory to bias value
359  if (capacity > 0) memcpy(new_data, data, old_capacity_bytes); // copy old values
360  if (data) free(data); // free old memory
361  data = new_data; // store new pointer
362  capacity = new_capacity_bytes*8; // store new capacity
363  return true;
364 }
365 #else
366 #error ps_bitset.hxx included twice
367 #endif
void get(void *_data, int _length)
long getTrueIndices(IndexSet &_index_set, const long _fill_index)
Definition: ps_bitset.hxx:123
bool copy(const PS_BitSet *_other_bitset)
Definition: ps_bitset.hxx:207
void x_or(const PS_BitSet *_other_set)
Definition: ps_bitset.hxx:242
void put_char(unsigned char _c)
void get_char(unsigned char &_c)
long getMaxUsedIndex() const
Definition: ps_bitset.hxx:33
bool bias
Definition: ps_bitset.hxx:15
void put_long(long int _l)
virtual bool reserve(const long _capacity)
Definition: ps_bitset.hxx:216
unsigned char * data
Definition: ps_bitset.hxx:13
void get_long(long int &_l)
virtual ~PS_BitSet()
Definition: ps_bitset.hxx:62
void print(FILE *out, const bool _header, const long _fill_index)
Definition: ps_bitset.hxx:249
long getCapacity() const
Definition: ps_bitset.hxx:34
PS_BitSet(const bool _bias, const long _max_index, const long _capacity)
Definition: ps_bitset.hxx:19
#define false
Definition: ureadseq.h:13
fputc('\n', stderr)
void put(const void *_data, int _length)
bool load(PS_FileBuffer *_file, const long _fill_index)
Definition: ps_bitset.hxx:279
long capacity
Definition: ps_bitset.hxx:17
set< long > IndexSet
Definition: ps_bitset.hxx:27
PS_BitSet(const bool _bias, const long _capacity)
Definition: ps_bitset.hxx:52
long getFalseIndices(IndexSet &_index_set, const long _fill_index)
Definition: ps_bitset.hxx:99
long max_index
Definition: ps_bitset.hxx:16
static const int BUFFER_SIZE
PS_BitSet(PS_FileBuffer *_file, const long _fill_index=-1)
Definition: ps_bitset.hxx:57
xml element
#define OVERRIDE
Definition: cxxforward.h:93
virtual bool Set(const long _index, const bool _value)
Definition: ps_bitset.hxx:169
virtual bool Get(const long _index)
Definition: ps_bitset.hxx:200
#define NULp
Definition: cxxforward.h:97
long getCountOfTrues(const long _fill_index=-1)
Definition: ps_bitset.hxx:147
bool save(PS_FileBuffer *_file)
Definition: ps_bitset.hxx:261
virtual void setTrue(const long _index)
Definition: ps_bitset.hxx:184
#define ps_assert(cond)
Definition: ps_assert.hxx:18
PS_BitSet_Fast(bool _bias, long _capacity)
Definition: ps_bitset.hxx:91
void invert()
Definition: ps_bitset.hxx:235
PS_BitSet_Fast(PS_FileBuffer *_file, const long _fill_index=-1)
Definition: ps_bitset.hxx:86
virtual void setFalse(const long _index)
Definition: ps_bitset.hxx:192