source: trunk/lib/bitblock_iterator.hpp @ 3142

Last change on this file since 3142 was 3142, checked in by cameron, 6 years ago

Hide default constructors for iterators.

File size: 15.3 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
142class BitBlockForwardScanner: public ForwardScanner<BitBlock, ScanWord> {
143public:
144        BitBlockForwardScanner(){}
145        BitBlockForwardScanner(BitBlock * s): ForwardScanner<BitBlock, ScanWord>(s){}
146};
147
148
149template <class bitblock_t, class scanblock_t>
150class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
151
152public:
153        ReverseScanner(){}
154        ReverseScanner(const bitblock_t * s) {
155                init(s);
156        }
157        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
158                this->strm = s;
159                this->pos = 0;
160                this->blk = BLOCK_COUNT-1;
161                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
162        }
163
164        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
165                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
166                while (this->blk > -1){
167                        if(has_bit(this->scan_blk)){
168                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
169                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
170                                return (this->pos);
171                        }
172
173                        this->blk--;
174                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
175                };
176
177                this->pos = -1;
178                return (this->pos);
179        }
180
181        /* Set or reset the iterator to position new_pos. */
182        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
183                const scanblock_t one_bit = 1;
184                this->blk = (new_pos / (sizeof(scanblock_t)*8));
185                this->pos = new_pos % (sizeof(scanblock_t)*8);
186                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
187                // clear bit at pos and all positions to the left.
188                scanblock_t marker = one_bit << this->pos;
189                this->scan_blk = this->scan_blk & (marker-1);
190        }
191
192        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
193        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
194        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
195        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
196
197        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
198
199};
200
201
202//
203// BitBlock Iterator Classses
204//
205template<class bitblock_t, class scanblock_t>
206class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
207{
208public:
209        ForwardIterator(bitblock_t * s): scanner(s)
210        {
211                scanner.scan_to_next();
212        }
213
214        void init(bitblock_t * s)
215        {
216                scanner.init(s);
217                scanner.scan_to_next();
218        }
219
220        // equal position and stream
221        bool operator==(const ForwardIterator& iter)
222        {
223                return ((scanner.get_strm() == iter.scanner.get_strm()) && 
224                        (scanner.get_pos() == iter.scanner.get_pos()));
225        }
226
227        // not equal position and stream
228        bool operator!=(const ForwardIterator& iter)
229        {
230                return ((scanner.get_strm() != iter.scanner.get_strm()) && 
231                        (scanner.get_pos() != iter.scanner.get_pos()));
232        }
233
234        // Returns absolute position.
235        IDISA_ALWAYS_INLINE int32_t operator*()
236        {
237                return scanner.get_pos();
238        }
239
240        // prefix increment
241        IDISA_ALWAYS_INLINE ForwardIterator& operator++()
242        {
243                scanner.scan_to_next();
244                return(*this);
245        }
246
247        // postfix increment
248        ForwardIterator operator++(int)
249        {
250                ForwardIterator temp(*this);
251                ++(*this);
252                return(temp);
253        }
254
255protected:
256        ForwardIterator() {}
257
258private:
259        ForwardScanner<bitblock_t, scanblock_t> scanner;
260};
261
262class BitBlockForwardIterator: public ForwardIterator<BitBlock, ScanWord> {
263public:
264        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, ScanWord>(s){}
265protected:
266        BitBlockForwardIterator(){}
267};
268
269
270template<class bitblock_t, class scanblock_t>
271class ReverseIterator 
272{
273public:
274        ReverseIterator(BitBlock * s): scanner(s)
275        {
276                scanner.scan_to_next();
277        }
278
279        void init(bitblock_t * s)
280        {
281                scanner.init(s);
282                scanner.scan_to_next();
283        }
284
285        // equal position and stream
286        bool operator==(const ReverseIterator& iter)
287        {
288                return ((scanner.get_strm() == iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
289        }
290
291        // not equal position and stream
292        bool operator!=(const ReverseIterator& iter)
293        {
294                return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
295        }
296
297        // Returns absolute position.
298        IDISA_ALWAYS_INLINE int32_t operator*()
299        {
300                return scanner.get_pos();
301        }
302
303        // prefix decrement
304        IDISA_ALWAYS_INLINE ReverseIterator& operator--()
305        {
306                scanner.scan_to_next();
307                return(*this);
308        }
309
310        // postfix decrement
311        ReverseIterator operator--(int)
312        {
313                ReverseIterator temp(*this);
314                --(*this);
315                return(temp);
316        }
317
318protected:
319        ReverseIterator() {}
320
321        ReverseScanner<bitblock_t, scanblock_t> scanner;
322};
323
324class BitBlockReverseIterator: public ReverseIterator<BitBlock, ScanWord> {
325public:
326        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, ScanWord>(s){}
327private:
328        BitBlockReverseIterator(){}
329
330};
331
332//
333// BitStream Iterator classes
334//
335class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
336{
337public:
338        BitStreamIterator():pos(-1), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
339        {
340                // default constructor defines past-the-end of bit stream semantics, pos == -1
341        }
342
343        BitStreamIterator(const BitBlock * s, int cnt):pos(0), 
344                                                                                         blk(0),
345                                                                                         blk_pos(0),
346                                                                                         strm((ScanWord *)s),
347                                                                                         scan_blk(*((ScanWord *)s)),
348                                                                                         scan_blk_cnt(cnt)
349        {
350                scan_to_next();
351        }
352
353        virtual ~BitStreamIterator() {};
354
355        // shallow copy, bit stream iterators refer to shared data
356        BitStreamIterator& operator=(const BitStreamIterator& iter)
357        {
358                pos = iter.pos;
359                blk = iter.blk;
360                blk_pos = iter.blk_pos;
361                strm = iter.strm;                       // No copy, both
362                scan_blk =  iter.scan_blk;
363                scan_blk_cnt = iter.scan_blk_cnt;
364                return(*this);
365        }
366
367        // equal position and stream
368        bool operator==(const BitStreamIterator& iter)
369        {
370                return((strm == iter.strm) && (pos == iter.pos));
371        }
372
373        // not equal position and stream
374        bool operator!=(const BitStreamIterator& iter)
375        {
376                return((strm != iter.strm) || (pos != iter.pos));
377        }
378
379        // prefix
380        inline BitStreamIterator& operator++()
381        {
382                scan_to_next();
383                return(*this);
384        }
385
386        // postfix
387        BitStreamIterator operator++(int)
388        {
389                BitStreamIterator temp(*this);
390                ++(*this);
391                return(temp);
392        }
393
394        // Returns absolute position.
395        inline int32_t operator*()
396        {
397                return pos;
398        }
399
400        /*
401        int operator->()
402        {
403                return(&*(BitStreamIterator)*this);
404        }
405        */
406
407        void debug() {
408        std::cout << "pos: " << pos << std::endl;
409        std::cout << "blk: " << blk << std::endl;
410        std::cout << "blk_pos: " << blk_pos << std::endl;
411        }
412
413private:
414        int32_t pos;
415        uint32_t blk;
416        int32_t blk_pos;
417        const ScanWord * strm;
418        ScanWord scan_blk;
419        uint32_t scan_blk_cnt;
420
421        // Helpers
422        inline void scan_to_next() {
423                while (blk<scan_blk_cnt) {
424                        if(scan_blk > 0){
425                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
426                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
427                                return;
428                        }
429
430                        blk_pos += (sizeof(ScanWord)*8);
431                        blk++;
432                        scan_blk = strm[blk];
433                };
434
435                pos = -1;
436                return;
437        }
438};
439
440/*=============================================================================
441 
442   Special iterators for content buffers with 16-bit right deletion results.
443   Input: (a) a bitblock with undeleted positions rightmost in each 16-bit field.
444          (b) a bitblock of 16-bit fields with a partial sum of the nondeleted
445              positions in this field and all the ones to the right.
446         
447          The partial sum may be computed given B, a bitblock containg the count
448          of nondeleted positions in each field using PartialSum16(B).
449       
450   
451*/
452
453
454static inline BitBlock PartialSum16(BitBlock BaseCounts16) {
455        BitBlock t = simd<16>::add(BaseCounts16, mvmd<16>::slli<1>(BaseCounts16));
456        BitBlock u = simd<16>::add(t, mvmd<16>::slli<2>(t));
457        return simd<16>::add(u, mvmd<16>::slli<4>(u));
458}
459
460template <class bitblock_t, class scanblock_t>
461class ForwardScannerWithBaseCounts16: public Scanner<bitblock_t, scanblock_t> {
462
463public:
464
465        ForwardScannerWithBaseCounts16(){}
466        ForwardScannerWithBaseCounts16(const bitblock_t * s, bitblock_t partial_sums_16) {
467                init(s, partial_sums_16);
468        }
469
470        IDISA_ALWAYS_INLINE void init(const bitblock_t * s, bitblock_t partial_sums_16) {
471                this->strm = s;
472                this->pos = 0;
473                this->blk = 0;
474                this->scan_blk = *(scanblock_t *)s;
475                /* Shift by one field so that the base is the sum for the prev. fields. */
476                this->base_per_field16._128 = mvmd<16>::slli<1>(partial_sums_16);
477        }
478
479        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
480                while (this->blk < BLOCK_COUNT){
481                        if(has_bit(this->scan_blk)){
482                                int pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
483                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
484               
485                                this->pos = this->base_per_field16._16[pos/16] + (pos & 15);
486
487                                return (this->pos);
488                        }
489
490                        this->blk++;
491                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
492                };
493
494                this->pos = -1;
495                return (this->pos);
496        }
497
498
499        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
500        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
501        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
502        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
503
504        static const int32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
505        ubitblock base_per_field16;
506};
507
508template <class bitblock_t> static inline bool eq_bitblocks(bitblock_t x, bitblock_t y) {
509  return bitblock::all(simd<16>::eq(x, y));
510}
511
512
513template<class bitblock_t, class scanblock_t>
514class ForwardIteratorWithBaseCounts16 : public std::iterator<std::input_iterator_tag, int>
515{
516public:
517        ForwardIteratorWithBaseCounts16() {}
518
519        ForwardIteratorWithBaseCounts16(bitblock_t * s, bitblock_t partial_sums_16): scanner(s, partial_sums_16)
520        {
521                scanner.scan_to_next();
522        }
523
524        void init(bitblock_t * s, bitblock_t partial_sums_16)
525        {
526                scanner.init(s, partial_sums_16);
527                scanner.scan_to_next();
528        }
529
530        // equal position and stream
531        bool operator==(const ForwardIteratorWithBaseCounts16& iter)
532        {
533                return (scanner.get_strm() == iter.scanner.get_strm()) && 
534                       (scanner.get_pos() == iter.scanner.get_pos) &&
535                       (eq_bitblocks<bitblock_t>(scanner.base_per_field16, iter.scanner.base_per_field16));
536        }
537
538        // not equal position and stream
539        bool operator!=(const ForwardIteratorWithBaseCounts16& iter)
540        {
541                return (scanner.get_strm() != iter.scanner.get_strm()) || 
542                       (scanner.get_pos() != iter.scanner.get_pos) ||
543                       (!eq_bitblocks<bitblock_t>(scanner.base_per_field16, iter.scanner.base_per_field16));
544        }
545
546        // Returns absolute position.
547        IDISA_ALWAYS_INLINE int32_t operator*()
548        {
549                return scanner.get_pos();
550        }
551
552        // prefix increment
553        IDISA_ALWAYS_INLINE ForwardIteratorWithBaseCounts16& operator++()
554        {
555                scanner.scan_to_next();
556                return(*this);
557        }
558
559        // postfix increment
560        ForwardIteratorWithBaseCounts16 operator++(int)
561        {
562                ForwardIteratorWithBaseCounts16 temp(*this);
563                ++(*this);
564                return(temp);
565        }
566
567private:
568        ForwardScannerWithBaseCounts16<bitblock_t, scanblock_t> scanner;
569};
570
571
572class BitBlockForwardIteratorWithBaseCounts16: public ForwardIteratorWithBaseCounts16<BitBlock, ScanWord> {
573public:
574        BitBlockForwardIteratorWithBaseCounts16(){}
575        BitBlockForwardIteratorWithBaseCounts16(BitBlock * s, BitBlock partial_sums_16): ForwardIteratorWithBaseCounts16<BitBlock, ScanWord>(s, partial_sums_16){}
576};
577
578
579#undef has_bit
580
581
582#endif // BITBLOCK_ITERATOR_H_
583
Note: See TracBrowser for help on using the repository browser.