source: trunk/lib/bitblock_iterator.hpp @ 2348

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

Removed #include.

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