Program Listing for File WordRangeMinimum.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File WordRangeMinimum.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/memory/HugePageAllocator.h"
#include "ADS/search/CountLess.h"

#include <bit>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS WordRangeMinimum --------------------------*/
/*--------------------------------------------------------------------------*/

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

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

 WordRangeMinimum( void ) = default;

 explicit WordRangeMinimum( 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:

 struct Place {
  T suf;
  T pre;
  std::uint8_t si;
  std::uint8_t pi;
  };

 struct Min {
  T v;
  std::uint32_t i;
  };

 [[nodiscard]] Min better( const Min & a , const Min & b ) const {
  const bool t = f_less( b.v , a.v );
  return( Min{ t ? b.v : a.v , t ? b.i : a.i } );
  }

 void stacks( std::size_t b , std::size_t n );

 std::vector< T > f_A;
 std::vector< std::uint64_t , HugePageAllocator< std::uint64_t > > f_M;
 std::vector< Place , HugePageAllocator< Place > > f_P;
 std::vector< Min , HugePageAllocator< Min > > f_S;
 std::size_t f_blocks = 0;
 [[no_unique_address]] Compare f_less;

 };  // end( class WordRangeMinimum )

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

}  // end( namespace ADS )

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

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

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

#endif  /* WordRangeMinimum.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File WordRangeMinimum.h -----------------------*/
/*--------------------------------------------------------------------------*/