bool_array Class Reference

#include <bool_array.h>

Detailed Description

Class to represent a packed boolean array.

This was first written in April 1995, before I knew of any existing implementation of this kind of classes. Of course, the C++ Standard Template Library now demands an implementation of packed boolean array as `vector<bool>', but the code here should still be useful for the following three reasons: (1) STL support of MSVC 6 did not implement this specialization (nor did it have a `bit_vector'); (2) I incorporated some useful member functions from the STL bitset into this `bool_array', including `reset', `set', `flip', and `count'; (3) In my tests under MSVC 6 and GCC 2.95.3/3.2.3 my code is really FASTER than vector<bool> or the normal boolean array.

Definition at line 67 of file bool_array.h.


Public Member Functions

bool at (unsigned long __idx) const
 bool_array (unsigned long __size)
 bool_array ()
unsigned long count (unsigned long __beg, unsigned long __end) const
unsigned long count () const
bool create (unsigned long __size)
void flip ()
void initialize (bool __value)
_Element operator[] (unsigned long __idx)
void reset (unsigned long __idx)
void set (unsigned long __idx)
unsigned long size () const
 ~bool_array ()

Private Attributes

BYTE * _M_byte_ptr
unsigned long _M_length

Static Private Attributes

static BYTE _S_bit_count [256]

Data Structures

class  _Element

Constructor & Destructor Documentation

bool_array::bool_array (  )  [inline]

Definition at line 83 of file bool_array.h.

00083 : _M_byte_ptr(NULL), _M_length(0) {}

bool_array::bool_array ( unsigned long  __size  )  [inline, explicit]

Constructs the packed boolean array with a specific size.

Parameters:
__size size of the array
Exceptions:
std::out_of_range if __size equals 0
std::bad_alloc if memory is insufficient

Definition at line 155 of file bool_array.h.

References create().

00156     : _M_byte_ptr(NULL), _M_length(0)
00157 {
00158     if (__size == 0)
00159         throw std::out_of_range("invalid bool_array size");
00160 
00161     if (!create(__size))
00162         throw std::bad_alloc();
00163 }

bool_array::~bool_array (  )  [inline]

Definition at line 85 of file bool_array.h.

References _M_byte_ptr.

00085 { if (_M_byte_ptr != NULL) free(_M_byte_ptr); }

Member Function Documentation

bool bool_array::at ( unsigned long  __idx  )  const [inline]

Reads the boolean value of an array element via an index.

Parameters:
__idx index of the array element to access
Returns:
the boolean value of the accessed array element
Exceptions:
std::out_of_range when the index is too big

Definition at line 184 of file bool_array.h.

References _M_byte_ptr, and _M_length.

00185 {
00186     size_t __byte_idx, __bit_idx;
00187     if (__idx >= _M_length)
00188         throw std::out_of_range("invalid bool_array subscript");
00189     __byte_idx = (size_t)(__idx / 8);
00190     __bit_idx  = (size_t)(__idx % 8);
00191     return *(_M_byte_ptr + __byte_idx) & (1 << __bit_idx) ? true : false;
00192 }

unsigned long bool_array::count ( unsigned long  __beg,
unsigned long  __end 
) const

Counts elements with a true value in a specified range.

Parameters:
__beg beginning of the range
__end end of the range (exclusive)
Returns:
the count of true elements

Definition at line 169 of file bool_array.cpp.

References _M_byte_ptr, _M_length, and _S_bit_count.

00170 {
00171     assert(_M_byte_ptr);
00172     unsigned long __true_cnt = 0;
00173     size_t __byte_idx_beg, __byte_idx_end;
00174     BYTE __byte_val;
00175 
00176     if (__beg >= __end)
00177         return 0;
00178     if (__end > _M_length)
00179         throw std::out_of_range("invalid bool_array subscript");
00180     --__end;
00181 
00182     __byte_idx_beg = (size_t)(__beg / 8);
00183     __byte_val = _M_byte_ptr[__byte_idx_beg];
00184     __byte_val &= ~0 << (__beg % 8);
00185 
00186     __byte_idx_end = (size_t)(__end / 8);
00187     if (__byte_idx_beg < __byte_idx_end)
00188     {
00189         __true_cnt = _S_bit_count[__byte_val];
00190         __byte_val = _M_byte_ptr[__byte_idx_end];
00191     }
00192     __byte_val &= ~(~0 << (__end % 8 + 1));
00193     __true_cnt += _S_bit_count[__byte_val];
00194 
00195     for (++__byte_idx_beg; __byte_idx_beg < __byte_idx_end; ++__byte_idx_beg)
00196         __true_cnt += _S_bit_count[_M_byte_ptr[__byte_idx_beg]];
00197     return __true_cnt;
00198 }

unsigned long bool_array::count (  )  const

Counts elements with a true value.

Returns:
the count of true elements

Definition at line 152 of file bool_array.cpp.

References _M_byte_ptr, _M_length, and _S_bit_count.

00153 {
00154     assert(_M_byte_ptr);
00155     unsigned long __true_cnt = 0;
00156     size_t __byte_cnt = (size_t)((_M_length - 1) / 8) + 1;
00157     for (size_t __i = 0; __i < __byte_cnt; ++__i)
00158         __true_cnt += _S_bit_count[_M_byte_ptr[__i]];
00159     return __true_cnt;
00160 }

bool bool_array::create ( unsigned long  __size  ) 

Creates the packed boolean array with a specific size.

Parameters:
__size size of the array
Returns:
false if __size equals 0 or is too big, or if memory is insufficient; true if __size has a suitable value and memory allocation is successful.

Definition at line 108 of file bool_array.cpp.

References _M_byte_ptr, and _M_length.

Referenced by bool_array().

00109 {
00110     if (__size == 0)
00111         return false;
00112     // Will be optimized away by a decent compiler if ULONG_MAX == UINT_MAX
00113     if (ULONG_MAX > UINT_MAX && ((__size - 1) / 8 + 1) > UINT_MAX)
00114         return false;
00115 
00116     size_t __byte_cnt = (size_t)((__size - 1) / 8 + 1);
00117     if (_M_byte_ptr)
00118         free(_M_byte_ptr);
00119     _M_length = 0;
00120 
00121     // Uses malloc/free instead of new/delete to avoid exception handling
00122     // differences between compilers
00123     if (!(_M_byte_ptr = (BYTE*)malloc(__byte_cnt)))
00124         return false;
00125 
00126     _M_length = __size;
00127     return true;
00128 }

void bool_array::flip (  ) 

Changes all true elements to false, and false ones to true.

Definition at line 203 of file bool_array.cpp.

References _M_byte_ptr, and _M_length.

00204 {
00205     assert(_M_byte_ptr);
00206     size_t __byte_cnt = (size_t)((_M_length - 1) / 8) + 1;
00207     for (size_t __i = 0; __i < __byte_cnt; ++__i)
00208         _M_byte_ptr[__i] = ~_M_byte_ptr[__i];
00209     int __valid_bits_in_last_byte = (_M_length - 1) % 8 + 1;
00210     _M_byte_ptr[__byte_cnt - 1] &= ~(~0 << __valid_bits_in_last_byte);
00211 }

void bool_array::initialize ( bool  __value  ) 

Initializes all array elements to a specific value optimally.

Parameters:
__value the boolean value to assign to all elements

Definition at line 135 of file bool_array.cpp.

References _M_byte_ptr, and _M_length.

00136 {
00137     assert(_M_byte_ptr);
00138     size_t __byte_cnt = (size_t)((_M_length - 1) / 8) + 1;
00139     memset(_M_byte_ptr, __value ? ~0 : 0, __byte_cnt);
00140     if (__value)
00141     {
00142         int __valid_bits_in_last_byte = (_M_length - 1) % 8 + 1;
00143         _M_byte_ptr[__byte_cnt - 1] &= ~(~0 << __valid_bits_in_last_byte);
00144     }
00145 }

bool_array::_Element bool_array::operator[] ( unsigned long  __idx  )  [inline]

Creates a reference to an array element.

Parameters:
__idx index of the array element to access

Definition at line 170 of file bool_array.h.

References _M_byte_ptr, and _M_length.

00171 {
00172     assert(_M_byte_ptr);
00173     assert(__idx < _M_length);
00174     return _Element(_M_byte_ptr, __idx);
00175 }

void bool_array::reset ( unsigned long  __idx  )  [inline]

Resets an array element to false via an index.

Parameters:
__idx index of the array element to access
Exceptions:
std::out_of_range when the index is too big

Definition at line 200 of file bool_array.h.

References _M_byte_ptr, and _M_length.

00201 {
00202     size_t __byte_idx, __bit_idx;
00203     if (__idx >= _M_length)
00204         throw std::out_of_range("invalid bool_array subscript");
00205     __byte_idx = (size_t)(__idx / 8);
00206     __bit_idx  = (size_t)(__idx % 8);
00207     *(_M_byte_ptr + __byte_idx) &= ~(1 << __bit_idx);
00208 }

void bool_array::set ( unsigned long  __idx  )  [inline]

Sets an array element to true via an index.

Parameters:
__idx index of the array element to access
Exceptions:
std::out_of_range when the index is too big

Definition at line 216 of file bool_array.h.

References _M_byte_ptr, and _M_length.

00217 {
00218     size_t __byte_idx, __bit_idx;
00219     if (__idx >= _M_length)
00220         throw std::out_of_range("invalid bool_array subscript");
00221     __byte_idx = (size_t)(__idx / 8);
00222     __bit_idx  = (size_t)(__idx % 8);
00223     *(_M_byte_ptr + __byte_idx) |= 1 << __bit_idx;
00224 }

unsigned long bool_array::size (  )  const [inline]

Definition at line 96 of file bool_array.h.

References _M_length.

00096 { return _M_length; }

Field Documentation

BYTE* bool_array::_M_byte_ptr [private]

Definition at line 102 of file bool_array.h.

Referenced by at(), count(), create(), flip(), initialize(), operator[](), reset(), set(), and ~bool_array().

unsigned long bool_array::_M_length [private]

Definition at line 103 of file bool_array.h.

Referenced by at(), count(), create(), flip(), initialize(), operator[](), reset(), set(), and size().

BYTE bool_array::_S_bit_count [static, private]

Definition at line 104 of file bool_array.h.

Referenced by count().

The documentation for this class was generated from the following files:
Generated on Wed May 5 00:06:40 2010 for Sumo - Simulation of Urban MObility by  doxygen 1.5.6