Program Listing for File WaveletMatrix.h

↰ Return to documentation for file (ADS/succinct/WaveletMatrix.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File WaveletMatrix.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/succinct/BitVector.h"
#include "ADS/succinct/RankSelect.h"

#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <span>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS WaveletMatrix --------------------------*/
/*--------------------------------------------------------------------------*/

class WaveletMatrix {

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

 WaveletMatrix( void ) = default;

 explicit WaveletMatrix( std::span< const std::uint64_t > x , int w = 0 );

 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

 [[nodiscard]] bool empty( void ) const { return( f_n == 0 ); }

 [[nodiscard]] int width( void ) const { return( int( f_lev.size() ) ); }

 [[nodiscard]] std::uint64_t access( std::size_t i ) const;

 [[nodiscard]] std::uint64_t operator[]( std::size_t i ) const {
  return( access( i ) );
  }

 [[nodiscard]] std::size_t rank( std::uint64_t c , std::size_t i ) const;

 [[nodiscard]] std::size_t select( std::uint64_t c , std::size_t k ) const;

 [[nodiscard]] std::uint64_t quantile( std::size_t i , std::size_t j ,
                                       std::size_t k ) const;

 [[nodiscard]] std::size_t countLess( std::size_t i , std::size_t j ,
                                      std::uint64_t c ) const;

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

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 using value_type = std::uint64_t;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = std::uint64_t;
 using const_reference = std::uint64_t;
 using const_iterator = SubscriptIterator< WaveletMatrix , std::uint64_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_n ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 [[nodiscard]] bool bit( std::uint64_t c , std::size_t l ) const {
  return( ( c >> ( f_lev.size() - 1 - l ) ) & 1 );
  }

 [[nodiscard]] std::size_t start( std::uint64_t c ) const;

 std::size_t f_n = 0;
 std::vector< RankSelect > f_lev;
 std::vector< std::size_t > f_zeros;

 };  // end( class WaveletMatrix )

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

}  // end( namespace ADS )

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

#include "ADS/succinct/impl/WaveletMatrix.tpp"

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

#endif  /* WaveletMatrix.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File WaveletMatrix.h ------------------------*/
/*--------------------------------------------------------------------------*/