tesseract  5.0.0-alpha-619-ge9db
tesseract::BitVector Class Reference

#include <bitvector.h>

Public Member Functions

 BitVector ()
 
 BitVector (int length)
 
 BitVector (const BitVector &src)
 
BitVectoroperator= (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_t lsb_index_ [256]
 
static const uint8_t lsb_eroded_ [256]
 
static const int hamming_table_ [256]
 

Detailed Description

Definition at line 30 of file bitvector.h.

Constructor & Destructor Documentation

◆ BitVector() [1/3]

tesseract::BitVector::BitVector ( )

Definition at line 110 of file bitvector.cpp.

110 : bit_size_(0), array_(nullptr) {}

◆ BitVector() [2/3]

tesseract::BitVector::BitVector ( int  length)
explicit

Definition at line 112 of file bitvector.cpp.

112  : bit_size_(length) {
113  array_ = new uint32_t[WordLength()];
114  SetAllFalse();
115 }

◆ BitVector() [3/3]

tesseract::BitVector::BitVector ( const BitVector src)

Definition at line 117 of file bitvector.cpp.

117  : bit_size_(src.bit_size_) {
118  if (src.bit_size_ > 0) {
119  array_ = new uint32_t[WordLength()];
120  memcpy(array_, src.array_, ByteLength());
121  } else {
122  array_ = nullptr;
123  }
124 }

◆ ~BitVector()

tesseract::BitVector::~BitVector ( )

Definition at line 134 of file bitvector.cpp.

134  {
135  delete [] array_;
136 }

Member Function Documentation

◆ At()

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

Definition at line 81 of file bitvector.h.

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

◆ DeSerialize()

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

Definition at line 153 of file bitvector.cpp.

153  {
154  uint32_t new_bit_size;
155  if (!tesseract::DeSerialize(fp, &new_bit_size)) return false;
156  if (swap) {
157  ReverseN(&new_bit_size, sizeof(new_bit_size));
158  }
159  Alloc(new_bit_size);
160  int wordlen = WordLength();
161  if (!tesseract::DeSerialize(fp, &array_[0], wordlen)) return false;
162  if (swap) {
163  for (int i = 0; i < wordlen; ++i)
164  ReverseN(&array_[i], sizeof(array_[i]));
165  }
166  return true;
167 }

◆ Init()

void tesseract::BitVector::Init ( int  length)

Definition at line 139 of file bitvector.cpp.

139  {
140  Alloc(length);
141  SetAllFalse();
142 }

◆ NextSetBit()

int tesseract::BitVector::NextSetBit ( int  prev_bit) const

Definition at line 178 of file bitvector.cpp.

178  {
179  // Move on to the next bit.
180  int next_bit = prev_bit + 1;
181  if (next_bit >= bit_size_) return -1;
182  // Check the remains of the word containing the next_bit first.
183  int next_word = WordIndex(next_bit);
184  int bit_index = next_word * kBitFactor;
185  int word_end = bit_index + kBitFactor;
186  uint32_t word = array_[next_word];
187  uint8_t byte = word & 0xff;
188  while (bit_index < word_end) {
189  if (bit_index + 8 > next_bit && byte != 0) {
190  while (bit_index + lsb_index_[byte] < next_bit && byte != 0)
191  byte = lsb_eroded_[byte];
192  if (byte != 0)
193  return bit_index + lsb_index_[byte];
194  }
195  word >>= 8;
196  bit_index += 8;
197  byte = word & 0xff;
198  }
199  // next_word didn't contain a 1, so find the next word with set bit.
200  ++next_word;
201  int wordlen = WordLength();
202  while (next_word < wordlen && (word = array_[next_word]) == 0) {
203  ++next_word;
204  bit_index += kBitFactor;
205  }
206  if (bit_index >= bit_size_) return -1;
207  // Find the first non-zero byte within the word.
208  while ((word & 0xff) == 0) {
209  word >>= 8;
210  bit_index += 8;
211  }
212  return bit_index + lsb_index_[word & 0xff];
213 }

◆ NumSetBits()

int tesseract::BitVector::NumSetBits ( ) const

Definition at line 216 of file bitvector.cpp.

216  {
217  int wordlen = WordLength();
218  int total_bits = 0;
219  for (int w = 0; w < wordlen; ++w) {
220  uint32_t word = array_[w];
221  for (int i = 0; i < 4; ++i) {
222  total_bits += hamming_table_[word & 0xff];
223  word >>= 8;
224  }
225  }
226  return total_bits;
227 }

◆ operator&=()

void tesseract::BitVector::operator&= ( const BitVector other)

Definition at line 236 of file bitvector.cpp.

236  {
237  int length = std::min(WordLength(), other.WordLength());
238  for (int w = 0; w < length; ++w)
239  array_[w] &= other.array_[w];
240  for (int w = WordLength() - 1; w >= length; --w)
241  array_[w] = 0;
242 }

◆ operator=()

BitVector & tesseract::BitVector::operator= ( const BitVector src)

Definition at line 126 of file bitvector.cpp.

126  {
127  Alloc(src.bit_size_);
128  if (src.bit_size_ > 0) {
129  memcpy(array_, src.array_, ByteLength());
130  }
131  return *this;
132 }

◆ operator[]()

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

Definition at line 84 of file bitvector.h.

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

◆ operator^=()

void tesseract::BitVector::operator^= ( const BitVector other)

Definition at line 243 of file bitvector.cpp.

243  {
244  int length = std::min(WordLength(), other.WordLength());
245  for (int w = 0; w < length; ++w)
246  array_[w] ^= other.array_[w];
247 }

◆ operator|=()

void tesseract::BitVector::operator|= ( const BitVector other)

Definition at line 231 of file bitvector.cpp.

231  {
232  int length = std::min(WordLength(), other.WordLength());
233  for (int w = 0; w < length; ++w)
234  array_[w] |= other.array_[w];
235 }

◆ ResetBit()

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

Definition at line 72 of file bitvector.h.

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

◆ Serialize()

bool tesseract::BitVector::Serialize ( FILE *  fp) const

Definition at line 145 of file bitvector.cpp.

145  {
146  if (!tesseract::Serialize(fp, &bit_size_)) return false;
147  int wordlen = WordLength();
148  return tesseract::Serialize(fp, &array_[0], wordlen);
149 }

◆ SetAllFalse()

void tesseract::BitVector::SetAllFalse ( )

Definition at line 169 of file bitvector.cpp.

169  {
170  memset(array_, 0, ByteLength());
171 }

◆ SetAllTrue()

void tesseract::BitVector::SetAllTrue ( )

Definition at line 172 of file bitvector.cpp.

172  {
173  memset(array_, ~0, ByteLength());
174 }

◆ SetBit()

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

Definition at line 69 of file bitvector.h.

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

◆ SetSubtract()

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

Definition at line 249 of file bitvector.cpp.

249  {
250  Alloc(v1.size());
251  int length = std::min(v1.WordLength(), v2.WordLength());
252  for (int w = 0; w < length; ++w)
253  array_[w] = v1.array_[w] ^ (v1.array_[w] & v2.array_[w]);
254  for (int w = WordLength() - 1; w >= length; --w)
255  array_[w] = v1.array_[w];
256 }

◆ SetValue()

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

Definition at line 75 of file bitvector.h.

75  {
76  if (value)
77  SetBit(index);
78  else
79  ResetBit(index);
80  }

◆ size()

int tesseract::BitVector::size ( ) const
inline

Definition at line 53 of file bitvector.h.

53  {
54  return bit_size_;
55  }

Member Data Documentation

◆ hamming_table_

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 40 of file bitvector.h.

◆ lsb_eroded_

const uint8_t tesseract::BitVector::lsb_eroded_
static

Definition at line 38 of file bitvector.h.

◆ lsb_index_

const uint8_t 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 35 of file bitvector.h.


The documentation for this class was generated from the following files:
tesseract::BitVector::SetBit
void SetBit(int index)
Definition: bitvector.h:69
tesseract::BitVector::SetAllFalse
void SetAllFalse()
Definition: bitvector.cpp:169
tesseract::BitVector::hamming_table_
static const int hamming_table_[256]
Definition: bitvector.h:40
tesseract::BitVector::ResetBit
void ResetBit(int index)
Definition: bitvector.h:72
tesseract::BitVector::lsb_eroded_
static const uint8_t lsb_eroded_[256]
Definition: bitvector.h:38
tesseract::BitVector::lsb_index_
static const uint8_t lsb_index_[256]
Definition: bitvector.h:35
ReverseN
void ReverseN(void *ptr, int num_bytes)
Definition: helpers.h:183
tesseract::DeSerialize
bool DeSerialize(FILE *fp, char *data, size_t n=1)
Definition: serialis.cpp:41
tesseract::Serialize
bool Serialize(FILE *fp, const char *data, size_t n=1)
Definition: serialis.cpp:73