Program Listing for File BPTree.h

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

/*--------------------------------------------------------------------------*/
/*----------------------------- File BPTree.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

#include <cstddef>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS BPTree ------------------------------*/
/*--------------------------------------------------------------------------*/

class BPTree {

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

 static constexpr std::size_t nil = std::size_t( -1 );

 BPTree( void ) = default;

 explicit BPTree( const std::vector< std::vector< std::size_t > > & c );

 explicit BPTree( BitVector b );

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

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

 [[nodiscard]] std::size_t parent( std::size_t v ) const;

 [[nodiscard]] std::size_t leftmostChild( std::size_t v ) const;

 [[nodiscard]] std::size_t rightSibling( std::size_t v ) const;

 [[nodiscard]] std::size_t degree( std::size_t v ) const;

 [[nodiscard]] std::size_t subtreeSize( std::size_t v ) const;

 [[nodiscard]] std::size_t depth( std::size_t v ) const;

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

 [[nodiscard]] bool isLeaf( std::size_t v ) const;

 [[nodiscard]] const BalancedParentheses & parentheses( void ) const;

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

 [[nodiscard]] std::size_t open( std::size_t v ) const;

 BalancedParentheses f_p;

 };  // end( class BPTree )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BPTree.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File BPTree.h ---------------------------*/
/*--------------------------------------------------------------------------*/