Program Listing for File RangeMinimum.h

↰ Return to documentation for file (ADS/search/RangeMinimum.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File RangeMinimum.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <utility>
#include <vector>

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

namespace ADS {

template< class T , class Compare = std::less< T > >
[[nodiscard]] std::vector< std::size_t > cartesianTree(
                         const std::vector< T > & A , Compare less = {} );

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS SparseTable ----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Compare = std::less< T > >
class SparseTable {

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

 SparseTable( void ) = default;

 explicit SparseTable( std::vector< T > A , Compare less = {} );

 [[nodiscard]] std::size_t query( std::size_t i , std::size_t j ) const;

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

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

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

 // a constant view of the array, random access

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using const_reference = const T &;
 using reference = const_reference;
 using const_iterator = typename std::vector< T >::const_iterator;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const { return( f_A.begin() ); }
 [[nodiscard]] const_iterator end( void ) const { return( f_A.end() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 [[nodiscard]] std::size_t better( std::size_t a , std::size_t b ) const;

 std::vector< T > f_A;
 std::vector< std::vector< std::size_t > > f_M;
 Compare f_less;

 };  // end( class SparseTable )

/*--------------------------------------------------------------------------*/
/*--------------------- CLASS PlusMinusOneRangeMinimum ---------------------*/
/*--------------------------------------------------------------------------*/

class PlusMinusOneRangeMinimum {

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

 PlusMinusOneRangeMinimum( void ) = default;

 explicit PlusMinusOneRangeMinimum( std::vector< long > D );

 [[nodiscard]] std::size_t query( std::size_t i , std::size_t j ) const;

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

 [[nodiscard]] std::size_t blockSize( void ) const { return( f_d ); }

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

 [[nodiscard]] std::size_t inBlock( std::size_t k , std::size_t a ,
                                    std::size_t b ) const;

 std::vector< long > f_D;
 std::size_t f_d = 1;
 std::vector< std::uint32_t > f_sig;
 std::vector< std::uint8_t > f_table;
 std::vector< std::size_t > f_blockMin;
 SparseTable< long > f_blocks;

 };  // end( class PlusMinusOneRangeMinimum )

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS RangeMinimum ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Compare = std::less< T > >
class RangeMinimum {

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

 RangeMinimum( void ) = default;

 explicit RangeMinimum( std::vector< T > A , Compare less = {} );

 [[nodiscard]] std::size_t query( std::size_t i , std::size_t j ) const;

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

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

 [[nodiscard]] const std::vector< std::size_t > & eulerTour( void ) const {
  return( f_E );
  }

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

 // a constant view of the array, random access

 using value_type = T;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using const_reference = const T &;
 using reference = const_reference;
 using const_iterator = typename std::vector< T >::const_iterator;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const { return( f_A.begin() ); }
 [[nodiscard]] const_iterator end( void ) const { return( f_A.end() ); }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 std::vector< T > f_A;
 std::vector< std::size_t > f_E;
 std::vector< std::size_t > f_first;
 PlusMinusOneRangeMinimum f_tour;
 Compare f_less;

 };  // end( class RangeMinimum )

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

}  // end( namespace ADS )

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

#include "ADS/search/impl/RangeMinimum.tpp"

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

#endif  /* RangeMinimum.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File RangeMinimum.h -------------------------*/
/*--------------------------------------------------------------------------*/