ScanBit

Files CCore/inc/ScanBit.h CCore/src/ScanBit.cpp

ScanBit is a "bit-array" class, designed for the quick bit scanning. It stores a bit array in the internal buffer, packed in some unsigned integral units. Logically, it is the array of bits. The length is determined by the second template argument. The first argument is an Algorithm Package, it provides a set of functions for the efficient implementation of the ScanBit.

template <class Algo,ulen Len>
class ScanBit
 {
   using Unit = typename Algo::Unit ;

   Unit bits[Len];
   
  public:
   
   static const ulen IndexLim = Len*Algo::UnitBits ;
   
   ScanBit();
   
   void set(ulen ind);
  
   void clear(ulen ind);
   
   Unit test(ulen ind) const;
  
   ulen findMin(ulen ind) const; // min>=ind , if( not found ) return IndexLim; 
   
   ulen findMax(ulen ind) const; // max<=ind , if( not found ) return IndexLim;
 };

The default constructor clears all bits.

The inner constant IndexLim is the array bit length. The argument ind in all methods must be less than IndexLim.

set() sets the bit with the given index.

clear() clears the bit with the given index.

test() tests the bit with the given index. The return value is non-zero iff the bit is set.

findMin() scans bits starting form the given index up. The index of the first found set bit is returned. If there is no such one, IndexLim is returned. The efficiency of this method depends on the efficiency of the method Algo::ScanUp().

findMax() scans bits starting form the given index down. The index of the first found set bit is returned. If there is no such one, IndexLim is returned. The efficiency of this method depends on the efficiency of the method Algo::ScanDown().

ScanMSBitAlgo and ScanLSBitAlgo

Two prepared Algorithm Packages for the ScanBit are provided: ScanMSBitAlgo and ScanLSBitAlgo. They are built, based on "quick" functions, provided by the target. They use different order of numbering bits in the unit. They ScanUp/ScanDown() methods use the opposite Quick::ScanMSBit/ScanLSBit() function calls, as shown below.

struct ScanMSBitAlgo
 {
  using Unit = Quick::ScanUInt ;
  
  static const ulen UnitBits;
  
  static const Unit Unit_msb;
  
  static const Unit Unit_all;
  
  static Unit Bit(ulen number);
  
  static Unit MaskUp(ulen number);
  
  static ulen ScanUp(Unit bit); // uses Quick::ScanMSBit()
  
  static Unit MaskDown(ulen number);
  
  static ulen ScanDown(Unit bit); // uses Quick::ScanLSBit()
 };

struct ScanLSBitAlgo
 {
  using Unit = Quick::ScanUInt ;
  
  static const ulen UnitBits;
  
  static const Unit Unit_1;
  
  static const Unit Unit_all;
  
  static Unit Bit(ulen number);
  
  static Unit MaskUp(ulen number);
  
  static ulen ScanUp(Unit bit); // uses Quick::ScanLSBit()
  
  static Unit MaskDown(ulen number);
  
  static ulen ScanDown(Unit bit); // uses Quick::ScanMSBit()
 };