Program Listing for File BalancedParentheses.h

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

/*--------------------------------------------------------------------------*/
/*----------------------- File BalancedParentheses.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*----------------------- CLASS BalancedParentheses ------------------------*/
/*--------------------------------------------------------------------------*/

class BalancedParentheses {

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

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

 BalancedParentheses( void );

 explicit BalancedParentheses( BitVector b );

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

 [[nodiscard]] bool operator[]( std::size_t i ) const;

 [[nodiscard]] std::int64_t excess( std::size_t i ) const;

 [[nodiscard]] std::size_t findClose( std::size_t i ) const;

 [[nodiscard]] std::size_t findOpen( std::size_t j ) const;

 [[nodiscard]] std::size_t enclose( std::size_t i ) const;

 [[nodiscard]] const CompactRankSelect & bits( void ) const;

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

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

 static constexpr std::size_t kLeaf = 512;
 static constexpr std::size_t kGroup = 16;

 [[nodiscard]] std::size_t scanForward( std::size_t a , std::size_t b ,
                                        std::int64_t & e ,
                                        std::int64_t d ) const;

 [[nodiscard]] std::size_t scanBackward( std::size_t a , std::size_t b ,
                                         std::int64_t & e ,
                                         std::int64_t d ) const;

 [[nodiscard]] std::size_t forwardSearch( std::size_t i ,
                                          std::int64_t d ) const;

 [[nodiscard]] std::size_t backwardSearch( std::size_t i ,
                                           std::int64_t d ) const;

 [[nodiscard]] std::size_t leafEnd( std::size_t l ) const {
  return( std::min( size() , ( l + 1 ) * kLeaf ) );
  }

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

 CompactRankSelect f_b;
 std::size_t f_nleaf = 0;
 std::size_t f_groups = 1;
 std::vector< std::int16_t > f_lexc , f_lmin;
 std::vector< std::int64_t > f_exc , f_min;

 };  // end( class BalancedParentheses )

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

}  // end( namespace ADS )

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

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

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

#endif  /* BalancedParentheses.h included */

/*--------------------------------------------------------------------------*/
/*--------------------- End File BalancedParentheses.h ---------------------*/
/*--------------------------------------------------------------------------*/