Program Listing for File RoaringBitmap.h

↰ Return to documentation for file (ADS/set/RoaringBitmap.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File RoaringBitmap.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_RoaringBitmap
 #define __ADS_RoaringBitmap
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/set/BoolSet.h"

#include <cstddef>
#include <bit>
#include <cstdint>
#include <iterator>
#include <memory>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS RoaringBitmap ---------------------------*/
/*--------------------------------------------------------------------------*/

class RoaringBitmap {

/*--------------------------------------------------------------------------*/
 public:

 using Item = std::uint32_t;

 static constexpr std::uint32_t ARRAY = 4096;

 RoaringBitmap( void ) = default;

 RoaringBitmap( const RoaringBitmap & o );

 RoaringBitmap( RoaringBitmap && o ) noexcept = default;

 RoaringBitmap & operator=( RoaringBitmap o ) noexcept;

 RoaringBitmap( const std::uint32_t * a , std::size_t n );

 [[nodiscard]] bool contains( std::uint32_t x ) const;

 bool insert( std::uint32_t x );

 bool remove( std::uint32_t x );

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const;

 void clear( void );

 void swap( RoaringBitmap & o ) noexcept;

 [[nodiscard]] std::size_t containers( void ) const;
 [[nodiscard]] std::size_t bitmaps( void ) const;

 [[nodiscard]] std::size_t bytes( void ) const;

 template< class F >
 void forEach( F && f ) const;

 [[nodiscard]] std::vector< std::uint32_t > items( void ) const;

 [[nodiscard]] std::size_t rank( std::uint32_t x ) const;

 friend RoaringBitmap setUnion( const RoaringBitmap & A ,
                                const RoaringBitmap & B );
 friend RoaringBitmap setIntersection( const RoaringBitmap & A ,
                                       const RoaringBitmap & B );
 friend RoaringBitmap setDifference( const RoaringBitmap & A ,
                                     const RoaringBitmap & B );
 friend RoaringBitmap setSymmetricDifference( const RoaringBitmap & A ,
                                              const RoaringBitmap & B );

/*--------------------------------------------------------------------------*/
 private:

 static constexpr std::size_t WORDS = 1024;

 struct Block {
  std::uint16_t key = 0;
  std::uint32_t card = 0;
  std::vector< std::uint16_t , detail::UninitAllocator< std::uint16_t > > a;
  std::unique_ptr< std::uint64_t[] > w;

  [[nodiscard]] bool bits( void ) const { return( w != nullptr ); }
  };

 enum class Op { AND , OR , ANDNOT , XOR };

 template< Op O >
 static RoaringBitmap combine( const RoaringBitmap & A ,
                               const RoaringBitmap & B );

 template< Op O >
 static Block combine( const Block & a , const Block & b );

 static Block copy( const Block & b );

 static void toBitmap( Block & b );

 static void toArray( Block & b );

 static Block fromWords( std::uint16_t key ,
                         std::unique_ptr< std::uint64_t[] > w ,
                         std::uint32_t card );

 [[nodiscard]] std::size_t find( std::uint16_t key ) const;

 [[nodiscard]] bool valid( void ) const;

 void rekey( void );

 std::vector< Block > f_B;
 std::vector< std::uint16_t > f_K;
 std::size_t f_size = 0;

/*------------------------- THE STANDARD INTERFACE -------------------------*/
 public:

 // a constant view of the items in increasing order, forward

 class const_iterator {
  public:
  using value_type = std::uint32_t;
  using reference = std::uint32_t;
  using difference_type = std::ptrdiff_t;
  using iterator_concept = std::forward_iterator_tag;
  using iterator_category = std::input_iterator_tag;

  const_iterator( void ) = default;

  reference operator*( void ) const { return( f_x ); }

  const_iterator & operator++( void ) {
   if( f_word ) {                           // the next bit of the word
    f_word &= f_word - 1;
    if( f_word ) {
     f_x = f_base + std::uint32_t( std::countr_zero( f_word ) );
     return( *this );
     }
    }
   ++f_i;
   settle();
   return( *this );
   }
  const_iterator operator++( int ) { auto t = *this; ++*this; return( t ); }

  bool operator==( const const_iterator & o ) const {
   return( ( f_b == o.f_b ) && ( f_i == o.f_i ) && ( f_x == o.f_x ) );
   }

  private:
  friend class RoaringBitmap;

  const_iterator( const RoaringBitmap * s , std::size_t b );

  void settle( void );

  const RoaringBitmap * f_s = nullptr;
  std::size_t f_b = 0;
  std::size_t f_i = 0;
  std::uint64_t f_word = 0;
  std::uint32_t f_base = 0;
  std::uint32_t f_x = 0;

 };  // end( class const_iterator )

 using value_type = std::uint32_t;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = std::uint32_t;
 using const_reference = std::uint32_t;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , f_B.size() ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

 [[nodiscard]] const_iterator lowerBound( std::uint32_t x ) const;

 [[nodiscard]] const_iterator select( std::size_t i ) const;

 };  // end( class RoaringBitmap )

RoaringBitmap setUnion( const RoaringBitmap & A , const RoaringBitmap & B );

RoaringBitmap setIntersection( const RoaringBitmap & A ,
                               const RoaringBitmap & B );

RoaringBitmap setDifference( const RoaringBitmap & A ,
                             const RoaringBitmap & B );

RoaringBitmap setSymmetricDifference( const RoaringBitmap & A ,
                                      const RoaringBitmap & B );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/set/impl/RoaringBitmap.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* RoaringBitmap.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File RoaringBitmap.h ------------------------*/
/*--------------------------------------------------------------------------*/