source: trunk/lib/bitblock_iterator.hpp @ 2594

Last change on this file since 2594 was 2594, checked in by ksherdy, 6 years ago

Rename scanword_t ScanWord?.

File size: 10.8 KB
Line 
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>
57
58        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, Scanword>
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
75template <class bitblock_t, class scanblock_t>
76class Scanner {
77
78protected:
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
88template <class bitblock_t, class scanblock_t>
89class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
90
91public:
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 int32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
139
140};
141
142template <class bitblock_t, class scanblock_t>
143class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
144
145public:
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//
199template<class bitblock_t, class scanblock_t>
200class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
201{
202public:
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
249private:
250        ForwardScanner<bitblock_t, scanblock_t> scanner;
251};
252
253class BitBlockForwardIterator: public ForwardIterator<BitBlock, ScanWord> {
254public:
255        BitBlockForwardIterator(){}
256        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, ScanWord>(s){}
257};
258
259template<class bitblock_t, class scanblock_t>
260class ReverseIterator 
261{
262public:
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
308private:
309        ReverseScanner<bitblock_t, scanblock_t> scanner;
310};
311
312class BitBlockReverseIterator: public ReverseIterator<BitBlock, ScanWord> {
313public:
314        BitBlockReverseIterator(){}
315        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, ScanWord>(s){}
316};
317
318//
319// BitStream Iterator classes
320//
321class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
322{
323public:
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 *)s),
333                                                                                         scan_blk(*((ScanWord *)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
399private:
400        int32_t pos;
401        uint32_t blk;
402        int32_t blk_pos;
403        const ScanWord * strm;
404        ScanWord 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)*8);
417                        blk++;
418                        scan_blk = strm[blk];
419                };
420
421                pos = -1;
422                return;
423        }
424};
425
426#endif // BITBLOCK_ITERATOR_H_
427
Note: See TracBrowser for help on using the repository browser.