KKB::BitString Class Reference

Allows you to manage very long bit strings. More...

#include <BitString.h>

Inheritance diagram for KKB::BitString:

Public Member Functions
	BitString ()
	Instantiates a empty bit-string of length 0; needed for ReadXML. More...
	BitString (kkuint32 _bitLen)
	Construct a bit string of length _binLen with all bits set to '0'. More...
	BitString (const BitString &b)
	Copy constructor. More...
	BitString (kkuint32 _bitLen, kkuint16 *_bitNums, kkuint32 _bitNumsLen)
	Construct a BitString of length _bitLen with bits indicated by '_bitNums' set to '1'. More...
	~BitString ()
kkuint32	BitLen () const
	Returns the length of the bit-string. More...
const char *	ClassName () const
kkuint32	Count () const
	Returns number of bits set to '1'. More...
virtual BitString *	Duplicate () const
KKStr	HexStr () const
	Returns a Hex-String representation. More...
void	ListOfSetBits16 (VectorUint16 &setBits) const
void	ListOfSetBits32 (VectorUint32 &setBits) const
bool	operator!= (const BitString &right) const
BitString &	operator&= (const BitString &right)
	Performs a bitwise AND against the left operand. More...
BitString &	operator*= (const BitString &right)
	Performs a bitwise AND against the left operand. More...
BitString &	operator+= (const BitString &right)
	Performs a bitwise OR against the left operand. More...
bool	operator< (const BitString &right) const
bool	operator<= (const BitString &right) const
BitString &	operator= (const BitString &right)
bool	operator== (const BitString &right) const
bool	operator> (const BitString &right) const
bool	operator>= (const BitString &right) const
BitString	operator^ (const BitString &right)
	Performs a bitwise XOR between two operands returning a new BitString. More...
BitString &	operator^= (const BitString &right)
	Performs a bitwise XOR against the left operand. More...
BitString &	operator|= (const BitString &right)
	Performs a bitwise OR against the left operand. More...
void	PopulateVectorBool (VectorBool &boolVector) const
	Populates a boolean vector where each element reflects whether the corresponding bit is set. More...
virtual void	ReadXML (XmlStream &s, XmlTagConstPtr tag, VolConstBool &cancelFlag, RunLog &log)
void	ReSet ()
	Set all bits to '0'. More...
void	ReSet (kkuint32 bitNum)
	Set the bit indicated by 'bitNum' to '0'. More...
void	Set ()
	Set all bits to '1'. More...
void	Set (kkuint32 bitNum)
	Set the bit indicated by 'bitNum' to '1'. More...
bool	Test (kkuint32 bitNum) const
virtual void	WriteXML (const KKStr &varName, std::ostream &o) const
Public Member Functions inherited from KKB::Atom
	Atom ()
virtual	~Atom ()

Static Public Member Functions
static BitString	FromHexStr (const KKStr &hexStr, bool &validHexStr)
	Create a bit-string from a Hex String. More...

Additional Inherited Members
Public Types inherited from KKB::Atom
typedef AtomPtr(*	AtomCreator) (XmlStream &i)
typedef Atom *	AtomPtr

Detailed Description

Allows you to manage very long bit strings.

Author

Kurt Kramer

Useful when you need to deal with very large yes/no decisions. For example performing Feature Selection on a DNA dataset where you can have 50,000+ features. You need to keep a list of which feature combinations have been tried. You can use a BitString to do this where a particular bit indicates a particular feature. In the feature selection case you may want to track several thousand feature combinations. If you did this using arrays you would require very large amount of memory to accomplish this. With BitString's the memory requirement is reduced to 1/8'the allowing for more efficient use of memory.

This class will manage Bit-Strings up to UINT_MAX in length. Logical operations such as bitwise AND, OR, and NOT are supported plus others. An example of where this class is used is in KKMLL::FeatureNumList.

Definition at line 31 of file BitString.h.

Constructor & Destructor Documentation

BitString::BitString

(

)

Instantiates a empty bit-string of length 0; needed for ReadXML.

Definition at line 58 of file BitString.cpp.

                     :
  bitLen  (0),
  byteLen (0)
{
  byteLen = ((bitLen - 1) / 8) + 1;
  str = NULL;
}

BitString::BitString

(

kkuint32

_bitLen

)

Construct a bit string of length _binLen with all bits set to '0'.

Parameters

[in]

_bitLen

Length of bit string to allocate.

Definition at line 68 of file BitString.cpp.

Referenced by FromHexStr(), and KKMLL::FeatureNumList::ToHexString().

                                      :
  bitLen  (_bitLen),
  byteLen (0)
{
  byteLen = ((bitLen - 1) / 8) + 1;
  str = new uchar[byteLen];
  memset (str, 0, byteLen);
}

