source: trunk/lib/bitblock_iterator.hpp @ 3148

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

Added isDone method to Forward/Reverse? Iterators. Minor additions.

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