tesseract::BitVector Class Reference

#include <bitvector.h>

Public Member Functions
	BitVector ()
	BitVector (int length)
	BitVector (const BitVector &src)
BitVector &	operator= (const BitVector &src)
	~BitVector ()
void	Init (int length)
int	size () const
bool	Serialize (FILE *fp) const
bool	DeSerialize (bool swap, FILE *fp)
void	SetAllFalse ()
void	SetAllTrue ()
void	SetBit (int index)
void	ResetBit (int index)
void	SetValue (int index, bool value)
bool	At (int index) const
bool	operator[] (int index) const
int	NextSetBit (int prev_bit) const
int	NumSetBits () const
void	operator|= (const BitVector &other)
void	operator&= (const BitVector &other)
void	operator^= (const BitVector &other)
void	SetSubtract (const BitVector &v1, const BitVector &v2)

Static Public Attributes
static const uinT8	lsb_index_ [256]
static const uinT8	lsb_eroded_ [256]
static const int	hamming_table_ [256]

Detailed Description

Definition at line 34 of file bitvector.h.

Constructor & Destructor Documentation

tesseract::BitVector::BitVector

(

)

Definition at line 109 of file bitvector.cpp.

: bit_size_(0), array_(NULL) {}

tesseract::BitVector::BitVector ( int  length )

explicit

Definition at line 111 of file bitvector.cpp.

                               : bit_size_(length) {
  array_ = new uinT32[WordLength()];
  SetAllFalse();
}

tesseract::BitVector::BitVector

(

const BitVector &

src

)

Definition at line 116 of file bitvector.cpp.

                                         : bit_size_(src.bit_size_) {
  array_ = new uinT32[WordLength()];
  memcpy(array_, src.array_, ByteLength());
}

tesseract::BitVector::~BitVector

(

)

Definition at line 127 of file bitvector.cpp.

                      {
  delete [] array_;
}

Member Function Documentation

bool tesseract::BitVector::At ( int  index ) const

inline

Definition at line 85 of file bitvector.h.

                           {
    return (array_[WordIndex(index)] & BitMask(index)) != 0;
  }

bool tesseract::BitVector::DeSerialize	(	bool	swap,
		FILE *	fp
	)

Definition at line 148 of file bitvector.cpp.

                                               {
  uinT32 new_bit_size;
  if (fread(&new_bit_size, sizeof(new_bit_size), 1, fp) != 1) return false;
  if (swap) {
    ReverseN(&new_bit_size, sizeof(new_bit_size));
  }
  Alloc(new_bit_size);
  int wordlen = WordLength();
  if (static_cast<int>(fread(array_, sizeof(*array_), wordlen, fp)) != wordlen)
      return false;
  if (swap) {
    for (int i = 0; i < wordlen; ++i)
      ReverseN(&array_[i], sizeof(array_[i]));
  }
  return true;
}

void tesseract::BitVector::Init

(

int

length

)

Definition at line 132 of file bitvector.cpp.

                               {
  Alloc(length);
  SetAllFalse();
}

int tesseract::BitVector::NextSetBit

(

int

prev_bit

)

const

Definition at line 174 of file bitvector.cpp.

                                            {
  // Move on to the next bit.
  int next_bit = prev_bit + 1;
  if (next_bit >= bit_size_) return -1;
  // Check the remains of the word containing the next_bit first.
  int next_word = WordIndex(next_bit);
  int bit_index = next_word * kBitFactor;
  int word_end = bit_index + kBitFactor;
  uinT32 word = array_[next_word];
  uinT8 byte = word & 0xff;
  while (bit_index < word_end) {
    if (bit_index + 8 > next_bit && byte != 0) {
      while (bit_index + lsb_index_[byte] < next_bit && byte != 0)
        byte = lsb_eroded_[byte];
      if (byte != 0)
        return bit_index + lsb_index_[byte];
    }
    word >>= 8;
    bit_index += 8;
    byte = word & 0xff;
  }
  // next_word didn't contain a 1, so find the next word with set bit.
  ++next_word;
  int wordlen = WordLength();
  while (next_word < wordlen && (word = array_[next_word]) == 0) {
    ++next_word;
    bit_index += kBitFactor;
  }
  if (bit_index >= bit_size_) return -1;
  // Find the first non-zero byte within the word.
  while ((word & 0xff) == 0) {
    word >>= 8;
    bit_index += 8;
  }
  return bit_index + lsb_index_[word & 0xff];
}

