bitVector.h

Go to the documentation of this file.

/************************************************************************
* CVS version control block - do not edit manually
*  $RCSfile: bitVector.h,v $
*  $Revision: 1.1 $
*  $Date: 2003/09/05 04:20:11 $
*  $Source: /usr/sci/projects/chimera/cvsroot/arbeit/gutz/mathGutz/bitVector.h,v $
*************************************************************************
* Aaron Lefohn
* Userid:       lefohn
* Email:        lefohn@sci.utah.edu
**************************************************************************
* gutz::BitVector - An arbitrary length bit vector class
*                                 - This class _owns_ its data
*                                 - TODO: Implement shift operators
*************************************************************************/

#ifndef __BITVEC_H__
#define __BITVEC_H__

#include <assert.h>
#include <math.h>
#include <vector>
#include <string>
#include <iostream>

#include <mathGutz.h>   // Gutz Files   
#include <arrayGutz.h>

namespace gutz {

#ifdef WIN32
        #ifdef _DEBUG
                // Disable the warning about template-explosion names being 
                // longer than 255 chars...we really don't care.
                #pragma warning(disable : 4786)
        #endif
#endif

// Typedefs
class BitVector;
typedef std::vector<BitVector>  VecBitVec;
typedef std::vector<BitVector*> VecBitVecP;
typedef std::vector<VecBitVec>  VecVecBitVec;

extern const uint g_BITS_PER_WORD;
extern const uint g_POW_OF_2_BITS_PER_WORD;

inline uint bitNum2wordNum(const uint bitNum);
inline uint bitMask(const uint bitNum);
inline uint bits2Words(const uint numBits);
inline uint fillWord(const bool initVal);
inline uint getBinary(const uint word, const uint bitNum);

class BitRef;//Forward Decl

class BitVector
{
public:
  //Constructors
  BitVector(const int numBits=0);                   // Create uninitialized BitVec of 'size' 
  BitVector(const int numBits, const bool initVal); // Create BitVec of 'size', with all elts init'd to 'initVal' 
  BitVector(const std::string& bitstring);                          // Create BitVec from a 0/1 character string 
  BitVector( uint word );                                                       // Create BitVec from single word
  BitVector(const arrayw1ui& data );                            // Create BitVec from array of unsigned ints
  BitVector(const arrayw1ub& data );                            // Create BitVec from array of unsigned bytes
  BitVector(const BitVector& rhs);
  ~BitVector();
  
  //Pointer to the internal data. 
  // - Despite the danger, these must exist for efficient use when a low-level
  //   API is writing the bit vector and copying into a new BitVector is prohibitive.
  // - MAKE SURE the sizes all match up!!
  ubyte* dataub() const {return (ubyte*)(m_vec.data());}
  uint*  dataui() const {return (uint*)(m_vec.data());}

  const uint            size() const {return m_numBits;}       // Return length of bit vector 
  const uint            numWords() const {return m_vec.size();}
  inline BitRef         operator[] (const int i);           // Return ref to ith element of bit vector 
  inline const bool operator[] (const int i) const; // Return 'true' if ith elt is 1, 'false' if 0
  BitVector&            operator= (const BitVector& value);    // Copy a bit vector
  BitVector&            operator= (const uint valWord);            // Fill bitvector with word-sized value
  BitVector&            operator= (const bool value);          // Fill a bit_vector with value 

  std::vector<uint> trueBits() const; // Return a vector of bitIndices for all true bits in the bitVector
  void                          trueBits( arrayw1ui& trueIndices ) const;//Non-memory-allocating version of 'trueBits() const'
  uint                          numTrueBits() const;  // Returns number of true bits in vector
  
  //For all ops that need 2 BitVectors as args, both vecs MUST be same length. Assertion failure if not same size.
  friend BitVector operator~ (const BitVector&);                  // Boolean NOT on a bit vector 
  friend BitVector operator& (const BitVector&, const BitVector&);// Boolean AND operation on two bit vectors 
  friend BitVector operator| (const BitVector&, const BitVector&);// Boolean OR operation on two bit vectors 
  friend BitVector operator^ (const BitVector&, const BitVector&);// Boolean XOR operation on two bit vectors 
  friend BitVector operator- (const BitVector&, const BitVector&);// Difference set on two bit vectors 

