// -*- c++ -*-
/// @file BitVector.h
/*
* Copyright © 2001 Marko Mäkelä <msmakela@tcs.hut.fi>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#ifndef BITVECTOR_H_
# define BITVECTOR_H_
# ifdef __GNUC__
# pragma interface
# endif // __GNUC__
# include <limits.h>
# include <string.h>
/** Binary digit (bit) vector */
class BitVector
{
public:
/** machine word */
typedef unsigned long word_t;
/** Constructor
* @param size number of elements in the vector
*/
explicit BitVector (unsigned size = 0) :
m_size (0), m_allocated (1), m_bits (new word_t[1]) {
*m_bits = 0;
setSize (size);
}
/** Copy constructor */
explicit BitVector (const class BitVector& old) :
m_size (old.m_size), m_allocated (old.m_allocated), m_bits (0) {
memcpy (m_bits = new word_t[m_allocated], old.m_bits,
m_allocated * sizeof (word_t));
}
private:
/** Assignment operator */
class BitVector& operator= (const class BitVector& old);
public:
/** Destructor */
~BitVector () { delete[] m_bits; }
/** Equality comparison
* @param other other bit vector to compare this against
* @return true if the bit vectors are identical,
* treating missing bits as unset
*/
bool operator== (const class BitVector& other) const {
unsigned tsize = getNumWords (m_size), osize = getNumWords (other.m_size);
if (tsize < osize) {
if (memcmp (m_bits, other.m_bits, tsize * sizeof (word_t)))
return false;
for (register const word_t* bits = other.m_bits + osize;
bits-- > other.m_bits + tsize; )
if (*bits)
return false;
}
else {
if (memcmp (m_bits, other.m_bits, osize * sizeof (word_t)))
return false;
for (register const word_t* bits = m_bits + tsize;
bits-- > m_bits + osize; )
if (*bits)
return false;
}
return true;
}
/** Determine the number of words the specified amount of bits occupy */
static unsigned getNumWords (unsigned bits) {
const unsigned bitsPerWord = CHAR_BIT * sizeof (word_t);
return (bits + bitsPerWord - 1) / bitsPerWord;
}
/** Set the size of the vector
* @param size the new size of the vector
*/
void setSize (unsigned size) {
const unsigned numWords = getNumWords (size);
if (m_allocated < numWords) {
while (m_allocated < numWords)
m_allocated <<= 1;
word_t* bits = new word_t[m_allocated];
const unsigned init = getNumWords (m_size);
memcpy (bits, m_bits, init * sizeof *m_bits);
memset (bits + init, 0, (m_allocated - init) * sizeof *m_bits);
delete[] m_bits;
m_bits = bits;
}
m_size = size;
}
/** Determine the size of the vector
* @return the size of the vector
*/
unsigned getSize () const { return m_size; }
/** Read a binary digit
* @param i zero-based index of the element
* @return value of the ternary digit
*/
bool operator[] (unsigned i) const {
return i < m_size &&
m_bits[i / (CHAR_BIT * sizeof (word_t))] &
(word_t (1) << (i % (CHAR_BIT * sizeof (word_t))));
}
/** Set a binary digit
* @param i zero-based index of the element
*/
void assign_true (unsigned i) {
if (i >= m_size)
setSize (i + 1);
m_bits[i / (CHAR_BIT * sizeof (word_t))] |=
word_t (1) << (i % (CHAR_BIT * sizeof (word_t)));
}
/** Clear a binary digit
* @param i zero-based index of the element
*/
void assign_false (unsigned i) {
m_bits[i / (CHAR_BIT * sizeof (word_t))] &=
~(word_t (1) << (i % (CHAR_BIT * sizeof (word_t))));
}
/** Determine whether the whole vector is filled with zero bits
* @return 0 if all bits in the vector are clear;
* index of a nonzero entry + 1 otherwise
*/
unsigned nonzero () const {
if (!m_size)
return 0;
return findNext (0);
}
/** Find the next index at which there is a set bit
* @param i the starting index (counting forward)
* @return 0 if all following bits in the vector are clear;
* index of the next nonzero entry + 1 otherwise
*/
unsigned findNext (unsigned i) const {
if (i >= m_size)
return 0;
register const word_t* w = &m_bits[i / (CHAR_BIT * sizeof (word_t))];
register word_t bit = 1 << (i % (CHAR_BIT * sizeof (word_t)));
if (*w >= bit) {
// found in the same word
do
if (*w & bit)
return i + 1;
while (i++, bit <<= 1);
}
const word_t* const w_end = m_bits + getNumWords (m_size);
// search in the remaining words
while (++w < w_end) {
if (!*w) continue;
for (i = 1, bit = 1; !(*w & bit); bit <<= 1, i++);
return i + (w - m_bits) * CHAR_BIT * sizeof (word_t);
}
return 0;
}
private:
/** Number of elements in the vector */
unsigned m_size;
/** Size of the allocated vector in words */
unsigned m_allocated;
/** The vector */
word_t* m_bits;
};
#endif // BITVECTOR_H_