int tesseract::BitVector::NumSetBits

(

)

const

Definition at line 212 of file bitvector.cpp.

                                {
  int wordlen = WordLength();
  int total_bits = 0;
  for (int w = 0; w < wordlen; ++w) {
    uinT32 word = array_[w];
    for (int i = 0; i < 4; ++i) {
      total_bits += hamming_table_[word & 0xff];
      word >>= 8;
    }
  }
  return total_bits;
}

void tesseract::BitVector::operator&=

(

const BitVector &

other

)

Definition at line 232 of file bitvector.cpp.

                                                 {
  int length = MIN(WordLength(), other.WordLength());
  for (int w = 0; w < length; ++w)
    array_[w] &= other.array_[w];
  for (int w = WordLength() - 1; w >= length; --w)
    array_[w] = 0;
}

BitVector & tesseract::BitVector::operator=

(

const BitVector &

src

)

Definition at line 121 of file bitvector.cpp.

                                                    {
  Alloc(src.bit_size_);
  memcpy(array_, src.array_, ByteLength());
  return *this;
}

bool tesseract::BitVector::operator[] ( int  index ) const

inline

Definition at line 88 of file bitvector.h.

                                   {
    return (array_[WordIndex(index)] & BitMask(index)) != 0;
  }

void tesseract::BitVector::operator^=

(

const BitVector &

other

)

Definition at line 239 of file bitvector.cpp.

                                                 {
  int length = MIN(WordLength(), other.WordLength());
  for (int w = 0; w < length; ++w)
    array_[w] ^= other.array_[w];
}

void tesseract::BitVector::operator|=

(

const BitVector &

other

)

Definition at line 227 of file bitvector.cpp.

                                                 {
  int length = MIN(WordLength(), other.WordLength());
  for (int w = 0; w < length; ++w)
    array_[w] |= other.array_[w];
}

void tesseract::BitVector::ResetBit ( int  index )

inline

Definition at line 76 of file bitvector.h.

                           {
    array_[WordIndex(index)] &= ~BitMask(index);
  }

bool tesseract::BitVector::Serialize

(

FILE *

fp

)

const

Definition at line 138 of file bitvector.cpp.

                                        {
  if (fwrite(&bit_size_, sizeof(bit_size_), 1, fp) != 1) return false;
  int wordlen = WordLength();
  if (static_cast<int>(fwrite(array_, sizeof(*array_), wordlen, fp)) != wordlen)
      return false;
  return true;
}

void tesseract::BitVector::SetAllFalse

(

)

Definition at line 165 of file bitvector.cpp.

                            {
  memset(array_, 0, ByteLength());
}

void tesseract::BitVector::SetAllTrue

(

)

Definition at line 168 of file bitvector.cpp.

                           {
  memset(array_, ~0, ByteLength());
}

void tesseract::BitVector::SetBit ( int  index )

inline

Definition at line 73 of file bitvector.h.

                         {
    array_[WordIndex(index)] |= BitMask(index);
  }

void tesseract::BitVector::SetSubtract	(	const BitVector &	v1,
		const BitVector &	v2
	)

Definition at line 245 of file bitvector.cpp.

                                                                    {
  Alloc(v1.size());
  int length = MIN(v1.WordLength(), v2.WordLength());
  for (int w = 0; w < length; ++w)
    array_[w] = v1.array_[w] ^ (v1.array_[w] & v2.array_[w]);
  for (int w = WordLength() - 1; w >= length; --w)
    array_[w] = v1.array_[w];
}

void tesseract::BitVector::SetValue ( int  index, bool  value  )

inline

Definition at line 79 of file bitvector.h.

                                       {
    if (value)
      SetBit(index);
    else
      ResetBit(index);
  }

int tesseract::BitVector::size ( ) const

inline

Definition at line 57 of file bitvector.h.

                   {
    return bit_size_;
  }

Member Data Documentation

const int tesseract::BitVector::hamming_table_

static

Initial value:

= {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
}

Definition at line 44 of file bitvector.h.

const uinT8 tesseract::BitVector::lsb_eroded_

static

Definition at line 42 of file bitvector.h.

const uinT8 tesseract::BitVector::lsb_index_

static

Initial value:

= {
  255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
}

Definition at line 39 of file bitvector.h.

---

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

• ccutil/bitvector.h
• ccutil/bitvector.cpp