  BitVector& not ();                                       // Boolean NOT on a bit vector in-place 
  BitVector& operator&= (const BitVector&);                // Boolean AND operation on two bit vectors in-place 
  BitVector& operator|= (const BitVector&);                // Boolean OR operation on two bit vectors in-place 
  BitVector& operator^= (const BitVector&);                // Boolean XOR operation on two bit vectors in-place 
  BitVector& operator-= (const BitVector&);                // Difference set on two bit vectors in-place 

  bool operator== (const bool u);                          // Do all elts in bitVec have value 'u'?
  bool operator!= (const bool u);                          // Check if no bit of vector has the value u 
  bool operator== (const BitVector& bv);                   // Compare two bit vectors for EQUALITY 
  bool operator!= (const BitVector& bv);                   // Compare two bit vectors for INEQUALITY 

  friend std::ostream &operator<<(std::ostream &, const BitVector& bv);
  
  /*bool operator< (const BitVector& bv);                  // Compare two bit vectors for LESS THAN (unsigned) 
  bool operator> (const BitVector& bv);                    // Compare two bit vectors for GREATER THAN (unsigned) 
  bool operator<= (const BitVector& bv);                   // Compare two bit vectors for LESS OR EQUAL (unsigned) 
  bool operator>= (const BitVector&bv);                    // Compare two bit vectors for GREATER OR EQUAL (unsigned) 
  */

private:
  arrayo1ui m_vec;
  uint          m_numBits;
  
  const bool getBoolVal(const uint bitNum) const; // Return true if 'bitNum' is 1, false otherwise.  
};

// Allows reference to a particular bit in a bit vector
// NOTE: This is meant to be an accessory class to BitVector
//       and should not need to be used
class BitRef
{
public:
  BitRef( uint* data, uint bit);// Constructor 
  BitRef( const BitRef& rhs);  // Copy Constructor

  BitRef& operator=(const BitRef& rhs);//Assignment operator
  bool    operator=(const bool u);     // Set value 
  bool    operator() () const;         // Test whether bit is TRUE or FALSE 

  friend std::ostream &operator<<(std::ostream &, const BitRef& bv);
  /*void operator&= (const bool u);// Perform boolean AND operation in-place 
  void operator|= (const bool u);  // Perform boolean OR operation in-place 
  void operator^= (const bool u);  // Perform boolean XOR operation in-place 
  */
private:
  uint* m_wordPtr;// Ptr to a uint word that holds the bit of interest
  uint  m_mask;   // Mask for the bit represented by this instance
};


// Return a reference to the bitNum'th elt of bit vector 
inline BitRef BitVector::operator[] (const int bitNum) {
  assert( (uint)bitNum < m_numBits );
        return BitRef( &m_vec[bitNum2wordNum(bitNum)], bitNum );
}

// Return 'true' if bitNum'th elt is 1, 'false' if 0 
inline const bool BitVector::operator[] (const int bitNum) const { 
  assert( (uint)bitNum < m_numBits );
  return getBoolVal(bitNum);
}

// Return true if 'bitNum' is 1, false otherwise.
// 'bitNum' is bit index in bitVector
inline const bool BitVector::getBoolVal(const uint bitNum) const {
  uint wordNum = bitNum2wordNum(bitNum);// In which array elt is the i'th bit?
  uint mask    = bitMask(bitNum);       // Create mask to get the i'th bit
  uint result  = m_vec[wordNum] & mask;
  return (result > 0);
}

// Given an array of uint words, in which array elt is the bit 'bitNum'.
inline uint bitNum2wordNum(const uint bitNum) {
  return (bitNum >> g_POW_OF_2_BITS_PER_WORD);
}

// Return a uint word mask for the (bitNum % sizeof(uint))'th bit.
inline uint bitMask(const uint bitNum) {
  uint bit = modPowOf2( bitNum, g_POW_OF_2_BITS_PER_WORD );
  return 1 << (g_BITS_PER_WORD - bit - 1);
}

// Returns the number of uint words necessary to represent 'numBits'
inline uint bits2Words(const uint numBits) {
  return uint( ceil(numBits/(float)g_BITS_PER_WORD) );
}

// Returns a uint word of either all 1's or 0's depending on 'initVal'
inline uint fillWord(const bool initVal) {
  return initVal ? UINT_MAX : 0;
}

//Return the value of the 'bitNum'th bit in 'word' (0 or 1)
inline uint getBinary(const uint word, const uint bitNum) {
  return (uint)((word & (1<<bitNum)) >> bitNum);
}

} // End of namespace gutz

#endif

---

Send questions, comments, and bug reports to: