Program Listing for File BVGraph.h

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

/*--------------------------------------------------------------------------*/
/*----------------------------- File BVGraph.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/compression/IntegerCodes.h"
#include "ADS/succinct/BitStream.h"
#include "ADS/succinct/BitVector.h"
#include "ADS/succinct/EliasFano.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS BVGraph ------------------------------*/
/*--------------------------------------------------------------------------*/

class BVGraph {

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

 using List = std::vector< std::size_t >;

 using Interval = std::pair< std::size_t , std::size_t >;

 BVGraph( void ) = default;

 explicit BVGraph( const std::vector< List > & a , std::size_t w = 7 ,
                   std::size_t r = 3 , std::size_t lmin = 4 );

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

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

 [[nodiscard]] std::size_t outdegree( std::size_t x ) const;

 [[nodiscard]] List successors( std::size_t x ) const;

 [[nodiscard]] std::size_t reference( std::size_t x ) const;

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

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

 [[nodiscard]] static BitVector copyList( const List & s , const List & ref );

 [[nodiscard]] static std::pair< bool , std::vector< std::size_t > >
 copyBlocks( const BitVector & c );

 [[nodiscard]] static std::pair< std::vector< Interval > , List >
 intervals( const List & e , std::size_t lmin );

 [[nodiscard]] static std::vector< std::uint64_t > residualGaps(
                                         const List & res , std::size_t x );

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

 [[nodiscard]] List decode( std::size_t x ) const;

 std::size_t f_n = 0;
 std::size_t f_m = 0;
 std::size_t f_lmin = 4;
 BitVector f_bits;
 EliasFano f_start;

 };  // end( class BVGraph )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BVGraph.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File BVGraph.h --------------------------*/
/*--------------------------------------------------------------------------*/