tesseract 4.1.1
Loading...
Searching...
No Matches
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}
void ReverseN(void *ptr, int num_bytes)
Definition: helpers.h:185
bool DeSerialize(FILE *fp, char *data, size_t n)
Definition: serialis.cpp:28

◆ 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}
static const uint8_t lsb_index_[256]
Definition: bitvector.h:35
static const uint8_t lsb_eroded_[256]
Definition: bitvector.h:38

◆ 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}
static const int hamming_table_[256]
Definition: bitvector.h:40

◆ 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}
bool Serialize(FILE *fp, const char *data, size_t n)
Definition: serialis.cpp:60

◆ 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 }
void SetBit(int index)
Definition: bitvector.h:69
void ResetBit(int index)
Definition: bitvector.h:72

◆ 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: