source: trunk/lib/bitblock_iterator.hpp @ 2352

#ifndef BITBLOCK_ITERATOR_H_
#define BITBLOCK_ITERATOR_H_

#include <iterator>
#include <iostream>
#include "bitblock.hpp"

/*=============================================================================
  bitblock_iterator.hpp

  Created on: Sept 2011
  Author: Ken Herdy

  Description:

        Scanner classes implement the low level methods to scan through 
        the 'scanwords' of a 'bitblock'. Scanner classes are templated 
        on bitblock type and scanword type. 

        BitBlock iterator classes provide Standard Template Library (STL) 
        Input iterator 'like' interface implementations as a programmer
        convenience and allow iterator classes to be used 
        with STL Algorithms. 
        Forward iterators can only step forward (++) marker-bit by marker-bit. 
        Reverse iterators can only step backwards (--) marker-bit by marker-bit.

        BitStream iterator class provide an STL Input iterator interface to scan 
        through an array of scanwords (stream) in the forward direction. 


  Classes Descriptions:

        *       BitBlock Scanners

        Scanner - Scanner base class.
        ForwardScanner - Scans a bitblock of scanwords in the forward direction.
        ReverseScanner - Scans a bitblock of scanwords in the reverse direction.

        * BitBlock Iterators

  ForwardIterator template class wraps ForwardScanner. 
        
        - Implements STL Input iterator interface.
        - Reads elements only once.     
  - '->' - Not implemented.

  ReverseIterator template class wraps ReverseScanner.

        - An STL 'like' iterator that implements prefix and postfix decrement operators.
    Under STL, a reverse iterator implementation necessitates the implementation of
                the STL bidirectional interface and hence scanning in both directions. 
                This functionality is not yet required and hence not implemented.
        - Reads elements only once. 
  - '->' - Not implemented.

        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, scanword_t>

        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, scanword_t>

        * BitStreamIterators

  BitStreamIterator class wraps ForwardScanner. 
        - Scans an array (stream) of scanwords in contiguous memory. 
        - Implements STL Input iterator interface.
        - Reads elements only once.     
  - '->' - Not implemented.
        - May be more appropriately named ForwardBitStreamIterator.

=============================================================================*/
//
// Scanner Classes
//
#define has_bit(x) (x != 0)

template <class bitblock_t, class scanblock_t>
class Scanner {

protected:
        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
        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) {}

        const bitblock_t * strm;
        int32_t pos;
        int32_t blk;
        scanblock_t scan_blk;
};

template <class bitblock_t, class scanblock_t>
class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {

public:

        ForwardScanner(){}
        ForwardScanner(const bitblock_t * s) {
                init(s);
        }

        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
                this->strm = s;
                this->pos = 0;
                this->blk = 0;
                this->scan_blk = *(scanblock_t *)s;
        }

        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
                while (this->blk < BLOCK_COUNT){
                        if(has_bit(this->scan_blk)){
                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit

                                return (this->pos);
                        }

                        this->blk++;
                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
                };

                this->pos = -1;
                return (this->pos);
        }

        /* Set or reset the iterator to position new_pos. */
        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {            
                const scanblock_t one_bit = 1;
                this->blk = new_pos / (sizeof(scanblock_t)*8);
                this->pos = new_pos % (sizeof(scanblock_t)*8);
                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
                // clear bit at pos and all positions to the right.
                scanblock_t marker = one_bit << this->pos;
                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
        }

        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}

        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);

};

template <class bitblock_t, class scanblock_t>
class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {

public:
        ReverseScanner(){}
        ReverseScanner(const bitblock_t * s) {
                init(s);
        }
        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
                this->strm = s;
                this->pos = 0;
                this->blk = BLOCK_COUNT-1;
                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
        }

        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
                while (this->blk > -1){
                        if(has_bit(this->scan_blk)){
                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
                                return (this->pos);
                        }

                        this->blk--;
                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
                };

                this->pos = -1;
                return (this->pos);
        }

        /* Set or reset the iterator to position new_pos. */
        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
                const scanblock_t one_bit = 1;
                this->blk = (new_pos / (sizeof(scanblock_t)*8));
                this->pos = new_pos % (sizeof(scanblock_t)*8);
                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
                // clear bit at pos and all positions to the left.
                scanblock_t marker = one_bit << this->pos;
                this->scan_blk = this->scan_blk & (marker-1);
        }

        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}

        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);

};

#undef has_bit

//
// BitBlock Iterator Classses
//
template<class bitblock_t, class scanblock_t>
class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
{
public:
        ForwardIterator() {}

        ForwardIterator(bitblock_t * s): scanner(s)
        {
                scanner.scan_to_next();
        }

        void init(bitblock_t * s)
        {
                scanner.init(s);
                scanner.scan_to_next();
        }

