source: trunk/lib/bitblock_iterator.hpp @ 3131

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

Fixes

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