BitString::BitString

(

const BitString &

b

)

Copy constructor.

Definition at line 78 of file BitString.cpp.

Referenced by Duplicate().

                                         :
  bitLen  (bs.bitLen),
  byteLen (bs.byteLen),
  str     (NULL)
{
  uchar*   str;
  str = new uchar[byteLen];
  memcpy (str, bs.str, byteLen);
}

BitString::BitString	(	kkuint32	_bitLen,
		kkuint16 *	_bitNums,
		kkuint32	_bitNumsLen
	)

Construct a BitString of length _bitLen with bits indicated by '_bitNums' set to '1'.

Parameters

[in]	_binLen	Length of bit string.
[in]	_bitNums	List if bit positions to set to '1'.
[in]	_bitNumsLen	Size of '_bitNums' array.

Definition at line 89 of file BitString.cpp.

References KKB::KKStr::Concat(), KKB::KKException::KKException(), KKB::KKStr::KKStr(), and Set().

                      :
    bitLen  (_bitLen),
    byteLen (0),
    str     (NULL)
{
  byteLen = ((bitLen - 1) / 8) + 1;
  str = new uchar[byteLen];
  memset (str, 0, byteLen);
  kkuint32  x;
  for  (x = 0;  x < bitNumsLen;  x++)
  {
    if  (bitNums[x] >= bitLen)
    {
      KKStr  msg (128);
      msg << "BitString   Constructing from list of numbers:  bitNums[" << x << "] = [" << bitNums[x] << "] which is >= bitLen[" << bitLen << "].";
      cerr << std::endl << std::endl << "BitString   ***ERROR***  " << msg << std::endl << std::endl;
      throw KKException (msg);
    }
    Set (bitNums[x]);
  }
}

BitString::~BitString

(

)

Definition at line 116 of file BitString.cpp.

{
  delete  str;
  str = NULL;
}

Member Function Documentation

kkuint32 KKB::BitString::BitLen ( ) const

inline

Returns the length of the bit-string.

Definition at line 64 of file BitString.h.

Referenced by KKMLL::FeatureNumList::FeatureNumList().

{return bitLen;}

const char* KKB::BitString::ClassName ( ) const

inlinevirtual

Implements KKB::Atom.

Definition at line 66 of file BitString.h.

{return "BitString";}

kkuint32 BitString::Count

(

)

const

Returns number of bits set to '1'.

summary> Returns true if bit indicated by bitNum is set to 1.

Definition at line 142 of file BitString.cpp.

{
  BuildBitCounts ();

  kkuint32  count = 0;
  kkuint32  byteOffset = 0;

  for  (byteOffset = 0;  byteOffset < byteLen;  byteOffset++)
    count += bitCounts[str[byteOffset]];

  return  count;
}  /* Count */

BitString * BitString::Duplicate ( ) const

virtual

Implements KKB::Atom.

Definition at line 124 of file BitString.cpp.

References BitString().

{
  return new BitString (*this);
}

BitString BitString::FromHexStr ( const KKStr &  hexStr, bool &  validHexStr  )

static

Create a bit-string from a Hex String.

Will convert the Hex String stored in the parameter 'hexStr' and create a bit string from it.
ex: "A189" will be converted into "1010000110001001"

Parameters

[in]	hexStr	String containing hex characters '0' - '9', 'A' - 'F'
[out]	validHexStr	returns 'TRUE' if no invalid characters.

Returns

BitString with the appropriate bits set to represent the hex number in 'hexStr'.

Definition at line 399 of file BitString.cpp.

References BitString(), KKB::KKStr::Len(), and KKB::KKStr::operator[]().

{
  BitString  bs (hexStr.Len () * 4);
  kkint32  byteNum = 0;
  kkint32  hexStrLen = hexStr.Len ();
  kkint32  high4Bits = 0;
  kkint32  low4Bits  = 0;
  kkint32  x = 0;

  validHexStr = true;

  while  (x < hexStrLen)
  {
    low4Bits = HexCharToInt (hexStr[x]);
    x++;
    if  (low4Bits < 0)
      validHexStr = false;

    if  (x < hexStrLen)
    {
      high4Bits = HexCharToInt (hexStr[x]);
      x++;
      if  (high4Bits < 0)
        validHexStr = false;
    }
    else
    {
      high4Bits = 0;
    }

    bs.str[byteNum] = (uchar)low4Bits + (uchar)high4Bits * 16;
    byteNum++;
  }

  return  bs;
} /* FromHexStr */

