1 | #ifndef BITBLOCK_ITERATOR_H_ |
---|
2 | #define BITBLOCK_ITERATOR_H_ |
---|
3 | |
---|
4 | #include <iterator> |
---|
5 | #include <iostream> |
---|
6 | #include "bitblock.hpp" |
---|
7 | |
---|
8 | /*============================================================================= |
---|
9 | bitblock_iterator.hpp |
---|
10 | |
---|
11 | Created on: Sept 2011 |
---|
12 | Author: Ken Herdy |
---|
13 | |
---|
14 | Description: |
---|
15 | |
---|
16 | Scanner classes implement the low level methods to scan through |
---|
17 | the 'scanwords' of a 'bitblock'. Scanner classes are templated |
---|
18 | on bitblock type and scanword type. |
---|
19 | |
---|
20 | BitBlock iterator classes provide Standard Template Library (STL) |
---|
21 | Input iterator 'like' interface implementations as a programmer |
---|
22 | convenience and allow iterator classes to be used |
---|
23 | with STL Algorithms. |
---|
24 | Forward iterators can only step forward (++) marker-bit by marker-bit. |
---|
25 | Reverse iterators can only step backwards (--) marker-bit by marker-bit. |
---|
26 | |
---|
27 | BitStream iterator class provide an STL Input iterator interface to scan |
---|
28 | through an array of scanwords (stream) in the forward direction. |
---|
29 | |
---|
30 | |
---|
31 | Classes Descriptions: |
---|
32 | |
---|
33 | * BitBlock Scanners |
---|
34 | |
---|
35 | Scanner - Scanner base class. |
---|
36 | ForwardScanner - Scans a bitblock of scanwords in the forward direction. |
---|
37 | ReverseScanner - Scans a bitblock of scanwords in the reverse direction. |
---|
38 | |
---|
39 | * BitBlock Iterators |
---|
40 | |
---|
41 | ForwardIterator template class wraps ForwardScanner. |
---|
42 | |
---|
43 | - Implements STL Input iterator interface. |
---|
44 | - Reads elements only once. |
---|
45 | - '->' - Not implemented. |
---|
46 | |
---|
47 | ReverseIterator template class wraps ReverseScanner. |
---|
48 | |
---|
49 | - An STL 'like' iterator that implements prefix and postfix decrement operators. |
---|
50 | Under STL, a reverse iterator implementation necessitates the implementation of |
---|
51 | the STL bidirectional interface and hence scanning in both directions. |
---|
52 | This functionality is not yet required and hence not implemented. |
---|
53 | - Reads elements only once. |
---|
54 | - '->' - Not implemented. |
---|
55 | |
---|
56 | BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, scanword_t> |
---|
57 | |
---|
58 | BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, scanword_t> |
---|
59 | |
---|
60 | * BitStreamIterators |
---|
61 | |
---|
62 | BitStreamIterator class wraps ForwardScanner. |
---|
63 | - Scans an array (stream) of scanwords in contiguous memory. |
---|
64 | - Implements STL Input iterator interface. |
---|
65 | - Reads elements only once. |
---|
66 | - '->' - Not implemented. |
---|
67 | - May be more appropriately named ForwardBitStreamIterator. |
---|
68 | |
---|
69 | =============================================================================*/ |
---|
70 | // |
---|
71 | // Scanner Classes |
---|
72 | // |
---|
73 | #define has_bit(x) (x != 0) |
---|
74 | |
---|
75 | template <class bitblock_t, class scanblock_t> |
---|
76 | class Scanner { |
---|
77 | |
---|
78 | protected: |
---|
79 | Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {} |
---|
80 | Scanner(const bitblock_t * s, uint32_t start_pos, uint32_t start_blk, scanblock_t start_scan_blk): strm(s), pos(start_pos), blk(start_blk), scan_blk(start_scan_blk) {} |
---|
81 | |
---|
82 | const bitblock_t * strm; |
---|
83 | int32_t pos; |
---|
84 | int32_t blk; |
---|
85 | scanblock_t scan_blk; |
---|
86 | }; |
---|
87 | |
---|
88 | template <class bitblock_t, class scanblock_t> |
---|
89 | class ForwardScanner: public Scanner<bitblock_t, scanblock_t> { |
---|
90 | |
---|
91 | public: |
---|
92 | |
---|
93 | ForwardScanner(){} |
---|
94 | ForwardScanner(const bitblock_t * s) { |
---|
95 | init(s); |
---|
96 | } |
---|
97 | |
---|
98 | IDISA_ALWAYS_INLINE void init(const bitblock_t * s) { |
---|
99 | this->strm = s; |
---|
100 | this->pos = 0; |
---|
101 | this->blk = 0; |
---|
102 | this->scan_blk = *(scanblock_t *)s; |
---|
103 | } |
---|
104 | |
---|
105 | IDISA_ALWAYS_INLINE int32_t scan_to_next() { |
---|
106 | while (this->blk < BLOCK_COUNT){ |
---|
107 | if(has_bit(this->scan_blk)){ |
---|
108 | this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8)); |
---|
109 | this->scan_blk = this->scan_blk & (this->scan_blk-1); // clear rightmost bit |
---|
110 | |
---|
111 | return (this->pos); |
---|
112 | } |
---|
113 | |
---|
114 | this->blk++; |
---|
115 | this->scan_blk = *((scanblock_t *)this->strm + this->blk); |
---|
116 | }; |
---|
117 | |
---|
118 | this->pos = -1; |
---|
119 | return (this->pos); |
---|
120 | } |
---|
121 | |
---|
122 | /* Set or reset the iterator to position new_pos. */ |
---|
123 | IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) { |
---|
124 | const scanblock_t one_bit = 1; |
---|
125 | this->blk = new_pos / (sizeof(scanblock_t)*8); |
---|
126 | this->pos = new_pos % (sizeof(scanblock_t)*8); |
---|
127 | this->scan_blk = ((scanblock_t *)this->strm)[this->blk]; |
---|
128 | // clear bit at pos and all positions to the right. |
---|
129 | scanblock_t marker = one_bit << this->pos; |
---|
130 | this->scan_blk = this->scan_blk &~((marker-1)|marker); |
---|
131 | } |
---|
132 | |
---|
133 | IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);} |
---|
134 | IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;} |
---|
135 | IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;} |
---|
136 | IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;} |
---|
137 | |
---|
138 | static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t); |
---|
139 | |
---|
140 | }; |
---|
141 | |
---|
142 | template <class bitblock_t, class scanblock_t> |
---|
143 | class ReverseScanner: public Scanner<bitblock_t, scanblock_t> { |
---|
144 | |
---|
145 | public: |
---|
146 | ReverseScanner(){} |
---|
147 | ReverseScanner(const bitblock_t * s) { |
---|
148 | init(s); |
---|
149 | } |
---|
150 | IDISA_ALWAYS_INLINE void init(const bitblock_t * s) { |
---|
151 | this->strm = s; |
---|
152 | this->pos = 0; |
---|
153 | this->blk = BLOCK_COUNT-1; |
---|
154 | this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1)); |
---|
155 | } |
---|
156 | |
---|
157 | IDISA_ALWAYS_INLINE int32_t scan_to_next() { |
---|
158 | const scanblock_t one_bit = 1; /* ensure enough bits for shift: one_bit << this->pos */ |
---|
159 | while (this->blk > -1){ |
---|
160 | if(has_bit(this->scan_blk)){ |
---|
161 | this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 ); |
---|
162 | this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit |
---|
163 | return (this->pos); |
---|
164 | } |
---|
165 | |
---|
166 | this->blk--; |
---|
167 | this->scan_blk = *((scanblock_t *)this->strm + this->blk); |
---|
168 | }; |
---|
169 | |
---|
170 | this->pos = -1; |
---|
171 | return (this->pos); |
---|
172 | } |
---|
173 | |
---|
174 | /* Set or reset the iterator to position new_pos. */ |
---|
175 | IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) { |
---|
176 | const scanblock_t one_bit = 1; |
---|
177 | this->blk = (new_pos / (sizeof(scanblock_t)*8)); |
---|
178 | this->pos = new_pos % (sizeof(scanblock_t)*8); |
---|
179 | this->scan_blk = ((scanblock_t *)this->strm)[this->blk]; |
---|
180 | // clear bit at pos and all positions to the left. |
---|
181 | scanblock_t marker = one_bit << this->pos; |
---|
182 | this->scan_blk = this->scan_blk & (marker-1); |
---|
183 | } |
---|
184 | |
---|
185 | IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);} |
---|
186 | IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;} |
---|
187 | IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;} |
---|
188 | IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;} |
---|
189 | |
---|
190 | static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t); |
---|
191 | |
---|
192 | }; |
---|
193 | |
---|
194 | #undef has_bit |
---|
195 | |
---|
196 | // |
---|
197 | // BitBlock Iterator Classses |
---|
198 | // |
---|
199 | template<class bitblock_t, class scanblock_t> |
---|
200 | class ForwardIterator : public std::iterator<std::input_iterator_tag, int> |
---|
201 | { |
---|
202 | public: |
---|
203 | ForwardIterator() {} |
---|
204 | |
---|
205 | ForwardIterator(bitblock_t * s): scanner(s) |
---|
206 | { |
---|
207 | scanner.scan_to_next(); |
---|
208 | } |
---|
209 | |
---|
210 | void init(bitblock_t * s) |
---|
211 | { |
---|
212 | scanner.init(s); |
---|
213 | scanner.scan_to_next(); |
---|
214 | } |
---|
215 | |
---|
216 | // equal position and stream |
---|
217 | bool operator==(const ForwardIterator& iter) |
---|
218 | { |
---|
219 | return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos)); |
---|
220 | } |
---|
221 | |
---|
222 | // not equal .get_pos()ition and stream |
---|
223 | bool operator!=(const ForwardIterator& iter) |
---|
224 | { |
---|
225 | return ( (scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos())); |
---|
226 | } |
---|
227 | |
---|
228 | // Returns absolute position. |
---|
229 | IDISA_ALWAYS_INLINE int32_t operator*() |
---|
230 | { |
---|
231 | return scanner.get_pos(); |
---|
232 | } |
---|
233 | |
---|
234 | // prefix increment |
---|
235 | IDISA_ALWAYS_INLINE ForwardIterator& operator++() |
---|
236 | { |
---|
237 | scanner.scan_to_next(); |
---|
238 | return(*this); |
---|
239 | } |
---|
240 | |
---|
241 | // postfix increment |
---|
242 | ForwardIterator operator++(int) |
---|
243 | { |
---|
244 | ForwardIterator temp(*this); |
---|
245 | ++(*this); |
---|
246 | return(temp); |
---|
247 | } |
---|
248 | |
---|
249 | private: |
---|
250 | ForwardScanner<bitblock_t, scanblock_t> scanner; |
---|
251 | }; |
---|
252 | |
---|
253 | class BitBlockForwardIterator: public ForwardIterator<BitBlock, scanword_t> { |
---|
254 | public: |
---|
255 | BitBlockForwardIterator(){} |
---|
256 | BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, scanword_t>(s){} |
---|
257 | }; |
---|
258 | |
---|
259 | template<class bitblock_t, class scanblock_t> |
---|
260 | class ReverseIterator |
---|
261 | { |
---|
262 | public: |
---|
263 | ReverseIterator() {} |
---|
264 | ReverseIterator(BitBlock * s): scanner(s) |
---|
265 | { |
---|
266 | scanner.scan_to_next(); |
---|
267 | } |
---|
268 | |
---|
269 | void init(bitblock_t * s) |
---|
270 | { |
---|
271 | scanner.init(s); |
---|
272 | scanner.scan_to_next(); |
---|
273 | } |
---|
274 | |
---|
275 | // equal position and stream |
---|
276 | bool operator==(const ReverseIterator& iter) |
---|
277 | { |
---|
278 | return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos)); |
---|
279 | } |
---|
280 | |
---|
281 | // not equal .get_pos()ition and stream |
---|
282 | bool operator!=(const ReverseIterator& iter) |
---|
283 | { |
---|
284 | return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos())); |
---|
285 | } |
---|
286 | |
---|
287 | // Returns absolute position. |
---|
288 | IDISA_ALWAYS_INLINE int32_t operator*() |
---|
289 | { |
---|
290 | return scanner.get_pos(); |
---|
291 | } |
---|
292 | |
---|
293 | // prefix decrement |
---|
294 | IDISA_ALWAYS_INLINE ReverseIterator& operator--() |
---|
295 | { |
---|
296 | scanner.scan_to_next(); |
---|
297 | return(*this); |
---|
298 | } |
---|
299 | |
---|
300 | // postfix decrement |
---|
301 | ReverseIterator operator--(int) |
---|
302 | { |
---|
303 | ReverseIterator temp(*this); |
---|
304 | --(*this); |
---|
305 | return(temp); |
---|
306 | } |
---|
307 | |
---|
308 | private: |
---|
309 | ReverseScanner<bitblock_t, scanblock_t> scanner; |
---|
310 | }; |
---|
311 | |
---|
312 | class BitBlockReverseIterator: public ReverseIterator<BitBlock, scanword_t> { |
---|
313 | public: |
---|
314 | BitBlockReverseIterator(){} |
---|
315 | BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, scanword_t>(s){} |
---|
316 | }; |
---|
317 | |
---|
318 | // |
---|
319 | // BitStream Iterator classes |
---|
320 | // |
---|
321 | class BitStreamIterator: public std::iterator<std::input_iterator_tag, int> |
---|
322 | { |
---|
323 | public: |
---|
324 | BitStreamIterator():pos(-1), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0) |
---|
325 | { |
---|
326 | // default constructor defines past-the-end of bit stream semantics, pos == -1 |
---|
327 | } |
---|
328 | |
---|
329 | BitStreamIterator(const BitBlock * s, int cnt):pos(0), |
---|
330 | blk(0), |
---|
331 | blk_pos(0), |
---|
332 | strm((scanword_t *)s), |
---|
333 | scan_blk(*((scanword_t *)s)), |
---|
334 | scan_blk_cnt(cnt) |
---|
335 | { |
---|
336 | scan_to_next(); |
---|
337 | } |
---|
338 | |
---|
339 | virtual ~BitStreamIterator() {}; |
---|
340 | |
---|
341 | // shallow copy, bit stream iterators refer to shared data |
---|
342 | BitStreamIterator& operator=(const BitStreamIterator& iter) |
---|
343 | { |
---|
344 | pos = iter.pos; |
---|
345 | blk = iter.blk; |
---|
346 | blk_pos = iter.blk_pos; |
---|
347 | strm = iter.strm; // No copy, both |
---|
348 | scan_blk = iter.scan_blk; |
---|
349 | scan_blk_cnt = iter.scan_blk_cnt; |
---|
350 | return(*this); |
---|
351 | } |
---|
352 | |
---|
353 | // equal position and stream |
---|
354 | bool operator==(const BitStreamIterator& iter) |
---|
355 | { |
---|
356 | return((strm = iter.strm) && (pos == iter.pos)); |
---|
357 | } |
---|
358 | |
---|
359 | // not equal position and stream |
---|
360 | bool operator!=(const BitStreamIterator& iter) |
---|
361 | { |
---|
362 | return((strm != iter.strm) || (pos != iter.pos)); |
---|
363 | } |
---|
364 | |
---|
365 | // prefix |
---|
366 | inline BitStreamIterator& operator++() |
---|
367 | { |
---|
368 | scan_to_next(); |
---|
369 | return(*this); |
---|
370 | } |
---|
371 | |
---|
372 | // postfix |
---|
373 | BitStreamIterator operator++(int) |
---|
374 | { |
---|
375 | BitStreamIterator temp(*this); |
---|
376 | ++(*this); |
---|
377 | return(temp); |
---|
378 | } |
---|
379 | |
---|
380 | // Returns absolute position. |
---|
381 | inline int32_t operator*() |
---|
382 | { |
---|
383 | return pos; |
---|
384 | } |
---|
385 | |
---|
386 | /* |
---|
387 | int operator->() |
---|
388 | { |
---|
389 | return(&*(BitStreamIterator)*this); |
---|
390 | } |
---|
391 | */ |
---|
392 | |
---|
393 | void debug() { |
---|
394 | std::cout << "pos: " << pos << std::endl; |
---|
395 | std::cout << "blk: " << blk << std::endl; |
---|
396 | std::cout << "blk_pos: " << blk_pos << std::endl; |
---|
397 | } |
---|
398 | |
---|
399 | private: |
---|
400 | int32_t pos; |
---|
401 | uint32_t blk; |
---|
402 | int32_t blk_pos; |
---|
403 | const scanword_t * strm; |
---|
404 | scanword_t scan_blk; |
---|
405 | uint32_t scan_blk_cnt; |
---|
406 | |
---|
407 | // Helpers |
---|
408 | inline void scan_to_next() { |
---|
409 | while (blk<scan_blk_cnt) { |
---|
410 | if(scan_blk > 0){ |
---|
411 | pos = scan_forward_zeroes(scan_blk) + blk_pos; |
---|
412 | scan_blk = scan_blk & (scan_blk-1); // clear rightmost bit |
---|
413 | return; |
---|
414 | } |
---|
415 | |
---|
416 | blk_pos += (sizeof(scanword_t)*8); |
---|
417 | blk++; |
---|
418 | scan_blk = strm[blk]; |
---|
419 | }; |
---|
420 | |
---|
421 | pos = -1; |
---|
422 | return; |
---|
423 | } |
---|
424 | }; |
---|
425 | |
---|
426 | #endif // BITBLOCK_ITERATOR_H_ |
---|
427 | |
---|