        // equal position and stream
        bool operator==(const ForwardIterator& iter)
        {
                return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
        }

        // not equal .get_pos()ition and stream
        bool operator!=(const ForwardIterator& iter)
        {
                return ( (scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
        }

        // Returns absolute position.
        IDISA_ALWAYS_INLINE int32_t operator*()
        {
                return scanner.get_pos();
        }

        // prefix increment
        IDISA_ALWAYS_INLINE ForwardIterator& operator++()
        {
                scanner.scan_to_next();
                return(*this);
        }

        // postfix increment
        ForwardIterator operator++(int)
        {
                ForwardIterator temp(*this);
                ++(*this);
                return(temp);
        }

private:
        ForwardScanner<bitblock_t, scanblock_t> scanner;
};

class BitBlockForwardIterator: public ForwardIterator<BitBlock, scanword_t> {
public:
        BitBlockForwardIterator(){}
        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, scanword_t>(s){}
};

template<class bitblock_t, class scanblock_t>
class ReverseIterator 
{
public:
        ReverseIterator() {}
        ReverseIterator(BitBlock * s): scanner(s)
        {
                scanner.scan_to_next();
        }

        void init(bitblock_t * s)
        {
                scanner.init(s);
                scanner.scan_to_next();
        }

        // equal position and stream
        bool operator==(const ReverseIterator& iter)
        {
                return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
        }

        // not equal .get_pos()ition and stream
        bool operator!=(const ReverseIterator& iter)
        {
                return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
        }

        // Returns absolute position.
        IDISA_ALWAYS_INLINE int32_t operator*()
        {
                return scanner.get_pos();
        }

        // prefix decrement
        IDISA_ALWAYS_INLINE ReverseIterator& operator--()
        {
                scanner.scan_to_next();
                return(*this);
        }

        // postfix decrement
        ReverseIterator operator--(int)
        {
                ReverseIterator temp(*this);
                --(*this);
                return(temp);
        }

private:
        ReverseScanner<bitblock_t, scanblock_t> scanner;
};

class BitBlockReverseIterator: public ReverseIterator<BitBlock, scanword_t> {
public:
        BitBlockReverseIterator(){}
        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, scanword_t>(s){}
};

//
// BitStream Iterator classes
//
class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
{
public:
        BitStreamIterator():pos(-1), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
        {
                // default constructor defines past-the-end of bit stream semantics, pos == -1
        }

        BitStreamIterator(const BitBlock * s, int cnt):pos(0),  
                                                                                         blk(0),
                                                                                         blk_pos(0),
                                                                                         strm((scanword_t *)s),
                                                                                         scan_blk(*((scanword_t *)s)),
                                                                                         scan_blk_cnt(cnt)
        {
                scan_to_next();
        }

        virtual ~BitStreamIterator() {};

        // shallow copy, bit stream iterators refer to shared data
        BitStreamIterator& operator=(const BitStreamIterator& iter)
        {
                pos = iter.pos;
                blk = iter.blk;
                blk_pos = iter.blk_pos;
                strm = iter.strm;                       // No copy, both
                scan_blk =  iter.scan_blk;
                scan_blk_cnt = iter.scan_blk_cnt;
                return(*this);
        }

        // equal position and stream
        bool operator==(const BitStreamIterator& iter)
        {
                return((strm = iter.strm) && (pos == iter.pos));
        }

        // not equal position and stream
        bool operator!=(const BitStreamIterator& iter)
        {
                return((strm != iter.strm) || (pos != iter.pos));
        }

        // prefix
        inline BitStreamIterator& operator++()
        {
                scan_to_next();
                return(*this);
        }

        // postfix
        BitStreamIterator operator++(int)
        {
                BitStreamIterator temp(*this);
                ++(*this);
                return(temp);
        }

        // Returns absolute position.
        inline int32_t operator*()
        {
                return pos;
        }

        /*
        int operator->()
        {
                return(&*(BitStreamIterator)*this);
        }
        */

        void debug() {
        std::cout << "pos: " << pos << std::endl;
        std::cout << "blk: " << blk << std::endl;
        std::cout << "blk_pos: " << blk_pos << std::endl;
        }

private:
        int32_t pos;
        uint32_t blk;
        int32_t blk_pos;
        const scanword_t * strm;
        scanword_t scan_blk;
        uint32_t scan_blk_cnt;

        // Helpers
        inline void scan_to_next() {
                while (blk<scan_blk_cnt) {
                        if(scan_blk > 0){
                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
                                return;
                        }

                        blk_pos += (sizeof(scanword_t)*8);
                        blk++;
                        scan_blk = strm[blk];
                };

                pos = -1;
                return;
        }
};

#endif // BITBLOCK_ITERATOR_H_