feisty meow concerns codebase  2.140
bit_vector.cpp
Go to the documentation of this file.
1 /*****************************************************************************\
2 * *
3 * Name : bit_vector *
4 * Author : Chris Koeritz *
5 * *
6 *******************************************************************************
7 * Copyright (c) 1990-$now By Author. This program is free software; you can *
8 * redistribute it and/or modify it under the terms of the GNU General Public *
9 * License as published by the Free Software Foundation; either version 2 of *
10 * the License or (at your option) any later version. This is online at: *
11 * http://www.fsf.org/copyleft/gpl.html *
12 * Please send any updates to: fred@gruntose.com *
13 \*****************************************************************************/
14 
15 #include "bit_vector.h"
16 
17 #include <basis/byte_array.h>
18 #include <basis/definitions.h>
19 #include <basis/functions.h>
20 #include <basis/guards.h>
21 
22 //#define DEBUG_BIT_VECTOR
23  // uncomment this to get debugging noise.
24 
25 #undef LOG
26 #ifdef DEBUG_BIT_VECTOR
27  #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
28 #else
29  #define LOG(s) {}
30 #endif
31 
32 using namespace basis;
33 
34 namespace structures {
35 
36 bit_vector::bit_vector()
37 : _implementation(new byte_array(0, NULL_POINTER)), _number_of_bits(0)
38 {}
39 
40 bit_vector::bit_vector(int number_of_bits, const abyte *initial)
41 : _implementation(new byte_array(0, NULL_POINTER)), _number_of_bits(0)
42 {
43  reset(number_of_bits);
44  if (!initial) return;
45  _implementation->reset(number_of_packets(number_of_bits,
46  int(BITS_PER_BYTE)), initial);
47 }
48 
50 : _implementation(new byte_array(*to_copy._implementation)),
51  _number_of_bits(to_copy._number_of_bits)
52 {}
53 
54 bit_vector::~bit_vector() { WHACK(_implementation); }
55 
57 {
58  if (this == &to_copy) return *this;
59  *_implementation = *to_copy._implementation;
60  _number_of_bits = to_copy._number_of_bits;
61  return *this;
62 }
63 
64 bit_vector::operator const byte_array & () const { return *_implementation; }
65 
66 int bit_vector::bits() const { return _number_of_bits; }
67 
68 bool bit_vector::whole() const { return negative(find_first(0)); }
69 
70 bool bit_vector::empty() const { return negative(find_first(1)); }
71 
72 bool bit_vector::operator == (const bit_vector &that) const
73 { return compare(that, 0, _number_of_bits); }
74 
75 bool bit_vector::on(int position) const
76 { return get_bit(into_two_dim(position)); }
77 
78 bool bit_vector::off(int position) const { return !on(position); }
79 
80 void bit_vector::resize(int number_of_bits)
81 {
82 //printf("resize invoked, old size %d, new size %d...\n", bits(), number_of_bits);
83  if (negative(number_of_bits)) return;
84  if (bits() == number_of_bits) return;
85  int old_size = bits();
86  _number_of_bits = number_of_bits;
87  int number_of_bytes = number_of_packets(number_of_bits, int(BITS_PER_BYTE));
88  _implementation->resize(number_of_bytes);
89  // clear new space if the vector got larger.
90  if (old_size < number_of_bits) {
91  // lazy reset doesn't compute byte boundary, just does 8 bits.
92  for (int i = old_size; i < old_size + 8; i++) {
93  clear(i);
94 //printf("clearing bit %d.\n", i);
95  }
96  // clear the bytes remaining.
97  int old_bytes = number_of_packets(old_size + 8, int(BITS_PER_BYTE));
98  for (int j = old_bytes; j < number_of_bytes; j++) {
99 //printf("clearing bit %d through %d.\n", j * 8, j * 8 + 7);
100  _implementation->use(j) = 0;
101  }
102  }
103 }
104 
105 void bit_vector::reset(int number_of_bits)
106 {
107  resize(number_of_bits);
108  memset(_implementation->access(), 0, _implementation->length());
109 }
110 
111 bit_vector::two_dim_location bit_vector::into_two_dim(int position) const
112 {
113  two_dim_location to_return;
114  to_return.c_byte = position / BITS_PER_BYTE;
115  to_return.c_offset = position % BITS_PER_BYTE;
116  return to_return;
117 }
118 
119 bool bit_vector::get_bit(const two_dim_location &pos_in2) const
120 {
121  bounds_return(pos_in2.c_byte * BITS_PER_BYTE + pos_in2.c_offset, 0,
122  _number_of_bits - 1, false);
123  abyte test_mask = abyte(1 << pos_in2.c_offset);
124  return TEST(abyte(_implementation->get(pos_in2.c_byte)), test_mask);
125 }
126 
127 void bit_vector::set_bit(int position, bool value)
128 {
129  bounds_return(position, 0, bits() - 1, );
130  set_bit(into_two_dim(position), value);
131 }
132 
133 void bit_vector::set_bit(const two_dim_location &pos_in2, bool set_it)
134 {
135  abyte test_mask = abyte(1 << pos_in2.c_offset);
136  if (set_it) SET(_implementation->use(pos_in2.c_byte), test_mask);
137  else CLEAR((abyte &)_implementation->get(pos_in2.c_byte), test_mask);
138 }
139 
140 bool bit_vector::operator [](int position) const
141 {
142  bounds_return(position, 0, _number_of_bits - 1, false);
143  return get_bit(into_two_dim(position));
144 }
145 
146 void bit_vector::light(int position)
147 {
148  bounds_return(position, 0, _number_of_bits - 1, );
149  set_bit(into_two_dim(position), true);
150 }
151 
152 void bit_vector::clear(int position)
153 {
154  bounds_return(position, 0, _number_of_bits - 1, );
155  set_bit(into_two_dim(position), false);
156 }
157 
158 int bit_vector::find_first(bool to_find) const
159 {
160  const abyte whole_set = abyte(0xFF);
161  // search through the whole bytes first.
162  for (int full_byte = 0; full_byte < _implementation->length(); full_byte++) {
163  if ( (to_find && _implementation->get(full_byte))
164  || (!to_find && (_implementation->get(full_byte) != whole_set)) ) {
165  // the first appropriate byte is searched for the first appropriate bit.
166  for (int i = full_byte * BITS_PER_BYTE; i < minimum
167  (int(_number_of_bits), (full_byte+1)*BITS_PER_BYTE); i++) {
168  if (on(i) == to_find) return i;
169  }
170  return common::NOT_FOUND;
171  }
172  }
173  return common::NOT_FOUND;
174 }
175 
176 bool bit_vector::compare(const bit_vector &that, int start, int stop) const
177 {
178  for (int i = start; i <= stop; i++) {
179  if (on(i) != that.on(i)) return false;
180  }
181  return true;
182 }
183 
185 {
186  astring to_return;
187  int bits_on_line = 0;
188  const int estimated_elements_on_line = 64;
189  for (int i = 0; i < _number_of_bits; i++) {
190  // below prints out the bit number heading.
191  if (bits_on_line == 0) {
192  if (i != 0) to_return += "\n";
193  if (i < 10000) to_return += " ";
194  if (i < 1000) to_return += " ";
195  if (i < 100) to_return += " ";
196  if (i < 10) to_return += " ";
197  to_return += a_sprintf("%d", i);
198  to_return += " | ";
199  }
200  if (on(i)) to_return += "1";
201  else to_return += "0";
202  bits_on_line++;
203  if (bits_on_line >= estimated_elements_on_line) bits_on_line = 0;
204  else if ( !(bits_on_line % BITS_PER_BYTE) ) to_return += " ";
205  }
206  to_return += "\n";
207  return to_return;
208 }
209 
210 bit_vector bit_vector::subvector(int start, int end) const
211 {
212  bounds_return(start, 0, bits() - 1, bit_vector());
213  bounds_return(end, 0, bits() - 1, bit_vector());
214  int size = end - start + 1;
215  bit_vector to_return(size);
216  for (int i = start; i <= end; i++) to_return.set_bit(i - start, on(i));
217  return to_return;
218 }
219 
220 bool bit_vector::overwrite(int start, const bit_vector &to_write)
221 {
222  bounds_return(start, 0, bits() - 1, false);
223  int end = start + to_write.bits() - 1;
224  bounds_return(end, 0, bits() - 1, false);
225  for (int i = start; i <= end; i++) set_bit(i, to_write[i - start]);
226  return true;
227 }
228 
230 endian host_byte_order = LEFT_ENDIAN; // bytes within words.
231 endian host_bit_order = LEFT_ENDIAN; // bits within bytes.
232 
233 // probably the treatment for right endian in either case
234 // of bytes or bits is wrong.
235 
236 bool bit_vector::set(int start, int size, basis::un_int source)
237 {
238  bounds_return(start, 0, bits() - 1, false);
239  int end = start + size - 1;
240  bounds_return(end, 0, bits() - 1, false);
241  bounds_return(size, 1, 32, false);
242  bit_vector from_int(32, (abyte *)&source);
243 
244 // is this algorithm even remotely near the truth?
246  from_int._implementation->resize(size, byte_array::NEW_AT_BEGINNING);
247  else from_int.resize(size); // left endian machine.
248  overwrite(start, from_int);
249  return true;
250 }
251 
252 basis::un_int bit_vector::get(int start, int size) const
253 {
254  int end = start + size - 1;
255  bit_vector segment = subvector(start, end);
256  // padding to bytes.
257  int new_length = segment.bits();
258  if (new_length % 8) {
259  new_length = ( (new_length+8) / 8) * 8;
260  LOG(a_sprintf("new size is %d.", new_length));
261  }
262  segment.resize(new_length);
263 
264  if (host_bit_order == RIGHT_ENDIAN) {
265  bit_vector new_segment(segment.bits());
266  for (int i = 0; i < segment.bits(); i += 8)
267  for (int j = i; j < i + BITS_PER_BYTE; j++)
268  if (j < segment.bits())
269  new_segment.set_bit(i + (7 - (j - i)), segment[j]);
270  segment = new_segment; // copy the new form.
271  }
272 
273  LOG("new seg after bit copy:");
274  LOG(segment);
275 
276  basis::un_int to_return = 0;
277 
278  int bytes_used = number_of_packets(segment.bits(), int(BITS_PER_BYTE));
279  // 4 = # of bytes in a int.
280  for (int i = minimum(4, bytes_used) - 1; i >= 0; i--) {
281 #ifdef DEBUG_BIT_VECTOR
282  bit_vector tmp(8, &segment._implementation->get(i));
283  LOG(a_sprintf("%d: src bits %s", i, tmp.text_form().s()));
284 #endif
285 
286 #ifdef DEBUG_BIT_VECTOR
287  bit_vector tmp4(32, (abyte *)&to_return);
288  LOG(a_sprintf("%d: pre shift dest %s", i, tmp4.text_form().s()));
289 #endif
290  if (host_byte_order == LEFT_ENDIAN) to_return <<= 8;
291  else to_return >>= 8;
292 #ifdef DEBUG_BIT_VECTOR
293  bit_vector tmp5(32, (abyte *)&to_return);
294  LOG(a_sprintf("%d: post shift dest %s", i, tmp5.text_form().s()));
295 #endif
296 
297  basis::un_int mask = segment._implementation->get(i);
298  if (host_byte_order == RIGHT_ENDIAN) mask <<= 23;
299 #ifdef DEBUG_BIT_VECTOR
300  bit_vector tmp3(32, (abyte *)&to_return);
301  LOG(a_sprintf("%d: pre dest bits %s", i, tmp3.text_form().s()));
302 #endif
303  SET(to_return, mask);
304 #ifdef DEBUG_BIT_VECTOR
305  bit_vector tmp2(32, (abyte *)&to_return);
306  LOG(a_sprintf("%d: post dest bits %s", i, tmp2.text_form().s()));
307 #endif
308  }
309 
310 #ifdef DEBUG_BIT_VECTOR
311  bit_vector tmp(32, (abyte *)&to_return);
312  LOG(a_sprintf("final bits %s", tmp.text_form().s()));
313 #endif
314  return to_return;
315 }
316 
317 } //namespace.
#define LOG(s)
Definition: bit_vector.cpp:29
a_sprintf is a specialization of astring that provides printf style support.
Definition: astring.h:440
void reset(int number=0, const contents *initial_contents=NULL_POINTER)
Resizes this array and sets the contents from an array of contents.
Definition: array.h:349
const contents & get(int index) const
Accesses individual objects stored in "this" at the "index" position.
Definition: array.h:372
contents * access()
A non-constant access of the underlying C-array. BE REALLY CAREFUL.
Definition: array.h:175
outcome resize(int new_size, how_to_copy way=NEW_AT_END)
Changes the size of the C array to "new_size".
Definition: array.h:585
int length() const
Returns the current reported length of the allocated C array.
Definition: array.h:115
contents & use(int index)
A non-constant version of get(); the returned object can be modified.
Definition: array.h:365
Provides a dynamically resizable ASCII character string.
Definition: astring.h:35
const char * s() const
synonym for observe. the 's' stands for "string", if that helps.
Definition: astring.h:113
A very common template for a dynamic array of bytes.
Definition: byte_array.h:36
An array of bits with operations for manipulating and querying individual bits.
Definition: bit_vector.h:26
void clear(int position)
clears the value of the bit at "position".
Definition: bit_vector.cpp:152
bool set(int start, int size, basis::un_int source)
puts the "source" value into the vector at "start".
Definition: bit_vector.cpp:236
bool whole() const
returns true if entire vector is set.
Definition: bit_vector.cpp:68
bool on(int position) const
returns true if the bit at "position" is set.
Definition: bit_vector.cpp:75
int find_first(bool to_find) const
Seeks the first occurrence of "to_find".
Definition: bit_vector.cpp:158
basis::astring text_form() const
prints a nicely formatted list of bits to a string.
Definition: bit_vector.cpp:184
bool empty() const
returns true if entire vector is unset.
Definition: bit_vector.cpp:70
int bits() const
returns the number of bits in the vector.
Definition: bit_vector.cpp:66
bool operator==(const bit_vector &that) const
returns true if "this" is equal to "that".
Definition: bit_vector.cpp:72
void light(int position)
sets the value of the bit at "position".
Definition: bit_vector.cpp:146
basis::un_int get(int start, int size) const
gets a portion of the vector as an unsigned integer.
Definition: bit_vector.cpp:252
void reset(int size)
resizes the bit_vector and clears all bits in it.
Definition: bit_vector.cpp:105
bool compare(const bit_vector &that, int start, int stop) const
true if "this" is the same as "that" between "start" and "stop".
Definition: bit_vector.cpp:176
void set_bit(int position, bool value)
sets the bit at "position" to a particular "value".
Definition: bit_vector.cpp:127
bit_vector()
creates a zero length bit_vector.
Definition: bit_vector.cpp:36
bool off(int position) const
returns true if the bit at "position" is clear.
Definition: bit_vector.cpp:78
bit_vector & operator=(const bit_vector &to_copy)
Definition: bit_vector.cpp:56
bool operator[](int position) const
returns the value of the bit at the position specified.
Definition: bit_vector.cpp:140
bool overwrite(int start, const bit_vector &to_write)
Stores bits from "to_write" into "this" at "start".
Definition: bit_vector.cpp:220
bit_vector subvector(int start, int end) const
Extracts a chunk of the vector between "start" and "end".
Definition: bit_vector.cpp:210
void resize(int size)
Changes the size of the bit_vector to "size" bits.
Definition: bit_vector.cpp:80
Constants and objects used throughout HOOPLE.
#define BITS_PER_BYTE
A fundamental constant measuring the number of bits in a byte.
Definition: definitions.h:38
#define NULL_POINTER
The value representing a pointer to nothing.
Definition: definitions.h:32
#define bounds_return(value, low, high, to_return)
Verifies that "value" is between "low" and "high", inclusive.
Definition: guards.h:48
The guards collection helps in testing preconditions and reporting errors.
Definition: array.h:30
type number_of_packets(type message_size, type packet_size)
Reports number of packets needed given a total size and the packet size.
Definition: functions.h:137
void WHACK(contents *&ptr)
deletion with clearing of the pointer.
Definition: functions.h:121
unsigned char abyte
A fairly important unit which is seldom defined...
Definition: definitions.h:51
unsigned int un_int
Abbreviated name for unsigned integers.
Definition: definitions.h:62
type minimum(type a, type b)
maximum returns the greater of two values.
Definition: functions.h:29
bool negative(const type &a)
negative returns true if "a" is less than zero.
Definition: functions.h:43
A dynamic container class that holds any kind of object via pointers.
Definition: amorph.h:55
endian host_bit_order
Definition: bit_vector.cpp:231
endian host_byte_order
Definition: bit_vector.cpp:230
bool TEST(type to_test, type bits)
returns non-zero if the "bits" bit pattern is turned on in "to_test".
Definition: bit_vector.h:155
void SET(type &to_modify, type bits)
returns a number based on "to_modify" but with "bits" turned on.
Definition: bit_vector.h:147
void CLEAR(type &to_modify, type bits)
returns a number based on "to_modify" but with "bits" turned off.
Definition: bit_vector.h:151