Program Listing for File K2Tree.h

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

/*--------------------------------------------------------------------------*/
/*----------------------------- File K2Tree.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS K2Tree ------------------------------*/
/*--------------------------------------------------------------------------*/

class K2Tree {

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

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

 K2Tree( void ) = default;

 K2Tree( std::size_t n , const std::vector< Edge > & e , std::size_t k = 2 );

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

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

 [[nodiscard]] std::vector< std::size_t > neighbors( std::size_t u ) const;

 [[nodiscard]] std::vector< std::size_t > reverseNeighbors(
                                                       std::size_t v ) const;

 [[nodiscard]] bool hasEdge( std::size_t u , std::size_t v ) const;

 [[nodiscard]] const BitVector & levels( void ) const;

 [[nodiscard]] const BitVector & leaves( void ) const;

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

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

 [[nodiscard]] bool mark( std::size_t p ) const;

 [[nodiscard]] std::size_t children( std::size_t p ) const;

 void walk( std::size_t s , std::size_t r , std::size_t o ,
            std::size_t base , bool row ,
            std::vector< std::size_t > & out ) const;

 std::size_t f_n = 0;
 std::size_t f_k = 2;
 std::size_t f_side = 1;
 std::size_t f_m = 0;
 RankSelect f_t;
 BitVector f_l;

 };  // end( class K2Tree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* K2Tree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File K2Tree.h ---------------------------*/
/*--------------------------------------------------------------------------*/