KKStr BitString::HexStr

(

)

const

Returns a Hex-String representation.

ex: "1110 0000 0101 1011" would return "E09B".

Definition at line 361 of file BitString.cpp.

References KKB::KKStr::Append(), KKB::KKStr::Concat(), and KKB::KKStr::KKStr().

Referenced by KKMLL::FeatureNumList::ToHexString(), and WriteXML().

{
  KKStr  hexStr (byteLen * 2);  // There will be 2 hex characters for every byte in bit string

  static char  hexChars[] = {'0', '1', '2', '3', '4', '5', '6', '7','8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};

  kkuint32  byteOffset = 0;
  kkint32   high4Bits;
  kkint32   low4Bits;

  for  (byteOffset = 0;  byteOffset < byteLen;  byteOffset++)
  {
    high4Bits = str[byteOffset] / 16;
    low4Bits  = str[byteOffset] % 16;

    hexStr.Append (hexChars[low4Bits]);
    hexStr.Append (hexChars[high4Bits]);
  }

  return hexStr;
}  /* HexStr */

void BitString::ListOfSetBits16

(

VectorUint16 &

setBits

)

const

summary> Get Bit positions that are set to "1". The parameter setBits will be populated with the list of bits that are set to "1" for bit strings that are up to 2^32-1 bits long. /summary> example> ex: Bit String "001200110011" will produce a vector <2, 3, 6, 7, 10, 11> /example> param in="setBits"> Will be populated with all bits that are set to "1", will be cleared first.

Definition at line 266 of file BitString.cpp.

References KKB::KKStr::Concat(), KKB::KKException::KKException(), and KKB::KKStr::KKStr().

Referenced by KKMLL::FeatureNumList::FeatureNumList().

{
  if  (bitLen > 65535)
  {
    KKStr  msg (50);
    msg << "BitString::ListOfSetBits  BitLen[" << bitLen << "] of this instance of BitString exceeds capacity of 'VectorUint16'.";
    cerr << std::endl << "BitString::ListOfSetBits   ***ERROR***   " << msg << std::endl << std::endl;
    throw KKException (msg);
  }

  setBits.clear ();

  kkuint32  byteOffset = 0;
  kkuint32  numOfBits  = 0;
  kkuint32  bitNum     = 0;

  for  (byteOffset = 0;  byteOffset < byteLen;  byteOffset++)
  {
    uchar  br = str[byteOffset];
    if  (br == 0)
    {
      bitNum = bitNum + 8;
      continue;
    }
    else
    {
      if  (byteOffset < (byteLen - 1))
        numOfBits = 8;
      else
      {
        numOfBits = bitLen % 8;
        if  (numOfBits == 0)
          numOfBits = 8;
      }

      kkuint32 x;
      for  (x = 0;  x < numOfBits;  x++)
      {
        if  ((br % 2) == 1)
        {
          setBits.push_back ((kkuint16)bitNum);
        }

        br = br / 2;
        bitNum++;
      }
    }
  }
}  /* ListOfSetBits16 */

void BitString::ListOfSetBits32

(

VectorUint32 &

setBits

)

const

Definition at line 317 of file BitString.cpp.

{
  setBits.clear ();

  kkuint32  byteOffset = 0;
  kkuint32  numOfBits  = 0;
  kkuint32  bitNum     = 0;

  for  (byteOffset = 0;  byteOffset < byteLen;  byteOffset++)
  {
    uchar  br = str[byteOffset];
    if  (br == 0)
    {
      bitNum = bitNum + 8;
      continue;
    }
    else
    {
      if  (byteOffset < (byteLen - 1))
        numOfBits = 8;
      else
      {
        numOfBits = bitLen % 8;
        if  (numOfBits == 0)
          numOfBits = 8;
      }

      kkuint32 x;
      for  (x = 0;  x < numOfBits;  x++)
      {
        if  ((br % 2) == 1)
        {
          setBits.push_back (bitNum);
        }

        br = br / 2;
        bitNum++;
      }
    }
  }
}  /* ListOfSetBits32 */

bool BitString::operator!=

(

const BitString &

right

)

const

Definition at line 552 of file BitString.cpp.

{
  return (Compare (right) != 0);
}  /* operator!= */

BitString & BitString::operator&=

(

const BitString &

right

)

Performs a bitwise AND against the left operand.

Definition at line 484 of file BitString.cpp.

Referenced by operator*=().

{
  kkuint32 shortestByteLen = Min (byteLen, right.byteLen);

  kkuint32  x;

  for  (x = 0;  x < shortestByteLen;  x++)
  {
    str[x] = str[x] & right.str[x];
  }
  for  (x = shortestByteLen;  x < byteLen;  ++x)
  {
    str[x] = 0;
  }

  return  *this;
} /* operator&= */

BitString & BitString::operator*=

(

const BitString &

right

)

Performs a bitwise AND against the left operand.

Definition at line 504 of file BitString.cpp.

References operator&=().

{
  operator&= (right);
  return  *this;
} /* operator*= */

BitString & BitString::operator+=

(

const BitString &

right

)

Performs a bitwise OR against the left operand.

Definition at line 475 of file BitString.cpp.

References operator|=().

{
  operator|= (right);
  return  *this;
} /* operator+= */

bool BitString::operator<

(

const BitString &

right

)

const

Definition at line 573 of file BitString.cpp.

{
  return (Compare (right) < 0);
}  /* operator< */

bool KKB::BitString::operator<=

(

const BitString &

right

)

const

BitString & BitString::operator=

(

const BitString &

right

)

Definition at line 441 of file BitString.cpp.

{
  delete  str;
  
  bitLen  = right.bitLen;
  byteLen = right.byteLen;
  str = new uchar[byteLen];

  kkuint32  x;
  for  (x = 0;  x < byteLen;  x++)
    str[x] = right.str[x];

  return  *this;
}  /* operator= */

bool BitString::operator==

(

const BitString &

right

)

const

Definition at line 545 of file BitString.cpp.

{
  return (Compare (right) == 0);
}  /* operator== */

bool BitString::operator>

(

const BitString &

right

)

const

Definition at line 559 of file BitString.cpp.

{
  return (Compare (right) > 0);
}  /* operator> */

bool BitString::operator>=

(

const BitString &

right

)

const

Definition at line 566 of file BitString.cpp.

{
  return (Compare (right) >= 0);
}  /* operator>= */

BitString BitString::operator^

(

const BitString &

right

)

Performs a bitwise XOR between two operands returning a new BitString.

Definition at line 598 of file BitString.cpp.

{
  kkuint32 shortestByteLen = Min (byteLen, right.byteLen);
  kkuint32 longestByteLen  = Max (byteLen, right.byteLen);

  kkuint32  x;

  BitString result (Max (bitLen, right.bitLen));

  for  (x = 0;  x < shortestByteLen;  x++)
    result.str[x] = str[x] ^ right.str[x];

  for  (x = shortestByteLen;  x < longestByteLen;  x++)
    result.str[x] = 0;

  return  result;
}

BitString & BitString::operator^=

(

const BitString &

right

)

Performs a bitwise XOR against the left operand.

Definition at line 580 of file BitString.cpp.

{
  kkuint32 shortestByteLen = Min (byteLen, right.byteLen);
  kkuint32 longestByteLen  = Max (byteLen, right.byteLen);

  kkuint32  x;

  for  (x = 0;  x < shortestByteLen;  x++)
    str[x] = str[x] ^ right.str[x];

  for  (x = shortestByteLen;  x < longestByteLen;  x++)
    str[x] = 0;

  return  *this;
}

BitString & BitString::operator|=

(

const BitString &

right

)

Performs a bitwise OR against the left operand.

Definition at line 459 of file BitString.cpp.

Referenced by operator+=().

{
  kkuint32 shortestByteLen = Min (byteLen, right.byteLen);

  kkuint32  x;

  for  (x = 0;  x < shortestByteLen;  x++)
  {
    str[x] = str[x] | right.str[x];
  }

  return  *this;
} /* operator|= */

void BitString::PopulateVectorBool

(

VectorBool &

boolVector

)

const

Populates a boolean vector where each element reflects whether the corresponding bit is set.

Parameters

[out]

boolVector

Vector to be populated reflecting which bits are set to '1'.

Definition at line 239 of file BitString.cpp.

{
  boolVector.erase (boolVector.begin (), boolVector.end ());

  kkuint32  byteOffset = 0;
  kkuint32  numOfBits  = 0;
  kkuint32  x;

  for  (byteOffset = 0;  byteOffset < byteLen;  byteOffset++)
  {
    uchar  br = str[byteOffset];
    if  (byteOffset < (byteLen - 1))
      numOfBits = 8;
    else
      numOfBits = bitLen % 8;

    for  (x = 0;  x < numOfBits;  x++)
    {
      boolVector.push_back ((br % 2) == 1);
      br = br / 2;
    }
  }
}  /* PopulateVectorBool */

void BitString::ReadXML ( XmlStream &  s, XmlTagConstPtr  tag, VolConstBool &  cancelFlag, RunLog &  log  )

virtual

TODO decode text block into list of bits.

Implements KKB::Atom.

Definition at line 618 of file BitString.cpp.

References KKB::XmlContent::Content(), and KKB::XmlStream::GetNextToken().

{
  kkint32  bitIndex = 0;
  XmlTokenPtr  t = s.GetNextToken (cancelFlag, log);
  while  (t  &&  (!cancelFlag))
  {
    if  (typeid (*t) == typeid (XmlContent))
    {
      XmlContentPtr c = dynamic_cast<XmlContentPtr> (t);
      if  (c  &&  c->Content ())
      {
        KKStrConstPtr  text = c->Content ();
        /** TODO decode text block into list of bits. */
        //ParseClassIndexList (*text, log);
        delete text;
        text = NULL;
      }
    }
    delete  t;
    t = s.GetNextToken (cancelFlag, log);
  }
  delete  t;
  t = NULL;
}  /* ReadXML */

void BitString::ReSet

(

)

Set all bits to '0'.

Definition at line 207 of file BitString.cpp.

Referenced by KKMLL::FeatureNumList::ToBitString().

{
  memset (str, 0, byteLen);
}

void BitString::ReSet

(

kkuint32

bitNum

)

Set the bit indicated by 'bitNum' to '0'.

Definition at line 215 of file BitString.cpp.

{
  if  (bitNum >= bitLen)
  {
    // Index violation.
    cerr << std::endl
         << "BitString::Set    Invalid Index[" << bitNum << "]  BitString::bitLen[" << bitLen << "]." << std::endl
         << std::endl;
    exit (-1);
  }

  kkint32 byteOffset;
  uchar   bitOffset;

  CalcByteAndBitOffsets (bitNum, byteOffset, bitOffset);

  uchar&  br = str[byteOffset];
    
  br = (br & bitMasksRev[bitOffset]);
}  /* ReSet */

void BitString::Set

(

)

Set all bits to '1'.

Definition at line 173 of file BitString.cpp.

{
  memset (str, 255, byteLen);
}  /* Set */

void BitString::Set

(

kkuint32

bitNum

)

Set the bit indicated by 'bitNum' to '1'.

Definition at line 182 of file BitString.cpp.

Referenced by BitString(), and KKMLL::FeatureNumList::ToBitString().

{
  if  (bitNum >= bitLen)
  {
    // Index violation.
    cerr << std::endl
         << "BitString::Set    Invalid Index[" << bitNum << "]  BitString::bitLen[" << bitLen << "]." << std::endl
         << std::endl;
    exit (-1);
  }

  kkint32 byteOffset;
  uchar   bitOffset;

  CalcByteAndBitOffsets (bitNum, byteOffset, bitOffset);

  uchar&  br = str[byteOffset];
    
  br = (br | bitMasks[bitOffset]);
}  /* Set */

bool BitString::Test

(

kkuint32

bitNum

)

const

summary> Get Bit positions that are set to 1; The parameter setBits will be populated with the list of bits that are set to 1 for bit strings that are up to 2^16-1 bits long. /summary> code> ex: Bit String "001200110011" will produce a vector <2, 3, 6, 7, 10, 11> /code> param name='setBits'> Will be populated with all bits that are set to '1', will be cleared first.

Definition at line 158 of file BitString.cpp.

{
  kkint32 byteOffset;
  uchar   bitOffset;

  CalcByteAndBitOffsets (bitNum, byteOffset, bitOffset);

  bool  bit = ((str[byteOffset] & bitMasks[bitOffset]) != 0);

  return bit;
}  /* IsSet */

void BitString::WriteXML ( const KKStr &  varName, std::ostream &  o  ) const

virtual

Implements KKB::Atom.

Definition at line 650 of file BitString.cpp.

References KKB::XmlTag::AddAtribute(), KKB::KKStr::Empty(), HexStr(), KKB::XmlTag::tagEnd, KKB::XmlTag::tagStart, KKB::XmlTag::WriteXML(), KKB::XmlContent::WriteXml(), and KKB::XmlTag::XmlTag().

{
  XmlTag  startTag ("BitString", XmlTag::TagTypes::tagStart);
  if  (!varName.Empty ())
    startTag.AddAtribute ("VarName", varName);
  startTag.WriteXML (o);
  XmlContent::WriteXml (this->HexStr(), o);
  XmlTag  endTag ("BitString", XmlTag::TagTypes::tagEnd);
  endTag.WriteXML (o);
  o << endl;
}

---

The documentation for this class was generated from the following files:

• C:/Users/Kurt/GitHub/KSquareLibraries/KKBase/BitString.h
• C:/Users/Kurt/GitHub/KSquareLibraries/KKBase/BitString.cpp